探索アルゴリズム：二分探索の O(log n) とハッシュ表の平均 O(1)

0. この記事の要点

• 線形探索は $\Theta(n)$ です。ソートという前処理を一度だけ払えば、二分探索は最悪でも $\lceil \log_2(n+1) \rceil$ 回の比較で答えます。$n = 10^9$ でも 30 回です。
• 二分探索の正しさは「探索区間の外側は答えが確定している」という不変条件で証明できます。実装の誤りの大半は、この不変条件を書き下さないまま添字をいじることから生じます。
• キーどうしの比較しか使えないモデルでは $\lceil \log_2(n+1) \rceil$ 回が下界で、二分探索は最適です。これ以上速くするにはモデルを変えるしかありません。
• ハッシュ表はキーの値から添字を計算し、比較モデルの外に出ます。最悪計算量は $\Theta(n)$ のままですが、負荷率 $\alpha = n/m$ を定数に保てば探索・挿入・削除は期待 $\Theta(1)$ 時間です。
• 「平均 $O(1)$」には性質の違う 3 つの意味（データの分布仮定、ハッシュ関数の乱択、リサイズのならし）が混在しています。実務で頼ってよいのは後ろの 2 つです。
• ハッシュ表は順序を失います。最小値・範囲検索が要るなら、ソート済み配列か平衡二分探索木を選びます。

1. 動機：探索を速くするために何を捨てるか

探索は、計算機がもっとも頻繁に実行する操作です。データベースのインデックス、コンパイラのシンボル表、ルータの経路表、言語の連想配列、いずれも中身は「キーを与えると対応する値を返す」装置です。素朴にやるなら線形探索で、$n$ 個のデータに $\Theta(n)$ 時間かかります。$n$ が 10 なら誰も困りませんが、$n = 10^9$ ではどうにもなりません。$O$ 記法がスケーラビリティを測る道具だという話は 計算量とO記法 で扱いました（Definition 3.1［Complexity and Big-O Notation］）。ここではその道具で、探索を速くする 2 つの道筋を最後まで追いかけます。

第 1 の道は前処理です。あらかじめデータを並べ替えておけば、1 回の比較で候補を半分に減らせます。これが二分探索で、比較回数は $\Theta(\log n)$ になります。ただしソートには $\Theta(n \log n)$ 時間かかる（ソートアルゴリズム の Theorem 4.2［Sorting Algorithms］）ので、前処理が引き合うかは検索回数次第です。$n = 10^6$ の配列を $q$ 回検索する場面を比較回数だけで概算すると、線形探索は最悪 $q \cdot 10^6$ 回、ソートしてから二分探索する方は $10^6 \log_2 10^6 + q \log_2 10^6 \approx 2 \times 10^7 + 20 q$ 回です。損益分岐点は $q \approx 20$ で、20 回より多く検索するならソートしたほうが得だと分かります。前処理は繰り返し使ってはじめて回収できるのです。

第 2 の道はキーの値を直接使うことです。比較は「大きいか小さいか」という 1 ビットしか引き出しませんが、キーが整数やビット列なら、その中身を計算に使って格納位置を決められます。これがハッシュ法で、うまくいけば $\log n$ すら要らず、平均で定数時間になります。

歴史を少しだけ挟みます。二分探索の着想自体は古く、Knuth によれば計算機上での言及は 1946 年の Mauchly の講義にさかのぼりますが、任意の長さ $n$ に対して正しく動く版が公刊されたのは 1960 年、最初の言及から 14 年後のことでした（『The Art of Computer Programming』第 3 巻 §6.2.1 の歴史的注記）。J. Bentley は『Programming Pearls』で、時間を与えられたプロの技術者の大半が正しい二分探索を書けなかったと報告しています。極めつけは 2006 年で、Java の標準ライブラリ Arrays.binarySearch が中央位置を (low + high) / 2 で計算していたために、要素数が $2^{30}$ を超えると加算が桁あふれして添字が負になる不具合が見つかりました。20 行に満たないアルゴリズムが、広く使われた標準ライブラリの中で壊れていたのです。だからこの記事では、正しさを不変条件で証明します。

ハッシュ法のほうは、Knuth の歴史的注記（同書 §6.4）によれば 1953 年 1 月の H. P. Luhn による IBM 社内メモが最初の記述で、そこにはすでにチェイン法が現れています。

2. 準備：探索問題と 2 つの計算モデル

まず、これから何を実装しようとしているのかを抽象データ型として固定します。

Definition 2.1（辞書（連想配列））

キーの集合 $U$ と値の集合 $V$ を固定します。辞書とは、相異なるキーをもつ有限個の対の集合 $S \subseteq U \times V$ を保持し、次の 3 つの操作を提供する抽象データ型です。

• $\mathrm{search}(k)$：$(k, v) \in S$ となる $v$ を返す。そのような $v$ がなければ「無い」と答える。
• $\mathrm{insert}(k, v)$：$S$ に $(k, v)$ を加える（同じキーの対がすでにあれば値を置き換える）。
• $\mathrm{delete}(k)$：キーが $k$ である対を $S$ から取り除く。

以下、$n = |S|$ と書きます。

Python の dict、Java の HashMap、C++ の std::map はいずれもこの抽象データ型の実装です。実装が違えば計算量も、できることも違います。その差は第 7 節で表にします。

次に、計算量を測る土俵を 2 つ用意します。どちらの土俵に立つかで結論が変わります。

Definition 2.2（比較モデル）

キーの集合 $U$ に全順序 $\le$ が与えられているとします。アルゴリズムがキーについて行える操作が「2 つのキー $k, l$ を比べて $k < l$, $k = l$, $k > l$ のいずれであるかを知る」ことだけであるとき、そのアルゴリズムは比較モデルで動くといいます。キーの値を使った算術（下位ビットを取り出す、$(k - a)/(b - a)$ を計算する、など）は比較モデルでは禁止されます。

これに対し、キーをビット列とみなして算術や添字計算に使ってよい土俵を、ここではアドレス計算モデル（語 RAM モデル）と呼びます。整数の加減乗除・剰余・ビット演算と、配列の添字アクセスが 1 単位時間でできるものとします。これは 一様コスト RAM モデル（Definition 2.1）［Complexity and Big-O Notation］ と同じ約束です。

これはソートの下界を論じるときに使った 比較ソートモデル（Definition 2.2）［Sorting Algorithms］ と同じ制約です。比較モデルの利点は汎用性です。キーが文字列でも日付でもユーザ定義の構造体でも、比較さえ定義されていれば同じアルゴリズムが動きます。代償として、第 4 節で見るとおり $\log n$ の壁が生じます。

土台として、線形探索の費用を確定させておきます。

Proposition 2.3（線形探索の比較回数）

長さ $n$ の配列 $A[0..n-1]$ の要素はすべて相異なるとし、キー $x$ を $A[0], A[1], \ldots$ の順に比べていく線形探索を考えます。

1. $x$ が $A$ のどこにも現れないとき、比較回数はちょうど $n$ 回です。
2. $x$ が $A$ のいずれかの位置に等確率で現れるとき、比較回数の期待値は $(n+1)/2$ 回です。

いずれの場合も計算量は $\Theta(n)$ です。

Proof（Proposition 2.3）

(1) アルゴリズムは $i = 0, 1, \ldots, n-1$ について $A[i] = x$ かどうかを調べ、どれも成立しないので $n$ 回比較して「無い」と答えます。

