Динамические структуры и классы в С# на основе коллекций: хеш-таблицы.

" Исследование логики работы программы, построенной на взаимодействии классов"

Динамические структуры и классы в С# на основе коллекций: хеш-таблицы.

Ход работы:

1. Изучить теоретические положения о хеш-таблицах и области их применения 2 часа

2. Выполнить тестовый пример по реализации элемента данных хеш-таблицы class Item(string key, string value) пара ключ-значение, сформировать из таких данных таблицу class Hashtable, с выводом, созданием, удалением данных в таблице. См. пример 1. 2 часа

3. Сравнить реализацию тестового примера 1 и готовую реализацию класса коллекций на платформе Net впримере 2, сделать выводы. 2 часа

4. Оформить данную часть работы в отчет по учебной практике, ответить наконтрольные вопросы. 2 часа

Хеш-таблица (hashtable) — это структура данных, представляющая собой специальным образом организованный набор элементов хранимых данных. Все данные хранятся в виде пар хеш-значения. Данная структура похожа на словарь (map), но имеет особенности такие как применение хеш-функции для увеличения скорости поиска. Принцип работы данной структуры схож с каталогом книг. Все книги разложены в алфавитном порядке, но не на одном стеллаже, а для каждой буквы выделен отдельный стеллаж, поэтому нам не нужно по порядку перебирать все книги, а можно подойти к нужному стеллажу и искать уже там.

Хеш-таблицы применяются в файловых системах операционных систем. Изначально, когда нужно найти имя файла, поиск в каталогах велся линейно, от начала до конца. Линейный поиск в очень длинных каталогах может выполняться довольно медленно. Ускорить поиск поможет присутствие в каждом каталоге хэш-таблицы. Пусть размер такой таблицы будет равен n. При добавлении в каталог нового имени файла оно должно хэшироваться в число от 0 до n – 1, к примеру, путем деления его на n и взятия остатка. В качестве альтернативы можно сложить слова, составляющие имя файла, и получившуюся сумму разделить на n или сделать еще что-либо подобное. Производится отображение символьного имени файла в целое число из требуемого диапазона по некоторому алгоритму, рассматривающему имя как некоторое число (битовую строку) или последовательность чисел (например, кодов символов и т. п. ).

В любом случае просматривается элемент таблицы, соответствующий полученному хэш-коду. Если элемент не используется, туда помещается указатель на запись о файле. Эти записи следуют сразу за хэш-таблицей. Если же элемент таблицы уже занят, то создается связанный список, объединяющий все записи о файлах, имеющих одинаковые хэш-коды, и заголовок этого списка помещается в элемент таблицы. При поиске файла производится такая же процедура.

Для выбора записи в хэш-таблице имя файла хэшируется. Затем на присутствие имени файла проверяются все записи в цепочке, чей заголовок помещен в элементе таблицы. Если искомое имя файла в этой цепочке отсутствует, значит, в каталоге файла с таким именем нет. Преимущество использования хэш-таблицы состоит в существенном увеличении скорости поиска, а недостаток заключается в усложнении процесса администрирования. Рассматривать применение хэш-таблицы стоит только в тех системах, где ожидается применение каталогов, содержащих сотни или тысячи файлов.

Другим способом ускорения поиска в больших каталогах является кэширование результатов поиска. Перед началом поиска проверяется присутствие имени файла в кэше. Если оно там есть, то местонахождение файла может быть определено немедленно. Разумеется, кэширование поможет, только если результаты поиска затрагивают относительно небольшое количество файлов.

Хеш-таблица позволяет выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу. Важное свойство хеш-таблиц состоит в том, что, при некоторых разумных допущениях, все три операции (поиск, вставка, удаление элементов) в среднем выполняются за время O(1). Но при этом не гарантируется, что время выполнения отдельной операции мало́. Это связано с тем, что при достижении некоторого значения коэффициента заполнения необходимо осуществлять перестройку индекса хеш-таблицы: увеличить значение размера массива и заново добавить в пустую хеш-таблицу все пары.

