Структуры данных: хэш-таблица
Хэш-таблица (hash table, hash map) представляет собой структуру данных, которая реализует абстрактный тип данных ассоциативного массива, структуру, которая может отображать ключи в значения. Хэш-таблица использует хэш-функцию для вычисления индекса, также называемого хэш-кодом, в массиве корзин (buckets) или слотов, из которого можно найти требуемое значение.
В идеале хэш-функция будет назначать каждому ключу уникальный корзину (bucket), но в большинстве конструкций хэш-таблиц используется несовершенная хэш-функция, которая может привести к коллизиям хэш-функции, когда хэш-функция генерирует один и тот же индекс для более чем одного ключа. Такие коллизии должны быть учтены каким-либо образом.
В хэш-таблице с большими размерами средняя стоимость (количество инструкций) для каждого поиска не зависит от количества элементов, хранящихся в таблице. Многие схемы хэш-таблиц также допускают произвольные вставки и удаления пар ключ-значение при (амортизированной) постоянной средней стоимости за операцию.
Во многих ситуациях хэш-таблицы оказываются в среднем более эффективными, чем деревья поиска или любая другая структура поиска таблиц. По этой причине они широко используются во многих видах компьютерного программного обеспечения, особенно для ассоциативных массивов, индексации баз данных, кэшей и наборов (сетов).
Производительность хэш-таблиц:
Хэширование
Идея хэширования состоит в том, чтобы распределить записи (пары ключ/значение) по массиву корзин (buckets). Учитывая ключ, алгоритм вычисляет индекс, который предлагает, где можно найти запись:
index = f(key, array_size)
Часто это делается в два этапа:
hash = hashfunc(key)
index = hash % array_size
В этом методе хэш не зависит от размера массива, а затем он сводится к индексу (число от 0 до array_size - 1), используя оператор по модулю (%).
В случае, когда размер массива равен степени двух, оставшаяся операция сокращается до маскирования, что повышает скорость, но может увеличить проблемы с плохой хэш-функцией.
Выбор хэш-функции
Основным требованием является то, что функция должна обеспечивать равномерное распределение значений хэш-функции. Неравномерное распределение увеличивает количество коллизий и стоимость их устранения. Однородность иногда трудно обеспечить с помощью дизайна, но ее можно оценить эмпирически, используя статистические тесты, например chi-squared тест Пирсона для дискретных равномерных распределений.
Распределение должно быть равномерным только для размеров таблицы, которые встречаются в приложении. В частности, если используется динамическое изменение размера с точным удвоением и уменьшением вдвое размера таблицы, то хэш-функция должна быть однородной только тогда, когда размер является степенью двойки. Здесь индекс может быть вычислен как некоторый диапазон битов хэш-функции. С другой стороны, некоторые алгоритмы хэширования предпочитают, чтобы размер был простым числом. Операция модуля может обеспечить некоторое дополнительное перемешивание; это особенно полезно с плохой хэш-функцией.
Для схем открытой адресации хэш-функция должна также избегать кластеризации, сопоставления двух или более ключей последовательным слотам. Такая кластеризация может привести к стремительному росту затрат на поиск, даже если коэффициент загрузки низкий, а коллизии нечасты. Утверждается, что популярный мультипликативный хэш обладает особенно плохим поведением кластеризации.
Считается, что криптографические хэш-функции обеспечивают хорошие хэш-функции для таблиц любого размера, либо путем уменьшения по модулю, либо путем маскировки битов. Они также могут быть уместны, если существует риск того, что злоумышленники попытаются саботировать сетевую службу, отправляя запросы, предназначенные для создания большого количества коллизий в хэш-таблицах сервера. Однако риск саботажа также можно избежать с помощью более дешевых методов (таких как применение секретной соли к данным или использование универсальной хэш-функции). Недостаток криптографических хэш-функций заключается в том, что они часто медленнее вычисляются, что означает, что в случаях, когда однородность для любого размера не требуется, некриптографическая хэш-функция может быть предпочтительнее.
Идеальная хэш-функция
Если все ключи известны заранее, можно использовать идеальную хэш-функцию для создания идеальной хэш-таблицы, в которой нет коллизий. Если используется минимальное идеальное хэширование, можно также использовать любое место в хэш-таблице.
Идеальное хэширование позволяет осуществлять поиск в постоянном времени во всех случаях. Это в отличие от большинства методов цепочки и открытой адресации, где время поиска в среднем мало, но может быть очень большим, например, O(n), когда все ключи хэшируют до нескольких значений.
Ключевые статистические данные
Критическая статистика для хэш-таблицы - это коэффициент загрузки, определяемый как
load factor = n/k
где
n - количество записей, занятых в хэш-таблице.
k - количество корзин (buckets)
При увеличении коэффициента загрузки хэш-таблица становится медленнее и может даже не работать (в зависимости от используемого метода). Ожидаемое свойство постоянного времени для хэш-таблицы предполагает, что коэффициент загрузки должен быть ниже некоторой границы. Для фиксированного количества сегментов время поиска увеличивается с увеличением количества записей, и, следовательно, желаемое постоянное время не достигается. В некоторых реализациях решение состоит в том, чтобы автоматически увеличивать (как правило, удваивать) размер таблицы при достижении границы коэффициента загрузки, заставляя таким образом повторно хэшировать все записи. Как пример из реальной жизни, коэффициент загрузки по умолчанию для HashMap в Java 10 составляет 0,75, что "предлагает хороший компромисс между временными и пространственными затратами".
Во-вторых, к коэффициенту загрузки, можно исследовать дисперсию количества записей на группу. Например, две таблицы имеют 1000 записей и 1000 корзин; одна имеет ровно одну запись в каждой корзине, а другая - все записи в одной корзине. Очевидно, что хэширование не работает во второй.
Низкий коэффициент загрузки не особенно выгоден. Когда коэффициент загрузки приближается к 0, доля неиспользуемых областей в хэш-таблице увеличивается, но не обязательно происходит какое-либо снижение стоимости поиска. Это приводит к потере памяти.
Читайте также:
Комментарии
Отправить комментарий