Что такое Hashtable?

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

Производительность хеш-таблицы для набора данных зависит от эффективности ее хеш-функции. Хорошая хеш-функция обычно обеспечивает равномерный поиск ключей и равномерное распределение отображений в соответствующем массиве. Столкновение хэша происходит, когда двум ключам присваивается одно и то же соответствующее значение. Когда происходит столкновение хеша, хеш-функция обычно выполняется снова, пока не будет найдено уникальное соответствующее значение; это обычно приводит к увеличению времени хеширования. Хотя количество ключей в хеш-таблице обычно фиксировано, иногда могут быть дубликаты ключей. Тем не менее, хорошо спроектированная хеш-таблица имеет эффективные хеш-функции, которые отображают каждый ключ на уникальное соответствующее значение в массиве.

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

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

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