ハッシュ法

データを数値に変換する関数を「ハッシュ関数」といい、変換された数値をハッシュ値という。ハッシュ法で不特定多数のデータを扱うとことなるデータでも同じハッシュ値になることがあります。これをハッシュ値の「衝突」といいます。この問題を解決する方法は二つあり、それは「チェイン法」と「オープンアドレス法」です。

参考サイト

チェイン法

ハッシュ表の同じ場所に写像されたデータを連結リストにつなぐ。ハッシュ表は連結リストの先頭を指すポインタの配列

オープンアドレス法

  • 線形探査
  • 平方探査
  • ダブルハッシュ