Хэш-таблицы как метод организации ассоциативных массивов

Алгоритмы   14 Июль 2012  Автор статьи:  

Ассоциативный массив — такой массив, индексы которого могут быть не только упорядоченными целыми числами от 0 или от 1, но и другие объекты любой природы. В языках С++ и Java ассоциативные массивы представлены интерфейсом Map. Одной из популярных имплементаций данного интерфейса является использование хэш-таблиц (Hash Map).В хэш-таблице используется обычный массив, в котором индексация ключа заменяется на его целочисленный хэш. Хэш функция имеет конечное последовательное множество значений от 0(1) до n-1, где n — мощность хэш-функции.
В ассоциативном массиве есть три операции:

  • put(K,V) — положить по ключу K значение V
  • get(K) — получить по данному ключа К его значение или установить что его не существует
  • del(K) — удаляет значение, содержащееся по ключу К (если оно существует)

Предположим, что у нас хэш-функция h была такова, что не существовало коллизий, то есть не существовало такой ситуации, что при несовпадении ключей x и y совпадали их хэш-значения h(x) и h(y). Тогда бы каждый значение хэш-таблицы t содержало значение ровно бы по одному ключу и операции put, get и del составляли бы просто запись, взятие и удаление значения из массива t по индексу i = h(K). Но так как на практике всегда существуют коллизии, нужны способы чтобы разрешать их. Существует два способа разрешения коллизий:

  • Использование цепочек
  • Использование открытой адресации

Разрешение коллизий методом цепочек
В этом случае каждый i-ый элемент массива t хранит список(цепочку) пар в виде (Kj,Vj), такие что h(Kj) = i.
При операции put сначала будет проверяться в списке наличие ключа Kj. Если такой ключ существует, обновляем значение Vj. В противном случае добавляем в этот список пару (Kj,Vj). При операции get и del также будет проверятся наличие ключа Kj и в случае успеха будет возвращаться(удаляться) значение Vj для get(del).
Если m = O(n)( где m — размер хэш-таблицы, а n — множество хэш-значений), то средняя длины цепочки будет O(1), следовательно время работы операций put, get и del будет составлять O(1). Величина \alpha = \frac{m}{n} называется loadfactor. Значение \alpha составляет среднюю длину цепочки и в среднем случае время работы основных алгоритма составляет O(1 + \frac{1}{\alpha}) . На практике в хэш-таблицах \alpha стараются делать от 0.5 до 3. Иногда хэш-таблицу делают самоорганизующейся, т.е. при возрастании loadfactora хеш-таблица будет перестраиваться путем выбора другой хэш-функции с большим значением n.
Разрешение коллизий методом открытой адресации
При хешировании открытой адресации используется массив длины m, его можно применять, когда n\lem. Назовем этот массив t. В массиве t его элементы могут быть в одном из трех состояний:

  1. Пусто(null) — элемент не использовался с момента инициализации
  2. Пара значений (K,V)
  3. Удален(deleted) — элемeнт раньше содержал пару (K,V)

Во всех операциях от ключа К берется хэш h. Во время выполнения операции put, если элемент массива t[h] null или deleted, то записываем в него пару (K,V). В противном случае переходи к элементу, находящемуся правее h (если такого элемента нет, то возвращаемся в начало массива) и проверяем его аналогичным образом. Алгоритм продолжается до тех пор, пока не найдется пустой или удаленный элемент или пока индекс снова не станет равным h. Во втором случае происходит переполнение хэш таблицы и запись новых значений в нее невозможен. Во время выполнения операции get также происходит циклическая проверка элементов массива, начиная с индекса h. Если элемент является парой и ключ этой пары совпадает с К, то возвращается значение V. Если же ключи не совпадают или элемент является deleted, то берется элемент, находящийся в массиве правее текущего (или первый элемент для последнего элемента в массиве). Если же элемент является null или же его индекс снова равен h, то выдается сообщение об отсутствии в ассоциативном массиве значений по данному ключу. Операция del сходна с операцией put за исключением того случая, что при нахождении ключа К мы значение данного элемента массива t заменяем на deleted.
У этого метода есть одни недостаток: при увеличении числа значений в массиве образуются длинные блоки из непустых элементов(кластеры), в результате чего увеличивается время работы основных операций ассоциативного массива. Более того блок длины а будет удлинятся с вероятностью (a+1)/m, т.е. чем длиннее будет становится кластер, тем больше вероятность что он станет еще длиннее. Очевидным решением данной проблемы является изменение процедуры выбор следующего элемента массива(пробы), если текущий не подходит для операций записи, взятия или удаления.
Одним из способом взятия проб является квадратичная адресация, где каждый следующий элемент на i-ой итерации выбирается по формуле h = (h_0 + r_1\cdot i +r_2\cdot i^2) mod m, где h_0 = hash(K)  — первоначальное значение хэша, а r_1 и r_2 — целочисленные константы, такие что для любых i от 0 до m-1 h по модулю m принимает все значения от 0 до m-1. Пр таком кластере возникает проблема кластеров второго порядка, которая встает не так остро, как проблема кластеров при линейной адресации.
Другим способом решения проблем кластеров является использования двойного хэширования для адресации элементов. При использовании этого метода следующая проба на i-ой итерации берется следующим образом: h =(h_0 + r_k \cdot i) mod m, где h_0 = hash(K)  — первоначальное значение хэша, а r_k = hash'(K) — вторая хэш функция, определяющая шаг адресации при взятии следующей пробы. Необходимо условием является то, чтобы для всех i от 0 до m-1 h должно по модулю m принимать все значения от 0 до m-1. Этого можно достигнуть, например взяв число m(т.е. размер массива t) за некоторую степень двойки и гарантировать, что r_k будет принимать нечетные занчения. Или же можно взять m простым числом, тогда r_k должно принимать занчения в диапазоне от 0 до m-1.
Следует заметить, что на процессорах с большим кэшем самый простой способ может работать быстрее квадратичной адресации или двойного хеширования из-за боьшей вероятности нахождения исходного ключа в кэше процессора.

  • max

    «хеш-таблица будет перестраиваться путем выбора другой хэш-функции» другой, это простите, какой?

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

    • http://cybern.ru/ lordrp

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

    • http://cybern.ru/ lordrp

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

  • Александр

    В ассоциативном массиве есть ДВЕ операции:
    put(K,V) — положить по ключу K значение V
    get(K) — получить по данному ключа К его значение или установить что его не существует
    del(K) — удаляет значение, содержащееся по ключу К (если оно существует)

    • http://cybern.ru/ lordrp

      Спасибо, исправили.

Научиться программировать

  • на Delphi

  • на Java

  • на C++