December 9, 2025
Cache me outside
My favourite small hash table
Tiny table, huge drama: mystery author and the simple-is-faster fight
TLDR: A developer shows off a tiny, fast key-value table using a fairness trick called “Robin Hood.” Commenters split between praising simple, cache-friendly design, questioning the 64-bit packing choice, and arguing you could just make a massive list instead—plus a fun side quest to unmask the anonymous author.
A cute little hash table just lit up nerd internet, and the comments are the real show. The author proposes a compact, cache-friendly design using a “Robin Hood” strategy—think: a super-fast list where items try to stay close to their ideal spot and will swap to keep things fair. It’s all about speed and simplicity, and the crowd is loudly into it… and also ready to bicker. One camp cheers the minimalist approach: as artur44 puts it, simple layouts often win because they fit in the CPU’s speedy memory. Another camp wants receipts: judofyr questions why the key and value are crammed into one 64-bit number instead of a tiny two-number container—calling out potential over-optimization. Aardwolf crashes the party with the nuclear take: with the 32 GB cap, you could just make a giant list indexed by the key and call it a day—then trolls the premise by asking for text strings to make it interesting. Meanwhile, the vibe check? clbrmbr wants to unmask the author, calling them a “kindred soul” and asking, “Who beeth this mysterious writer?” Bonus spice: ww520’s subtle warning that “random” keys can still collide. It’s a mix of performance worship, practical nitpicking, and a dash of meme-worthy mystery, with a side of Robin Hood hashing lore.
Key Points
- •Design uses Robin Hood open addressing with linear probing and a power-of-two table size.
- •Assumes 32-bit random keys and 32-bit values; table size capped at 32 GiB; key 0’s value is non-zero if present.
- •Each slot is a 64-bit integer: low 32 bits key, high 32 bits value; zero indicates an empty slot, no tombstones needed.
- •Indexing uses K & mask (mask = length - 1); the score function Score(Index, Key) = (Index - Key) & mask enforces the Robin Hood property.
- •Lookup stops when the key is found, an empty slot is encountered, or a slot with a smaller score than the current key’s score appears; returns 64-bit result with value in low 32 bits if found.