Существуют два основных способа реализации хеш-таблиц:

- Метод цепочек (открытое хеширование) — все элементы данных с совпадающем хешем объединяются в список.

- Метод открытой адресации (закрытое хеширование) — добавляем элемент данных в ячейку по хешу, если эта ячейка занята, то переходим в следующую до тех пор, пока не найдем свободную.

Давайте рассмотрим пример 1 реализации хеш-таблицы на языке C#.

Для простоты будем рассматривать структуру из пары двух строк. Данная реализация является весьма примитивной, но позволяет разобраться в структуре и алгоритме работы данного типа данных.

Элемент данных хеш-таблицы

using System;

namespace HashTable

{

/// < summary>

/// Элемент данных хеш таблицы.

/// < /summary>

public class Item

{

/// < summary>

/// Ключ.

/// < /summary>

public string Key { get; private set; }

/// < summary>

/// Хранимые данные.

/// < /summary>

public string Value { get; private set; }

/// < summary>

/// Создать новый экземпляр хранимых данных Item.

/// < /summary>

/// < param name=" key" > Ключ. < /param>

/// < param name=" value" > Значение. < /param>

public Item(string key, string value)

{

// Проверяем входные данные на корректность.

if(string. IsNullOrEmpty(key))

{

throw new ArgumentNullException(nameof(key));

}

if(string. IsNullOrEmpty(value))

{

throw new ArgumentNullException(nameof(value));

}

// Устанавливаем значения.

Key = key;

Value = value;

}

/// < summary>

/// Приведение объекта к строке.

/// < /summary>

/// < returns> Ключ объекта. < /returns>

public override string ToString()

{

return Key;

}

Хеш-таблица

using System;

using System. Collections. Generic;

using System. Linq;

namespace HashTable

{

/// < summary>

/// Хеш-таблица.

/// < /summary>

/// < remarks>

/// Используется метод цепочек (открытое хеширование).

/// < /remarks>

public class HashTable

{

/// < summary>

/// Максимальная длина ключевого поля.

/// < /summary>

private readonly byte _maxSize = 255;

/// < summary>

/// Коллекция хранимых данных.

/// < /summary>

/// < remarks>

/// Представляет собой словарь, ключ которого представляет собой хеш ключа хранимых данных,

/// а значение это список элементов с одинаковым хешем ключа.

/// < /remarks>

private Dictionary< int, List< Item> > _items = null;

/// < summary>

/// Коллекция хранимых данных в хеш-таблице в виде пар Хеш-Значения.

/// < /summary>

public IReadOnlyCollection< KeyValuePair< int, List< Item> > > Items => _items?. ToList()?. AsReadOnly();

/// < summary>

/// Создать новый экземпляр класса HashTable.

/// < /summary>

public HashTable()

{

// Инициализируем коллекцию максимальным количество элементов.

_items = new Dictionary< int, List< Item> > (_maxSize);

}

/// < summary>

/// Добавить данные в хеш таблицу.

/// < /summary>

/// < param name=" key" > Ключ хранимых данных. < /param>

/// < param name=" value" > Хранимые данные. < /param>

public void Insert(string key, string value)

{

// Проверяем входные данные на корректность.

if (string. IsNullOrEmpty(key))

{

throw new ArgumentNullException(nameof(key));

}

if (key. Length > _maxSize)

{

throw new ArgumentException($" Максимальная длинна ключа составляет {_maxSize} символов. ", nameof(key));

}

if (string. IsNullOrEmpty(value))

{

throw new ArgumentNullException(nameof(value));

}

// Создаем новый экземпляр данных.

var item = new Item(key, value);

// Получаем хеш ключа

var hash = GetHash(item. Key);

// Получаем коллекцию элементов с таким же хешем ключа.

// Если коллекция не пустая, значит заначения с таким хешем уже существуют,

// следовательно добавляем элемент в существующую коллекцию.

// Иначе коллекция пустая, значит значений с таким хешем ключа ранее не было,

// следовательно создаем новую пустую коллекцию и добавляем данные.

List< Item> hashTableItem = null;

if (_items. ContainsKey(hash))

{

// Получаем элемент хеш таблицы.

hashTableItem = _items[hash];

// Проверяем наличие внутри коллекции значения с полученным ключом.

// Если такой элемент найден, то сообщаем об ошибке.

var oldElementWithKey = hashTableItem. SingleOrDefault(i => i. Key == item. Key);

if (oldElementWithKey! = null)

{

throw new ArgumentException($" Хеш-таблица уже содержит элемент с ключом {key}. Ключ должен быть уникален. ", nameof(key));

}

// Добавляем элемент данных в коллекцию элементов хеш таблицы.

_items[hash]. Add(item);

}

else

{

// Создаем новую коллекцию.

hashTableItem = new List< Item> { item };

// Добавляем данные в таблицу.

_items. Add(hash, hashTableItem);

}

/// < summary>

/// Удалить данные из хеш таблицы по ключу.

/// < /summary>

/// < param name=" key" > Ключ. < /param>

public void Delete(string key)

{

// Проверяем входные данные на корректность.

if (string. IsNullOrEmpty(key))

{

throw new ArgumentNullException(nameof(key));

}

if (key. Length > _maxSize)

{

throw new ArgumentException($" Максимальная длинна ключа составляет {_maxSize} символов. ", nameof(key));

}

// Получаем хеш ключа.

var hash = GetHash(key);

// Если значения с таким хешем нет в таблице,

// то завершаем выполнение метода.

if (! _items. ContainsKey(hash))

{

return;

}

// Получаем коллекцию элементов по хешу ключа.

var hashTableItem = _items[hash];

// Получаем элемент коллекции по ключу.

var item = hashTableItem. SingleOrDefault(i => i. Key == key);

// Если элемент коллекции найден,

// то удаляем его из коллекции.

if (item! = null)

{

hashTableItem. Remove(item);

}

/// < summary>

/// Поиск значения по ключу.

/// < /summary>

/// < param name=" key" > Ключ. < /param>

/// < returns> Найденные по ключу хранимые данные. < /returns>

public string Search(string key)

{

// Проверяем входные данные на корректность.

if (string. IsNullOrEmpty(key))

{

throw new ArgumentNullException(nameof(key));

}

if (key. Length > _maxSize)

{

throw new ArgumentException($" Максимальная длинна ключа составляет {_maxSize} символов. ", nameof(key));

}

// Получаем хеш ключа.

var hash = GetHash(key);

// Если таблица не содержит такого хеша,

// то завершаем выполнения метода вернув null.

if(! _items. ContainsKey(hash))

{

return null;

}

// Если хеш найден, то ищем значение в коллекции по ключу.

var hashTableItem = _items[hash];

// Если хеш найден, то ищем значение в коллекции по ключу.

if (hashTableItem! = null)

{

// Получаем элемент коллекции по ключу.

var item = hashTableItem. SingleOrDefault(i => i. Key == key);

// Если элемент коллекции найден,

// то возвращаем хранимые данные.

if (item! = null)

{

return item. Value;

}

// Возвращаем null если ничего найдено.

return null;

}

/// < summary>

/// Хеш функция.

/// < /summary>

/// < remarks>

/// Возвращает длину строки.

/// < /remarks>

/// < param name=" value" > Хешируемая строка. < /param>

/// < returns> Хеш строки. < /returns>

private int GetHash(string value)

{

// Проверяем входные данные на корректность.

if (string. IsNullOrEmpty(value))

{

throw new ArgumentNullException(nameof(value));

}

if (value. Length > _maxSize)

{

throw new ArgumentException($" Максимальная длинна ключа составляет {_maxSize} символов. ", nameof(value));

}

// Получаем длину строки.

var hash = value. Length;

return hash;

}

Вызов

using System;

namespace HashTable

{

class Program

{

static void Main(string[] args)

{

// Создаем новую хеш таблицу.

var hashTable = new HashTable();

// Добавляем данные в хеш таблицу в виде пар Ключ-Значение.

hashTable. Insert(" Little Prince", " I never wished you any sort of harm; but you wanted me to tame you... " );

hashTable. Insert(" Fox", " And now here is my secret, a very simple secret: It is only with the heart that one can see rightly; what is essential is invisible to the eye. " );

hashTable. Insert(" Rose", " Well, I must endure the presence of two or three caterpillars if I wish to become acquainted with the butterflies. " );

hashTable. Insert(" King", " He did not know how the world is simplified for kings. To them, all men are subjects. " );

// Выводим хранимые значения на экран.

ShowHashTable(hashTable, " Created hashtable. " );

Console. ReadLine();

// Удаляем элемент из хеш таблицы по ключу

// и выводим измененную таблицу на экран.

hashTable. Delete(" King" );

ShowHashTable(hashTable, " Delete item from hashtable. " );

Console. ReadLine();

// Получаем хранимое значение из таблицы по ключу.

Console. WriteLine(" Little Prince say: " );

var text = hashTable. Search(" Little Prince" );

Console. WriteLine(text);

Console. ReadLine();

}

/// < summary>

/// Вывод хеш-таблицы на экран.

/// < /summary>

/// < param name=" hashTable" > Хеш таблица. < /param>

/// < param name=" title" > Заголовок перед выводом таблицы. < /param>

private static void ShowHashTable(HashTable hashTable, string title)

{

// Проверяем входные аргументы.

if(hashTable == null)

{

throw new ArgumentNullException(nameof(hashTable));

}

if(string. IsNullOrEmpty(title))

{

throw new ArgumentNullException(nameof(title));

}

// Выводим все имеющие пары хеш-значение

Console. WriteLine(title);

foreach (var item in hashTable. Items)

{

// Выводим хеш

Console. WriteLine(item. Key);

// Выводим все значения хранимые под этим хешем.

foreach(var value in item. Value)

{

Console. WriteLine($" \t{value. Key} - {value. Value}" );

}

Console. WriteLine();

}

На платформе. NET уже есть готовая реализация данной структуры данных. Она содержится в пространстве имен System. Collections и называется аналогично Hashtable.

В классе Hashtable реализуются интерфейсы IDictionary, ICollection, IEnumerable, ISerializable, IDeserializationCallback и ICloneable. В классе Hashtable определено немало конструкторов. Ниже приведены наиболее часто используемые конструкторы этого класса:

public Hashtable()

public Hashtable(IDictionary d)

public Hashtable(int capacity)

public Hashtable(int capacity, float loadFactor)

В первой форме создается создаваемый по умолчанию объект класса Hashtable. Во второй форме создаваемый объект типа Hashtable инициализируется элементами из коллекции d. В третьей форме создаваемый объект типа Hashtable инициализируется, учитывая емкость коллекции, задаваемую параметром capacity. И в четвертой форме создаваемый объект типа Hashtable инициализируется, учитывая заданную емкость capacity и коэффициент заполнения loadFactor. Коэффициент заполнения, иногда еще называемый коэффициентом загрузки, должен находиться в пределах от 0. 1 до 1. 0. Он определяет степень заполнения хеш-таблицы до увеличения ее размера. В частности, таблица расширяется, если количество элементов оказывается больше емкости таблицы, умноженной на коэффициент заполнения. В тех конструкторах, которые не принимают коэффициент заполнения в качестве параметра, этот коэффициент по умолчанию выбирается равным 1. 0.

В классе Hashtable определяется ряд собственных методов, помимо тех, что уже объявлены в интерфейсах, которые в нем реализуются. Некоторые из наиболее часто используемых методов этого класса приведены ниже. В частности, для того чтобы определить, содержится ли ключ в коллекции типа Hashtable, вызывается метод ContainsKey(). А для того чтобы выяснить, хранится ли в такой коллекции конкретное значение, вызывается метод ContainsValue(). Для перечисления содержимого коллекции типа Hashtable служит метод GetEnumerator(), возвращающий объект типа IDictionaryEnumerator. Напомним, что IDictionaryEnumerator — это перечислитель, используемый для перечисления содержимого коллекции, в которой хранятся пары " ключ-значение".

ContainsKey()

Возвращает логическое значение true, если в вызывающей коллекции типа Hashtable содержится ключ, а иначе — логическое значение false

ContainsValue()

Возвращает логическое значение true, если в вызывающей коллекции типа Hashtable содержится значение, а иначе — логическое значение false

GetEnumerator()

Возвращает для вызывающей коллекции типа Hashtable перечислитель типа IDictionaryEnumerator

Synchronized()

Возвращает синхронизированный вариант коллекции типа Hashtable, передаваемой в качестве параметра

В классе Hashtable доступны также открытые свойства, определенные в тех интерфейсах, которые в нем реализуются. Особая роль принадлежит двум свойствам, Keys и Values, поскольку с их помощью можно получить ключи или значения из коллекции типа Hashtable. Эти свойства определяются в интерфейсе IDictionary следующим образом:

public virtual ICollection Keys { get; }

public virtual ICollection Values { get; }

В классе Hashtable не поддерживаются упорядоченные коллекции, и поэтому ключи или значения получаются из коллекции в произвольном порядке. Кроме того, в классе Hashtable имеется защищенное свойство EqualityComparer. А два других свойства, hep и comparer, считаются устаревшими.

Давайте расмотрим пример:

using System;

using System. Collections;

namespace ConsoleApplication1

{

class Program

{

static void Main()

{

// Создаем хеш-таблицу

Hashtable ht = new Hashtable();

// Добавим несколько записей

ht. Add(" alex85", " 12345" );

ht. Add(" fg230404", " 12ldsd" );

ht. Add(" I_best_user", " 12349" );

// Считаем коллекцию ключей

ICollection keys = ht. Keys;

foreach (string s in keys)

Console. WriteLine(s + ": " + ht[s]);

Console. ReadLine();

}

Класс Hashtable платформы Net

public Hashtable()

public Hashtable(IDictionary d)

public Hashtable(int capacity)

public Hashtable(int capacity, float loadFactor)

ContainsKey()

ContainsValue()

GetEnumerator()

Возвращает для вызывающей коллекции типа Hashtable перечислитель типа IDictionaryEnumerator

Synchronized()

Возвращает синхронизированный вариант коллекции типа Hashtable, передаваемой в качестве параметра

public virtual ICollection Keys { get; }

public virtual ICollection Values { get; }

Давайте расмотрим пример:

using System;

using System. Collections;

namespace ConsoleApplication1

{

class Program

{

static void Main()

{

// Создаем хеш-таблицу

Hashtable ht = new Hashtable();

// Добавим несколько записей

ht. Add(" alex85", " 12345" );

ht. Add(" fg230404", " 12ldsd" );

ht. Add(" I_best_user", " 12349" );

// Считаем коллекцию ключей

ICollection keys = ht. Keys;

foreach (string s in keys)

Console. WriteLine(s + ": " + ht[s]);

Console. ReadLine();

}

Добавьте в пример операцию удаления записей.

Контрольные вопросы:

1. Понятие хеш-таблицы.

2. В чем сходство и различие структуры хеш-таблицы и словаря в программировании?

3. Область применения хеш-таблиц в системном программировании? В прикладном? При изучении каких тем вы встречали пары ключ-значение?

4. Как вы понимаете термин «хеширование»?

5. Какие способы реализации хеш-таблиц вам известны?

6. Какой класс(свойства, методы) платформы Net реализует хеш-таблицы?

Литература:

Таненбаум Э., Бос Х. Т18 Современные операционные системы. 4-е изд. — СПб.: Питер, 2015. — 1120 с.: ил. — (Серия «Классика computer science»). ISBN 978-5-496-01395-6

Интернет источники:

https: //ru. wikipedia. org/wiki/%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0

https: //professorweb. ru/my/csharp/charp_theory/level12/12_5. php

https: //shwanoff. ru/hashtable/

https: //www. youtube. com/watch? v=PwAeMJGjKk8 начиная с 03: 50