2

容量が倍数または 2 でなければならないのはなぜですか? indexFor 関数で「&」を使用する理由 キーのハッシュ コードを直接使用するのではなく、ハッシュ関数でハッシュを再計算するのはなぜですか?

この実装と「アルゴリズム入門」の説明との間には、いくつかの重要な違いがあると思います。

>>> とはどういう意味ですか?

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

誰かガイドを教えてもらえますか？誰かがハッシュアルゴリズムを説明できれば幸いです。どうもありがとう！

4

2 に答える 2

5

これはパフォーマンスの最適化です。ハッシュ コードをテーブル インデックスにマップする通常の方法は次のとおりです。

table_index = hash_code % table_length;

%オペレーターは高価です。が 2 の累乗の場合table_length、計算は次のとおりです。

table_index = hash_code & (table_length - 1);

（はるかに）高価な剰余演算と同等です。

于 2012-04-03T21:34:28.023 に答える
0

カーテンの後ろの男に注意を払わないでください。

実際のアルゴリズムは、間違いなく、開発者にとって「心地よいもの」、いくつかの奇妙な退化したケースの修正、および単純な伝統 (ユーザーがあいまいな依存関係を開発することが多い) の組み合わせです。

そしてこれに注意してください：

 * Applies a supplemental hash function to a given hashCode, which
 * defends against poor quality hash functions.  This is critical
 * because HashMap uses power-of-two length hash tables, that
 * otherwise encounter collisions for hashCodes that do not differ
 * in lower bits. Note: Null keys always map to hash 0, thus index 0.

Net: 機能し、パフォーマンスが良好である限り、気にする必要はありません。

于 2012-04-03T21:46:02.647 に答える