Изменения

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

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

1745 байт добавлено, 23:38, 15 мая 2011
Промежуточное
При использовании открытого хеширования такой проблемы не возникает, так как там в каждой ячейке хранится список всех элементов. При добавлении необходимо просто дописать элемент в конец списка.
Закрытое хеширование работает иначе: в каждой ячейке хеш-таблицы хранится только один элемент. Тогда при добавлении, если ячейка свободна, мы просто записываем добавляемый элемент в эту ячейку. Однако если эта ячейка занята - необходимо поместить добавляемый элемент в какую-нибудь другую свободную ячейку. Такие ситуации нередки, так как невозможно использовать хеш-функцию, не дающую коллизий, а каждой ячейке таблицы соответствует одно значение хеш-функции.Далее мы рассмотрим несколько стратегий поиска свободного места в данном случае. == Стратегии поиска == '' Последовательный поиск '' При попытке добавить элемент в занятую ячейку <tex>i</tex> начинаем последовательно просматривать ячейки <tex>i+1, i+2, i+3</tex> и так далее, пока не найдём свободную ячейку. В неё и запишем элемент. '' Линейный поиск '' Выбираем шаг <tex>q</tex>. При попытке добавить элемент в занятую ячейку <tex>i</tex> начинаем последовательно просматривать ячейки <tex>i+(1*q), i+(2*q), i+(3*q)</tex> и так далее, пока не найдём свободную ячейку. В неё и запишем элемент.По сути Последовательный поиск - частный случай линейного, где <tex>q=1</tex>. '' Квадратичный поиск '' Шаг <tex>q</tex> не фиксирован, а изменяется квадратично. В качестве начального значения часто выбирается <tex>1</tex>. При попытке добавить элемент в занятую ячейку <tex>i</tex> начинаем последовательно просматривать ячейки <tex>i+q, i+q^2, i+q^3</tex> и так далее, пока не найдём свободную ячейку. == Проверка наличия элемента в таблице==
42
правки

Навигация