Отдельная цепь Хеширование для избежания столкновений Hash

Question

Мои знания о хэш-таблицах ограничены, и я в настоящее время их изучаю. У меня вопрос о разрешении столкновения Хэша открытым хэшированием или отдельным хешированием цепей.

Я понимаю, что хэш-ведра в этом случае содержат указатель на связанный список, в котором все элементы, которые отображаются в один и тот же ключ, связаны. поэтому сложность поиска будет в порядке o (n), где n - количество элементов в связанном списке. Есть ли способ сделать это проще?

Кроме того, если существует ограничение на размер связанного списка, можно сказать, что он может содержать только 5 элементов max и, если более 5 элементов хеша в одном и том же ведре, что было бы лучшим способом справиться с этим сценарием?

Любые указатели для получения дополнительной информации о вышеуказанных и любой помощи будут очень признательны.

Answer 1

Конфликты хеширования не должны быть слишком распространенными, иначе вы делаете что-то неправильно (например, плохая хеш-функция или не достаточно большая хеш-таблица). Поэтому количество элементов в каждом связанном списке должно быть минимальным, а сложность O (n) не должна быть слишком плохой.

Вы могли бы теоретически заменить его одной из многих других структур данных. Например, двоичное дерево поиска будет получать время поиска O (log n) (при условии, что элементы сопоставимы), но тогда время вставки будет до O (log n) вместо O (1), и потребуется больше пространство.

Максимальное количество элементов в списке не должно превышать. Если бы это было возможно, вы могли бы, вероятно, прибегнуть к зондированию (например, к линейному зондированию), но удаление могло бы стать кошмаром, так как вам может понадобиться немного перемещать элементы.