データ構造の選び方
1,023個のキーの中でない値を探すと、線形探索は1,023回、二分探索は10回比べます。1,023個のバケットのハッシュテーブルは、ラボでは最大6回でした。
どんな問いをするかから始める
何にでもいちばんよいデータ構造はありません。どれも、ある操作を安くする代わりに別の操作を高くしています。だから選ぶには、プログラムがいちばんよく行うことを書き出します。MITの6.006は、ありうる使い方を2つのインターフェースに分けています。列（シーケンス）は、項目をあなたが決めた順番（1番目、2番目、3番目）に保ち、位置で項目を求めます。集合（セット）は、項目をキーで保ち、あるキーがあるか、いちばん小さいキーは何か、あるキーの次のキーは何かを求めます。順序の問いを持たない集合は辞書と呼ばれます。
よくある場面と、ふつうの答えをいくつか挙げます。
- 位置で項目を読み、末尾に加える：動的配列（JavaScriptの配列）。
- 元に戻す履歴、かっこの対応、深さ優先探索：スタック。末尾だけを使う配列です。
- 届いた順に片づける仕事、幅優先探索：キュー。長い配列で shift を使うのではなく、head インデックスかリングバッファを使います。
- 名前やidで調べる：ハッシュテーブル。JavaScriptでは Map か Set です。
- 挿入や削除をしながらキーを整列させておき、次のキーを求める：つり合った二分探索木。
- すでに持っている場所で何度も挿入や削除をする：連結リスト。
5つの構造で同じ検索
下のラボは、同じキーを5通りの方法で保存し、その1つを見つけるのに必要な比較の回数を数えます。キーは15個、127個、または1,023個のランダムな整数です。整列していない配列は線形探索を使います。整列済みの配列は二分探索を使います。つり合った木は真ん中のキーから先に挿入して作ったので、できるだけ低くなっています。もう1つの木は整列した順にキーを入れて作ったので、鎖になっています。ハッシュテーブルはキーと同じ数のバケットを持ち、h(k) の計算を1と数えます。
ドラッグで回転、スクロールまたはピンチで拡大・縮小。
キーが15個なら差は小さく、線形探索は平均8回、二分探索は約3.3回です。キーが1,023個になると話は別です。線形探索は平均512回で、ないキーには1,023回かかりますが、二分探索とつり合った木は10回を超えることがありません。鎖の木は線形探索と同じくらい悪くなります。ハッシュテーブルはチェインが短いままなので、どの大きさでも平均2.3回から2.5回の間にとどまり、このラボでは1,023個のキーでの最悪の場合が6回でした。だから検索にはまず Map を選びます。整列した構造が割に合うのは、順序も必要なときだけです。
| 位置で | 項目 i を得る | 先頭で挿入・削除 |
|---|---|---|
| 動的配列 | 1 | n |
| 連結リスト | n | 1 |
| 整列済みの配列 | 1 | n |
| キーで | 検索 | 挿入 | 次のキー |
|---|---|---|---|
| 配列かリスト | n | n | n |
| 整列済みの配列 | log n | n | log n |
| ハッシュテーブル | 平均1 | 平均1 | n |
| つり合ったBST | log n | log n | log n |
この2つの表の各マスは、n 個の項目に対する費用の増え方を表しています。MITの講義ノート第2回・第4回・第7回の表にならっています。ハッシュテーブルと探索木が2つ目の表にしかないのは、位置ではなくキーで動くからです。整列していない配列やリストでは、キーの挿入に n かかります。まず、そのキーがまだないことを確かめなければならないからです。整列済みの配列は検索が速いものの、新しいキーの場所を空けるために値を動かす必要があります。
Mapかオブジェクトか
JavaScriptのプログラムでは、ふつうのオブジェクトを辞書として使い、prices["apple"] と書くことがよくあります。MDNは、キーがデータから来るときに Map を選ぶ理由を挙げています。オブジェクトにはプロトタイプがあるので、自分のキーとぶつかるかもしれない既定のキーを持っています。Mapは文字列やシンボルだけでなく、どんな値でもキーにできます。大きさは map.size というプロパティ1つでわかります。そして挿入した順に反復されます。決まった名前の欄を持つ記録には、今でもオブジェクトが自然な選択です。
- 1953: H・P・ルーンのIBMの社内メモが、バケットへのハッシュとチェイン法を提案する。
- 1956年ごろ: ニューウェル、ショー、サイモンのIPLが連結リストをもたらす。
- 1957: バウアーとザメルソンがスタックの方法の特許を出願する。Fortranが配列とともに世に出る。
- 1962: アデルソン＝ヴェルスキーとランディスが、最初のつり合った探索木であるAVL木を発表する。
- 2015: ECMAScript 2015がJavaScriptに Map と Set を加える。
- 1,023個のキーの中でないキーを線形探索すると、比較は何回ですか？
- 1,023個の整列済みのキーで二分探索をすると、比較は最大で何回ですか？
- 15個のキーで線形探索をするとき、15個すべてのキーについての比較の平均は何回ですか？
- 127個のキーを整列した順に挿入して作ったBSTで、いちばん大きいキーを探すと比較は何回ですか？
- テキストエディターに「元に戻す」が必要です。どの構造が合いますか？
- キュー
- スタック
- ハッシュテーブル
- 整列済みの配列
- 印刷サーバーは届いた順に仕事を片づけなければなりません。どの構造が合いますか？
- キュー
- スタック
- BST
- スタックとして使う連結リスト
- ユーザーの記録をidで毎秒何度も調べなければなりません。JavaScriptでふつう選ぶのはどれですか？
- ループで探す配列
- idをキーにした Map
- スタック
- 連結リスト
- 挿入や削除をしながらキーを整列させておき、次に大きいキーをよく求めます。いちばん合うのはどれですか？
- ハッシュテーブル
- つり合ったBST
- キュー
- 整列していない配列
- MIT 6.006の言葉で、順序の操作を持たない集合は何と呼ばれますか？
- 列
- 辞書
- スタック
- キュー
- MDNによると、データから来るキーの辞書としてふつうのオブジェクトを使うと危ないことがあるのはなぜですか？
- オブジェクトは文字列を持てないから
- プロトタイプが、自分のキーとぶつかるかもしれない既定のキーを持ちこむから
- オブジェクトは配列よりいつも遅いから
- オブジェクトは1秒たつと値を忘れるから
- いちばんよく行う操作で選びます。
- 列：配列、連結リスト、スタック、キュー。集合：ハッシュテーブル、BST。
- 1,023個のキーでは、線形探索は最大1,023回、二分探索とつり合った木は最大10回の比較です。
- JavaScriptでは Map がふつうの辞書です。順序も必要なら、つり合った木を使います。
このコースの出典 (11)
- MIT OpenCourseWare 6.006 Introduction to Algorithms, Spring 2020 (Demaine, Ku, Solomon)
- lecture notes 2 Data Structures (interface vs data structure, Sequence and Set interfaces, stack = insert_last/delete_last, queue = insert_last/delete_first, array, linked list, dynamic array, amortized Θ(1) append)
- 4 Hashing (chaining, pigeonhole collisions, chain length n/m)
- 6 Binary Trees Part 1 (height, traversal order, O(h) operations) and 7 Binary Trees Part 2: AVL (Adelson-Velsky and Landis, 1962) at ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/pages/lecture-notes
- MDN Web Docs, Array.prototype.shift (shifts all values left by 1)
- Array.prototype.unshift, Map (insertion order, Map vs Object, spec requires sublinear average access) and Set (developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects)
- ECMAScript 2025 Language Specification (tc39.es/ecma262)
- 24.1 Map Objects and 24.2 Set Objects ("must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements")
- Array.prototype.shift steps (Repeat, while k < len: move element k to k - 1)
- D. E. Knuth, The Art of Computer Programming vol. 3 (2nd ed. 1998) section 6.4 History (H. P. Luhn, IBM internal memorandum January 1953, hashing with chaining; digit pairs added mod 10, 31415926 -> 4548) via gwern.net copy, and IEEE Spectrum, "Hans Peter Luhn and the Birth of the Hashing Algorithm" (2018)
- "A brief history of the stack", SIGCIS (sigcis.org/files/A brief history.pdf: Bauer and Samelson applied for the patent in 1957, US 3,047,228 granted July 31, 1962; IPL list processing by Newell, Simon and Shaw at RAND 1956) and Wikipedia, Information Processing Language (Newell, Shaw, Simon, RAND and Carnegie Institute of Technology, about 1956).
確認日: 2026-10-18