負荷率のみに基づいてハッシュテーブルのサイズを動的に調整するのはなぜですか？一様分布ハッシュ戦略で衝突が検出されるたびにテーブルサイズを幾何学的に増やすことを選択した場合、考えられる影響はありますか？
1 に答える
0
負荷率は、ハッシュ関数が適切であると仮定した場合の衝突の確率とほぼ同じであるため、2 つのアイデアはそれほど離れていません。
負荷係数は、計算が簡単で、統計的にノイズが少ないため、実際の衝突で使用されます。
追加の理由は、テーブル内のすべての要素をトラバースするコストです。空のバケットはまだチェックする必要があるため、負荷係数のブラケットは、格納されているすべての要素を列挙する最悪のパフォーマンスのブラケットでもあります。
衝突パターンの自然なノイズは、それらを使用してテーブル サイズを調整するときに問題になります。私たちは、あなたが提案したポリシーに正確に従うことを決して望んでいません. 負荷率が 25% の場合でも、挿入ごとに確率 1/4 で、次に再び確率 1/(4G) で、テーブルを幾何学的に (係数 G>1 で) 拡大します。テーブルを縮小するタイミング 確かに、衝突がないたびにではありません!
したがって、実際には、衝突と挿入を「ウィンドウ」でカウントし、比率が高いしきい値と低いしきい値を超えたときに調整する必要があります。適切な確率でノイズを除去するには、ウィンドウをかなり大きくする必要があります。維持するには、ストレージとコンピューティングのオーバーヘッドが必要です。少なくとも、ほとんどの場合に使用される小さなテーブルでは、これはおそらく価値がありません。
それでも、テーブルが大きく、多くの操作があるデータベースのような設定では、パフォーマンスを最適化するために実際の統計が使用されます。実際のソフトウェアでこの最適化にハッシュ テーブルのサイズが含まれているかどうかはわかりませんが、可能です。私が想像できる最も可能性の高い理由は、ハッシュ関数が失敗するという小さなリスクを受け入れたくないということです。
于 2012-06-07T04:44:50.220 に答える