Хеш-таблица

Хеш-таблица — специальная структура данных, в которой данные хранятся в виде хеш — значение. Очень похожа на словарь, но в ее основе используется хеш функция для ускорения поиска.

Есть два основных способа реализации хеш-таблицы:

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

В .NET уже существует готовая реализация этой структуры: System.Collections.HasTable. Но с появлением обобщенных коллекций стал устаревшим. На его место пришел словарь — Dictionary. Так как в базовом объекте есть 2 метода Equal и GetHashCode мы можем в качестве ключа словаря использовать любой тип данных.

Поделиться
Отправить
Популярное