c - ハッシュテーブルのサイズを小さくするのは理にかなっていますか？そしていつ？

Question

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

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

Answer 1

高品質のハッシュ関数がある場合、ハッシュ テーブルは素数の長さである必要はありません (こちらを参照)。それらを 2 の累乗にすることができ、これによりインデックスの計算が大幅に高速化されます。

なぜこれが質問に関連するのですか？2 のべき乗ハッシュテーブルを縮小すると、下半分のすべてのエントリをそのままにして、スロットのリンク リストをi(上半分から)スロットのリンク リストに単純に追加できるためi - n/2です。

Answer 2

メモリが安い場合は、そのままにしておきます。メモリが高価な場合は、提案したようにヒステリシスでサイズを変更してください。完了したら、結果をプロファイリングして、パフォーマンスが良好で、ばかげたことをしていないことを確認します。

Answer 3

汎用のハッシュテーブルを作成していますか、それとも特定の目的がありますか？一般的な実装では、サイズを小さくしないことをお勧めします。これにより、テーブルがシンプルに保たれ、テーブルが頻繁にいっぱいになり、空になる状況でメモリがスラッシングするのを防ぐことができます。ハッシュテーブルのサイズを縮小する必要がある状況に陥った場合は、その時点でハッシュテーブルを拡張してください。

Answer 4

最初のアイデア: ハッシュテーブルを大きくする唯一の理由は、衝突が多すぎるとハッシュテーブルのパフォーマンスが低下するためです。負荷が 70% を超えたときにテーブルを拡張することは、これを防ぐための経験則としては適切ですが、経験則にすぎません。衝突の数を追跡し、特定の制限を超えた場合、または特定の衝突率に達した場合にのみハッシュテーブルを拡張することをお勧めします。結局のところ、90% の負荷がかかっているにも関わらず衝突が 1 回も発生していないハッシュテーブルを拡張する必要があるのはなぜでしょうか? それは何の利点もありません。

2 番目のアイデア: ハッシュテーブルを縮小する唯一の理由はメモリを節約することですが、縮小すると衝突の数が増え、ルックアップのパフォーマンスが低下する可能性があります。これは従来の速度とメモリのトレードオフであり、なぜ自分で解決する必要があるのでしょうか? あなたのコードを使用している人に任せてください。自分で縮小するのではなく、縮小方法を提供してください。メモリ使用量を少なくする必要がある場合は、コードを使用している人は誰でも、定期的に縮みを呼び出すことができます。必要に応じて最大のパフォーマンスが得られる場合、コードを使用している人は誰でも決して縮んではいけません。他の誰もが何らかのヒューリスティックを使用して、shrink を呼び出すかどうか、いつ呼び出すかを決定できます。

3 番目のアイデア: 拡大または縮小するときは、操作後に一定の負荷率が保証されるように常に拡大/縮小します。たとえば、成長するときは、その後の負荷率が 50% になるように常に成長し、縮小するときは、その後の負荷率が 70% になるように常に縮小します。もちろん、それは衝突の数については何も言っていないので、拡大/縮小の直後に要素を追加すると、ハッシュテーブルが再び拡大する可能性がありますが、拡大/縮小の効果をシミュレートするには通常コストがかかりすぎるため、これは避けられません。また、それ以上の変更が予定されていない場合、shrink が呼び出されることがよくあります。そのため、将来再び拡張する必要がないようにするよりも、むしろメモリを節約する必要があります。

最後のアイデア: 決定を下すたびに、ハッシュテーブルを一部のユース ケースでは改善し、他のユース ケースでは悪化させます。ハッシュテーブルがどのように使用されるかを知っていれば、これは問題になりません。しかし、そうでない場合、通常はそうでない場合、なぜこれらの決定を自分で行うのでしょうか? それらを委任するだけです。ハッシュテーブルの作成時にこれらすべての要素を設定できるようにするか、ハッシュテーブルにデリゲート関数 (コールバック関数が何をすべきかわからない場合はいつでも尋ねることができます）。そうすれば、コードのすべてのユーザーは、必要な使用シナリオに合わせて実行時でもコードをカスタマイズできます。