Компьютеры и Интернет
В информатике хеш таблица – это структура данных для хранения данных, которая состоит из списка значений, называемых ключами, которые соединяются с соответствующим списком значений, называемым массивом. Например, название компании может быть связано с её адресом. Как правило, каждое значение в массиве имеет номер позиции, называемый хешем. Хеш функция, как правило, представляет собой набор инструкций или алгоритм, который отображает каждое значение ключа в хеш код, например, связывая название предприятия с его адресом, номером телефона и категорией бизнеса.
Цель хэш функции – назначить каждому ключу уникальное соответствующее значение в массиве – это обычно называют хэшированием. Хеш функции должны быть правильно отформатированы, чтобы хеш таблица работала правильно.
Производительность хеш таблицы для набора данных зависит от эффективности её хеш функции. Хорошая хеш функция обычно обеспечивает равномерный поиск ключей и равномерное распределение отображений в соответствующем массиве. Столкновение хэша происходит, когда двум ключам присваивается одно и то же соответствующее значение. Когда происходит коллизия хеша, хеш функция обычно выполняется снова, пока не будет найдено уникальное соответствующее значение – это обычно приводит к увеличению времени хеширования. Хотя количество ключей в хеш таблице обычно фиксированное, иногда могут быть дубликаты ключей. Тем не менее, хорошо спроектированная хеш таблица имеет эффективные хеш функции, которые отображают каждый ключ на уникальное соответствующее значение в массиве.
Иногда неэффективные хеш функции в хеш таблице также могут создавать кластер отображений. Если хеш функция создает кластер сопоставлений для существующих ключей, это может увеличить время, необходимое для поиска соответствующих значений. Это может замедлить хеширование для будущих ключей, поскольку большинство хеш функций обычно ищут следующую доступную позицию в массиве. Если большой кластер значений уже назначен, поиск нового неназначенного значения обычно занимает намного больше времени.
Коэффициент загрузки является еще одним понятием, связанным с эффективностью хэш функции; коэффициент загрузки – это количество уже существующих хеш-кодов по отношению к общему размеру соответствующего массива в хеш таблице. Обычно это определяется путем деления количества уже назначенных ключей на размер соответствующего массива. При увеличении коэффициента загрузки хорошая хеш-функция обычно будет поддерживать постоянное количество столкновений и кластеров до определенной точки. Часто этот порог можно использовать для определения того, насколько эффективна хеш-функция с заданным количеством ключей и когда может потребоваться новая хеш функция.
Многие исследователи в области компьютерных наук стремились создать идеальную хеш-функцию, которая не создает столкновений или кластеров при увеличении коэффициента загрузки. Теоретически, ключом к созданию идеальной хеш-таблицы является создание идеальной хеш функции. В целом, исследователи считают, что идеальная хеш функция должна иметь постоянную производительность – количество столкновений и кластеров – с увеличением коэффициента загрузки. В наихудших сценариях идеальная хеш функция всё равно допускает постоянное хеширование без достижения порогового значения.
