Хэш-таблица оптимизирована для полной итерации + замена ключа

У меня есть хеш-таблица, где подавляющее большинство обращений во время выполнения следуют одному из следующих шаблонов:

  • Итерации через все пары ключ/значение. (Скорость этой операции критическая.)
  • Изменить ключи (например, удалить пару ключ/значение и добавить другую с тем же значением, но с другим ключом. Обнаружение дублирующих клавиш и объединение значений, если это необходимо.) Это делается в цикле, затрагивающем многие тысячи ключей, но с никаких других операций не происходит.

Я также хотел бы, чтобы он потреблял как можно меньше памяти.

Другие стандартные операции должны быть доступны, хотя они используются реже, например.

  • Вставить новую пару ключ/значение
  • С учетом ключа найдите соответствующее значение
  • Измените значение, связанное с существующим ключом

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

Проблемы с общими реализациями:

  • В большинстве реализаций хэш-таблицы используется отдельная цепочка (т.е. связанный список для каждого ведра.) Это работает, но я надеюсь на то, что занимает меньше памяти с лучшей локалью ссылки. Примечание. Мои ключи маленькие (по 13 байт, с 16 байтами).
  • Большинство открытых схем адресации имеют большой недостаток для моего приложения: ключи удаляются и заменяются большими группами. Это оставляет маркеры удаления, которые увеличивают коэффициент загрузки, требуя, чтобы таблица была повторно построена часто.

Схемы, которые работают, но не идеальны:

  • Отдельная цепочка с массивом (вместо связанного списка) на ведро:
    Плохая локальность ссылок, возникающая из-за фрагментации памяти, поскольку небольшие массивы перераспределяются много раз.
  • Линейное зондирование/квадратичное хеширование/двойное хеширование (с или без вариации Brent):
    Таблица быстро заполняется марками удаления.
  • Хеширование кукушки
    Работает только с коэффициентом загрузки менее 50%, и я хочу, чтобы LF сохранял память и ускорял итерацию.

Существует ли специализированная схема хэширования, которая бы хорошо работала для этого случая?


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

Ответы

Ответ 1

Была ли Extendable Hashing help? Итерация по клавишам с помощью "каталога" должна быть быстрой. Не уверен, что операция "изменить ключ для значения" лучше с этой схемой или нет.

Ответ 2

На основе того, как вы обращаетесь к данным, действительно ли имеет смысл использовать хеш-таблицу вообще?

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

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

Ответ 3

Вы можете сделать намного лучше, чем коэффициент загрузки 50% с хешированием кукушки.

Две хеш-функции с четырьмя элементами помогут вам получить более 90% усилий. См. Этот документ:

http://www.ru.is/faculty/ulfar/CuckooHash.pdf

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