skeeto / hash-prospector

Automated integer hash function discovery
The Unlicense
672 stars 27 forks source link

[Q] One round 32 bit hash? #20

Open OneKnightOnly opened 2 years ago

OneKnightOnly commented 2 years ago

Curious as to how well a one round 32 bit hash could perform, probably not great, but I can think of a few uses for it, like folding multiple coordinates into a single integer before using a more robust finalizer like the triple32.

stravager commented 1 year ago

For that I believe you want a https://en.wikipedia.org/wiki/Pairing_function Also see https://www.vertexfragment.com/ramblings/cantor-szudzik-pairing-functions/

tommyettinger commented 1 year ago

For a case where I had many 2D points in a known finite area, I tried changing the hash code for one point (I call this a point hash because there's a fixed number of inputs of a specific size and a smaller total size output, unlike a same-to-same size bijective unary hash or a variable-to-fixed size algorithm like wyhash or XXHash) between various algorithms. I tried Java's simplistic default using 31 all the way to a much more complex hash that was similar in structure to a generation of a xoroshiro generator. When I switched to a very simple, very fast Cantor pairing function, and used it without change as the hash, I got significant speedups as long as the load factor was no higher than 0.5. I still can't fully explain this, but it must have something to do with each pairing being unique as long as neither x nor y is too large. I only noticed this as a significant speedup in this particular case, on a particular (open addressing, linear probing) hash table, so take it with a large block of salt, but there are cases where everything comes together for a point hash, and many more cases where every point hash you try is about the same.