Методы сортировки и поиска

Коллизии при хэшировании и способы их разрешения


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

Распространенным методом является использование эмпирически подобранной хэш-функции, которая (a) по значению ключа производит значение индекса в границах массива и (b) равномерно распределяет ключи по элементам массива. Если ORD(k) обозначает порядковый номер ключа k в упорядоченном множестве допустимых ключей, а N - число элементов в массиве записей, то одной из наиболее естественных хэш-функций является H(k) = ORD(k) MOD N, т.е. взятие остатка от деления порядкового номера ключа на число элементов массива. Такая функция выполняется очень быстро, если N является степенью числа 2. Для числовых ключей функция обеспечивает достаточную равномерность распределения ключей в массиве.

Однако если ключом является последовательность символов (что чаще всего и бывает), то при применении такой функции возникает большая вероятность выработки одного и того же значения для ключей, отличающихся небольшим числом символов. Ситуацию несколько облегчает использование в качестве N простого числа. Вычисление функции становится более сложным, но вероятность выработки одного значения для разных ключей уменьшается.

Используются и более сложные способы вычисления хэш-функции основанные, например, на вырезке поднабора бит из битового представления ключа или вычислении квадратичного выражения от ORD(k). Но в любом случае с ненулевой вероятностью хэш-функция может выдать одно значение для разных значений ключа. Такая ситуация называется коллизией ключей и проявляется в том, что при попытке занести в хэш-таблицу запись с новым ключом мы наталкиваемся на то, что требуемый элемент массива уже занят. Одним из выходов (к которому рано или поздно, может быть, придется прибегнуть) является увеличение размера массива, образование новой хэш-функции и расстановка заново всех занятых элементов массива. Но поскольку возникновение коллизии может являться флуктуацией, до поры до времени обычно пытаются разрешать эту ситуацию другими способами. Традиционно принято различать методы прямой адресации (ключ, появление которого вызвало коллизию, помещается в один из свободных элементов хэш-таблицы) и методы цепочек (записи, для ключей которых выработано одинаковое значение хэш-функции связываются в линейный список).

Содержание раздела