FNV Hash Map - Ducktape’s blog

submited by

Style Pass

2025-01-20 21:30:16

This article was partially written by Claude Sonnet 3.5. All of the below was an attempt by me to understanding how hashtables work better, and FNV was the function I chose since I use it often without understanding why it is fast.

:warning: I’m not a C programmer, I just want to get better at it. I found bugs in Claude’s implementation, and I’m sure there’s more I didn’t find. All code below includes my bugfixes, and what I found is cataloged at the end.

All of this is because of a build-it-from-scratch kick with C that I’ve been on, re-inventing a lot of wheels to see how they work. See the use case for this hashmap here.

When we do a bitwise AND (&) with any number and (capacity-1), we’re essentially taking the remainder of that number when divided by capacity. But we’re doing it much faster than using the modulo operator (%).

This would lead to uneven distribution of indices because some bits in our mask would be 0, meaning those positions in our hash value wouldn’t contribute to the final index.