java - ハッシュに適したテーブルサイズの選択

Question

キーセットが1000の場合、ハッシュテーブルに適したサイズはどれくらいですか。それはどのように決定されますか？

Answer 1

これは、負荷係数 (テーブルのサイズが大きくなり、要素が再分散される "% フル" ポイント) に依存します。正確に 1000 のエントリがあり、その数が決して変わらないことがわかっている場合は、負荷係数を 1.0 に設定し、初期サイズを 1000 に設定して最大の効率を得ることができます。正確なサイズがわからない場合は、負荷係数をデフォルトの 0.75 のままにして、初期サイズを 1334 (予想サイズ/LF) に設定すると、非常に優れたパフォーマンスを得ることができますが、余分なメモリが必要になります。

次のコンストラクターを使用して、負荷係数を設定できます。

Hashtable(int initialCapacity, float loadFactor) 

Answer 2

ハッシュ関数も考慮する必要があります。

1 つの経験則では、テーブル サイズを約 2 倍にして拡張の余地を残し、できれば衝突の数を少なくすることをお勧めします。

もう 1 つの経験則は、何らかのモジュロ関連のハッシングを行っていると仮定し、次にテーブル サイズを次に大きい素数に丸め、その素数をモジュロ値として使用することです。

どのようなものをハッシュしていますか? より詳細にすると、より良いアドバイスが生成されるはずです。

Answer 3

これらの要因については、次のドキュメントで説明されています。Hashtable

Answer 4

成長させましょう。このサイズなら自動ハンドリングもバッチリ。それ以外は、2 x サイズ + 1 という単純な計算式です。素数も良いですが、データ セットが特定のサイズに達するとすぐに、ハッシュの実装が再ハッシュしてテーブルを拡大することを決定する可能性があります。

あなたのキーは有効性を促進しており、うまくいけば十分に明確です。

結論: サイズやパフォーマンスの低下などの問題がある場合は、サイズに関する質問をしてください。それ以外の場合: 心配しないでください!

Answer 5

https://stackoverflow.com/users/33229/wwwflickrcomphotosrene-germanyが上で言ったことを繰り返したいと思います。1000は私にはそれほど大きなハッシュのようには思えません。私は、パフォーマンスの問題をあまり見ずに、Javaでそのサイズのハッシュテーブルをたくさん使用してきました。そして、私はサイズや負荷率をいじくり回すことはほとんどありません。

コードでプロファイラーを実行し、ハッシュテーブルが問題であると判断した場合は、必ず微調整を開始してください。そうでなければ、私はあなたが確信するまであなたが問題を抱えているとは思いません。

結局のところ、ほとんどのコードでは、パフォーマンスの問題はあなたが思っているところにはありません。予想しないようにしています。

Answer 6

2回でいいです。

あなたは大きなキーセットを持っていません。HashTable の実装に関する難しい議論は気にせず、2000 に進んでください。