-1

http://en.wikipedia.org/wiki/Hash_table

私はwikiを見ていましたが、テーブルインデックスを見つける手順は次のとおりです。

hash = hashfunc(key) // calculate hash value.
index = hash % array_size // calculate index value through modulus.

しかし、Java での実行方法はかなり異なるようです。

static int hash(int h) {
   h ^= (h >>> 20) ^ (h >>> 12);
   return h ^ (h >>> 7) ^ (h >>> 4);
}

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

テーブルのインデックスを計算するindexForメソッドが違うようです。誰でもこれに光を加えることができますか？

アップデート：

ハッシュアルゴリズムはそれに応じて異なる場合がありますが、テーブルインデックスを計算する方法は、私が間違っていなくても正しいはずですが、Wiki の機能と Java の機能に競合が見られます。

テストするサンプル コード:

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class Test {

    public static void main(String args[]) {
        Map<String, String> m = new HashMap<String, String>();
        m.put("Shane", null);
        Iterator<String> itr = m.keySet().iterator();
        while (itr.hasNext()) {
            String key = itr.next();
            int hash = hash(key.hashCode());
            System.out.println("&&& used" + "table[" + (hash & 15) + "]=" + key);
            System.out.println("%%% used" + "table[" + (hash % 15) + "]=" + key);
        }
    }

    static int hash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }   

}

出力：

&&& usedtable[14]=Shane
%%% usedtable[8]=Shane

上記のプログラムを実行すると、% を使用するとテーブル インデックスが異なり、& を使用するとテーブル インデックスが異なることがわかります。

4

1 に答える 1

3

しかし、Java での実行方法はかなり異なるようです。

実際、それらはまったく同じです。

hash = hashfunc(key) // calculate hash value.

と同じです

hash = hash(key.hashCode());

と

index = hash % array_size       (assumes the hash is unsigned)

と同じです

return h & (length-1);

長さは 2 の累乗なので。

于 2013-09-26T15:32:54.907 に答える