Integer Hash Function (1997) | Hacker News Reader

Integer Hash Function (1997)

gist.github.com

53 pointsantirez15 comments

Good read to get a historical context. On the other hand in new code I'd most likely use SipHash: https://131002.net/siphash/

Siphash is simple, pretty fast, versatile and can be used in a way not vulnerable to hash collisions denial of service attacks (aka: hash flooding): http://www.ocert.org/advisories/ocert-2011-003.html

Thanks for that! I myself always had MurmurHash (https://code.google.com/p/smhasher/wiki/MurmurHash3) in mind, mainly because I liked the touted benefits (from the possibly biased main page) and it's worked out for me. Seems like I need to educate myself a bit more.

There's also CityHash, which has some nice claimed performance numbers depending on your application.

https://code.google.com/p/cityhash/ http://www.stanford.edu/class/ee380/Abstracts/121017-slides....

This article contains errors.

"Using multiplication requires a mechanism to transport changes from high bit positions to low bit positions. Bit reversal is best, but is slow to implement. A viable alternative is left shifts."

Left shifts transport bits from low to high, no?

Less trivially, the discussion of reversibility appears to be incorrect and irrelevant. The property that every key has a unique hash is too strong for a general purpose hash function. For a general purpose hash function, the space of hashes is assumed to be much smaller than the space of keys, so a 1:1 mapping is unattainable. The goal instead is to decorrelate collisions from the input key distribution, even when the key distribution isn't known in advance. The hashes should resemble random numbers, even when the set of inputs is highly skewed (which is almost always the case). Collisions should occur about as often as if the hashes had actually been random numbers. The random-appearing distribution of outputs, regardless of input distribution, is the property that defines a good general purpose hash.

This is an hash functions classic that was apparently "lost". Recovered by github/badboy from archive.org and reformatted into a Gist.

Relevant theory, also not particularly new:

http://en.wikipedia.org/wiki/Universal_hashing

Thorup: Even strongly universal hashing is pretty fast ([PDF] http://www.diku.dk/hjemmesider/ansatte/henglein/papers/thoru...)

And another: [PDF] http://www.daimi.au.dk/~bromille/Notes/un.pdf

It always pains me when I see people use cryptographic hashes (such as MD5 or SHA) in situations where they just need a hash with good mixing and avalanche behaviour.

Cryptographic hashes may perform to good quality, but they are a zillion times slower. And obviously they are not guaranteed to be reversible.

Elsewhere in this discussion are some good links to fast, non-cryptographic hashing functions (very cool, I hadn't heard about SipHash before).

SipHash is a cryptographic hash function (more accurate a MAC). It's designed like one and behaves like one. SipHash is significant in that it demonstrates that there is no reason to use a non-cryptographic hashing function for general purpose hashing these days.

Talking about the best way to construct a hash function without having any concept of the distribution of the things that it is hashing seems wrong.

I don't understand how this article does not give any consideration to the distribution of the input integer. After all, if the input key is uniformly distributed, or is already unique, then you could just use the identity function as your hash function.

I figured the same, but then I realized the use. Even if your input key is unique, it does not mean that every bit is uniformly distributed. For example a counter has zero upper bits with high propability. By ensuring that the mapping is uniform you can take any number of bits from the result (say the first 16 bits for a hash table with 65536 entires) and retain uniformity.

It attaches great importance to having a 1:1 mapping from keys to hashes. If that is critical, then presumably the intent must not be to shorten the hash, because once you've shortened the hash, the 1:1 mapping is lost.

Having a hash function that gives a 1:1 mapping for short keys could be considered a positive feature, all else being equal, but in reality, all else would not be equal, because this property doesn't naturally go along with the things that make a good hash function generally. It would certainly come at a cost, and it serves little purpose. It makes no sense to me, and I think the author must have been making it up as he went.

We tried this hash function for a while as the standard hash function for `Int`s in Haskell and real world performance was worse than when using the identity function. I'd like the author to back up the statement that the better distribution actually helps on real examples.

I have a favorable impression of Marsaglia's Xorshift / Xorwow. Not least because it's a linear operator over GF(2) and thus, properties about its behavior, such as the period or bijectivity, can be determined analytically.

If you're using it for a hash function, I'd advise several repititions for good mixing. Hmm, maybe I'll write a blog post about that...

[1] http://en.wikipedia.org/wiki/Xorshift

Where's xxHash? https://code.google.com/p/xxhash/

It looks like xxHash was crated in 2012.

This document was lasted updated in 2007.

Reply on news.ycombinator.com