(2) $x = A[i]$ である場合、比較は $A[0], \ldots, A[i]$ に対して行われるので $i + 1$ 回です。各 $i$ の確率が $1/n$ なので、期待値は

$$\sum_{i=0}^{n-1} \frac{1}{n}(i+1) = \frac{1}{n}\sum_{j=1}^{n} j = \frac{1}{n}\cdot\frac{n(n+1)}{2} = \frac{n+1}{2}$$

です。途中で等差数列の和 $\sum_{j=1}^{n} j = n(n+1)/2$ を使いました。$(n+1)/2$ も $n$ も $\Theta(n)$ です。

∎

期待値を取っても定数倍しか改善しません。$\Theta(n)$ から抜け出すには、走査の順序ではなくデータの持ち方を変える必要があります。

3. 二分探索：不変条件で正しさを保証する

3.1. 何を返す関数として定義するか

「$x$ を見つけたら添字、見つからなければ $-1$」という仕様は、実は扱いにくい仕様です。重複キーがあるとどの添字を返すか曖昧ですし、「無かった」ときに挿入すべき位置が分かりません。そこで境界を返す形に定義し直します。

Definition 3.1（下限位置）

昇順にソートされた配列 $A[0..n-1]$（すなわち $A[0] \le A[1] \le \cdots \le A[n-1]$）とキー $x$ に対して

$$\mathrm{lb}_A(x) = \#\{\, i \mid 0 \le i \le n-1,\ A[i] < x \,\}$$

を $x$ の下限位置と呼びます。

$A$ が昇順である以上、$A[i] < x$ を満たす添字の集合は $\{0, 1, \ldots, t-1\}$ という形の切片になります。実際 $A[i] < x$ かつ $i' < i$ なら $A[i'] \le A[i] < x$ だからです。したがって $\mathrm{lb}_A(x)$ は「$A[i] \ge x$ となる最小の添字」（そのような添字がなければ $n$）と一致します。この値さえ得られれば、存在判定は $\mathrm{lb}_A(x) < n$ かつ $A[\mathrm{lb}_A(x)] = x$ で済み、ソート順を保った挿入位置もそのまま得られます。

3.2. アルゴリズム

def lower_bound(a, x):
    """昇順の配列 a に対し、a[i] >= x となる最小の i を返す（無ければ len(a)）。"""
    lo, hi = 0, len(a)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo


def contains(a, x):
    i = lower_bound(a, x)
    return i < len(a) and a[i] == x

区間は半開区間 $[lo, hi)$ で持ちます。hi を「まだ調べていない範囲の右端の 1 つ先」とすることで、空区間が $lo = hi$ という 1 つの条件で表せ、場合分けが減ります。

二分探索の 1 反復で探索区間の長さは半分以下になる。長さが 0 になった時点で答えが確定する。

3.3. 正しさ

Theorem 3.2（二分探索の正当性）

$A[0..n-1]$ を昇順にソートされた配列（$n \ge 0$）、$x$ を任意のキーとします。このとき lower_bound(a, x) は必ず停止し、$\mathrm{lb}_A(x)$ を返します。

Proof（Theorem 3.2）

次の 3 つの条件をループ不変条件とします。

• (I1) $0 \le lo \le hi \le n$
• (I2) すべての $i < lo$ について $A[i] < x$
• (I3) すべての $i \ge hi$ について $A[i] \ge x$

初期化。 $lo = 0$, $hi = n$ のとき (I1) は明らかに成立します。(I2) は「$i < 0$ なる添字」が存在しないので空虚に真、(I3) も「$i \ge n$ なる添字」が存在しないので空虚に真です。

中央位置の範囲。 ループ本体に入るとき $lo < hi$、すなわち $d := hi - lo \ge 1$ です。$mid = lo + \lfloor d/2 \rfloor$ について $\lfloor d/2 \rfloor \ge 0$ より $mid \ge lo$。また $d = 1$ なら $\lfloor d/2 \rfloor = 0 = d - 1$、$d \ge 2$ なら $\lfloor d/2 \rfloor \le d/2 \le d - 1$ なので、いずれにせよ $\lfloor d/2\rfloor \le d-1$、つまり $mid \le hi - 1$ です。よって $lo \le mid < hi$ であり、$A[mid]$ の参照は配列の範囲内で、(I1) も保たれます。

保存。 2 つの場合に分かれます。

$A[mid] < x$ のとき、$lo$ を $mid + 1$ に更新します。$i \le mid$ なる任意の $i$ について、$A$ が昇順（定理の仮定）なので $A[i] \le A[mid] < x$。よって新しい $lo$ についても (I2) が成り立ちます。(I3) は $hi$ を変えていないので保たれます。

$A[mid] \ge x$ のとき、$hi$ を $mid$ に更新します。$i \ge mid$ なる任意の $i$ について、昇順性より $A[i] \ge A[mid] \ge x$。よって新しい $hi$ についても (I3) が成り立ちます。(I2) は $lo$ を変えていないので保たれます。

停止。 $A[mid] < x$ の場合、$hi - lo$ は $hi - mid - 1 \le hi - lo - 1$ に、そうでない場合は $mid - lo \le hi - lo - 1$ になります（どちらも $lo \le mid \le hi-1$ を使いました）。したがって $hi - lo$ は毎回 1 以上減り、かつ (I1) より $0$ 以上なので、ループは有限回で終わります。

終了時。 ループを抜けたとき $lo = hi$ です。(I2) より $i < lo$ なるすべての添字が $A[i] < x$ を満たすので $\#\{i \mid A[i] < x\} \ge lo$、(I3) より $i \ge lo$ なる添字はどれも $A[i] \ge x$ で条件を満たさないので $\#\{i \mid A[i] < x\} \le lo$。両者を合わせて $\mathrm{lb}_A(x) = lo$ であり、返り値は正しい値です。$n = 0$ のときはループが 1 度も回らず $0$ を返しますが、これも $\mathrm{lb}_A(x) = 0$ と一致します。

∎

3.4. 計算量

Theorem 3.3（二分探索の比較回数）

$n \ge 1$ とします。Theorem 3.2 と同じ仮定のもとで、lower_bound(a, x) が実行するキーの比較回数は高々

$$\lfloor \log_2 n \rfloor + 1 = \lceil \log_2 (n+1) \rceil$$

回です。特に、比較 1 回と添字の演算がそれぞれ定数時間で済むなら、計算時間は $O(\log n)$ です。

Proof（Theorem 3.3）

まず 2 つの表示が等しいことを確かめます。$k = \lfloor \log_2 n \rfloor$ とおくと $2^k \le n < 2^{k+1}$、したがって $2^k < n + 1 \le 2^{k+1}$ なので $\lceil \log_2 (n+1) \rceil = k+1$ です。

次に反復回数を数えます。反復開始時の区間長を $d = hi - lo$、終了時を $d'$ とし、$\mathrm{mid}$ の定義から $m = \lfloor d/2 \rfloor$ とおきます。Theorem 3.2 の証明で見たとおり $lo \le mid \le hi - 1$ です。

• $A[mid] < x$ の場合：$d' = hi - (mid+1) = d - m - 1 = \lceil d/2 \rceil - 1$。
• $A[mid] \ge x$ の場合：$d' = mid - lo = m = \lfloor d/2 \rfloor$。

