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

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

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

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

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

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

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

Проблемы с распространенными реализациями:

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

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

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

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

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