「 d["key"]、ハッシュテーブルが動作しています。その仕組みは単純です：キーを数値に変換し、その数値を配列のインデックスとして使い、直接アクセスするのです。
衝突は避けられない出来事だ
鍵の空間は無限大ですが、配列は有限であるため、同じインデックスに対して異なる2つの鍵が存在することは確実です。これに対処するには、主に2つの方法があります：
- 連結：各セルにはリストが含まれており、キーが一致した場合はそのリストに追加する
- 線形探索：セルがすでに使用されている場合は、次の空きセルを探す
2つ目の方法はCPUキャッシュに優しいことから、要素の削除はより複雑になるものの、現代のライブラリでは広く採用されています。
負荷係数が速度を決定する
負荷係数とは、要素数とセル数の比率のことです。これが閾値（通常は約0.7）を超えると、衝突が急増し、検索速度が徐々に低下します。その時点で、テーブルは元の2倍の大きさの新しい配列を割り当て、全体を再ハッシュする必要があります。
再ハッシュをトリガーする挿入処理は、通常よりも数千倍も遅くなる可能性があります。平均値としては定数ですが、レイテンシに敏感なシステムを開発している場合、そのわずかな遅延が致命的になる可能性があります。
実用的なポイント
- 要素の数があらかじめ分かっている場合は、最初から十分な容量を確保し、ハッシュの再計算を何度も行わなくて済むようにしてください
- キーは不変でなければなりません。挿入後にキーを変更すると、ハッシュ値が変更されるため、要素が失われてしまいます
- ハッシュテーブルは、言語がそれを保証している場合を除き、挿入順序を保持しません。偶然観察された順序に依存しないでください
Thảo luận