Perfect hashing hits 1.3ns lookups, ~12x faster than std::unordered_map
arpit_bhayani · x · 2026-10-29
A write-up on a C++ header-only perfect hashing library for compile-time-known key sets (HTTP methods, header names, compiler keywords, ticker symbols). At compile time it builds a hash function tailored to the exact keys, so each known key maps to a unique slot: it uses string length plus a few selected characters via a small association table (4 instructions), then verifies with a single 16-byte SIMD comparison instead of a byte loop.
Result: 1.3ns per lookup (about 5 cycles) vs 16.6ns for std::unorderedmap on the same machine. Caveats: fixed key sets only, and trivial comparisons may win for tiny key sets — but for extremely hot lookup paths, trading generality for speed can pay off.
More from Research
- Can homomorphic encryption make private LLM personalization practical? — burkov · 2026-10-29
- UIST 2026 Best Paper Honorable Mention: Attribution Gradients Unfolds AI Citations Step by Step — lucy3_li · 2026-10-29
- In-context learning lifts LLM music valence prediction from R² 0.11 to 0.43 — affige_yang · 2026-10-29
- Hexels: JHU's Hexagonal Primitives Cut VRAM 5.5x While Beating 3DGS by 4.96dB — ssh4net · 2026-10-29
- 3,957-task study finds no reliable way to combine human and AI oversight yet — sethlazar · 2026-10-29
- New preprint measures 'articulation gaps': how much knowledge in humans and AI is tacit — sanmikoyejo · 2026-10-29