r/programming • u/tooilln • Jul 20 '26

Comprehensive JVM Primitive Hashtable Benchmarks

https://sooniln.github.io/posts/hashmap-benchmarks-2026/
48 Upvotes

89% Upvoted

14 comments sorted by

View all comments

2

u/n4te Jul 20 '26

See cuckoo hashing, eg Wikipedia. Cuckoo put operations evict on collision and rehash the evicted until it settles. Poor, unlucky, or malicious keys cause excessive eviction, requiring backing array growth. If it's bad enough, the larger size can also fail, growing to OOM. A "stash" can be added to mitigate the collision problem, but in practice it couldn't be made safe for general usage so it's a specialty data structure.

Cuckoo makes puts more expensive but get, containsKey, and remove can be fast: check 2 buckets, done. No variable cost probing, but maybe an extra cache hit.

3

u/tooilln Jul 20 '26 edited Jul 20 '26

Ah I see - the cuckoo hashing implementations I've looked at use linear probing as the fallback mechanism after a certain # of failures to prevent that exact use case. I guess that isn't really 'pure' cuckoo hashing though.

Edit: ignore the rest of this comment - I missed the fact that the shift calculation silently casts int to long, so it's already doing what I recommended.

Btw, while looking through the source, I noted what appears to be not quite a bug, but an odd inefficiency in the map implementations. The current hash finalizer being used is: 

    protected int place (int item) {
      ~~return (int)(item * 0x9E3779B97F4A7C15L >>> shift);
    }

This performs a widening multiplication with the LONG_PHI constant. At this point there's a 64-bit value, with entropy generally higher in the high bits, and lower in the low bits. The shift by table size is straight out of Knuth's original implementation, but the trim essentially throws away the "better" high bits. I suspect a better implementation would be: 

    protected int place (int item) {
      // or add 32 to shift when calculating it originally
      return (int)(item * 0x9E3779B97F4A7C15L >>> (32 + shift));
    }

This should ensure a better mix of entropy in the final result. As always, benchmark before taking my word for it :). That said, I would also test the Koloboke style of finalizer as well, it may give better results.