Связанные таблицы Hash и таблицы Hash с открытым адресом

Ответ 1

Статья в Википедии о хеш-таблицах дает значительно лучшее объяснение и обзор различных схем хеш-таблиц, которые люди использовали, чем я могу изо всех сил. На самом деле, вам, вероятно, лучше прочитать эту статью, чем задавать вопрос здесь. :)

Это сказал...

Связанная хеш-таблица индексирует в массив указателей на заголовки связанных списков. Каждая ячейка связанного списка имеет ключ, для которого она была выделена, и значение, которое было вставлено для этого ключа. Когда вы хотите найти конкретный элемент по его ключу, ключевой хеш используется для определения того, за каким связанным списком следовать, а затем этот конкретный список просматривается, чтобы найти нужный элемент. Если более чем один ключ в хеш-таблице имеет один и тот же хеш, то у вас будут связанные списки с более чем одним элементом.

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

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

Открытая адресация обычно быстрее, чем цепное хеширование, когда коэффициент загрузки низкий, потому что вам не нужно следовать указателям между узлами списка. Он становится очень, очень медленным, если коэффициент загрузки приближается к 1, потому что вам обычно приходится искать во многих слотах в массиве сегментов, прежде чем вы найдете либо искомый ключ, либо пустой слот. Кроме того, вы никогда не можете иметь больше элементов в хеш-таблице, чем есть записи в массиве сегментов.

Чтобы справиться с тем фактом, что все хеш-таблицы по крайней мере становятся медленнее (а в некоторых случаях фактически полностью ломаются), когда их коэффициент загрузки приближается к 1, практические реализации хеш-таблиц увеличивают массив сегментов (выделяя новый массив сегментов и копируя элементы из старый в новый, затем освобождая старый), когда коэффициент загрузки становится выше определенного значения (обычно около 0,7).

Есть много вариантов всего вышеперечисленного. Снова, пожалуйста, смотрите статью в Википедии, это действительно неплохо.

Для библиотеки, которая предназначена для использования другими людьми, я настоятельно рекомендую экспериментировать. Поскольку они, как правило, очень важны для производительности, лучше всего использовать чью-то реализацию хеш-таблицы, которая уже была тщательно настроена. Существует множество реализаций лицензированных хеш-таблиц с открытым исходным кодом BSD, LGPL и GPL.

Например, если вы работаете с GTK, то в GLib есть хорошая хеш-таблица.

Ответ 2

Поскольку дается отличное объяснение, я просто добавлю визуализации, взятые из CLRS, для дальнейшей иллюстрации:

Открытая адресация:

Сцепление:

Ответ 3

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

Цепочный метод:

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

Открытая адресация с помощью линейного зонда:

Здесь, когда возникает столкновение, переходите к следующему индексу, пока мы не найдем открытое пятно. Итак, если число столкновений низкое, это очень быстро и эффективно. Ограничение здесь - общее количество записей в таблице ограничено размером массива. Это не относится к цепочке.

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

Ответ 4

Открытая адресация или отдельная цепочка

Линейное зондирование, двойное и случайное хеширование целесообразно, если ключи хранятся в виде записей в самой хеш-таблице... выполнение этого называется "открытой адресацией", это также называется "закрытым хешированием"

Другая идея: записи в хеш-таблице являются просто указателями на заголовок связанного списка ("цепочка"); элементы связанного списка содержат ключи... это называется "отдельное сцепление", оно также называется "открытое хеширование"

Разрешение коллизий становится проще благодаря отдельной цепочке: просто вставьте ключ в его связанный список, если он еще не существует (для этого можно использовать более сложные структуры данных, чем связанные списки; но связанные списки работают очень хорошо в среднем случае, так как мы посмотрим) Давайте посмотрим на анализ затрат времени этих стратегий

Источник: http://cseweb.ucsd.edu/~kube/cls/100/Lectures/lec16/lec16-25.html

Ответ 5

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

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

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

В случае сомнений используйте прикованные хэш-таблицы. Добавление большего количества данных, чем вы ожидали, не приведет к замедлению работы сканера.