什么整数哈希函数好接受一个整数哈希键？(What integer hash function are good that accepts an integer hash key?)

什么整数哈希函数好接受一个整数哈希键？(What integer hash function are good that accepts an integer hash key?)

什么整数哈希函数好接受一个整数哈希键？

What integer hash function are good that accepts an integer hash key?

最满意答案

Knuth的乘法方法：

hash(i)=i*2654435761 mod 2^32

一般来说，你应该选择一个乘数大小的顺序（在本例中为2^32 ），并且没有共同的因素。 这样一来，散列函数就会统一覆盖所有的哈希空间。

编辑：这个哈希函数的最大的缺点是它保留了可分割性，所以如果你的整数都可以被2或4整除（这并不罕见），他们的哈希也是。 这是哈希表中的一个问题 - 您最终只能使用1/2或1/4的存储桶。

Knuth's multiplicative method:

hash(i)=i*2654435761 mod 2^32

In general, you should pick a multiplier that is in the order of your hash size (2^32 in the example) and has no common factors with it. This way the hash function covers all your hash space uniformly.

Edit: The biggest disadvantage of this hash function is that it preserves divisibility, so if your integers are all divisible by 2 or by 4 (which is not uncommon), their hashes will be too. This is a problem in hash tables - you can end up with only 1/2 or 1/4 of the buckets being used.