2.3 Обработка коллизий
2.3.1 Основные концепции
Все существующие методы обработки коллизий можно разделить на две основные категории:
- методы, называемые внутренней адресацией, в которых в качестве резервных используются ячейки самой таблицы хеширования;
- методы, в которых для хранения элементов с одинаковыми хеш-адресами отводится специальная область переполнения.
Для внутренней адресации используются различные, часто сложные, алгоритмы, позволяющие повысить эффективность поиска. В отличие от этих методов – методы 2-го типа (переполнения) – достаточно просты.
Если определить эффективность как среднее число операций поиска, необходимых для выборки одного элемента таблицы, то преимущество 2-й группы методов может показаться очевидным. Тем не менее, больше применяются методы 1-й группы (т.е. внутренняя адресация).
Процедура, при помощи которой в методе внутренней адресации отыскиваются резервные ячейки, получила название пробинга. В сущности, пробинг является методом проб и ошибок, примененным к поиску пустой ячейки. Какой бы конкретный алгоритм ни был положен в основу этой процедуры, последовательность определяемых им действий обязательно должна быть детерминированной, т.к. при записи и выборке ЭД выполняются одни и те же операции.
Разработано много различных высокоэффективных алгоритмов пробинга, о некоторых из них кратко будет сказано ниже.