Целью этой библиотеки является реализация неупорядоченных контейнеров в проекте стандарта, поэтому интерфейс был исправлен. Но есть еще некоторые решения по реализации. Приоритеты соответствуют стандарту и портативности.
СтатьяВикипедии о хеш-таблицахсодержит хорошее резюме вопросов реализации хеш-таблицы в целом.
Указывая интерфейс для доступа к ведрам контейнера, стандарт в значительной степени требует, чтобы хеш-таблица использовала цепную адресацию.
Можно было бы написать хеш-таблицу, которая использует другой метод. Например, он может использовать открытую адресацию и использовать цепочку поиска в качестве ведра, но с этим есть некоторые серьезные проблемы:
- Проект стандарта требует, чтобы указатели на элементы не были недействительными, поэтому элементы не могут быть сохранены в одном массиве, но вместо этого потребуется слой непрямого действия - потеря эффективности и большая часть прироста памяти, основные преимущества открытой адресации.
- Локальные итераторы будут очень неэффективными и могут не соответствовать требованиям сложности.
- Существуют также ограничения на то, когда итераторы могут быть признаны недействительными. Поскольку открытая адресация сильно ухудшается, когда происходит большое количество столкновений, ограничения могут предотвратить повторение, когда это действительно необходимо. Максимальный коэффициент нагрузки может быть установлен на довольно низкое значение, но стандарт требует, чтобы он изначально был установлен на 1,0.
- И поскольку стандарт написан с прицелом на цепную адресацию, пользователи будут удивлены, если производительность не отражает этого.
Таким образом, используется цепная адресация.
Существует два популярных метода выбора количества ведер в хеш-таблице. Один должен иметь простое число ведер, другой - использовать мощность 2.
Использование простого числа ведер и выбор ведра с использованием модуля результата хеш-функции обычно дает хороший результат. Недостатком является то, что требуемый модуль достаточно дорогой. Именно это делают контейнеры в большинстве случаев.
Использование мощности 2 позволяет гораздо быстрее выбирать ведро для использования, но за счет потери верхних бит хеш-значения. Для некоторых специально разработанных хеш-функций это можно сделать и получить хороший результат, но поскольку контейнеры могут принимать произвольные хеш-функции, на это нельзя полагаться.
Чтобы избежать этого, преобразование может быть применено к хеш-функции, например, см.Статья Томаса Ванга о целочисленных хеш-функциях. К сожалению, такая трансформация, как у Ванга, требует знания количества битов в хеш-значении, поэтому она недостаточно портативна для использования по умолчанию. Он может применяться в определенных случаях, поэтому контейнеры имеют реализацию на основе политики, которая может использовать этот альтернативный метод.
В настоящее время это делается только на 64-битных архитекурах, где модуль простого числа может быть дорогим. Хотя это зависит от архитектуры, я, вероятно, должен пересмотреть его.
Я также думаю о внедрении механизма, посредством которого хеш-функция может указывать на то, что она безопасна для использования непосредственно с мощностью 2 ведра, и в этом случае может использоваться более быстрая простая мощность 2 реализации.
