ハッシュテーブルの実装について

ハッシュテーブルの実装について学習したため、そのまとめとしてここに整理する。

ハッシュテーブルの実装

• キーのハッシュ値が配列の添字となるように計算し、値を格納する

衝突への対策

• キーのハッシュ値が衝突した際に、格納場所が重ならないように工夫する必要がある
• チェイン法
  • 同一のハッシュ値に対応する値をLinkedListで管理する
  • ハッシュ値に対応するLinedListを探索したあとは、線形探索で値を探索する
• 線形探索法
  • ハッシュ値に対応する格納場所にデータが存在する場合は、その隣にデータを格納する