## 2. 準備：探索問題と 2 つの計算モデル
まず、これから何を実装しようとしているのかを抽象データ型として固定します。
キーの集合 $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 つ用意します。どちらの土俵に立つかで結論が変わります。
キーの集合 $U$ に全順序 $\le$ が与えられているとします。アルゴリズムがキーについて行える操作が「2 つのキー $k, l$ を比べて $k < l$, $k = l$, $k > l$ のいずれであるかを知る」ことだけであるとき、そのアルゴリズムは**比較モデル**で動くといいます。キーの値を使った算術（下位ビットを取り出す、$(k - a)/(b - a)$ を計算する、など）は比較モデルでは禁止されます。
これに対し、キーをビット列とみなして算術や添字計算に使ってよい土俵を、ここでは**アドレス計算モデル**（語 RAM モデル）と呼びます。整数の加減乗除・剰余・ビット演算と、配列の添字アクセスが 1 単位時間でできるものとします。これは
これはソートの下界を論じるときに使った
と同じ制約です。比較モデルの利点は汎用性です。キーが文字列でも日付でもユーザ定義の構造体でも、比較さえ定義されていれば同じアルゴリズムが動きます。代償として、第 4 節で見るとおり $\log n$ の壁が生じます。
土台として、線形探索の費用を確定させておきます。
長さ $n$ の配列 $A[0..n-1]$ の要素はすべて相異なるとし、キー $x$ を $A[0], A[1], \ldots$ の順に比べていく線形探索を考えます。
1. $x$ が $A$ のどこにも現れないとき、比較回数はちょうど $n$ 回です。
2. $x$ が $A$ のいずれかの位置に等確率で現れるとき、比較回数の期待値は $(n+1)/2$ 回です。
いずれの場合も計算量は $\Theta(n)$ です。
(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$」という仕様は、実は扱いにくい仕様です。重複キーがあるとどの添字を返すか曖昧ですし、「無かった」ときに挿入すべき位置が分かりません。そこで境界を返す形に定義し直します。
昇順にソートされた配列 $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. アルゴリズム
```python
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 つの条件で表せ、場合分けが減ります。
### 3.3. 正しさ
$A[0..n-1]$ を昇順にソートされた配列（$n \ge 0$）、$x$ を任意のキーとします。このとき `lower_bound(a, x)` は必ず停止し、$\mathrm{lb}_A(x)$ を返します。
次の 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. 計算量
$n \ge 1$ とします。
### 3.5. 配列でなくてもよい：述語の二分探索
二分探索が使えるための本質的な条件は「配列がソートされていること」ではなく、**判定が単調であること**です。真偽値を返す述語 $P$ が $P(0) \le P(1) \le \cdots$（偽が続いた後に真が続く）を満たすなら、同じ手続きで「$P$ が真になる最小の点」を求められます。$A[i] < x$ という述語はその特別な場合です。
非負整数 $N$ に対して $\lfloor \sqrt{N} \rfloor$、つまり $v^2 \le N$ を満たす最大の整数 $v$ を求めます。述語 $P(v) = (v^2 > N)$ は $v$ について単調（$v$ が大きくなると偽から真に一度だけ変わる）なので、二分探索できます。
```python
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)$ 下界（
）とまったく同じ道具立てで、葉の個数を下から、木の深さを上から押さえます。
$n \ge 1$ とします。比較モデル（
## 5. ハッシュ表：キーから住所を計算する
### 5.1. 直接アドレス表とその破綻
キーが $0$ 以上 $|U|-1$ 以下の整数なら、長さ $|U|$ の配列 $T$ を用意して $T[k]$ に値を置けば、探索・挿入・削除はすべて最悪 $O(1)$ です。これを直接アドレス表といいます。問題は空間です。キーが 64 ビット整数なら $|U| = 2^{64} \approx 1.8 \times 10^{19}$ 個のスロットが要り、格納するキーが 1000 個でも不可能です。文字列キーならさらに絶望的です。
そこで、大きなキー空間 $U$ を小さな添字空間に**押し込む**関数を挟みます。
$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$ を**負荷率**と呼びます。
$|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$ がその全部を同一のスロットに写すものが存在します。
前半は鳩の巣原理です。$|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. チェイン法
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（空）"]`} />
チェイン法では、$T[j]$ に「$h(k) = j$ であるキーの連結リスト」への参照を置きます。挿入はリストの先頭に繋ぐだけ、探索は $T[h(k)]$ のリストを走査、削除はリストから外します。連結リストの基本操作は [基本的なデータ構造](/computer-science/algorithms/data-structures) で扱ったとおりです（
）。
$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)$ です。
**(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)$ です。
$m = \Omega(n)$、すなわち $\alpha = O(1)$ を保つなら、チェイン法による辞書（
### 5.3. 仮定を捨てる：万能ハッシュ族
の弱点は、確率がデータの側にあることです。入力がどう分布するかは、たいていの場合こちらには決められません。そこで、確率の出どころを**アルゴリズム自身のコイン投げ**に移します。ハッシュ関数を 1 つに固定せず、族から実行時にランダムに選ぶのです。
$\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）であるといいます。
$\mathcal{H}$ を万能ハッシュ族とし、$h$ を $\mathcal{H}$ から一様ランダムに選んで $m$ スロットの表に使います。$S \subseteq U$ を $|S| = n$ である**任意の**キー集合（$h$ の選択と無関係に定められたもの）とし、チェイン法で格納します。このとき任意のキー $k \in U$ に対して、$k$ と同じスロットに入る $S \setminus \{k\}$ の元の個数 $Y_k$ の期待値は $\alpha = n/m$ 以下です。
$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$ なので
この定理には「データがランダムである」という仮定がどこにもありません。入力は敵が選んでよく、それでも期待値は $\alpha$ 以下です。ランダムなのは $h$ の選び方だけで、敵は $h$ を知らないからです。
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$ をプログラム起動時に乱数で選べば
## 6. オープンアドレス法とリサイズ
### 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. 削除には墓標が要る
オープンアドレス法で削除するとき、そのスロットをただ空にしてはいけません。探索は空スロットに当たった時点で「無い」と結論するので、探査列の途中に穴が空くと、その先のキーが見つからなくなります。そこで「削除済み」を表す印（墓標）を書き込み、探索はそこを通過し、挿入はそこを再利用します。
$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 回かかります。かたまりが長いほど新しい挿入が高くつく、この現象を一次クラスタリングと呼びます（
### 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）による値で、原因は
で見たかたまりです。表が 9 割埋まると探査が 50 回、$\Theta(1)$ という漸近的な主張が実際の速度を保証しないことの好例です。だから実装では、負荷率が閾値（0.5 から 0.75 程度）を超えたら表を作り直します。
### 6.4. リサイズのならし計算量
空のハッシュ表（初期容量 $m_0 \ge 1$）から始め、負荷率が $1/2$ に達するたびに容量を 2 倍にして全要素を新しい表に入れ直すとします。1 回のキー挿入自体の費用と、1 個の要素の入れ直しの費用をそれぞれ定数とみなすと、$n$ 回の挿入にかかる総費用は $O(n)$ です。すなわち 1 回の挿入あたりのならし費用は $O(1)$ です。
容量は $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)$ 時間かかります（作り直しに当たったとき）。ならし計算量が保証するのは操作列全体の総和であって、各操作の上界ではありません。同じ等比級数の議論は動的配列の倍々拡張にもそのまま当てはまります（
## 7. どの構造を選ぶか
辞書（
）の 3 操作について、これまでの結果と既出の構造を並べます。$n$ は要素数、$k$ は範囲検索が返す要素数です。
| 構造 | 探索 | 挿入 | 削除 | 最小値・範囲検索 | 根拠 |
|---|---|---|---|---|---|
| 未整列の配列・連結リスト | $\Theta(n)$ | $O(1)$ | $\Theta(n)$ | $\Theta(n)$ |
|
| ソート済み配列 | $\Theta(\log n)$ | $\Theta(n)$ | $\Theta(n)$ | $O(\log n + k)$ |
、
|
| 平衡二分探索木 | $O(\log n)$ | $O(\log n)$ | $O(\log n)$ | $O(\log n + k)$ | [基本的なデータ構造](/computer-science/algorithms/data-structures) |
| ハッシュ表 | 期待 $O(1)$、最悪 $\Theta(n)$ | 期待 $O(1)$ | 期待 $O(1)$ | $\Theta(n + m)$ |
、
|
選択の指針は次のとおりです。
- データが静的で範囲検索や整列出力が要るなら、ソート済み配列と二分探索がもっとも単純で速く、余分な空間も要りません。
- 挿入・削除が頻繁で順序も要るなら平衡二分探索木です。ハッシュ表と違って「$x$ 以上の最小の要素」を $O(\log n)$ で答えられます。
- 順序が要らないならハッシュ表が最速です。ただし最悪 $\Theta(n)$ であることと、外部から来るキーにはハッシュの種のランダム化が要ること（
）を忘れないでください。
なお、この記事で扱ったのは「キーの集合の中を探す」問題です。状態空間や地図のように要素が辺で繋がった構造を探す問題は幅優先探索・深さ優先探索の話題で、[グラフアルゴリズム](/computer-science/algorithms/graph-algorithms) で扱います。同じ「探索」でも枠組みが違います。
## 8. 演習
`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$ で値を確かめてください。
判定を `a[mid] < x` から `a[mid] <= x` に変えるだけです。不変条件は「$i < lo \Rightarrow A[i] \le x$」「$i \ge hi \Rightarrow A[i] > x$」となり、
## 参考文献
- 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"](https://research.google/blog/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]$ が現れることを使いました）。
**
の (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$ で右辺が発散することが、表を満杯近くまで使ってはいけない理由を定量的に示しています。