2026-08-05·無料·8分で読めます

データ構造の選び方 — 配列・ハッシュ・木・ヒープ

配列・ハッシュ表・木・ヒープが、それぞれ何を速くして何を諦めているのか。用途からの逆引き表と、トークナイザ・ベクトル検索・KVキャッシュといったAI実装で実際にどれが使われているかまで。

#data-structures #hash-table #tree #heap #algorithms

対象textタスクbasics

比喩: 台所の収納は「取り出したい順序」で決まる

同じ調味料でも、しまい方は用途で変わります。毎日使う塩と胡椒はコンロの脇に出しっぱなし——取るのが速いかわりに、場所を食い、数が増えると散らかります。乾物は種類ごとにラベルを貼った引き出しへ——名前が分かれば一発で取れるかわりに、「賞味期限が近い順に見せて」には答えられません。冷蔵庫の手前には期限が近いものを置く——常に「次に消費すべき1つ」だけがすぐ取れます。

データ構造の選択もこれと同じです。万能の収納は存在せず、どれも何かを速くする代わりに何かを諦めています。設計とは、自分のアクセスの仕方に合った諦め方を選ぶことです。

直感: 4つの道具と、それぞれの取引条件

道具は4つ覚えれば大半の場面が回ります。それぞれ「何が速いか」より先に「何を捨てたか」を見てください。

配列（動的配列・リスト）

$i$ 番目を取り出すのが $O(1)$ 。メモリ上で要素が連続して並ぶので、先頭から順に舐める操作は全構造の中で最速です（計算量の話で触れたキャッシュの効きが最大になる）。末尾への追加は、容量を倍々に拡張する実装ならならし $O(1)$ 。

諦めているのは途中への挿入と削除で、後続を全部ずらすため $O(n)$ です。値による検索も $O(n)$ （ソート済みなら二分探索で $O(\log n)$ ）。

ハッシュ表（辞書・集合）

キーを数値に潰して、その番号の棚に直接置きます。挿入・検索・削除がすべて平均 $O(1)$ 。件数が100万でも1000万でも1回の操作コストが変わらないのが強みです。

仕組みの中心は負荷率です。

\alpha = \frac{\text{格納された要素数}}{\text{バケット数}}

(1)

つまり、入れたものの個数を、置き場所である棚の数で割った値です。要素200個に対して棚が400個あれば $\alpha = 0.5$ ——半分は意図的に空けたまま持っている、ということ。

$\alpha$ は「棚の混み具合」です。混むほど別のキーが同じ棚に来る衝突が増え、性能が落ちます。だから実装は $\alpha$ が一定を超えると棚を増やして全要素を入れ直します（リハッシュ）。「平均 $O(1)$ 」は、この空き容量を常に抱えることで買っている性能です。

諦めているのは順序です。範囲検索も、次に大きい要素の取得も、ソート順の走査もできません。加えて最悪計算量は $O(n)$ 、そしてメモリのオーバーヘッドがそこそこ大きい。

木（平衡二分探索木・B木）

検索・挿入・削除がすべて $O(\log n)$ で、しかも順序が保たれます。 $n$ 個を左右に振り分けていくので、木の高さは

$h \approx \log_2 n$

つまり100万件でも約20回の比較でたどり着きます。 $n$ が1000倍になっても $h$ は10しか増えない——これが対数の効き方です。

順序が残るので、「100以上200以下を全部」「この値の次に大きいもの」「小さい順に全走査」が自然にできます。ハッシュ表より定数倍は重いので、順序が要らないなら使う理由はありません。

データベースの索引に使われるB木は、この考えを記憶階層に合わせて調整したものです。1ノードに多数のキーを詰めて分岐数を増やし、木を低くする。ノード1つがディスクやページの読み込み単位に一致するため、遅い記憶装置へのアクセス回数が減ります。

ヒープ（優先度付きキュー）

最小値（または最大値）を見るのが $O(1)$ 、追加と取り出しが $O(\log n)$ 。

代わりに諦めるのは、順序の全体です。ソートされているわけではなく、「親は子より小さい」という緩い条件しか持ちません。3番目に小さい要素をすぐには出せませんし、任意の値の検索は $O(n)$ です。

「常に次の1つだけが欲しい」場面——上位k件の維持、タスクのスケジューリング、ダイクストラ法の次ノード選択——では、全体をソートしないぶんヒープが最も安く済みます。

用途からの逆引き

