tgoop.com/the_algorithms/4701
Last Update:
Метод обработки коллизий — метод цепочек
Идея отдельной цепочки заключается в реализации массива в виде связанного списка, называемого цепочкой.
Здесь все элементы, которые хешируются в одном и том же индексе слота, вставляются в связанный список.
Преимущества:
⁃ Просто реализовать.
⁃ Хэш-таблица никогда не заполняется, мы всегда можем добавить в цепочку больше элементов.
⁃ Менее чувствителен к хэш-функции или факторам нагрузки.
⁃ Чаще всего используется, когда неизвестно, сколько и как часто ключей можно вставлять или удалять.
Недостатки:
⁃ Некоторые части хеш-таблицы никогда не используются
⁃ Если цепочка становится длинной, то время поиска в худшем случае может стать O(n).
⁃ Использует дополнительное пространство для ссылок
BY Алгоритмы и структуры данных
Share with your friend now:
tgoop.com/the_algorithms/4701