キーから候補の場所を選ぶ
ハッシュ表は、キーをハッシュ関数に通し、得た値から格納先の候補を選ぶ辞書構造です。たとえば表の大きさが8で、整数キーを8で割った余りを位置に使うと、キー10は位置2に対応します。ハッシュ値はキーそのものの代わりにはなりません。異なるキーが同じ位置に対応し得るため、検索時には候補のキーとの等価比較も必要です。キーの等価性とハッシュ関数の規則をそろえることが実装の前提です。
衝突を解決する二つの考え方
同じ表にキー18を入れると、10と同じ位置2に衝突します。連鎖法では、その位置に複数の要素を持つリストなどを置きます。開番地法では、規則に従って別の空き位置を探します。検索と削除にも同じ規則が必要で、開番地法で削除位置を単純に未使用へ戻すと、後ろにあるキーを見つけられなくなることがあります。削除印など、探索経路を保つ仕組みを使います。
負荷率と再ハッシュ
要素数をn、バケット数をmとすると、負荷率はn/mです。負荷率が上がると、同じ場所へ集まる要素や探索する位置が増えやすくなります。適切なハッシュ分布と負荷率の管理などを仮定すれば検索は期待O(1)ですが、多数のキーが一つのバケットに集まれば最悪O(n)になり得ます。容量を増やす再ハッシュでは各要素の場所を計算し直すため、その一回は通常O(n)の仕事になります。
順序と安全性は別の要件
ハッシュ表は、キーが存在するか、対応する値が何かを調べる用途に向いています。一方、最小キーの取得や範囲検索、キー順の走査は基本機能ではありません。順序が必要なら平衡探索木なども比較します。また、外部入力をキーにするサービスでは、攻撃者が衝突を集中させる可能性も考慮します。暗号学的ハッシュの性質と、辞書として適切な分布や実装上の衝突対策は、目的を分けて検討します。
線形探索法の削除で探索を切らない
大きさ8の表でh(key)=key mod 8とし、衝突時は次の位置へ進む線形探索法を考えます。10、18、26はすべて最初の候補が2なので、位置2、3、4へ順に入ります。ここで10を削除して位置2を「一度も使われていない空き」と同じにすると、26の検索が位置2で終了し、存在するキーを見落とします。削除済みの目印を置いて探索を続ける方法や、後ろのクラスタを整え直す方法などが必要です。削除マーカーが増えると、見かけの要素数が少なくても探索が長くなる点も重要です。
再配置と一回の高い費用
表を拡張すると、バケットを決める法やビットマスクが変わるため、既存キーを新しい表へ再配置する必要があります。8から16へ広げる例では、10 mod 8と18 mod 8はともに2ですが、16では10と2へ分かれます。拡張を伴う一回の挿入はO(n)になり得るので、償却O(1)の挿入と、あらゆる一回の挿入がO(1)という主張は違います。実時間の上限を厳しく求める場面では、段階的な再ハッシュや事前確保も検討します。等しいと判定するキーは同じハッシュを返すという契約を、拡張の前後でも維持します。