Статья Википедии о хеш-таблицах дает отчетливо лучшее объяснение и обзор различных схем хеш-таблиц, которые использовали люди, чем я могу выразить все мои мысли. На самом деле, вам, вероятно, лучше прочитать эту статью, чем задавать вопрос здесь. :)
Тем не менее ...
Связанная хеш-таблица индексирует в массив указателей на заголовки связанных списков. Каждая ячейка связанного списка имеет ключ, для которого она была выделена, и значение, которое было вставлено для этого ключа. Когда вы хотите найти конкретный элемент по его ключу, хеш ключа используется для определения того, за каким связанным списком следовать, а затем этот конкретный список просматривается, чтобы найти нужный элемент. Если более чем один ключ в хеш-таблице имеет один и тот же хеш, то у вас будут связанные списки с более чем одним элементом.
Недостатком цепочечного хеширования является необходимость следовать указателям для поиска связанных списков. Положительным моментом является то, что связанные хэш-таблицы становятся линейно медленнее, когда увеличивается коэффициент загрузки (отношение элементов в хэш-таблице к длине массива сегментов), даже если он поднимается выше 1.
Хеш-таблица с открытой адресацией индексирует в массив указателей на пары (ключ, значение). Вы используете хеш-значение ключа, чтобы определить, какой слот в массиве смотреть в первую очередь. Если более чем один ключ в хеш-таблице имеет один и тот же хеш, тогда вы используете какую-то схему для выбора другого слота для поиска. Например, линейное зондирование - это то, где вы смотрите на следующий слот после выбранного, а затем на следующий слот после этого и так далее, пока вы либо не найдете слот, соответствующий ключу, который вы ищете, либо не нажмете пустой слот (в этом случае ключ не должен быть там).
Открытая адресация обычно быстрее цепного хеширования при низком коэффициенте загрузки, поскольку вам не нужно следовать указателям между узлами списка. Он становится очень, очень медленным, если коэффициент загрузки приближается к 1, потому что вам обычно приходится искать во многих слотах в массиве сегментов, прежде чем вы найдете либо искомый ключ, либо пустой слот. Кроме того, в хеш-таблице никогда не может быть больше элементов, чем записей в массиве сегментов.
Чтобы справиться с тем фактом, что все хеш-таблицы, по крайней мере, становятся медленнее (а в некоторых случаях фактически полностью ломаются), когда их коэффициент загрузки приближается к 1, практические реализации хеш-таблиц увеличивают массив сегментов (путем выделения нового массива сегментов и копирование элементов из старого в новый, а затем освобождение старого), когда коэффициент загрузки становится выше определенного значения (обычно около 0,7).
Существует множество вариантов всего вышеперечисленного. Снова, пожалуйста, смотрите статью в Википедии, это действительно неплохо.
Для библиотеки, которая предназначена для использования другими людьми, я бы настоятельно рекомендовал поэкспериментировать. Поскольку они, как правило, очень важны для производительности, лучше всего использовать чью-то реализацию хеш-таблицы, которая уже была тщательно настроена. Существует множество реализаций лицензированных хеш-таблиц с открытым исходным кодом BSD, LGPL и GPL.
Если вы работаете, например, с GTK, то обнаружите, что в GLib .
есть хорошая
хеш-таблица.