0

私はJavaでHashMapの実装を書いています。衝突解決にはオープンアドレス法を使用しています。より良いキー配布のために、キーのハッシュコードに素晴らしいハッシュ関数を使用したいと思いintます。どのハッシュ関数がそれに適しているのかわかりませんか？

public int getIndex(K key) { return hash(key.hashCode()) % capacity; }

キーのハッシュコード用のハッシュ関数が必要です。

4

2 に答える 2

3

受け取ることを期待している値を均等に分散するハッシュは、優れたハッシュ関数です。

あなたの目標は、パフォーマンスを最大化することです（まあ、正確さを維持しながらパフォーマンスを最大化する）。そこにある主な関心事は、バケットの衝突を最小限に抑えることです。これは、理想的なハッシュが入力データに合わせて調整されていることを意味します。受け取るものがわかっている場合は、衝突の数を最小限に抑え、キャッシュに最適なアクセスパターンを生成するハッシュを選択できます。

ただし、これは通常現実的なオプションではないため、出力が偏りがなく予測できないハッシュを選択するだけです（疑似乱数ジェネレーターのように動作しますが、決定論的です）。そのような関数のいくつかは「つぶやき」ハッシュファミリーです。

于 2012-02-04T07:07:24.947 に答える
1

を使用する際の主な問題% capacityは、負の値と正の値を返す可能性があることです。

HashMapは、2の累乗を使用してこの問題を回避し、次のアプローチを使用します

 public int getIndex(K key) { return hash(key.hashCode()) & (capacity-1); }

容量が2の累乗でない場合は、上位ビットを無視できます（これは多くの場合それほどランダムではありません）

 public int getIndex(K key) { return (hash(key.hashCode()) & 0x7FFFFFFF) % capacity; }

実際に使用されるハッシュ関数は重要です。HashMapは以下を使用します

/**
 * 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.
 */
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);
}

あなたがそうしない正当な理由がない限り、私はこれを使います。たとえば、セキュリティ上の理由から、サービス拒否攻撃の対象となる可能性のあるサービスがある場合は、悪意のあるユーザーがHashMapをLinkedListに変えないように、別のハッシュを使用することをお勧めします。残念ながら、別のhashCode（）を使用する必要があります。また、基になるハッシュコードを使用して文字列の長いリストを作成できるため、後で変更するのは遅すぎます。

これは、すべてが0のhashCode（）を持つ文字列のリストです。hash（）関数がそれについてできることは何もありません。

StringのhashCode（）が0をキャッシュしないのはなぜですか？

于 2012-02-04T09:22:15.443 に答える