3

重要的提醒：

这不是一个供人们向我发表他们对哈希的看法的讨论帖。我只需要知道如何使给定的函数在 java 中工作——最好有一个例子。

问题：

为了在即将到来的面试中磨练我对哈希函数的理解，我观看了麻省理工学院计算机科学教授的两场免费讲座 (http://videolectures.net/mit6046jf05_leiserson_lec08/)。所以讲座结束后，我尝试在java中实现以下哈希函数。

h(k) = (A·k mod 2^w) >> (w – r)
WHERE
r: m, the size of the array, is a power of 2 such that m=2^r
w: the computer has w-bit words, such as 32-bit or 64-bit computer
k: the value I am to find a key for
A: a random odd number (prime would be great) between 2^(w-1) and 2^w

我认为这在java中很容易实现。但是当我在 w=32 处执行 2^w 时，我在 Java 中得到不准确的结果。在现实生活中2^32 = 4294967296但不是在 java 中，它会将结果截断为2^31 - 1or 2147483647。

有谁知道如何解决这个问题以便在 Java 中实现该功能？

编辑：

我看到很多回复都集中在 32 上。如果我的电脑是 64 位的怎么办？w = 32因为我使用的是 Java ，所以我被设置困住了？

4

4 回答 4

4

有些术语是多余的，因为 Java 无论如何都假定了这种行为。

A·k mod 2^w

在 Java 中，整数乘法会溢出，因此会进行 mod 2^w（带符号）。如果您随后移动至少一位，它有符号的事实并不重要。

Shift of与 Java(w - r)中的 shift of 相同-r（类型隐含 w）

private static final int K_PRIME = (int) 2999999929L;

public static int hash(int a, int r) {
   // return (a * K_PRIME % (2^32)) >>> (32 - r);
   return (a * K_PRIME) >>> -r;
}

对于 64 位

private static final long K_PRIME = new BigInteger("9876534021204356789").longValue();

public static long hash(long a, int r) {
    // return (a * K_PRIME % (2^64)) >>> (64 - r);
    return (a * K_PRIME) >>> -r;
}

我写了这个例子来说明你可以在 BigInteger 中做同样的事情，以及为什么你不这样做。;)

public static final BigInteger BI_K_PRIME = new BigInteger("9876534021204356789");
private static long K_PRIME = BI_K_PRIME.longValue();

public static long hash(long a, int r) {
    // return (a * K_PRIME % (2^64)) >>> (64 - r);
    return (a * K_PRIME) >>> -r;
}

public static long biHash(long a, int r) {
    return BigInteger.valueOf(a).multiply(BI_K_PRIME).mod(BigInteger.valueOf(2).pow(64)).shiftRight(64 - r).longValue();
}

public static void main(String... args) {
    Random rand = new Random();
    for (int i = 0; i < 10000; i++) {
        long a = rand.nextLong();
        for (int r = 1; r < 64; r++) {
            long h1 = hash(a, r);
            long h2 = biHash(a, r);
            if (h1 != h2)
                throw new AssertionError("Expected " + h2 + " but got " + h1);
        }
    }

    int runs = 1000000;
    long start1 = System.nanoTime();
    for (int i = 0; i < runs; i++)
        hash(i, i & 63);
    long time1 = System.nanoTime() - start1;

    long start2 = System.nanoTime();
    for (int i = 0; i < runs; i++)
        biHash(i, i & 63);
    long time2 = System.nanoTime() - start2;
    System.out.printf("hash with long took an average of %,d ns, " +
            "hash with BigInteger took an average of %,d ns%n",
            time1 / runs, time2 / runs);
}

印刷

hash with long took an average of 3 ns, \
    hash with BigInteger took an average of 905 ns
于 2012-05-02T15:56:06.837 回答
2

也int不会long足够大以容纳您在 2^(w-1) 中需要的所有值。你最好配上BigInteger.

于 2012-05-02T15:17:52.193 回答
1

让我们看看number % 2^32实际做了什么：它得到除以 2^32 的余数。如果你有一个从 0 到 2^32 的范围，计算机会自动为你做模，因为它会丢弃 2^32 以上的所有内容。

让我们取 8 而不是 32，并切换到二进制数系统：

  1000 1000 % 1 0000 0000 = 1000 1000
1 1000 1000 % 1 0000 0000 = 1000 1000

所以你应该做的是将数量限制在计算机的范围内。如果你会使用例如 c++，它就像将值声明为一样简单unsigned int。上面第二个示例中的第一个1将被截断，因为它不适合变量。

在java中，你没有无符号整数。如果您计算A * k并导致溢出，您可能会得到一个有符号值。但是，由于您接下来要做的唯一事情就是进行右移，因此这无关紧要。

所以我的建议是简单地放弃模计算。试试吧，我不太确定它是否有效。

于 2012-05-02T15:25:44.213 回答
0

Java原语int的最小值为 -2,147,483,648，最大值为 2,147,483,647

查看此链接以获取有关原语的详细信息。

我建议使用 along而不是int.

于 2012-05-02T15:15:09.857 回答