Хеш-таблица (hashtable) на языке C#
Хеш-таблица (hashtable) — это структура данных, представляющая собой специальным образом организованный набор элементов хранимых данных. Все данные хранятся в виде пар хеш-значения. Данная структура похожа на словарь (map), но имеет особенности такие как применение хеш-функции для увеличения скорости поиска. Принцип работы данной структуры схож с каталогом книг. Все книги разложены в алфавитном порядке, но не на одном стеллаже, а для каждой буквы выделен отдельный стеллаж, поэтому нам не нужно по порядку перебирать все книги, а можно подойти к нужному стеллажу и искать уже там. Давайте рассмотрим пример реализации хеш-таблицы на языке C#.
Существуют два основных способа реализации хеш-таблиц:
- Метод цепочек (открытое хеширование) — все элементы данных с совпадающем хешем объединяются в список.
- Метод открытой адресации (закрытое хеширование) — добавляем элемент данных в ячейку по хешу, если эта ячейка занята, то переходим в следующую до тех пор, пока не найдем свободную.
В данном примере мы будем реализовывать первый вариант.
На рисунке ниже представлена схематичная структура хеш-таблицы.
Доступ к элементам осуществляется по его ключу. Основные операции, которые могут выполняться с хеш-таблицей?
- Insert — добавить новый элемент в хеш-таблицу
- Delete — удалить элемент из хеш-таблицы по ключу
- Search — получить значение по ключу
Основной принцип работы хеш-таблицы заключается в том, что в качестве входных параметров она принимает пары ключ-значение. Затем с помощью специальной хеш функции получает короткий ключ на основе полученного ключа. И наконец добавляет данные в таблицу. Если в таблице уже существует значения с таким хешем, то объединяет их в коллекции. Внутри коллекции поиск выполняется по изначальному полученному ключу.
Теперь приступим к реализации данной структуры данных. Для простоты будем рассматривать структуру из пары двух строк. Данная реализация является весьма примитивной, но позволяет разобраться в структуре и алгоритме работы данного типа данных.
Класс элемента данных хеш-таблицы
Класс хеш-таблицы
Работа с хеш-таблицей
Результат работы приложения
На платформе .NET уже есть готовая реализация данной структуры данных. Она содержится в пространстве имен System.Collections и называется аналогично Hashtable. Я не претендую на правильность, оптимальность и красоту реализации. Единственная цель, которую я преследую, поделиться полезной информацией о программировании, которая может кому-то пригодиться.
Источник: https://shwan.ru/hashtable/