3

重要なお知らせ：

これは、人々がハッシュについて意見を述べるためのディスカッション スレッドではありません。指定された関数をJavaで機能させる方法を知る必要があるだけです-例が最適です。

問題：

保留中のインタビューに向けてハッシュ関数の理解を深めるために、MIT コンピューター サイエンスの教授による 2 つの無料講義 (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 = 32Javaを使用しているため、設定に行き詰まっていますか?

4

4 に答える 4

4

Javaはとにかくこの動作を想定しているため、一部の用語は冗長です。

A·k mod 2^w

Javaでは、整数の乗算がオーバーフローするため、mod 2^w（符号付き）が実行されます。符号が付いているという事実は、少なくとも1ビットシフトしている場合は問題ではありません。

Shift of(w - r)は、Javaの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

また、2 ^（w-1）で必要なすべての値を保持するのに十分な大きさでintもありません。longで提供するのが最適BigIntegerです。

于 2012-05-02T15:17:52.193 に答える
1

実際の動作を見てみましょうnumber % 2^32: 2^32 による除算の余りを取得します。範囲が 0 から 2^32 の場合、2^32 を超えるものはすべて破棄されるため、コンピューターが自動的にモジュロを計算します。

32 の代わりに 8 を取り、2 進数システムに切り替えましょう。

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

したがって、何をすべきかは、数をコンピューターの範囲に制限することです。たとえば c++ を使用する場合、値を として宣言するのと同じくらい簡単unsigned intです。上記の 2 番目の例の 11番目は、変数に収まらないため単純に切り捨てられます。

Java では、符号なし整数はありません。を計算A * kしてオーバーフローが発生すると、符号付きの値が得られる場合があります。しかし、次にしなければならないことは右シフトを行うことだけなので、これは問題ではありません。

したがって、私の提案は、モジュロ計算を単純に削除することです。試してみてください。うまくいくかどうかはよくわかりません。

于 2012-05-02T15:25:44.213 に答える