ハッシュテーブルの負荷率：リサイズとパフォーマンスチューニング
負荷率がハッシュテーブルのパフォーマンスにどう影響するか、いつどのようにリサイズするか、メモリ使用量と検索速度のトレードオフを学びます。償却O(1)分析を理解します。
Hash Table
詳細な説明
ハッシュテーブルの負荷率
負荷率は格納された要素数とバケット数の比率です：
load_factor = n / m
ここでnは要素数、mはバケット数です。負荷率はハッシュテーブルのパフォーマンスに直接影響します。
パフォーマンスへの影響
負荷率が増加すると：
- チェイニング：平均チェーン長が増加。検索時間はO(1 + load_factor)に。
- オープンアドレッシング：探査シーケンスが長くなる。負荷率0.75で平均探査≈4回、0.9で≈10回。
リサイズプロセス
負荷率がしきい値を超えると：
- 新しい、より大きなバケット配列を確保（通常は現在のサイズの2倍）。
- すべての要素を再ハッシュ。
- 古い配列を新しいもので置換。
リサイズはすべての要素を再ハッシュする必要があるためO(n)です。しかし、リサイズは容量を2倍にするため、次のn/2回の挿入はそれぞれO(1)です。これにより挿入あたりの**償却O(1)**コストが得られます。
適切なしきい値の選択
- 低いしきい値（例：0.5）：高速な検索、多いメモリ使用量
- 高いしきい値（例：0.9）：低速な検索、少ないメモリ使用量
- デフォルトの0.75はほとんどのワークロードに対するよくテストされたバランス
ユースケース
負荷率の理解はパフォーマンスチューニングに不可欠です。高スループットシステムでは、ホットパス中のリサイズを避けるためにハッシュマップを事前サイズ設定することでレイテンシスパイクを防止できます。メモリ制約のある環境では、高い負荷率を選択してスピードとメモリをトレードオフします。