4 ms·

Integer Hash Function (1997)

53 points by antirez 13y ago

antirez 13y ago
This is an hash functions classic that was apparently "lost". Recovered by github/badboy from archive.org and reformatted into a Gist.
zvrba 13y ago
Relevant theory, also not particularly new: http://en.wikipedia.org/wiki/Universal_hashing http://en.wikipedia.org/wiki/Universal_hashing Thorup: Even strongly universal hashing is pretty fast ([PDF] http://www.diku.dk/hjemmesider/ansatte/henglein/papers/thorup2000.pdf http://www.diku.dk/hjemmesider/ansatte/henglein/papers/thoru...) And another: [PDF] http://www.daimi.au.dk/~bromille/Notes/un.pdf http://www.daimi.au.dk/~bromille/Notes/un.pdf
Patient0 13y ago
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.
- nightcracker 13y ago
  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.
  - mtdewcmu 13y ago
    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.
- tibbe 13y ago
  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.
opless 13y ago
Where's xxHash? https://code.google.com/p/xxhash/ https://code.google.com/p/xxhash/
- adestefan 13y ago
  It looks like xxHash was crated in 2012. This document was lasted updated in 2007.
majke 13y ago
Good read to get a historical context. On the other hand in new code I'd most likely use SipHash: https://131002.net/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 http://www.ocert.org/advisories/ocert-2011-003.html
- aktau 13y ago
  Thanks for that! I myself always had MurmurHash (https://code.google.com/p/smhasher/wiki/MurmurHash3 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.
  - packetslave 13y ago
    There's also CityHash, which has some nice claimed performance numbers depending on your application. https://code.google.com/p/cityhash/ https://code.google.com/p/cityhash/ http://www.stanford.edu/class/ee380/Abstracts/121017-slides.pdf http://www.stanford.edu/class/ee380/Abstracts/121017-slides....
deleted 13y ago
[deleted]
picomancer 13y ago
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 http://en.wikipedia.org/wiki/Xorshift
tripzilch 13y ago
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).
- vicaya 13y ago
  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.
mtdewcmu 13y ago
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.

53 points by antirez 13y ago

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

zvrba 13y ago

Relevant theory, also not particularly new: http://en.wikipedia.org/wiki/Universal_hashing http://en.wikipedia.org/wiki/Universal_hashing Thorup: Even strongly universal hashing is pretty fast ([PDF] http://www.diku.dk/hjemmesider/ansatte/henglein/papers/thorup2000.pdf http://www.diku.dk/hjemmesider/ansatte/henglein/papers/thoru...) And another: [PDF] http://www.daimi.au.dk/~bromille/Notes/un.pdf http://www.daimi.au.dk/~bromille/Notes/un.pdf

Patient0 13y ago

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.

nightcracker 13y ago
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.
- mtdewcmu 13y ago
  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.
tibbe 13y ago
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.

opless 13y ago

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

adestefan 13y ago
It looks like xxHash was crated in 2012. This document was lasted updated in 2007.

majke 13y ago

Good read to get a historical context. On the other hand in new code I'd most likely use SipHash: https://131002.net/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 http://www.ocert.org/advisories/ocert-2011-003.html

aktau 13y ago
Thanks for that! I myself always had MurmurHash (https://code.google.com/p/smhasher/wiki/MurmurHash3 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.
- packetslave 13y ago
  There's also CityHash, which has some nice claimed performance numbers depending on your application. https://code.google.com/p/cityhash/ https://code.google.com/p/cityhash/ http://www.stanford.edu/class/ee380/Abstracts/121017-slides.pdf http://www.stanford.edu/class/ee380/Abstracts/121017-slides....

deleted 13y ago

[deleted]

picomancer 13y ago

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 http://en.wikipedia.org/wiki/Xorshift

tripzilch 13y ago

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).

vicaya 13y ago
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.

mtdewcmu 13y ago

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.