やりたいこと	選ぶもの
添字で取る／端から全部走査する	配列
キーで引く・重複を消す	ハッシュ表
範囲で引く・順序どおりに並べる	平衡木（DBならB木）
常に最小／上位k件だけ欲しい	ヒープ
「〜で始まる」で引く・最長一致で切る	トライ（trie）
「見たことがあるか」を省メモリで（誤検出可）	ブルームフィルタ

トライは、共通の接頭辞を1本の枝にまとめた木です。文字を1つ読むごとに候補が絞られるので、補完や辞書引きに向きます。ブルームフィルタは「入っていない」を確実に、「入っている」を誤検出込みで答える構造で、正確さを捨てる代わりにメモリが劇的に小さくなります。

コードで見る、いちばんよくある置き換え

性能問題の大半は、ループの中で線形探索している箇所です。

# O(n*m): x in b が毎回 b を頭から走査する
def common_slow(a, b):
    return [x for x in a if x in b]

# O(n+m): 集合を1度だけ作る
def common_fast(a, b):
    bs = set(b)                       # 構築コスト O(m)
    return [x for x in a if x in bs]  # 判定は平均 O(1)

違いは1行、set(b) を先に作るかどうかだけです。 $n = m = 10^4$ なら前者は約1億回、後者は約2万回の操作になります。データ構造の選択が効くというのは、こういうことです。

AIの実装では、どれが使われているか

トークナイザ——語彙は「文字列→ID」のハッシュ表です。SentencePiece や WordPiece のように最長一致で切る方式は、語彙をトライに載せると1文字読むごとに候補が絞れて素直に速くなります。BPEでは、マージ規則の優先順位をハッシュで引き、「次に結合すべき組」をヒープで取り出す実装が一般的です。1つのトークナイザの中に3種類の構造が同居しています。

ベクトル検索——埋め込みの「近さ」は内積（正規化すればコサイン類似度）で測ります。まずこの量の気持ちを掴んでください。

FIG 1bの向きを回すと内積が変わる。ベクトル検索が測っているのはこの量で、これを何百万件ぶん比べることになる

$N$ 件すべてと内積を取れば $O(Nd)$ （ $d$ は次元数）で、これは百万件規模になると現実的ではありません。そこでグラフを使う索引（HNSWのように「近いもの同士を辺で結び、辺を辿って目的地へ降りていく」構造）や、事前にクラスタへ分けて候補を絞る索引が使われます。全件比較を諦めて近似解を受け入れる代わりに、探索が対数的に済む——これも典型的な取引です（RAGの基礎）。

KVキャッシュ——生成が1トークン進むごとに伸びていく配列です。長さが読めないものを連続領域で確保しようとすると断片化するため、OSの仮想メモリのように固定長のページに切り、ページ表で間接参照する方式が使われます。データ構造の教科書がそのまま推論エンジンに出てくる例です。

ビームサーチは上位k候補の維持にヒープ、データの重複除去はハッシュ（規模が大きければ近似的な手法）。特別な発明は要らず、道具は同じです。

実務で効く4つ

1. まず配列と辞書で書く 凝った構造は、プロファイラがそこを指してから入れます。多くの場合この2つで足りますし、足りないと分かってから選ぶほうが正しく選べます。

2. 「順序が要るか」を最初に決める ハッシュか木かの分岐はここだけです。後から範囲検索が必要になると、構造ごと入れ替えることになります。

3. 1件ずつ引くループを、まとめて引く形に変える 外部ストレージやAPIが相手なら、データ構造以前に往復回数が支配的です。キーを集めて一度に引き、返ってきたものを辞書にしてから使います。

4. メモリも計算量のうち ハッシュ表は空き容量を抱えて速度を買っています。件数が数千万を超えるなら、辞書1つのオーバーヘッドが効いてきます。ソート済み配列＋二分探索に落とすとメモリは減り、代わりに $O(\log n)$ を払う——これも時間と空間の取引です。

まとめ

どのデータ構造も「何かを速くして何かを諦める」。諦めた側が自分の用途に当たらないかで選ぶ
配列＝連続・添字が速い／ハッシュ＝平均 $O(1)$ だが順序なし／木＝ $O(\log n)$ で順序あり／ヒープ＝最小1つだけが速い
ハッシュ表の $O(1)$ は、負荷率 $\alpha$ を低く保つメモリと引き換えに買っている
ループ内の線形探索を集合・辞書に変えるだけで $O(n^2)$ が $O(n)$ になる
AI実装も同じ道具立て。トークナイザにトライとヒープ、ベクトル検索にグラフ索引、KVキャッシュにページ表

次は、表を持って再計算を避けるという発想を最も体系化した手法——動的計画法を扱います（動的計画法を1から）。