Mímisbrunnr知恵の泉

← コンピュータ基礎 一覧

🎓 レベル：基礎　|　重要度：A（必須）

📎 前提：計算量とオーダー記法　|　関連：基本アルゴリズム・メモリ階層とキャッシュ

要点（BLUF）

概念 ── 持ち方がコストを決める

データを「どう並べ、どう繋ぐか」で、操作の速さが変わります。万能のデータ構造はなく、ある操作を速くすると別の操作が遅くなるのが常。だから「この処理で頻繁にやる操作は何か」を見て選びます。

仕組み ── 4つの基本構造

配列（array）

メモリ上に要素を連続して並べる。base + i × 要素サイズ で位置を即計算できるので添字アクセスが O(1)（物理メモリと論理アドレス のアドレス計算そのもの）。連続ゆえキャッシュ局所性も抜群（メモリ階層とキャッシュ）。弱点は途中への挿入/削除が O(n)（後続を全部ずらす）と、サイズ変更が苦手。

連結リスト（linked list）

各要素（ノード）が「値＋次ノードへのポインタ」を持ち、メモリ上はバラバラでよい。位置が分かれば挿入/削除はポインタの繋ぎ替えだけで O(1)。弱点はi番目を得るのに先頭からn回辿る O(n)、ポインタのぶんメモリを食う、バラバラ配置でキャッシュミスが多い。

flowchart LR
    subgraph A["配列（連続・添字O(1)・挿入O(n)）"]
      a0["要素0"]-->a1["要素1"]-->a2["要素2"]-->a3["要素3"]
    end
    subgraph L["連結リスト（分散・添字O(n)・挿入O(1)）"]
      n0["値・next"]-->n1["値・next"]-->n2["値・next"]
    end

ハッシュ表（hash table）

キーをハッシュ関数で配列の添字に変換し、そこに値を置く。位置 = hash(key) mod 表サイズ。うまく散れば検索/挿入/削除が平均 O(1)。弱点は、異なるキーが同じ位置に来る衝突（チェイン法や開番地法で対処）と、最悪 O(n)、順序を保たないこと。OSのプロセステーブルやファイルのディレクトリ（ファイルシステムの構造）の高速ルックアップに使われます。

木（tree）/ 平衡二分探索木

階層構造。二分探索木は「左の子 < 親 < 右の子」を保ち、検索を木の高さぶん＝バランスが取れていれば O(log n) に。平衡木（赤黒木・AVL・B木）は挿入/削除でも高さを O(log n) に保つ。ハッシュと違い順序を保てる（範囲検索・ソート順の走査ができる）。DBのインデックスやファイルシステムのメタデータ管理に使われます。

仕組み ── 操作コスト早見表

データ構造添字アクセス検索挿入/削除順序保持
配列O(1)O(n)（未ソート）O(n)並べれば可
連結リストO(n)O(n)O(1)（位置既知）可
ハッシュ表―平均O(1)平均O(1)不可
平衡二分探索木―O(log n)O(log n)可

太字がその構造の「売り」。ハッシュは最速だが順序を捨て、木は少し遅いが順序を保つ――このトレードオフが選択の決め手です。

具体例 ── 「あるか調べる」を計測

同じ「存在確認」を、線形検索（配列）とハッシュ検索（集合）で比べます（[[#対応ラボ]] の 06-02_data_structures.py、n=100万）。

実行結果（実機・値は環境で変動）:

配列の添字アクセス lst[i]   :    100.0 ns   (O(1))
ハッシュ検索 (i in set)     :    100.0 ns   (平均 O(1))
線形検索 (i in list)       :   6797.8 us   (O(n)・末尾)
線形検索はハッシュ検索の約 67,977 倍遅い（n=1,000,000）

添字アクセスもハッシュ検索も一定時間（ns）。一方、配列を線形に探す検索はマイクロ秒オーダで、約7万倍遅い。「リストに in で含まれるか調べる」コードが遅いなら、set/dict に変えるだけで劇的に速くなる――その理由がこれです。

仕組みの直観 ── なぜこの設計か

⚠️ よくある誤解・落とし穴

対応ラボ

cs-foundations-study/labs/06-02_data_structures.py（実行して添字/ハッシュ/線形の速度差を確認済み）。

関連

← 第6章 計算量とデータ構造の基礎 目次