夕蛙のなく頃に

データアナリストとして学んだことや趣味で勉強し始めたIoTをアウトプットする

OpenDataStructures第5章を自分用にまとめる(ハッシュテーブル)

なにこれ

前回の続き

blog.frogdusk.com

ハッシュテーブルを用いてUSetインターフェースを実装します。
USetインターフェースは順序付けられていない値の集合です。

Setインターフェースで重要なのは、ある値がすでに保持されているかを確認するfindですが、簡単に言うと、ある値を格納する場所は一意に決まっているので、その場所さえ確認すればfindできるよという実装です。

  • ChainedHashTable
  • LinearHashTable

ChainedHashTable

ArrayStackを格納した配列を考えます。
ある値を格納する一意な場所(index)に値を追加していきます。

f:id:frogdusk:20190718101829p:plain

  • ある値が格納されているかは、1ヶ所だけ確認すればよいので、add・remove・findの期待実行時間はO(1)です。

乗算ハッシュ法

重要なのは格納する場所を一意に決めるハッシュ関数です。
本の以下の流れがわかりやすいです。
(w=32は固定値。d=8、すなわち28以下のランダムな値に変換する必要があります。)

f:id:frogdusk:20190718101916p:plain

  1. 232の値を得る
  2. 232以下のランダムな奇数を得る
  3. x=42を変換したい
  4. 2と3で出てきた値を掛け合わせて、大きな値を作る
  5. 232以上の値になったら、232未満にしたいので、mod232をする
  6. 5で出てきた値に対して、24(32-8)だけ右シフト -> 28以下の値になる

LinearHashTable

わざわざArrayStackを配列にせず、そのままの配列を使います。
もしハッシュ値が衝突したら、次のindexを見に行き、nullなものが見つかったらfindを終了したり、新しくaddします。