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

Question

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

Answer 1

これは、負荷係数（テーブルがサイズを増やして要素を再配分する「満杯率」ポイント）に依存します。エントリが正確に1000であり、その数が決して変わらないことがわかっている場合は、負荷率を1.0に、初期サイズを1000に設定するだけで効率を最大化できます。正確なサイズがわからない場合は、負荷係数をデフォルトの0.75のままにして、初期サイズを1334（予想サイズ/ LF）に設定して、本当に良いパフォーマンスを得ることができます。余分なメモリ。

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

Hashtable(int initialCapacity, float loadFactor) 

Answer 2

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

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

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

どのようなものをハッシュしていますか？より詳細にすれば、より良いアドバイスが得られます。

Answer 3

これらの要因については、 ハッシュテーブル

Answer 4

成長させましょう。このサイズでは、自動処理は問題ありません。それ以外は、2 xサイズ+ 1は単純な式です。素数も少し良いですが、データセットが特定のサイズに達するとすぐに、ハッシュ実装はテーブルを再ハッシュして成長させることを決定するかもしれません。

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

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

Answer 5

2回は良いです。

大きなキーセットはありません。 HashTableの実装に関する難しい議論を気にせず、2000年に進みます。

Answer 6

https://stackoverflow.com/users/33229/wwwflickrcomphotosrene-germany上記。 1000は私にとって非常に大きなハッシュのようには見えません。私は、Javaでそのサイズについて多くのハッシュテーブルを使用してきましたが、パフォーマンスの問題についてはあまり気にしていませんでした。そして、私はサイズや負荷係数についてほとんど考えたことはありません。

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

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