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