18

HashMap実装を検索した後、 http：//www.docjar.com/html/api/java/util/HashMap.java.htmlでこのコードを見つけました。

  264       static int hash(int h) {
  265           // This function ensures that hashCodes that differ only by
  266           // constant multiples at each bit position have a bounded
  267           // number of collisions (approximately 8 at default load factor).
  268           h ^= (h >>> 20) ^ (h >>> 12);
  269           return h ^ (h >>> 7) ^ (h >>> 4);
  270       }

誰かがこれに光を当てることができますか？コメントは、このコードがここにある理由を示していますが、これによって不正なハッシュ値がどのように改善され、位置が衝突の数を制限することを保証するのかを理解したいと思います。これらのマジックナンバーはどういう意味ですか？

4

1 に答える 1

22

それが意味をなすためには、HashMapがどのようにバケットに物事を割り当てるかを理解することと組み合わせる必要があります。これは、バケットインデックスを選択するための簡単な関数です。

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

つまり、デフォルトのテーブルサイズが16の場合、バケットの割り当てに実際に重要なのはハッシュの最下位4ビットだけであることがわかります。（16-1 = 15、これは1111bによってハッシュをマスクします）

hashCode関数が次を返した場合、これは明らかに悪いニュースになる可能性があります。

10101100110101010101111010111111

01111100010111011001111010111111

11000000010100000001111010111111
//etc etc etc

このようなハッシュ関数は、作成者に見える方法で「悪い」ものではない可能性があります。しかし、それをマップがバケット、ブーム、MapFail（tm）を割り当てる方法と組み合わせると。

hが32ビットの数値であることを覚えておいてください。これらは、マジックナンバーではありません。これは、数値の最上位ビットを最下位ビットに体系的にxorします。目的は、バイナリで表示したときに「全体」のどこかで発生する数の「違い」が最下位ビットで表示されるようにすることです。

バイナリ表現のどこかで発生する差異がバケット化に重要なビットに圧縮されるため、関連するLSBが同じである異なる数値の数が大幅に制限されるため、衝突が制限されます。

于 2011-10-27T20:50:46.140 に答える