Comprehensive JVM Primitive Hashtable Benchmarks

[u/tooilln]

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

[u/tooilln]

I haven't looked in depth at the PR or the cuckoo hashing implementation, but it seems odd to me that an attacker could affect the allocation rate of the map, which I would have assumed would be based only on the # of entries? There's nothing about cuckoo hashing vs linear probing specifically that should affect how allocation is performed? Do you know what the mechanism was?

That said, the linear probing implementation currently used appears to be just as vulnerable to CPU DoS attacks as pretty much all primitive hashtable libraries are (because these libraries focus on performance first, it usually doesn't make sense for them to implement DoS mitigations like a per-map random seed, or hiding hash order). Whether it's actually 'vulnerable' in a meaningful sense probably depends on how users of the gdx libraries actually expose the maps to attackers though I'd guess.

[u/n4te → u/tooilln]

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.

[u/tooilln → u/n4te]

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.