Как они работают? В чем их основные отличия? Каковы их соответствующие компромиссы? Каковы их типы (если есть)? Когда одно предпочтительнее другого (если вообще)?
PS: я уже прошел через Anagrams - хэширование с цепочкой и зондированием в C и Почему мы используем линейное зондирование в хеш-таблицах, когда есть отдельная цепочка, связанная со списками?, но ни один из них, похоже, не проводит контраста между двумя методами.
Цепочка и открытая адресация (простая реализация которых основана на линейном зондировании) используются в хеш-таблицах для разрешения коллизий. Коллизия происходит всякий раз, когда хэш-функция для двух разных ключей указывает на одно и то же место для хранения значения.
Чтобы сохранить оба значения с разными ключами, которые должны были бы храниться в одном и том же месте, цепочка и открытая адресация используют разные подходы: в то время как цепочка разрешает конфликт, создавая связанный список значений с одним и тем же хешем; открытая адресация пытается найти другое место для хранения значений с тем же хешем.
Интересной альтернативой линейному зондированию для разрешения конфликтов с открытой адресацией является так называемое двойное хеширование.
Основное отличие, которое возникает, заключается в скорости получения хэшируемого значения при разных условиях.
Начнем с цепочки в качестве разрешения конфликтов. Обратите внимание, что после вычисления хэш-функции для Лизы вам нужно получить первый элемент из списка, чтобы получить требуемое значение. Поэтому вы получаете доступ к указателю на начало списка, а затем к значению: 2 операции.
С другой стороны, при открытой адресации, такой как линейное зондирование, когда нет коллизии, вы немедленно получаете искомое значение. То есть вам требуется всего 1 операция, что быстрее.
Однако, когда ваша HashTable начинает заполняться, и у вас высокая загрузка фактор, из-за того, что коллизии случаются чаще, вам потребуется проверить больше местоположений Hashtable, прежде чем вы найдете действительное значение, которое вам нужно. Примерно при коэффициенте загрузки 0,8 цепочка начинает становиться более эффективной из-за множественных столкновений: вам придется исследовать множество пустых ячеек, чтобы найти фактическое значение, которое вы хотите с помощью проверки, в то время как с цепочкой у вас есть список значений которые имеют один и тот же хеш-ключ.
Это всего лишь краткий обзор, так как фактические данные, распределение ключей, используемая хэш-функция и точная реализация разрешения столкновений будут иметь значение для вашей фактической скорости.
how do they work?: D, спасибо за указание.
- person th3an0maly; 10.04.2016
