# Q：实现双散列的整数可以是负的

I am implementing a hash class for integers using the double hashing method. The input will be random integers that can be either positive or negative.

My question is how will I compute the hash value of negative integers?

This is the method:

``````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
``````

After computing h(k), if there is no collision, it will be inserted in its position. If there is collision, I will compute (h(k) + s(k)) mod p and will store the key in the resulting value of the computation.

So my question is if the key is a negative integer, should I take its absolute value (make it positive) before hashing it? Or is there any other method?

``````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
``````

From the 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 computes an index from a hashcode as follows:

`````` static int indexFor(int hashcode, int length) {
return hashcode & (length-1);
}
``````

java计算指数从一个hashCode如下：

`````` static int indexFor(int hashcode, int length) {
return hashcode & (length-1);
}
``````

Assuming you hash with funtion 1 first and then place result in function 2 the result will allways be a positive number.

In function 2

``````If k > 0 => 0 < (k mod (p - 2)) < p - 2
``````

So function 2 returns a positive value

``````If k < 0 => (k mod (p - 2)) < 0
``````

Then -(k mod (p - 2)) > 0

So function 2 returns a positive value

In either case the double hashing will return a positive value from function 2 no matter if the input is positive or negative.

``````If k > 0 => 0 < (k mod (p - 2)) < p - 2
``````

``````If k < 0 => (k mod (p - 2)) < 0
``````

java  c++  hash  double-hashing