Hash table

Program

Parameters \(x\):
\(h(x)\):
\(h(x) mod N\):

Address	Open addressing	Chaining

Hash tableは、挿入、削除、検索が定数時間で行えるデータ構造である。

値\(x\)は長さ\(N\)の配列の位置\(h(x) mod N\)に保持される。

ここで、\(h\)のことをハッシュ関数、\(h(x)\)のことをハッシュ値という。

異なる値\(x, y\)に対して\(h(x) = h(y)\)となることを、衝突(collision)という。衝突した場合は、大別して次の方法で保持する位置を解決しなければならない。

\(h(x) = h(y)\)であるような\(x, y\)をListとして位置\(h(x) mod N\)に保持する。

衝突しないような別の位置を決定する新たな関数を定義する。

要素の数\( n \)に対する、配列の長さ\(N\)の比\( \frac{n}{N} \)をLoad factorという。Load factorが大きくなると衝突率が高くため、より大きな配列に再配置する必要がある。これをrehashという。

開番地法は隣の番地を順番に探索する方法(linear probing)で実装してある。
衝突の観察がしやすいように、ハッシュ関数\(h\)はデータの先頭一文字のコードポイントを返す関数とした。
削除はrehashのタイミングが一致しなくなってしまい見栄えが悪くなるため、あえて実装しなかった。開番地法で削除を行えるようにするのは難しくはないが、各番地に削除されたかの状態を保持する必要がある。連鎖法ではほとんど自明なポインタの修正で実装できる。