Открытое и закрытое хеширование — различия между версиями
(→Открытое хеширование) |
(Добавлена ссылка на "Поиск свободного места при закрытом хешировании") |
||
| Строка 2: | Строка 2: | ||
==Открытое хеширование== | ==Открытое хеширование== | ||
Открытое хеширование (метод цепочек) — простейший метод борьбы с коллизиями. При использовании этого метода мы объединяем все элементы, хешированные в одну и ту же ячейку, в связный список. Ячейка <tex>j</tex> содержит указатель на заголовок списка всех элементов, хэш-значение ключа которых равно <tex>j</tex>; если таких элементов нет, ячейка содержит значение <tex>nil</tex>. Вставляем элемент в заголовок списка. Время, необходимое для вставки в наихудшем случае равно <tex>O(1)</tex>. При использовании двусвязных списков удаление также может быть выполено за <tex>O(1)</tex>. (доказательство см. Т.Корман, второе издание, стр. 288) | Открытое хеширование (метод цепочек) — простейший метод борьбы с коллизиями. При использовании этого метода мы объединяем все элементы, хешированные в одну и ту же ячейку, в связный список. Ячейка <tex>j</tex> содержит указатель на заголовок списка всех элементов, хэш-значение ключа которых равно <tex>j</tex>; если таких элементов нет, ячейка содержит значение <tex>nil</tex>. Вставляем элемент в заголовок списка. Время, необходимое для вставки в наихудшем случае равно <tex>O(1)</tex>. При использовании двусвязных списков удаление также может быть выполено за <tex>O(1)</tex>. (доказательство см. Т.Корман, второе издание, стр. 288) | ||
| + | |||
| + | ==Закрытое хеширование== | ||
| + | [[Поиск свободного места при закрытом хешировании]] | ||
Версия 23:08, 15 мая 2011
Есть разные методы борьбы с коллизиями. Рассмотрим два из них.
Открытое хеширование
Открытое хеширование (метод цепочек) — простейший метод борьбы с коллизиями. При использовании этого метода мы объединяем все элементы, хешированные в одну и ту же ячейку, в связный список. Ячейка содержит указатель на заголовок списка всех элементов, хэш-значение ключа которых равно ; если таких элементов нет, ячейка содержит значение . Вставляем элемент в заголовок списка. Время, необходимое для вставки в наихудшем случае равно . При использовании двусвязных списков удаление также может быть выполено за . (доказательство см. Т.Корман, второе издание, стр. 288)
