Редактирование: Разрешение коллизий
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 44: | Строка 44: | ||
=== Проблемы данных стратегий === | === Проблемы данных стратегий === | ||
− | Проблем две — крайне нетривиальное удаление элемента из таблицы и образование кластеров | + | Проблем две — крайне нетривиальное удаление элемента из таблицы и образование кластеров. |
− | + | {{Определение | |
+ | |definition= | ||
+ | Кластер — последовательность занятых клеток. | ||
+ | }} | ||
Кластеризация замедляет все операции с хеш-таблицей: при добавлении требуется перебирать всё больше элементов, при проверке тоже. Чем больше в таблице элементов, тем больше в ней кластеры и тем выше вероятность того, что добавляемый элемент попадёт в кластер. | Кластеризация замедляет все операции с хеш-таблицей: при добавлении требуется перебирать всё больше элементов, при проверке тоже. Чем больше в таблице элементов, тем больше в ней кластеры и тем выше вероятность того, что добавляемый элемент попадёт в кластер. | ||
Для защиты от кластеризации используется двойное хеширование и [[Хеширование кукушки|хеширование кукушки]]. | Для защиты от кластеризации используется двойное хеширование и [[Хеширование кукушки|хеширование кукушки]]. |