Тебе точно стоит хранить всё в одном сплошном блоке памяти, чтобы кэш не прыгал туда-сюда. Используй открытую хеш-таблицу с размером, кратным степени двойки, и быстрый, простой хеш, например, Murmur или FNV. Сделай ключ и значение фиксированного размера, чтобы сразу индексировать массив. Выдели всю таблицу сразу и никогда не перераспределяй и не перехешируй — это поможет предсказателю ветвлений. Храни ключи и значения в плотно упакованных структурах, избегай указателей внутри них; так ты сможешь пройтись по таблице простым циклом, а процессор автоматически будет подгружать следующий слот. Используй небольшой, фиксированный размер ячейки и поддерживай низкий коэффициент заполнения, скажем, 0.5 – тогда попадание в ячейку будет быстрым. И наконец, помести всё состояние в одну структуру и держи ее в кэше L1. С одним потоком ты сможешь избежать атомарных операций и добиться времени поиска менее миллисекунды.

Да, пересчет хешей – тот еще геморрой, особенно если приходится менять размер. Хороший трюк – использовать двухступенчатую хеш-таблицу: основную таблицу, которая не меняет размер, и небольшую таблицу переполнения, которую перестраиваешь только когда она заполняется. Так избежишь полной перестройки каждый раз. Двойное хеширование – отличный вариант; вторую хеш-функцию можно вывести из первой с небольшим нечетным множителем, чтобы она работала быстро. А для выравнивания просто добей ключ до 64 байта, чтобы каждый ключ попадал в отдельную строку кэша, или используй структуру с атрибутом __attribute__((aligned(64))), если твой компилятор это поддерживает. Это должно свести штраф за промахи к минимуму.

Тридцать два байта – вполне приемлемый компромисс. Просто выравнивай структуру на 32 байта, чтобы она помещалась в одну кеш-линию, без потерь. Для переполнения можно использовать небольшой кольцевой буфер LRU – он ограничит размер без значительных накладных расходов. Или просто добавить метку времени к каждой записи и периодически удалять самые старые, когда достигнешь определённого лимита. Так ты и вторую таблицу маленькой удержишь, и цели по времени меньше миллисекунды достигнешь.