31

多くの書籍やチュートリアルでは、すべてのバケットにキーを均等に分散するには、ハッシュ テーブルのサイズが素数でなければならないと述べています。しかし、JavaHashMapは常に 2 の累乗のサイズを使用します。素数を使用するべきではありませんか？ハッシュテーブルのサイズとして、「素数」と「2 の累乗」のどちらが優れていますか?

4

5 に答える 5

29

2 のべき乗を使用すると、ハッシュ コードの上位ビットが効果的にマスクされます。したがって、このシナリオでは、品質の低いハッシュ関数のパフォーマンスが特に低下する可能性があります。

Javaは、オブジェクトの実装を信用せず、その結果に第 2 レベルのハッシュを適用することで、HashMapこれを緩和します。hashCode()

指定された hashCode に補助ハッシュ関数を適用し、低品質のハッシュ関数から防御します。HashMap は 2 の累乗の長さのハッシュ テーブルを使用するため、これは重要です。そうしないと、下位ビットが変わらない hashCode の衝突が発生します。

優れたハッシュ関数がある場合、またはハッシュ関数に似たものHashMapを使用している場合、素数などをテーブル サイズとして使用するかどうかは問題ではありません。

一方、ハッシュ関数が不明または品質が低い場合は、素数を使用する方が安全です。ただし、サイズに定数を掛けるだけでなく、突然素数を生成できるようにする必要があるため、動的にサイズ変更されたテーブルの実装は難しくなります。

于 2013-03-15T16:23:41.650 に答える
6

標準の HashMap 実装には、hashオブジェクトのハッシュコードを再ハッシュしてその落とし穴を回避するメソッドがあります。メソッドの前のhash()コメントは次のとおりです。

/**
 * Retrieve object hash code and applies a supplemental hash function to the
 * result hash, 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.
 */
于 2013-03-15T16:24:43.690 に答える
5

素数と 2 のべき乗のどちらが優れているかを知る唯一の方法は、それをベンチマークすることです。

何年も前に、パフォーマンスがシンボル talbe ルックアップに大きく依存するアセンブラを作成したとき、生成された識別子の大きなブロックを使用してこれをテストしました。単純なマッピングを使用しても、2 のべき乗は、予想どおり、同様のサイズの素数のバケットよりも分散が少なく、チェーンが長いことがわかりました。ビットマスキングによるバケット選択の速度により、それでも高速に実行されました。

java.util の開発者は、素数のバケットを使用することに対するベンチマークを行わずに、余分なハッシュと 2 のべき乗に頼らなかったのではないかと強く思います。ハッシュ化されたデータ構造を設計するとき、これは非常に明白なことです。

そのため、再ハッシュと 2 の累乗のサイズは、素数のバケットよりも典型的な Java ハッシュ マップのパフォーマンスが優れていると確信しています。

于 2013-03-15T16:36:30.757 に答える
1

パフォーマンス/計算の観点から、2の累乗のサイズは、ビットマスキングだけで計算できます。これは、そうでない場合に必要となる整数除算よりも高速です。

于 2013-03-15T16:27:47.247 に答える
0

衝突の解決に2 次プロービングを使用する場合は、素数サイズのハッシュ テーブルを使用する必要があります。素数サイズのテーブルがある場合、二次プロービングはエントリの半分にヒットし、素数でない場合はそれ以下になります。そのため、ハッシュ テーブルが半分以下であっても、エントリを保存する適切な場所が見つからない可能性があります。Java ハッシュ マップは 2 次プロービングを使用しないため、素数をサイズとして使用する必要はありません。

于 2014-04-08T14:41:22.847 に答える