Открытое и закрытое хеширование — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «Есть разные методы борьбы с коллизиями. Рассмотрим два из них. ==Открытое хеширование== Отк…»)
 
(Открытое хеширование)
Строка 1: Строка 1:
 
Есть разные методы борьбы с коллизиями. Рассмотрим два из них.
 
Есть разные методы борьбы с коллизиями. Рассмотрим два из них.
 
==Открытое хеширование==
 
==Открытое хеширование==
Открытое хеширование (метод цепочек) — простейший метод борьбы с коллизиями. При использовании этого метода мы объединяем все элементы, хешированные в одну и ту же ячейку, в связный список. Ячейка <tex>j</tex> содержит указатель на заголовок списка всех элементов, хэш-значение ключа которых равно <tex>j</tex>; если таких элементов нет, ячейка содержит значение <tex>nil</tex>. Время, необходимое для вставки в наихудшем случае равно <tex>O(1)</tex>. Процедура вставки выполняется очень быстро, потому что предполагается, что вставляемый элемент отсутствует в таблице. При необходимости это предположение может быть проверено путем проведения поиска перед вставкой. Время работы поиска в наихудшем случае пропорционально длине списка.
+
Открытое хеширование (метод цепочек) — простейший метод борьбы с коллизиями. При использовании этого метода мы объединяем все элементы, хешированные в одну и ту же ячейку, в связный список. Ячейка <tex>j</tex> содержит указатель на заголовок списка всех элементов, хэш-значение ключа которых равно <tex>j</tex>; если таких элементов нет, ячейка содержит значение <tex>nil</tex>. Вставляем элемент в заголовок списка. Время, необходимое для вставки в наихудшем случае равно <tex>O(1)</tex>. При использовании двусвязных списков удаление также может быть выполено за <tex>O(1)</tex>. (доказательство см. Т.Корман, второе издание, стр. 288)

Версия 05:29, 14 мая 2011

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

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

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