3

2の累乗の長さのハッシュテーブル（初期容量とサイズ変更のたび）を使用しない独自のハッシュマップを実装するかどうか疑問に思っています。その場合、オブジェクトのハッシュコードを使用して合計サイズを直接変更できますか？ハッシュ関数を使用してオブジェクトのハッシュコードをハッシュする代わりに？

例えば

   public V put(K key, V value) {
         if (key == null)
             return putForNullKey(value);
         // int hash = hash(key.hashCode());     original way
         //can we just use the key's hashcode if our table length is not power-of-two ?
         int hash = key.hashCode();              
         int i = indexFor(hash, table.length);
         ...
         ...
     }
4

3 に答える 3

3

OpenJDK 7 について話していると仮定すると、追加hashは雪崩を刺激するために使用されます。ミキシング機能です。これが使用されるのは、容量に 2 のべき乗を使用していたため、ハッシュからバケットへのマッピング関数が単なるビット単位であるためです&( is はiffが 2 のべき乗であるため)。これは、下位ビットのみが重要であることを意味するため、この混合ステップを適用することで、より貧弱なハッシュから保護することができます。a % ba & (b - 1)b

 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);
 }

2 の累乗ではないサイズを使用する場合は、上記は必要ない場合があります。

実際にマッピングをハッシュからバケットに変更するには (通常、容量が 2 のべき乗であることに依存します)、以下を確認する必要がありますindexFor。

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

ここで使用でき(h & 0x7fffffff) % lengthます。

于 2012-08-08T15:37:43.053 に答える
1

mod関数は単純な形式のハッシュ関数と考えることができます。広範囲のデータをより小さなスペースにマッピングします。元のハッシュコードが適切に設計されていると仮定すると、modを使用してハッシュコードを使用しているテーブルのサイズに変換できない理由はわかりません。

元のハッシュ関数が適切に実装されていない場合、たとえば常に偶数を返す場合は、ハッシュ関数としてmod関数だけを使用して非常に多くの衝突が発生します。

于 2012-08-08T15:36:48.450 に答える
1

これは本当です、代わりに擬素数を選ぶことができます。

注：indexForは、ルックアップを実際に遅くする可能性%のある単純なものではなく、符号の補正を使用する必要があります。&

indexFor = (h & Integer.MAX_VALUE) % length
// or
indexFor = Math.abs(h % length)
于 2012-08-08T15:37:18.123 に答える