Открытое и закрытое хеширование

Есть разные методы борьбы с коллизиями. Рассмотрим два из них.

Открытое хеширование

Открытое хеширование (метод цепочек) — простейший метод борьбы с коллизиями. При использовании этого метода мы объединяем все элементы, хешированные в одну и ту же ячейку, в связный список. Ячейка [math]j[/math] содержит указатель на заголовок списка всех элементов, хэш-значение ключа которых равно [math]j[/math]; если таких элементов нет, ячейка содержит значение [math]nil[/math]. Элементы вставляются в заголовок списка. Время, необходимое для вставки в наихудшем случае равно [math]O(1)[/math], учитывая то, что мы предполагаем отсутствие вставляемого элемента в таблице. Время поиска зависит от длины списка, и в худшем случае равно [math]O(n)[/math]. Эта ситуация, когда все элементы хешируются в единственную ячейку. Если функция распределяем [math]n[/math] ключей по [math]m[/math] ячейкам таблицы равномерно, то в каждом списке будет содержаться порядка [math]n/m[/math] ключей. Это число называется коэффициентом заполнения хеш-таблицы. Математический анализ хеширования с цепочками показывает, что в среднем случае все операции в такой хеш-таблице в среднем выполняются за время [math]O(1)[/math]. При использовании двусвязных списков удаление также может быть выполено за [math]O(1)[/math]. (доказательство см. Т.Корман, второе издание, стр. 288)

описание

Закрытое хеширование

Поиск свободного места при закрытом хешировании