$d$ が偶数なら $\lceil d/2\rceil - 1 = d/2 - 1 < \lfloor d/2 \rfloor$、$d$ が奇数なら $\lceil d/2 \rceil - 1 = (d-1)/2 = \lfloor d/2 \rfloor$ なので、どちらの場合も $d' \le \lfloor d/2 \rfloor \le d/2$ が成り立ちます。

$k$ 回の反復後の区間長を $d_k$ と書くと $d_0 = n$ で、いま示した不等式から $d_k \le n / 2^k$ です（$k$ についての帰納法）。$d_k$ は非負整数なので $d_k \le \lfloor n/2^k \rfloor$ です。$k = \lfloor \log_2 n \rfloor + 1$ とすると $2^k > n$ なので $\lfloor n/2^k\rfloor = 0$、つまり $d_k = 0$ となり、ループ条件 $lo < hi$ が破れます。よって反復回数は高々 $\lfloor \log_2 n\rfloor + 1$ 回で、各反復はキーの比較をちょうど 1 回行うので、比較回数も同じ上界を持ちます。

∎

Example 3.4（二分探索の実行を最後まで追う）

$A = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]$（$n = 10$）とします。上界は $\lfloor \log_2 10\rfloor + 1 = 3 + 1 = 4$ 回です。

まず $x = 13$ を探します。

反復	lo	hi	mid	A[mid]	$A[\text{mid}] < x$	更新
1	0	10	5	13	偽	hi = 5
2	0	5	2	5	真	lo = 3
3	3	5	4	11	真	lo = 5
—	5	5	—	—	—	終了、5 を返す

比較 3 回で $\mathrm{lb}_A(13) = 5$ を得ました。$A[5] = 13 = x$ なので $x$ は存在します。

次に $x = 14$ を探します。

反復	lo	hi	mid	A[mid]	$A[\text{mid}] < x$	更新
1	0	10	5	13	真	lo = 6
2	6	10	8	23	偽	hi = 8
3	6	8	7	19	偽	hi = 7
4	6	7	6	17	偽	hi = 6
—	6	6	—	—	—	終了、6 を返す

比較 4 回で $\mathrm{lb}_A(14) = 6$。$A[6] = 17 \ne 14$ なので $14$ は存在せず、もし挿入するなら添字 6 の位置だと分かります。この 4 回は Theorem 3.3 の上界ちょうどで、上界が達成され得ることも確認できました。

Remark 3.5（実装上の落とし穴）

mid = (lo + hi) // 2 と書くと、固定長整数を使う言語では lo + hi が桁あふれします。32 ビット符号付き整数なら、要素数が $2^{30} \approx 1.07 \times 10^9$ を超えた時点で和が負になり、添字が範囲外になります。これが 2006 年に Java 標準ライブラリで見つかった不具合で、lo + (hi - lo) // 2 と書けば $hi - lo \le hi$ なので桁あふれしません。Python の整数は多倍長なのでこの問題は起きませんが、書き癖として後者を勧めます。

もう 1 つは「等しいときに即座に返す」変種です。運がよければ早く終わりますが、重複キーのときどの添字を返すか決まらず、最悪比較回数も減りません（Theorem 4.1）。境界を返す形に統一しておくほうが応用が利きます。

Tip

Python では bisect.bisect_left(a, x) が lower_bound に、bisect.bisect_right(a, x) が「$x$ 以下の要素数」に相当します。C++ では std::lower_bound / std::upper_bound です。自分で書くのは仕組みを理解するためで、実務では標準ライブラリを使ってください。

3.5. 配列でなくてもよい：述語の二分探索

二分探索が使えるための本質的な条件は「配列がソートされていること」ではなく、判定が単調であることです。真偽値を返す述語 $P$ が $P(0) \le P(1) \le \cdots$（偽が続いた後に真が続く）を満たすなら、同じ手続きで「$P$ が真になる最小の点」を求められます。$A[i] < x$ という述語はその特別な場合です。

Example 3.6（答えで二分探索する：整数平方根）

非負整数 $N$ に対して $\lfloor \sqrt{N} \rfloor$、つまり $v^2 \le N$ を満たす最大の整数 $v$ を求めます。述語 $P(v) = (v^2 > N)$ は $v$ について単調（$v$ が大きくなると偽から真に一度だけ変わる）なので、二分探索できます。

def isqrt(n):
    """n >= 0 に対し floor(sqrt(n)) を返す。"""
    lo, hi = 0, n + 1          # 不変条件: lo*lo <= n < hi*hi
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if mid * mid <= n:
            lo = mid
        else:
            hi = mid
    return lo

不変条件は $lo^2 \le N < hi^2$ です。初期値では $lo^2 = 0 \le N$ であり、$hi^2 = (N+1)^2 = N^2 + 2N + 1 > N$ なので成立します。ループ内で $lo < mid < hi$（$hi - lo \ge 2$ のとき $mid = \lfloor (lo+hi)/2 \rfloor$ は両端の間に来る）なので、どちらの更新でも区間は真に狭まり、不変条件は保たれます。終了時 $hi = lo + 1$ かつ $lo^2 \le N < (lo+1)^2$ なので、$lo = \lfloor \sqrt N \rfloor$ です。

$N = 10^{18}$ なら、初期区間長 $10^{18}+1$ が 1 回ごとに半分以下になるので反復は $\lceil \log_2 (10^{18}+1) \rceil = 60$ 回です（$2^{59} \approx 5.76 \times 10^{17} < 10^{18} < 2^{60}$ による）。答えの $\lfloor \sqrt{10^{18}} \rfloor = 10^9$ を $1$ から順に試せば $10^9$ 回のところ、60 回で終わります。なお Python には math.isqrt があります。

4. なぜ log n より速くならないのか：比較モデルの下界

$\Theta(\log n)$ をさらに縮められないかを考えます。答えは「比較モデルの中では不可能」です。証明の道具は決定木、つまりアルゴリズムの実行を「比較の結果でどちらの枝に進むか」の木として表す見方です。比較ソートの $\Omega(n \log n)$ 下界（Theorem 6.1［Sorting Algorithms］）とまったく同じ道具立てで、葉の個数を下から、木の深さを上から押さえます。

Theorem 4.1（比較モデルにおける探索の下界）

$n \ge 1$ とします。比較モデル（Definition 2.2）で動く任意の決定的アルゴリズム $\mathcal{A}$ が、昇順にソートされた長さ $n$ の配列 $A$ とキー $x$ を入力として $\mathrm{lb}_A(x)$ を出力するならば、ある入力 $(A, x)$ に対して $\mathcal{A}$ は少なくとも $\lceil \log_2 (n+1) \rceil$ 回の比較を行います。

Proof（Theorem 4.1）

配列を $A = (1, 3, 5, \ldots, 2n-1)$、すなわち $A[i] = 2i+1$ に固定します。これは昇順で要素はすべて相異なります。探索キーとして $x_j = 2j$（$j = 0, 1, \ldots, n$）という $n+1$ 個の入力を考えます。

これらの出力はすべて異なります。実際 $\mathrm{lb}_A(x_j) = \#\{ i \mid 2i + 1 < 2j \} = \#\{ i \mid i < j - \tfrac12 \} = \#\{0, 1, \ldots, j-1\} = j$ だからです。

