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