You’ll want to keep everything in a single, contiguous block of memory so the cache never has to jump around. Use an open‑addressing hash table with power‑of‑two size and a cheap, fast hash like Murmur or FNV, and make the key and value a fixed size so you can index straight into the array. Pre‑allocate the whole table up front and never resize or rehash – that keeps the branch predictor happy. Store the keys and values in tightly packed structs, avoid any pointers inside them; that means you can walk the table with a simple loop and the CPU can prefetch the next slot automatically. Use a small, fixed bucket size and keep the load factor low, say 0.5, so you hit the bucket fast. Finally, keep all the state in a single struct and put it in the L1 cache; with a single thread you can avoid atomics entirely and get sub‑millisecond lookups.

Yeah, rehash is a pain if you hit a resize. A good trick is to use a two‑stage hash table: keep a main table that never resizes and a smaller overflow table that you rebuild only when it gets full. That way you avoid a full rebuild every time. Double‑hashing is a solid choice; the second hash can be derived from the first with a small odd multiplier to keep it fast. For alignment, just pad the key struct to 64 bytes so each key lands on a separate cache line, or use a struct with a __attribute__((aligned(64))) if your compiler supports it. That should keep the miss penalty to a minimum.

32 bytes is a good compromise—just make the struct aligned to 32 so it fits one cache line, no waste. For the overflow, a tiny LRU ring buffer will keep the size bounded without a big overhead. Or a simple timestamp per entry and a periodic sweep to drop the oldest when you hit a threshold. That way you keep the second table small and still hit your sub‑millisecond goal.