CODEWITHSUNDEEP
javac++hashdouble-hashing
ah786
ah786

Reputation: 71

Implementing double hashing for integers that can be negative

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?

Upvotes: 1

Views: 1914

Answers (2)

faerubin
faerubin

Reputation: 187

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);
 }

Upvotes: 3

Henrik Ståhlberg
Henrik Ståhlberg

Reputation: 318

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.

Upvotes: 0

Related Questions