ハッシュテーブル MOC

ハッシュテーブル MOCは、キーをハッシュ値から求めたバケットへ対応づける探索構造またはその構成要素である。

仕組み

ハッシュ関数h(k)で候補位置を決め、衝突はチェイン法またはオープンアドレス法で解決する。負荷因子α=n/mを監視して再構築する。

一様性を仮定した検索・挿入・削除は平均O(1)だが、衝突が集中する最悪時はO(n)。

m=8でh(k)=k mod 8なら10と18は同じバケット2へ入るため衝突処理が必要になる。

ハッシュ値の等しさはキーの等しさを意味しない。敵対的入力と反復順序にも注意する。