四十三庵

蔀の雑記帳

Hash

データ構造とアルゴリズム (新・情報 通信システム工学)

  • ハッシュ値を使うとO(1)で値を求められる
  • 衝突という問題がある
  • 衝突を回避するためには二つ方法がある

チェイン法(chaining mechanism)

衝突した値はリスト構造でenqueして格納する

開番地法(open addressing)

衝突したら再ハッシュを行い、空いているメモリ番地を使う方法