Цепочечные хеш-таблицы по сравнению с открыто обращенными хеш-таблицами

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

При этом ...

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

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

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

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

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

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

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

Если вы, например, работаете с GTK, то обнаружите, что в GLib есть хорошая хэш-таблица .