Причины использования Quadratic Probing для реализации хэш-таблиц
Я узнал о хэш-таблицах в последнее время. Есть несколько примеров Коллизионных Резолюций, и один из них - Квадратичное зондирование. Почему кто-то будет использовать квадратичное зондирование? Знает ли он, что хеш-таблица всегда будет заполнена менее чем наполовину? И если так, почему он использует такой большой стол для начала?
2 ответа
Зачем кому-то использовать квадратичное зондирование?
Предполагая, что нам нужен алгоритм разрешения коллизий,
Квадратичное зондирование может быть более эффективным алгоритмом в закрытой хеш-таблице, поскольку оно лучше избегает проблемы кластеризации, которая может возникнуть при линейном зондировании, хотя и не является иммунной.
Квадратичное зондирование не является идеальным, но оно дает некоторые преимущества перед альтернативами:
Преимущества квадратичной (или других форм) цепочки
- более простая логика для управления хранилищем (без динамического выделения)
- более быстрые вставки (по причине более простого хранения)
- Снижение требований к хранению в целом
Знает ли он, что хеш-таблица всегда будет заполнена менее чем наполовину?
Не обязательно; это зависит от используемой стратегии изменения размера, если таковая имеется.
Считайте, что ваше обучение по QP является в первую очередь образовательным. Практические реализации хэш-таблиц , по моему опыту, не часто используют открытую адресацию.
Квадратичная перефразировка - это очень простой и быстрый способ избежать проблемы кластеризации линейного хэша. Обычно он используется только тогда, когда размер таблицы прост (что также может быть полезно по другим причинам).
Чтобы не беспокоиться о том, что "стол наполовину полон", проще всего в какой-то момент переключиться на линейный зонд. (Вы можете поместить пороговый тест для такого переключения в обычный блок if (index >= size) {index -= size;}, чтобы избежать потери производительности.