4 ms·
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 un
by 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 agoI 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 agoIt 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 agoWe 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.