Ответ 1
Была ли Extendable Hashing help? Итерация по клавишам с помощью "каталога" должна быть быстрой. Не уверен, что операция "изменить ключ для значения" лучше с этой схемой или нет.
Хэш-таблица оптимизирована для полной итерации + замена ключа
У меня есть хеш-таблица, где подавляющее большинство обращений во время выполнения следуют одному из следующих шаблонов:
- Итерации через все пары ключ/значение. (Скорость этой операции критическая.)
- Изменить ключи (например, удалить пару ключ/значение и добавить другую с тем же значением, но с другим ключом. Обнаружение дублирующих клавиш и объединение значений, если это необходимо.) Это делается в цикле, затрагивающем многие тысячи ключей, но с никаких других операций не происходит.
Я также хотел бы, чтобы он потреблял как можно меньше памяти.
Другие стандартные операции должны быть доступны, хотя они используются реже, например.
- Вставить новую пару ключ/значение
- С учетом ключа найдите соответствующее значение
- Измените значение, связанное с существующим ключом
Конечно, все "стандартные" хэш-таблицы, включая стандартные библиотеки большинства языков высокого уровня, обладают всеми этими возможностями. Я ищу реализацию, оптимизированную для операций в первом списке.
Проблемы с общими реализациями:
- В большинстве реализаций хэш-таблицы используется отдельная цепочка (т.е. связанный список для каждого ведра.) Это работает, но я надеюсь на то, что занимает меньше памяти с лучшей локалью ссылки. Примечание. Мои ключи маленькие (по 13 байт, с 16 байтами).
- Большинство открытых схем адресации имеют большой недостаток для моего приложения: ключи удаляются и заменяются большими группами. Это оставляет маркеры удаления, которые увеличивают коэффициент загрузки, требуя, чтобы таблица была повторно построена часто.
Схемы, которые работают, но не идеальны:
- Отдельная цепочка с массивом (вместо связанного списка) на ведро:
Плохая локальность ссылок, возникающая из-за фрагментации памяти, поскольку небольшие массивы перераспределяются много раз. - Линейное зондирование/квадратичное хеширование/двойное хеширование (с или без вариации Brent):
Таблица быстро заполняется марками удаления. - Хеширование кукушки
Работает только с коэффициентом загрузки менее 50%, и я хочу, чтобы LF сохранял память и ускорял итерацию.
Существует ли специализированная схема хэширования, которая бы хорошо работала для этого случая?
Примечание. У меня есть хорошая хеш-функция, которая хорошо работает как с параметрами power-of-2, так и с основными таблицами, и может использоваться для двойного хэширования, поэтому это не должно быть проблемой.
Ответы
Ответ 2
На основе того, как вы обращаетесь к данным, действительно ли имеет смысл использовать хеш-таблицу вообще?
Поскольку вы используете основные варианты использования, итерация - отсортированный список или btree может быть лучшей структурой данных.
Не похоже, что вам действительно нужен доступ к случайным данным по постоянному времени, для которого построена хеш-таблица.
Ответ 3
Вы можете сделать намного лучше, чем коэффициент загрузки 50% с хешированием кукушки.
Две хеш-функции с четырьмя элементами помогут вам получить более 90% усилий. См. Этот документ:
http://www.ru.is/faculty/ulfar/CuckooHash.pdf
Я создаю предварительно вычисленный словарь, используя хеш-кукушку и получая коэффициент загрузки более 99% с двумя хеш-функциями и семью элементами на каждый ковш.