負荷率と再ハッシュ

負荷率は、ハッシュ テーブルがどの程度満たされているかを測定します。負荷係数を超えた場合は、ハッシュ テーブルのサイズを増やし、エントリを新しいより大きなハッシュ テーブルに再ロードします。これをリハッシュと呼びます。負荷係数 l (ラムダ) は、ハッシュ テーブルがどの程度満たされているかを測定します。
の数の比率です つまり、l = n / N、n は要素の数、N はハッシュ テーブル内の位置の数を表します。

ハッシュ テーブルが空の場合、l はゼロであることに注意してください。オープン アドレス指定スキームの場合、l は 0 と 1 の間です。ハッシュテーブルがいっぱいの場合、l は 1 です。個別のチェーン スキームの場合、l は任意の値にすることができます。

l が増加すると、衝突の確率が増加します。研究によると、オープン アドレッシング スキームの場合は負荷係数を 0.5 未満に維持し、セパレート チェーン スキームの場合は 0.9 未満に維持する必要があることがわかっています。

負荷係数を特定のしきい値以下に維持することは、ハッシュのパフォーマンスにとって重要です。 Java API の java.util.HashMap クラスの実装では、しきい値 0.75 が使用されます。負荷率がしきい値を超えるたびに、ハッシュテーブルのサイズを増やし、マップ内のすべてのエントリを新しいより大きなハッシュテーブルに再ハッシュする必要があります。ハッシュ テーブルのサイズが変更されたため、ハッシュ関数を変更する必要があることに注意してください。再ハッシュの可能性を減らすには、コストがかかるため、ハッシュ テーブルのサイズを少なくとも 2 倍にする必要があります。定期的な再ハッシュを使用する場合でも、ハッシュはマップの効率的な実装です。

以上が負荷率と再ハッシュの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。