$\mathcal{A}$ の実行を、この $n+1$ 個の入力に限って決定木として描きます。$\mathcal{A}$ が行う比較は 2 種類あります。

1. 配列の要素どうしの比較 $A[i]$ と $A[i']$：$A$ は $n+1$ 個の入力すべてで同じなので、結果もすべて同じです。したがってこの節点ではすべての入力が同じ枝に進み、入力の区別に寄与しません。
2. 探索キーと配列要素の比較 $x_j$ と $A[i]$：$x_j$ は偶数、$A[i]$ は奇数なので $x_j = A[i]$ は決して起こりません。よって結果は「$<$」か「$>$」の 2 通りで、この節点の枝は実質 2 本です。

1 に当たる節点を縮約すれば、$n+1$ 個の入力の実行経路は 2 分木の根から葉への経路になります。比較回数の最大値を $T$ とすると、この 2 分木の深さは $T$ 以下なので、葉の個数は高々 $2^T$ です。

一方、2 つの入力 $x_j \ne x_{j'}$ が同じ葉に到達したとすると、$\mathcal{A}$ は決定的なので同じ出力を返します。しかし上で見たように $\mathrm{lb}_A(x_j) = j \ne j' = \mathrm{lb}_A(x_{j'})$ なので、少なくとも一方は誤答です。$\mathcal{A}$ が正しい以上これは起こり得ず、$n+1$ 個の入力は相異なる葉に到達します。

したがって $2^T \ge n+1$、すなわち $T \ge \log_2 (n+1)$ です。$T$ は整数なので $T \ge \lceil \log_2(n+1)\rceil$ が従います。

∎

Corollary 4.2（二分探索の最適性）

比較モデルにおいて、ソート済み配列に対する探索の最悪比較回数の最小値はちょうど $\lceil \log_2 (n+1)\rceil$ であり、二分探索はそれを達成します。

Proof（Corollary 4.2）

上界は Theorem 3.3（二分探索の比較回数は高々 $\lfloor \log_2 n\rfloor + 1 = \lceil \log_2(n+1)\rceil$）、下界は Theorem 4.1 です。両者が一致するので、これが最小値です。

∎

Remark 4.3（下界から逃げる 2 つの方向）

Theorem 4.1 が縛っているのは「比較しかしない」アルゴリズムだけです。キーの値そのものを計算に使えば、この下界は適用されません。

1 つ目の逃げ道は補間探索です。電話帳で「さ」を引くとき真ん中を開かないのと同じ発想で、$x$ の値から予想位置 $lo + \lfloor (x - A[lo])(hi - lo)/(A[hi] - A[lo]) \rfloor$ を計算します（この式に限り $[lo, hi]$ は両端を含む閉区間とし、$A[hi]$ も探索範囲の要素とします）。キーが区間上の一様分布から独立に選ばれるという仮定のもとで期待比較回数は $O(\log\log n)$ になりますが（Knuth 前掲書 §6.2.1）、分布が偏ると最悪 $\Theta(n)$ に劣化します。

2 つ目が次節のハッシュ法で、キーから格納位置そのものを計算し、比較回数を定数にします。どちらも「比較しかしない」制約を捨てて下界を回避しています。下界とは、モデルの中でできることの限界であって、問題の限界ではありません。

5. ハッシュ表：キーから住所を計算する

5.1. 直接アドレス表とその破綻

キーが $0$ 以上 $|U|-1$ 以下の整数なら、長さ $|U|$ の配列 $T$ を用意して $T[k]$ に値を置けば、探索・挿入・削除はすべて最悪 $O(1)$ です。これを直接アドレス表といいます。問題は空間です。キーが 64 ビット整数なら $|U| = 2^{64} \approx 1.8 \times 10^{19}$ 個のスロットが要り、格納するキーが 1000 個でも不可能です。文字列キーならさらに絶望的です。

そこで、大きなキー空間 $U$ を小さな添字空間に押し込む関数を挟みます。

Definition 5.1（ハッシュ表・ハッシュ関数・負荷率）

$m$ を正の整数、$T[0..m-1]$ を長さ $m$ の配列（ハッシュ表）、$h : U \to \{0, 1, \ldots, m-1\}$ を関数（ハッシュ関数）とします。キー $k$ はスロット $h(k)$ に関係づけて格納します。相異なるキー $k \ne l$ に対して $h(k) = h(l)$ となることを衝突といいます。格納されているキーの個数を $n$ として、$\alpha = n/m$ を負荷率と呼びます。

Proposition 5.2（衝突は原理的に避けられない）

$|U| > m$ ならば、どんな関数 $h : U \to \{0, \ldots, m-1\}$ に対しても $h(k) = h(l)$ となる相異なる $k, l \in U$ が存在します。さらに $|U| \ge (n-1)m + 1$ ならば、$n$ 個の相異なるキーからなる集合 $S \subseteq U$ で、$h$ がその全部を同一のスロットに写すものが存在します。

Proof（Proposition 5.2）

前半は鳩の巣原理です。$|U| > m$ 個の元を $m$ 個の値に写す以上、同じ値を取る 2 元が存在します。

後半を示します。$U$ は $m$ 個の逆像 $h^{-1}(0), \ldots, h^{-1}(m-1)$ に分割されます。もしすべての $j$ について $|h^{-1}(j)| \le n-1$ なら、$|U| = \sum_{j=0}^{m-1} |h^{-1}(j)| \le (n-1)m$ となり、仮定 $|U| \ge (n-1)m+1$ に反します。よってある $j$ で $|h^{-1}(j)| \ge n$ となり、その逆像から $n$ 個選べば $S$ が得られます。

∎

つまり、$h$ をどれほど巧妙に設計しても、それを知った相手は全キーを同じスロットに集める入力を作れます。**ハッシュ表の最悪計算量は $\Theta(n)$ であり、これは改善できません。**それでも実用になるのは平均で見れば定数時間だからです。以下、その「平均」の意味を 2 通りに分けて厳密に述べます。

5.2. チェイン法

flowchart LR
K1["キー 5"] --> H["h(k) = k mod 4"]
K2["キー 9"] --> H
K3["キー 12"] --> H
H -->|"h(12) = 0"| S0["スロット 0"]
H -->|"h(5) = h(9) = 1"| S1["スロット 1"]
S0 --> N12["12"]
S1 --> N5["5"] --> N9["9"]
S2["スロット 2（空）"]
S3["スロット 3（空）"]

チェイン法。同じスロットに写るキー（5 と 9）は、そのスロットにぶら下がる連結リストに並ぶ。

チェイン法では、$T[j]$ に「$h(k) = j$ であるキーの連結リスト」への参照を置きます。挿入はリストの先頭に繋ぐだけ、探索は $T[h(k)]$ のリストを走査、削除はリストから外します。連結リストの基本操作は 基本的なデータ構造 で扱ったとおりです（Proposition 4.2［Fundamental Data Structures］）。

Theorem 5.3（チェイン法の期待計算量）

$m$ スロットのハッシュ表に $n$ 個のキーをチェイン法で格納し、$\alpha = n/m$ とします。次の仮定を置きます。

• 単純一様ハッシュの仮定：格納される各キーは、他のキーと独立に、$m$ 個のスロットのそれぞれに確率 $1/m$ で写る。
• ハッシュ関数 $h$ の計算は $O(1)$ 時間でできる。
• 新しいキーはリストの先頭に挿入する。

このとき次が成り立ちます。

1. 表に格納されていないキー $x$（その $h(x)$ もまた $m$ 個のスロット上の一様分布に従い、格納済みのキーとは独立とする）を探索するとき、走査されるリスト要素数の期待値は $\alpha$ であり、探索時間の期待値は $\Theta(1 + \alpha)$ です。
2. 格納されている $n$ 個のキーのどれを探すかが等確率であるとき、走査されるリスト要素数の期待値は $1 + \dfrac{\alpha}{2} - \dfrac{\alpha}{2n}$ であり、探索時間の期待値は $\Theta(1 + \alpha)$ です。

Proof（Theorem 5.3）

(1) 不成功探索。 スロット $j$ のリストの長さを $n_j$ と書きます。$i$ 番目のキー $k_i$ について指標変数 $Y_{ij} = 1$（$h(k_i) = j$ のとき）、$0$（それ以外）を定めると $n_j = \sum_{i=1}^n Y_{ij}$ です。単純一様ハッシュの仮定から $\Pr[Y_{ij} = 1] = 1/m$、したがって $E[Y_{ij}] = 1/m$ です。期待値の線形性より

$$E[n_j] = \sum_{i=1}^{n} E[Y_{ij}] = \frac{n}{m} = \alpha .$$

不成功探索では $T[h(x)]$ のリストを最後まで走査します。$h(x)$ が格納済みキーの配置と独立で一様なので、走査数の期待値は $\sum_{j=0}^{m-1} \frac{1}{m} E[n_j] = \alpha$ です。これに $h(x)$ の計算と表アクセスの $O(1)$ を加えて、時間は $\Theta(1+\alpha)$ です。

(2) 成功探索。 挿入された順にキーを $k_1, k_2, \ldots, k_n$ とします。先頭挿入なので、$k_i$ を探すときにリスト上で $k_i$ より前にあるのは「$k_i$ より後に挿入され、かつ $k_i$ と同じスロットに写ったキー」です。$j > i$ に対して指標変数 $X_{ij} = 1$（$h(k_i) = h(k_j)$ のとき）、$0$（それ以外）を定めると、単純一様ハッシュの仮定と独立性から

$$E[X_{ij}] = \Pr[h(k_i) = h(k_j)] = \sum_{s=0}^{m-1} \Pr[h(k_i) = s]\Pr[h(k_j) = s] = m \cdot \frac{1}{m^2} = \frac{1}{m}$$

です。$k_i$ の探索で調べる要素数は $1 + \sum_{j=i+1}^{n} X_{ij}$（$k_i$ 自身の 1 個と、前に並ぶキーの個数）なので、どのキーを探すかについて平均を取ると

$$\begin{aligned} \frac{1}{n}\sum_{i=1}^{n} E\!\left[1 + \sum_{j=i+1}^{n} X_{ij}\right] &= \frac{1}{n}\sum_{i=1}^{n}\left(1 + \frac{n-i}{m}\right) \\ &= 1 + \frac{1}{nm}\sum_{i=1}^{n}(n-i) \\ &= 1 + \frac{1}{nm}\cdot\frac{n(n-1)}{2} \\ &= 1 + \frac{n-1}{2m} = 1 + \frac{\alpha}{2} - \frac{\alpha}{2n} \end{aligned}$$

を得ます。途中で $\sum_{i=1}^{n}(n-i) = \sum_{t=0}^{n-1} t = n(n-1)/2$ を、最後の等号では $\frac{1}{2m} = \frac{n/m}{2n} = \frac{\alpha}{2n}$ を使いました。この値は $1$ 以上 $1 + \alpha/2$ 以下なので、時間は $\Theta(1+\alpha)$ です。

∎

Corollary 5.4（負荷率を定数に保てば定数時間）

$m = \Omega(n)$、すなわち $\alpha = O(1)$ を保つなら、チェイン法による辞書（Definition 2.1）の探索・挿入・削除はいずれも期待 $O(1)$ 時間です。

Proof（Corollary 5.4）

探索は Theorem 5.3 から期待 $\Theta(1+\alpha) = O(1)$ です。挿入は、同じキーが無いことが分かっているならリスト先頭に繋ぐだけで最悪 $O(1)$、重複を排除するなら先に探索するので期待 $O(1)$ です。削除は、双方向連結リストを使い削除対象の要素への参照が与えられていれば最悪 $O(1)$、キーだけが与えられた場合は探索を伴うので期待 $O(1)$ です。

∎

Example 5.5（チェイン法を手で動かす）

$m = 8$、$h(k) = k \bmod 8$ とし、$5, 13, 21, 9, 4$ をこの順に挿入します。$h(5) = 5$, $h(13) = 5$, $h(21) = 5$, $h(9) = 1$, $h(4) = 4$ なので、先頭挿入の結果は

$$T[1] = (9),\quad T[4] = (4),\quad T[5] = (21, 13, 5),\quad \text{他は空}$$

です。$13$ の探索は $h(13) = 5$ のリストを先頭から見て、$21$（不一致）、$13$（一致）の 2 回の比較で成功します。$29$ の探索は $h(29) = 5$ なので $21, 13, 5$ の 3 回を比較して不成功に終わります。

負荷率は $\alpha = 5/8 = 0.625$ で、Theorem 5.3 の (1) が予言する不成功探索の期待走査数は $0.625$ 回ですが、実際には 3 回かかりました。矛盾ではありません。定理は「キーが一様ランダムに散る」という仮定の下での期待値であり、いま選んだ 5 個は仮定から見て極端に運の悪い配置だからです。しかも $h(k) = k \bmod 8$ を使う限り、8 の倍数だけ離れたキーは必ず衝突します。仮定は現実には成り立ちません。次の節がこの穴を塞ぎます。

5.3. 仮定を捨てる：万能ハッシュ族

Theorem 5.3 の弱点は、確率がデータの側にあることです。入力がどう分布するかは、たいていの場合こちらには決められません。そこで、確率の出どころをアルゴリズム自身のコイン投げに移します。ハッシュ関数を 1 つに固定せず、族から実行時にランダムに選ぶのです。

Definition 5.6（万能ハッシュ族）

$\mathcal{H}$ を $U$ から $\{0, 1, \ldots, m-1\}$ への関数からなる有限集合とします。任意の相異なる $k, l \in U$ に対して

$$\Pr_{h \in \mathcal{H}}\left[\, h(k) = h(l) \,\right] \le \frac{1}{m}$$

が成り立つとき（確率は $\mathcal{H}$ から一様に選ばれる $h$ についてのもの）、$\mathcal{H}$ を万能（universal）であるといいます。

Theorem 5.7（万能族なら入力の分布を仮定しなくてよい）

$\mathcal{H}$ を万能ハッシュ族とし、$h$ を $\mathcal{H}$ から一様ランダムに選んで $m$ スロットの表に使います。$S \subseteq U$ を $|S| = n$ である任意のキー集合（$h$ の選択と無関係に定められたもの）とし、チェイン法で格納します。このとき任意のキー $k \in U$ に対して、$k$ と同じスロットに入る $S \setminus \{k\}$ の元の個数 $Y_k$ の期待値は $\alpha = n/m$ 以下です。

Proof（Theorem 5.7）

$l \in S \setminus \{k\}$ について指標変数 $Z_l = 1$（$h(l) = h(k)$ のとき）、$0$（それ以外）とすると $Y_k = \sum_{l \in S \setminus \{k\}} Z_l$ です。$l \ne k$ なので Definition 5.6 がそのまま使えて $E[Z_l] = \Pr[h(l) = h(k)] \le 1/m$ です。期待値の線形性から

$$E[Y_k] = \sum_{l \in S \setminus \{k\}} E[Z_l] \le \frac{|S \setminus \{k\}|}{m} \le \frac{n}{m} = \alpha$$

を得ます。$k$ の探索で走査するリスト要素数は高々 $Y_k + 1$ なので、探索時間の期待値は $O(1 + \alpha)$ です。

∎

この定理には「データがランダムである」という仮定がどこにもありません。入力は敵が選んでよく、それでも期待値は $\alpha$ 以下です。ランダムなのは $h$ の選び方だけで、敵は $h$ を知らないからです。

Remark 5.8（具体的な万能族と、ハッシュ衝突攻撃）

Carter と Wegman は、$|U|$ より大きい素数 $p$ を取り、$a \in \{1, \ldots, p-1\}$、$b \in \{0, \ldots, p-1\}$ に対して

$$h_{a,b}(k) = \left(\,(a k + b) \bmod p \,\right) \bmod m$$

と定めた族 $\mathcal{H} = \{h_{a,b}\}$ が万能であることを示しました（原論文および Cormen ほか『Introduction to Algorithms』第 11 章に証明があります）。$a, b$ をプログラム起動時に乱数で選べば Theorem 5.7 が使えます。

これは理論的な贅沢ではありません。Crosby と Wallach は 2003 年に、固定のハッシュ関数を使う Web アプリケーションに対して、意図的に衝突するキーを大量に送り込んで処理を $\Theta(n)$ に劣化させるサービス妨害攻撃を報告しました（Proposition 5.2 がこの攻撃が常に可能であることを保証しています）。現在の主要な言語処理系は、この対策として起動ごとにハッシュの種をランダム化しています。Python では文字列のハッシュ値がプロセスごとに変わり、環境変数 PYTHONHASHSEED で制御できます。

6. オープンアドレス法とリサイズ

6.1. 表の外に出ない衝突解決

連結リストはポインタの分だけ空間を食い、キャッシュ効率も悪くなります。全要素を表の中だけに置く方法がオープンアドレス法です。

Definition 6.1（オープンアドレス法）

$n \le m$ とし、すべてのキーを表 $T[0..m-1]$ に直接格納します。探査関数 $h : U \times \{0, 1, \ldots, m-1\} \to \{0, \ldots, m-1\}$ を、各キー $k$ について探査列 $\langle h(k,0), h(k,1), \ldots, h(k,m-1)\rangle$ が $\{0, \ldots, m-1\}$ の並べ替えになるように定めます。

• 挿入：$i = 0, 1, 2, \ldots$ の順に $T[h(k,i)]$ を調べ、最初に見つかった空スロットに置く。
• 探索：同じ順に調べ、キーが一致すれば成功。空スロットに当たったら「無い」と答えて終了する。

代表的な探査法は次の 3 つです。

• 線形探査：$h(k,i) = (h'(k) + i) \bmod m$
• 二次探査：$h(k,i) = (h'(k) + c_1 i + c_2 i^2) \bmod m$（$c_1, c_2, m$ は探査列が表全体を覆うように選ぶ）
• 二重ハッシュ：$h(k,i) = (h_1(k) + i \cdot h_2(k)) \bmod m$（$h_2(k)$ は $m$ と互いに素でなければならない。$m$ を素数にして $1 \le h_2(k) \le m-1$ とすればよい）

$h_2(k)$ と $m$ が互いに素でなければならない理由は、そうでないと探査列が表全体を覆わないからです。$g = \gcd(h_2(k), m) > 1$ なら、$i h_2(k) \bmod m$ が動く範囲は $g$ の倍数だけ、すなわち $m/g$ 個のスロットに限られ、空きがあるのに挿入に失敗する事態が起こります。

6.2. 削除には墓標が要る

オープンアドレス法で削除するとき、そのスロットをただ空にしてはいけません。探索は空スロットに当たった時点で「無い」と結論するので、探査列の途中に穴が空くと、その先のキーが見つからなくなります。そこで「削除済み」を表す印（墓標）を書き込み、探索はそこを通過し、挿入はそこを再利用します。

Example 6.2（線形探査を手で動かし、素朴な削除を壊す）

$m = 8$、$h'(k) = k \bmod 8$ の線形探査で $5, 13, 21, 4$ をこの順に挿入します。

• $5$：$h(5,0) = 5$ が空なので $T[5] = 5$。
• $13$：$h(13,0) = 5$ は埋まっている。$h(13,1) = 6$ が空なので $T[6] = 13$。探査 2 回。
• $21$：$5, 6$ が埋まっているので $h(21,2) = 7$ に置く。探査 3 回。
• $4$：$h(4,0) = 4$ が空なので $T[4] = 4$。探査 1 回。

結果は $T[4..7] = (4, 5, 13, 21)$ という長さ 4 のかたまりです。ここで $21$ を探すと、スロット $5$（$5 \ne 21$）、$6$（$13 \ne 21$）、$7$（一致）で 3 回の探査を要します。

次に $13$ を削除して $T[6]$ を単に空にしてみます。すると $21$ の探索は、スロット $5$（不一致）、スロット $6$（空）で打ち切られ、表の中に $21$ があるにもかかわらず「無い」と答えます。これが墓標が必要な理由です。

ついでに $12$ を挿入すると、$h(12,0) = 4$ から $5, 6, 7$ まで埋まっているので $0$ に回り込み、探査 5 回かかります。かたまりが長いほど新しい挿入が高くつく、この現象を一次クラスタリングと呼びます（Exercise 8.3 で定量化します）。

6.3. 探査回数の評価

Theorem 6.3（オープンアドレス法の期待探査回数）

一様ハッシュの仮定、すなわち各キーの探査列が $\{0, 1, \ldots, m-1\}$ の $m!$ 通りの並べ替えから一様ランダムに、他のキーと独立に選ばれると仮定します。表に $n$ 個のキーが格納されており $\alpha = n/m < 1$ とすると、

1. 不成功探索の探査回数の期待値は $\dfrac{1}{1-\alpha}$ 以下です。
2. 表にあるキーの探索（どのキーを探すかは等確率）の探査回数の期待値は $\dfrac{1}{\alpha}\ln\dfrac{1}{1-\alpha}$ 以下です。

(1) の証明は Appendix に置きます。(2) は、あるキーの探索コストがそのキーを挿入したときの探査回数に等しいことを使い、(1) を $n$ 個の挿入時点について平均して積分で評価します（Cormen ほか『Introduction to Algorithms』第 11 章）。

この式の意味は数値にすると明快です。

負荷率 $\alpha$	一様ハッシュ・不成功 $\frac{1}{1-\alpha}$	線形探査・不成功 $\frac{1}{2}\left(1 + \frac{1}{(1-\alpha)^2}\right)$
0.50	2.0	2.5
0.75	4.0	8.5
0.90	10.0	50.5
0.95	20.0	200.5

右列は線形探査に対する Knuth の解析（『The Art of Computer Programming』第 3 巻 §6.4）による値で、原因は Example 6.2 で見たかたまりです。表が 9 割埋まると探査が 50 回、$\Theta(1)$ という漸近的な主張が実際の速度を保証しないことの好例です。だから実装では、負荷率が閾値（0.5 から 0.75 程度）を超えたら表を作り直します。

6.4. リサイズのならし計算量

Proposition 6.4（倍々リサイズのならし計算量）

空のハッシュ表（初期容量 $m_0 \ge 1$）から始め、負荷率が $1/2$ に達するたびに容量を 2 倍にして全要素を新しい表に入れ直すとします。1 回のキー挿入自体の費用と、1 個の要素の入れ直しの費用をそれぞれ定数とみなすと、$n$ 回の挿入にかかる総費用は $O(n)$ です。すなわち 1 回の挿入あたりのならし費用は $O(1)$ です。

Proof（Proposition 6.4）

容量は $m_0, 2m_0, 4m_0, \ldots$ と推移します。容量 $m_j = 2^j m_0$ の表からの作り直しは、要素数が $m_j / 2$ に達したときに起こり、そのとき移し替える要素は $m_j/2$ 個なので費用は定数 $c$ を用いて $c\, m_j / 2$ と書けます。

$n$ 回の挿入の間に起こる作り直しは、$m_j/2 \le n$ を満たす $j$ についてのものだけです。そのような $j$ の最大値を $J$ とすると、作り直しの総費用は

$$\sum_{j=0}^{J} \frac{c\, m_j}{2} = \frac{c\,m_0}{2}\sum_{j=0}^{J} 2^{j} = \frac{c\,m_0}{2}\left(2^{J+1} - 1\right) < c\, m_0 2^{J} = c\, m_J \le 2cn$$

です。等比数列の和 $\sum_{j=0}^{J} 2^j = 2^{J+1}-1$ と、$J$ の取り方から $m_J/2 \le n$ すなわち $m_J \le 2n$ であることを使いました。これに挿入そのものの費用 $O(n)$ を足しても総費用は $O(n)$ で、1 回あたり $O(1)$ です。

なお、個々の挿入は最悪 $\Theta(n)$ 時間かかります（作り直しに当たったとき）。ならし計算量が保証するのは操作列全体の総和であって、各操作の上界ではありません。同じ等比級数の議論は動的配列の倍々拡張にもそのまま当てはまります（Theorem 3.3［Fundamental Data Structures］）。

∎

Remark 6.5（「平均 O(1)」の 3 つの意味）

ここまでで、性質の違う 3 種類の「平均」が出てきました。混同すると議論が噛み合いません。

• 入力の分布に関する平均：ランダムなのは入力データです（Theorem 5.3）。単純一様ハッシュが現実に成り立つ保証はありません（Example 5.5）。
• 乱択アルゴリズムの期待値：ランダムなのはアルゴリズムが選ぶハッシュ関数で、入力は任意でよい（Theorem 5.7）。実務で頼れるのはこちらです。
• ならし（償却）計算量：ランダムな要素はどこにもなく、操作列全体の総費用を操作数で割った決定的な上界です（Proposition 6.4）。償却と平均が別物であることは Remark 3.5［Fundamental Data Structures］ でも注意しました。

現代のハッシュ表は後ろ 2 つを組み合わせています。種をランダム化したハッシュ関数を使い、負荷率が閾値を超えたら倍々に拡張するのです。

7. どの構造を選ぶか

辞書（Definition 2.1）の 3 操作について、これまでの結果と既出の構造を並べます。$n$ は要素数、$k$ は範囲検索が返す要素数です。

構造	探索	挿入	削除	最小値・範囲検索	根拠
未整列の配列・連結リスト	$\Theta(n)$	$O(1)$	$\Theta(n)$	$\Theta(n)$	Proposition 2.3
ソート済み配列	$\Theta(\log n)$	$\Theta(n)$	$\Theta(n)$	$O(\log n + k)$	Theorem 3.3、Corollary 4.2
平衡二分探索木	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n + k)$	基本的なデータ構造
ハッシュ表	期待 $O(1)$、最悪 $\Theta(n)$	期待 $O(1)$	期待 $O(1)$	$\Theta(n + m)$	Theorem 5.3、Proposition 5.2

選択の指針は次のとおりです。

• データが静的で範囲検索や整列出力が要るなら、ソート済み配列と二分探索がもっとも単純で速く、余分な空間も要りません。
• 挿入・削除が頻繁で順序も要るなら平衡二分探索木です。ハッシュ表と違って「$x$ 以上の最小の要素」を $O(\log n)$ で答えられます。
• 順序が要らないならハッシュ表が最速です。ただし最悪 $\Theta(n)$ であることと、外部から来るキーにはハッシュの種のランダム化が要ること（Remark 5.8）を忘れないでください。

なお、この記事で扱ったのは「キーの集合の中を探す」問題です。状態空間や地図のように要素が辺で繋がった構造を探す問題は幅優先探索・深さ優先探索の話題で、グラフアルゴリズム で扱います。同じ「探索」でも枠組みが違います。

8. 演習

Exercise 8.1易

lower_bound の判定を 1 か所だけ変えて、$\mathrm{ub}_A(x) = \#\{\, i \mid A[i] \le x \,\}$ を返す関数 upper_bound を作ってください。またそれを使って、昇順配列 $A$ に含まれる $x$ の個数を $O(\log n)$ 時間で求める方法を述べ、$A = [2,3,3,3,5,5,7]$、$x = 3$ で値を確かめてください。

Solution

判定を a[mid] < x から a[mid] <= x に変えるだけです。不変条件は「$i < lo \Rightarrow A[i] \le x$」「$i \ge hi \Rightarrow A[i] > x$」となり、Theorem 3.2 の証明と同じ議論（昇順性で片側の添字全体に条件を伝播させる）が通って、返り値は $\#\{i \mid A[i] \le x\}$ になります。

個数は、$\{ i \mid A[i] = x \} = \{ i \mid A[i] \le x\} \setminus \{ i \mid A[i] < x\}$ で、$A$ が昇順だから両方の集合は $\{0, \ldots, t-1\}$ の形の切片です。差は区間 $[\mathrm{lb}_A(x), \mathrm{ub}_A(x))$ となり、個数は $\mathrm{ub}_A(x) - \mathrm{lb}_A(x)$。二分探索 2 回なので比較回数は高々 $2(\lfloor \log_2 n\rfloor + 1)$ 回、$O(\log n)$ 時間です。

$A = [2,3,3,3,5,5,7]$、$x = 3$ では、$A[i] < 3$ なのは $A[0] = 2$ だけなので $\mathrm{lb} = 1$、$A[i] \le 3$ なのは $A[0..3]$ の 4 個なので $\mathrm{ub} = 4$。個数は $4 - 1 = 3$ で、確かに $3$ は 3 個あります。$n = 7$ なので比較回数の上界は $2(\lfloor \log_2 7\rfloor + 1) = 2 \times 3 = 6$ 回です。

Exercise 8.2標準

単純一様ハッシュの仮定（Theorem 5.3）のもとで、$n$ 個のキーを $m$ スロットに入れたとき、同じスロットに入るキーの対の個数 $X$ の期待値を求めてください。次に $m = 365$, $n = 23$ で数値を計算し、「同じスロットに入る対が少なくとも 1 つ存在する確率」が約 $0.507$ であることと比べて、両者の関係を説明してください。

Solution

$1 \le i < j \le n$ なる対に指標変数 $X_{ij} = 1$（$h(k_i) = h(k_j)$ のとき）、$0$（それ以外）を割り当てます。Theorem 5.3 の証明中で計算したとおり $E[X_{ij}] = 1/m$ です。対の総数は $\binom{n}{2}$ なので、期待値の線形性から

$$E[X] = \sum_{1 \le i < j \le n} E[X_{ij}] = \binom{n}{2}\frac{1}{m} = \frac{n(n-1)}{2m}.$$

$m = 365$, $n = 23$ では $E[X] = \dfrac{23 \times 22}{2 \times 365} = \dfrac{253}{365} = 0.6931\ldots$ です。一方、どの対も衝突しない確率は $\prod_{i=0}^{22}\left(1 - \frac{i}{365}\right) = 0.4927\ldots$ なので、少なくとも 1 対衝突する確率は $1 - 0.4927 = 0.5073$ です。

両者は別の量です。$E[X] \approx 0.69$ は「衝突対の個数の平均」で、0 対の場合と 2 対以上の場合を均した値です。マルコフの不等式 $\Pr[X \ge 1] \le E[X]$ が両者を結びつけており、実際 $0.507 \le 0.693$ で整合しています。

一般に $E[X] \approx 1$ となるのは $n \approx \sqrt{2m}$ のときで、$m = 10^6$ のスロットでも $n$ が 1400 程度あれば衝突が起こるのが普通です。衝突処理はハッシュ表の付随機能ではなく本体です。

Exercise 8.3難

線形探査（Definition 6.1）で、占有されたスロットが連続して $L$ 個並び、その両隣が空である状態（長さ $L$ のかたまり）を考えます。次に挿入されるキー $k$ について $h'(k)$ が $\{0, \ldots, m-1\}$ 上の一様分布に従うとき、このかたまりの長さが $L+1$ 以上になる確率を求めてください。孤立した空スロット 1 個が埋まる確率と比べて、何が起こるかを述べてください。

Solution

かたまりが占める $L$ 個のスロットのいずれかに $h'(k)$ が落ちた場合、線形探査は右へ進み、かたまりの直後にある空スロットに $k$ を置きます。その結果、長さは $L+1$ になります。また $h'(k)$ がかたまりの直前の空スロットに落ちた場合も、そこが埋まってかたまりは長さ $L+1$ になります（左に伸びる）。この $L+1$ 個以外のスロットに落ちた場合はかたまりの長さは変わりません。$h'(k)$ は一様なので、求める確率は

$$\frac{L+1}{m}$$

です。これに対して、周囲が埋まっていない孤立した空スロット 1 個が埋まる確率は、そこにちょうど $h'(k)$ が落ちる場合だけなので $1/m$ です。

したがって、長いかたまりほど速く成長します。$L$ が大きくなるほど吸い込む確率が上がるという正のフィードバックがあり、これを一次クラスタリングといいます。Example 6.2 で $12$ の挿入に 5 回の探査を要したのは、長さ 4 のかたまりができていたためです。

定量的には、線形探査の不成功探索の期待探査回数は $\frac{1}{2}\left(1 + \frac{1}{(1-\alpha)^2}\right)$ であり（第 6 節の表）、$\alpha = 0.9$ では一様ハッシュを仮定した Theorem 6.3 の 5 倍かかります。対策は負荷率を 0.5 前後に保つか、二重ハッシュのように探査の刻み幅をキーごとに変えてかたまりの成長を断つことです。ただし線形探査は連続領域を舐めるためキャッシュとの相性がよく、負荷率を低く保てば実測で速いこともあります。漸近的な式だけで優劣を決めないでください。

参考文献

• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022 — 第 11 章（ハッシュ表：チェイン法、万能ハッシュ、オープンアドレス法）。邦訳は『アルゴリズムイントロダクション』（近代科学社）。
• D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998 — §6.2.1（順序付き表の探索と二分探索の歴史）、§6.4（ハッシュ法と線形探査の解析、および歴史的注記）。
• J. Bentley, Programming Pearls, 2nd ed., Addison-Wesley, 2000 — コラム 4（二分探索を不変条件から正しく書く）。
• J. Bloch, “Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts Are Broken”, Google Research Blog, 2006.
• J. L. Carter, M. N. Wegman, “Universal classes of hash functions”, Journal of Computer and System Sciences 18(2) (1979), 143–154.
• S. A. Crosby, D. S. Wallach, “Denial of Service via Algorithmic Complexity Attacks”, Proceedings of the 12th USENIX Security Symposium, 2003.

Appendix: オープンアドレス法の不成功探索の証明

準備：期待値の裾表示。 値が非負整数の確率変数 $X$ について $E[X] = \sum_{i \ge 1} \Pr[X \ge i]$ が成り立ちます。実際、$\Pr[X \ge i] = \sum_{v \ge i} \Pr[X = v]$ を代入して和の順序を交換すると

$$\sum_{i\ge 1}\Pr[X \ge i] = \sum_{i \ge 1}\sum_{v \ge i}\Pr[X = v] = \sum_{v \ge 1} v \Pr[X = v] = E[X]$$

となります（各 $v$ に対して $i = 1, \ldots, v$ の $v$ 回だけ $\Pr[X=v]$ が現れることを使いました）。

Theorem 6.3 の (1) の証明。 一様ハッシュを仮定し、$n$ 個のキーが格納された表で、格納されていないキーを探索するときの探査回数を $X$ とします。探索は空スロットに当たるまで続くので、「$X \ge i$」は「最初の $i-1$ 回の探査がすべて占有スロットに当たった」ことと同値です。

一様ハッシュの仮定から、探査列は $m$ 個のスロットの一様ランダムな並べ替えです。第 1 探査が占有スロットに当たる確率は $n/m$ です。それが起こったという条件のもとで、第 2 探査は残り $m-1$ 個のスロットのどれかを等確率で見ることになり、そのうち占有されているのは $n-1$ 個なので、条件付き確率は $(n-1)/(m-1)$ です。以下同様に、$j$ 回目の探査が占有スロットに当たる条件付き確率は $(n-j+1)/(m-j+1)$ です。よって

$$\Pr[X \ge i] = \frac{n}{m}\cdot\frac{n-1}{m-1}\cdots\frac{n-i+2}{m-i+2}$$

です（$i - 1$ 個の因子の積、$i \le n+1$ のとき。$i > n+1$ なら確率は $0$）。

各因子を $\alpha = n/m$ で押さえます。$0 \le j < n \le m$ のとき

$$\frac{n-j}{m-j} \le \frac{n}{m} \iff m(n-j) \le n(m-j) \iff -mj \le -nj \iff nj \le mj$$

であり、最後の不等式は $n \le m$ と $j \ge 0$ から成り立ちます。したがって $\Pr[X \ge i] \le \alpha^{\,i-1}$ です。

以上を裾表示に代入し、$\alpha < 1$ による等比級数の収束を使うと

$$E[X] = \sum_{i \ge 1}\Pr[X \ge i] \le \sum_{i\ge 1}\alpha^{\,i-1} = \sum_{t \ge 0}\alpha^{t} = \frac{1}{1-\alpha}$$

を得ます。これが求める評価です。$\alpha \to 1$ で右辺が発散することが、表を満杯近くまで使ってはいけない理由を定量的に示しています。