找到你要的答案

Q:Implementing double hashing for integers that can be negative

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

计算h(k)后,如果没有碰撞,它将被插入到它的位置。如果有碰撞,我将计算(H(k)+ S(k))国防部和将存储在计算结果值的关键。

所以我的问题是,如果密钥是一个负整数,我应该采取绝对值(使其积极)之前散列吗?或者还有其他方法吗?

answer1: 回答1:

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

来自普林斯顿算法网站:

问:什么是错误的与使用(美国hashcode() % m)或数学。ABS(美国hashcode())% m哈希0 m-1之间的价值?

如果第一个参数为负值,则%运算符返回非正整数,这将创建一个数组索引越界错误。令人惊讶的是,绝对值函数甚至可以返回一个负整数。这一切发生的时候,如果它的参数是integer.min_value因为产生的正整数,不能使用一个32位的补码整数表示。这种错误是很困难的追踪因为它只会发生在40亿个时间![“polygenelubricants”是2 ^ 31字符串的哈希代码。]

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

 static int indexFor(int hashcode, int length) {
     return hashcode & (length-1);
 }
answer2: 回答2:

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.

假设你与功能1第一然后将导致功能2的结果会是一个正数的哈希。

在功能2

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

所以函数2返回一个正数值

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

然后(k mod(P - 2))& gt;0

所以函数2返回一个正数值

在任何一种情况下,无论输入是正数还是负值,双散列都会从函数2返回一个正数。

java  c++  hash  double-hashing