Изменения

Перейти к: навигация, поиск

Разрешение коллизий

1337 байт убрано, 23:38, 31 мая 2015
Нет описания правки
'''Разрешение [[Хеш-таблица|коллизий]]''' (англ. collision resolution) в хеш-таблице, задача, решаемая несколькими способами. Можно использовать списки, а можно открытую адресацию.
 
При использовании списков особых проблем не возникает, так как там в каждой ячейке хранится список всех элементов. При добавлении необходимо просто добавить элемент в начало списка.
 
При открытой адресации будет иначе: в каждой ячейке хеш-таблицы хранится только один элемент. Тогда при добавлении, если ячейка свободна, мы просто записываем добавляемый элемент в эту ячейку. Однако если эта ячейка занята {{---}} необходимо поместить добавляемый элемент в какую-нибудь другую свободную ячейку. Такие ситуации нередки, так как невозможно использовать хеш-функцию, не дающую коллизий, а каждой ячейке таблицы соответствует одно значение хеш-функции. Далее мы рассмотрим несколько стратегий поиска свободного места в данном случае.
== Разрешение коллизий с помощью цепочек ==
106
правок

Навигация