Вопрос 6: Открытые и закрытые хеш-таблицы: способы разрешения коллизий
По способу разрешения коллизий различают хеш-таблицы двух типов:
С открытой адресацией (закрытые хеш-таблицы):
Конфликтующие значения ключей размещаются в свободных ячейках таблицы.
С цепочками переполнения (открытые хеш-таблицы):
Каждая ячейка таблицы содержит указатель на список конфликтующих ключей.
Таблицы второго типа применяются чаще, потому что для них не существует проблемы переполнения. Если мощность хранимого множества становится слишком большой, таблица просто начинает работать как m (m - размер хэш-таблицы) списков. Если же таблица правильно построена и не переполнена, проверка принадлежности элемента множеству, а также вставка и удаление элемента выполняются в ней за постоянное время, примерно такое же, как и в массиве битов.