問題タブ [load-factor]

私は、実際には容量が10.000.000、負荷率が.75で構築され、いくつかの値をキャッシュするために使用される大規模な（数百万の）ハッシュマップを使用してJavaを起動しています。

キャッシュされた値は時間の経過とともに役に立たなくなります（もうアクセスされなくなります）が、パフォーマンスが低下し始めたときにキャッシュを完全に空にしたい途中で、役に立たない値を削除することはできません。いつそれをするのが良いかをどうやって決めることができますか？

たとえば、容量が1,000万で、0.75の場合、750万の要素に達したときに空にする必要がありますか？いろいろ試してみましたが、分析的なものが欲しいので。

完全にいっぱいになったときにそれをエンピングするとパフォーマンスが向上するという事実をすでにテストしました（ワイプ後の最初の2〜3回のアルゴリズムの反復は、それを埋め戻すだけで、ワイプ前よりも速く実行を開始します）

編集：追加情報

ハッシュマップには、キーとフロートが値として含まれています。これには、コンテンツのキャッシュされた相関関係が含まれています。これは、（パフォーマンスを向上させるために）キャッシュしたかったタグベクトルの内積であるためです。

つまり、基本的に私が行うことはlong、2つのコンテンツのハッシュコードを使用してキーを計算することです。

保存された値を取得するために使用します。階層的クラスタリングのコンテンツがマージされ、他のコンテンツとの相関値が不要になるため、ハッシュマップを時々ワイプして、内部の不要な値による劣化を回避したいと思います。

を使用するWeakHashMapと、データがまだ必要な場合でも、予期せずにデータが消去されます。私はそれを制御できません。

ありがとう

私のハッシュテーブルの実装には、負荷が約70％に達したときにテーブルのサイズを変更する機能があります。私のハッシュテーブルは、衝突のために別々のチェーンで実装されています。

ハッシュテーブルのサイズをいつでも変更する必要があるのは理にかなっていますか、それともそのままにしておく必要がありますか？それ以外の場合、負荷が70％のときにサイズを大きくすると（ほぼ2倍、実際には次のようになります：リンク）、負荷が30％以下になったときにサイズを小さくする必要がありますか？

現在、私のハッシュテーブルは、ハッシュテーブルに挿入されたすべての要素の数を数えています。このカウントとハッシュ テーブルの合計サイズを使用して負荷率を計算し、70% 程度に達したら再ハッシュします。

挿入された要素をすべてではなく、空のスロットを埋めるだけでカウントする必要があるのではないかと考えていました。私が使用している衝突方法は、個別の連鎖です。要素の負荷は増加し続けますが、いくつかの衝突が発生する可能性がある場合は、ハッシュ テーブルに多くの空のスロットが残ります。

あなたはおそらく、これほど多くの衝突が発生した場合、最適なハッシュ方法を使用していないのではないかと考えているでしょう。しかし、それはポイントではありません。私は既知のハッシュ アルゴリズムの 1 つを使用しています。サンプル データで 3 つのアルゴリズムをテストし、衝突が少ないアルゴリズムを選択しました。

私の疑問はまだ残っています。挿入されたすべての要素を数え続けるべきですか、それともハッシュ テーブルの空のスロットを埋める要素だけを数えるべきですか?

私が使用しているオープンアドレッシング配列の実装でハッシュテーブルの負荷率を計算するとき：

ただし、削除されたエントリは（空のスペースと区別するために）そのようにマークする必要があるため、キーの数にこれらを含めることが理にかなっている場合があります。

私の考えでは、エントリを見つけるためのプローブの平均数を見積もる場合、削除されたエントリは負荷率にカウントされますが、新しいキーを挿入する場合はカウントされません。

適切な計算はどれですか：削除されたキーを含めるかどうか？

13 個のアイテムを格納できることがわかっているハッシュ テーブルがある場合、テーブルを適切なサイズに初期化するにはどうすればよいですか? 負荷率は 2/3 以下である必要があると本で読みました。これは、任意の時点でテーブル内のアイテムの最大数が 13 になることが既にわかっている場合、次のようなことができるということですか。

上記の割り当てに関する私の考えでは、numEntries は数値 13 を表し、負荷率が 2/3 未満でなければならないことがわかっているので、比率を 2/3 にするために必要な値を見つけます。

HashMapには と の 2 つの重要なプロパティがsizeありload factorます。Javaのドキュメントを調べたところ0.75f、初期負荷係数であると書かれています。しかし、私はそれの実際の使用を見つけることができません。

負荷率を設定する必要があるさまざまなシナリオと、さまざまなケースでの理想的な値の例を誰かが説明できますか?

私の理解と私が読んだことによると

負荷率は、容量が自動的に増加する前に、ハッシュ テーブルがどれだけいっぱいになることができるかの尺度です。

したがって、loadfactor が .8(80%) の場合、マップ サイズが 10Mapの場合、8 つの要素が に配置されると、サイズが 10 だけ大きくなりMapます。

したがって、Mapサイズは 20 になりました。私の疑問は、次の 10 要素スペースが にいつ追加されるかMapです。

• が再び 80% 埋まったときMap、つまり 16 個の要素が に入れられたときMapです。

また

• 18枚のエレメントを入れた場合Map。