データ構造の選び方 — 配列・リスト・スタック・ハッシュ・木
データ構造に優劣はありません。あるのはどの操作を速くして、どの操作を犠牲にしたかという設計の違いだけです。
配列は添字アクセスが速いかわりに、途中への挿入が遅い。連結リストはその逆。この対称性が分かると、選ぶ基準がはっきりします。
この章で学ぶこと
- 主要なデータ構造が、どの操作を速くしてどれを犠牲にしているか
- スタックとキューの取り出し順の違い
- ハッシュマップが平均
O(1)になる仕組みと、最悪の場合 - 木構造とトライ木がそれぞれ何のためにあるか
計算量 の O 記法を使います。
操作ごとの計算量
主要なデータ構造を並べます。n は要素数です。
| 添字アクセス | 検索 | 先頭に挿入 | 末尾に挿入 | 途中に挿入・削除 | |
|---|---|---|---|---|---|
| 配列 | O(1) | O(n) | O(n) | O(1) | O(n) |
| 連結リスト | O(n) | O(n) | O(1) | O(1) | O(1) ※ |
| ハッシュマップ | — | O(1) 平均 | — | O(1) 平均 | O(1) 平均 |
| 平衡二分探索木 | — | O(log n) | — | O(log n) | O(log n) |
※ 連結リストの「途中に挿入・削除」が O(1) なのは、その位置のノードを既に持っている場合です。位置を探すところから始めるなら、探索の O(n) が加わります。
配列 — 連続した領域に並べる
要素がメモリ上で連続して並んでいます。だから「先頭アドレス + 添字 × 要素サイズ」の計算だけで任意の要素に届きます。これが添字アクセス O(1) の正体です。
代わりに、途中への挿入や削除ではそれ以降の要素をすべてずらす必要があります。先頭への挿入なら全要素が動くので O(n) です。
連続していることには別の利点もあります。隣り合う要素が同じキャッシュラインに載るので、順に走査する処理は実測でかなり速くなります。計算量が同じ O(n) でも、配列の走査は連結リストの走査より速いのが普通です。
連結リスト — ノードが次を指す
各要素 (ノード) が値と「次のノードへの参照」を持ちます。メモリ上で連続している必要がありません。
挿入と削除は参照を 3 本つなぎ替えるだけなので、位置さえ分かっていれば O(1) です。要素をずらす必要がありません。
代わりに「5 番目の要素」を取りに行くには先頭から 5 回辿るしかなく、添字アクセスは O(n) です。この性質から、連結リストでは二分探索が効きません。中央へ飛べないためです。
連結リストが有効なのは、位置を保持したまま頻繁に挿入・削除する場合です。LRU キャッシュの実装で、ハッシュマップとリンクリストを組み合わせるのが典型です。ハッシュマップでノードへの参照を持っておき、リストのつなぎ替えを O(1) で行います。
スタックとキュー — 取り出す順が違う
この 2 つは「どこに入れてどこから出すか」だけが違います。
| 入れる場所 | 出す場所 | 取り出し順 | |
|---|---|---|---|
| スタック | 末尾 | 末尾 | LIFO (Last In, First Out) 後入れ先出し |
| キュー | 末尾 | 先頭 | FIFO (First In, First Out) 先入れ先出し |
**スタックは LIFO、キューが FIFO です。**この対応を逆に覚えていると、選ぶ場面で間違えます。
用途で覚えるほうが確実です。
| 使われる場面 | |
|---|---|
| スタック | 関数の呼び出し履歴 (コールスタック)、元に戻す操作、括弧の対応判定、深さ優先探索 |
| キュー | 印刷待ち行列、ジョブキュー、リクエストの受付、幅優先探索 |
「元に戻す」は直前の操作から戻すのでスタック、「順番待ち」は先に並んだ人からなのでキューです。どちらもグラフと探索で、探索の順序を決める部品として出てきます。
ハッシュマップ — 鍵から場所を計算する
キーをハッシュ関数に通して数値に変換し、その数値から配列上の位置を決めます。
探すときも同じ計算をするだけです。走査しないので平均 O(1) になります。ここが誤解されやすい点で、配列を走査するから速いのではありません。走査しないから速いのです。
最悪は O(n)
違うキーが同じ添字に割り当てられることがあります (衝突)。衝突した要素は連鎖などの形でまとめて保持されるので、取り出すときはその中を走査します。
すべてのキーが同じ添字に衝突すると、連鎖が n 個の一本道になり、探索は O(n) に退化します。実用上は良いハッシュ関数と適切なサイズ調整でこれを避けますが、保証されているのは平均であって最悪ではありません。
意図的に衝突するキーを大量に送り込んでサーバーを止める攻撃 (ハッシュ衝突攻撃) が成立するのは、この最悪値が理由です。多くの言語処理系がハッシュ関数に乱数の種を混ぜているのは、その対策です。
順序を持たない
ハッシュマップは格納順や大小の順序を保証しません。「キーの小さい順に取り出す」「範囲を指定して取り出す」といった操作が要るなら、木構造のほうが向いています。
木 — 階層と順序を保つ
二分探索木は、各ノードについて「左の子は自分より小さく、右の子は自分より大きい」を保ちます。だから探すときに毎回どちらかの枝を捨てられ、O(log n) になります。二分探索と同じ発想を、配列ではなくノードの連結で実現したものです。
ただし偏ると性能が落ちます。ソート済みのデータを順に挿入すると、右に伸び続けて実質的な連結リストになり O(n) に退化します。これを防ぐために、挿入や削除のたびに形を整える平衡二分探索木 (赤黒木、AVL 木) が使われます。
データベースのインデックスで使われる B-Tree も、同じ「毎回枝を捨てる」発想の木です。1 ノードに多くのキーを詰めることでディスクの読み取り回数を減らす設計になっています。
トライ木 — 文字列の前方一致に特化する
トライ木 (trie) は、文字列を 1 文字ずつ枝に対応させた木です。
cat / car / card を格納すると、共通する接頭辞 ca の部分が 1 本にまとまります。
この構造だと、「ca で始まる単語をすべて列挙する」が、ca のノードまで降りてその配下を辿るだけで済みます。単語数に関係なく、辿る長さは検索文字列の長さで決まります。
用途は前方一致に関わるものです。
- 検索窓のオートコンプリート
- 辞書の見出し語検索
- IP アドレスのルーティングテーブル (最長一致)
- 入力補完、スペルチェック
トライ木が扱うのは文字列の接頭辞です。グラフ上で最短経路を求める問題はグラフと探索が扱い、辺に重みがあるならダイクストラ法のような別のアルゴリズムが要ります。木という語が共通するので同じ話に見えることがありますが、解いている問題が違います。
選ぶ基準
| やりたいこと | 向いている構造 |
|---|---|
| 添字で高速に取り出す | 配列 |
| 順に全部なめる | 配列 (キャッシュに乗る) |
| 頻繁に途中へ挿入・削除する | 連結リスト |
| キーで高速に引く | ハッシュマップ |
| キーの順序や範囲が要る | 平衡二分探索木 |
| 後入れ先出しで処理する | スタック |
| 先入れ先出しで処理する | キュー |
| 文字列の前方一致で引く | トライ木 |
よくある誤解
「スタックは FIFO」 — スタックは LIFO です。FIFO はキューです。
「ハッシュマップが速いのは、探し方が賢いから」 — 探していないから速いのです。キーから格納位置を計算して直接そこへ行きます。1 件ずつ見ていく手順が入った時点で O(n) です。
「ハッシュマップは常に O(1)」 — 平均が O(1) で、衝突が集中すると最悪 O(n) です。
「連結リストは配列の上位互換」 — 添字アクセスが O(n) になり、キャッシュ効率も落ちます。挿入・削除が頻繁な場合に限って有利です。
「二分探索木なら常に O(log n)」 — 偏ると O(n) に退化します。保証するには平衡化が要ります。
確認問題
問 1. ブラウザの「戻る」ボタンの履歴を保持するのに適したデータ構造はどれですか。
答え: スタック
「戻る」は直前に見たページへ移動する操作です。最後に訪れたページから順に取り出すので、後入れ先出し (LIFO) になります。
ページを開くたびに履歴へ積み (push)、「戻る」で最後の 1 件を取り出します (pop)。「進む」を実装するなら、戻したページを別のスタックへ積みます。
キュー (FIFO) を使うと、最初に訪れたページへ戻ってしまいます。
問 2. 100 万語の辞書から「pro で始まる単語」をすべて列挙します。ハッシュマップとトライ木のどちらが向いていますか。
答え: トライ木
ハッシュマップはキーの完全一致でしか引けません。前方一致で探すには全 100 万件を走査して先頭 3 文字を比較するしかなく O(n) です。ハッシュ値は元の文字列の順序も接頭辞の情報も保持しないので、この用途には使えません。
トライ木なら根から p → r → o と 3 段降りるだけで、その配下がすべて「pro で始まる単語」です。降りるコストは検索文字列の長さ (3) で決まり、辞書の総語数には依存しません。
これがオートコンプリートでトライ木が使われる理由です。
問 3. 「配列の先頭から要素を取り出し続ける」処理が遅いと報告されました。原因と対策は何ですか。
答え: 配列の先頭削除が O(n) で、全体が O(n²) になっているためです。
配列は要素が連続して並んでいるので、先頭を削除すると残り全部を 1 つずつ前へずらします。1 回あたり O(n) で、n 回繰り返せば O(n²) です。
対策は 2 つあります。
- キューとして適した構造を使う — 連結リストなら先頭の削除が
O(1)です - 削除せず読み取り位置だけ進める — 先頭の添字を持つ変数を 1 つ用意し、取り出すたびに増やします。配列は変更しないので 1 回
O(1)です
2 つ目は「リングバッファ」の考え方で、要素を実際に動かさずにキューを実現します。データ構造を変えられない場面でも、操作の仕方を変えれば計算量を落とせることがあります。
まとめ
- データ構造の違いは「どの操作を速くして、どれを犠牲にしたか」です
- 配列は添字アクセスが
O(1)、途中への挿入・削除がO(n)。連結リストはその逆です - スタックは LIFO (後入れ先出し)、キューは FIFO (先入れ先出し) です
- ハッシュマップが平均
O(1)なのは、走査せずキーから位置を計算するためです。衝突が集中すると最悪O(n)に退化します - ハッシュマップは順序を持ちません。順序や範囲が要るなら平衡二分探索木です
- 二分探索木は偏ると
O(n)になります。平衡化してO(log n)を保ちます - トライ木は文字列の前方一致のための構造で、経路の最適化とは無関係です
- データベース設計ガイド — インデックス設計入門 — B-Tree インデックスが検索を速くする仕組み
次に読む
- ビット演算 — 真偽値の集合を 1 つの整数で持つ方法