アルゴリズム・データ構造図鑑 · 入門

ハッシュ表:平均O(1)に必要な条件

ハッシュ値から候補位置を選び、衝突・負荷率・再配置まで含めて仕組みを理解する。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. キーから候補の場所を選ぶ
  2. 衝突を解決する二つの考え方
  3. 負荷率と再ハッシュ
  4. 順序と安全性は別の要件
  5. 線形探索法の削除で探索を切らない
  6. 再配置と一回の高い費用
  7. この記事をロゲイアに質問する理解を確かめる

キーから候補の場所を選ぶ

ハッシュ表は、キーをハッシュ関数に通し、得た値から格納先の候補を選ぶ辞書構造です。たとえば表の大きさが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)という主張は違います。実時間の上限を厳しく求める場面では、段階的な再ハッシュや事前確保も検討します。等しいと判定するキーは同じハッシュを返すという契約を、拡張の前後でも維持します。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 9

学習コースから次を選ぶ