我正在使用双重哈希方法为整数实现一个哈希类。输入将是随机整数，可以是正数也可以是负数。
我的问题是如何计算负整数的哈希值？
这是方法:
hash function 1 h: h(k) = k mod (p)
hash function 2 s(k)= p –2 – (k mod(p-2))
p = table size, k = key
计算完h(k)后，如果没有碰撞，就插到它的位置上。如果发生冲突，我将计算 (h(k) + s(k)) mod p 并将 key 存储在计算结果值中。
所以我的问题是如果 key 是一个负整数，我应该在散列之前取它的绝对值(使其为正值)吗？或者还有其他方法吗？
最佳答案
来自Princeton Algorithms website :
Q: What's wrong with using (s.hashCode() % M) or Math.abs(s.hashCode()) % M to hash to a value between 0 and M-1?
A: The % operator returns a non-positive integer if its first argument is negative, and this would create an array index out-of-bounds error. Surprisingly, the absolute value function can even return a negative integer. This happens if its argument is Integer.MIN_VALUE because the resulting positive integer cannot be represented using a 32-bit two's complement integer. This kind of bug would be excruciatingly difficult to track down because it would only occur one time in 4 billion! [ The String hash code of "polygenelubricants" is -2^31. ]
Java 从哈希码 as follows 计算索引:
static int indexFor(int hashcode, int length) {
return hashcode & (length-1);
}
关于java - 为可能为负的整数实现双重哈希，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30018125/