У меня есть хеш-таблица, в которой подавляющее большинство обращений во время выполнения выполняется по одному из следующих шаблонов:
- Итерация по всем парам ключ / значение.(Скорость этой операции имеет решающее значение.)
- Изменить ключи (т.е. удалить пару ключ / значение и добавить другую с тем же значением, но другим ключом. Определить дубликаты ключей и объединить значения, если необходимо.) Этовыполняется в цикле, затрагивая многие тысячи ключей, но не вмешиваясь в другие операции.
Я также хотел бы, чтобы он занимал как можно меньше памяти.
Другие стандартные операции должныбыть доступными, хотя они используются реже, например
- Вставить новую пару ключ / значение
- По заданному ключу найдите соответствующее значение
- Изменитезначение, связанное с существующим ключом
Конечно, все «стандартные» реализации хеш-таблиц, включая стандартные библиотеки большинства языков высокого уровня, имеют все эти возможности.Я ищу реализацию, оптимизированную для операций из первого списка.
Проблемы с распространенными реализациями:
- В большинстве реализаций хеш-таблиц используютсяотдельная цепочка (т. е. связанный список для каждого сегмента). Это работает, но я надеюсь на то, что занимает меньше памяти с лучшей локализацией ссылок.Примечание: мои ключи маленькие (по 13 байт, дополняются до 16 байт).
- Большинство открытых схем адресации имеют серьезный недостаток для моего приложения: ключи удаляются и заменяются большими группами.Это оставляет маркеры удаления, которые увеличивают коэффициент загрузки, что требует частой перестройки таблицы.
Схемы, которые работают, но не идеальны:
- Отдельное сцепление с массивом (вместо связанного списка) для каждой корзины:
Плохая локальность ссылок, возникающая из-за фрагментации памяти, поскольку небольшие массивы перераспределяются много раз - Линейное зондирование / квадратичное хеширование /двойное хеширование (с изменением Брента или без него):
Таблица быстро заполняется маркерами удаления - Хеширование кукушки
Работает только при <50% коэффициенте загрузки, и я хочу, чтобы высокий LF сохранял память иускорить итерацию. </li>
Существует ли специальная схема хеширования, которая будет хорошо работать в этом случае?
Примечание: у меня есть хорошая хеш-функция, которая хорошо работает как с мощностью-of-2 и простые таблицы размеров, и могут использоваться для двойного хеширования, поэтому это не должно быть проблемой.