Материал из Викиконспекты
|
|
| (не показано 16 промежуточных версий 3 участников) |
| Строка 1: |
Строка 1: |
| − | Есть разные методы борьбы с коллизиями. Рассмотрим два из них.
| + | #перенаправление [[Хеш-таблица#Разрешение коллизий с помощью цепочек]] |
| − | ==Открытое хеширование==
| |
| − | Открытое хеширование (метод цепочек) — простейший метод борьбы с коллизиями. При использовании этого метода мы объединяем все элементы, хешированные в одну и ту же ячейку, в связный список. Ячейка <tex>j</tex> содержит указатель на заголовок списка всех элементов, хэш-значение ключа которых равно <tex>j</tex>; если таких элементов нет, ячейка содержит значение <tex>nil</tex>. Вставляем элемент в заголовок списка. Время, необходимое для вставки в наихудшем случае равно <tex>O(1)</tex>. При использовании двусвязных списков удаление также может быть выполено за <tex>O(1)</tex>. (доказательство см. Т.Корман, второе издание, стр. 288)
| |
| − | | |
| − | ==Закрытое хеширование==
| |
| − | [[Поиск свободного места при закрытом хешировании]]
| |
Текущая версия на 13:21, 12 июня 2012
