ハッシュテーブル

7個のバケットの表に47が入っているとき、コンピューターは表全体を探さずに、まっすぐバケット 47 mod 7 = 5 に向かいます。

キーを位置に変える

これまで、値を見つけるには探す必要がありました。整列していない配列や連結リストでは最大 n ステップです。けれども配列は、どの位置にも1ステップで行けます。キーそのものが位置を教えてくれたらどうでしょう。キーが小さな整数、たとえば0から99までの出席番号なら、100個のマスの配列を用意して、番号 k の生徒をマス k に入れればよいのです。MITの資料ではこれを直接アクセス配列と呼んでいます。この方法は、電話番号や単語のようにありうるキーが膨大なときにはうまくいきません。ありうるキーすべてにマスを用意する余裕はないからです。

ハッシュ関数は、どんなキーも 0 から m − 1 までの小さな範囲の位置に押しこめることで、この問題を解決します。整数に使えるかんたんなものは h(k) = k mod m で、m でわった余りです。m 個のマスの配列がハッシュテーブルで、そのマスはよくバケットと呼ばれます。m = 7 で47を保存するには、47 mod 7 = 5 を計算してバケット5に入れます。あとで47を探すときは、同じ計算をしてバケット5だけを見ます。

衝突とチェイン法

問題があります。バケットが7個で、ありうるキーが7個より多ければ、いくつかのキーは同じバケットを使うしかありません。12、33、47はどれも余りが5です。これを衝突といい、MITの資料は、鳩の巣原理によってこれは避けられないと指摘しています。ふつうの対策はチェイン法です。各バケットは、そこにハッシュされたすべてのキーの小さなリスト（チェイン）を持ちます。すると47を探す費用は、ハッシュの1ステップと、チェイン5で調べたキー1つごとに1回の比較です。前に12と33があれば、1 + 3 = 4 ステップです。

チェインの長さはどれくらいでしょうか。キーが均等に散らばれば、各チェインにはおよそ n/m 個のキーが入ります。この数を負荷率といいます。m を n と同じくらいの大きさに保てばチェインは短いままで、検索・挿入・削除は平均して一定のステップ数で済みます。危ないのは散らばり方が悪いときです。すべてのキーが同じバケットにハッシュされると、1つのチェインに n 個のキーがすべて入り、表は連結リストと変わらなくなります。ラボでバケットを7個にして14、21、28を挿入してみましょう。すべてバケット0に入ります。

読み込み中

ドラッグで回転、スクロールまたはピンチで拡大・縮小。

12、25、33、47、70を持つ7個のバケットのハッシュテーブルで、h(k) = k mod 7 です。キーを選んで挿入・検索・削除をしましょう。ステップのカウンターは、ハッシュに1、チェインで比べたキー1つごとに1を数えます。

本物のハッシュ関数はキーのすべてのビットを混ぜ合わせます。よく設計されたライブラリは、ふつうのデータが均等に散らばるようにハッシュ関数を選んでいます。MITの6.006はさらに進んで、ハッシュ関数をある族の中からランダムに選びます。そうすれば、毎回悪い結果になる決まったキーの組はなくなります。ラボで単純な k mod m を使っているのは、手で確かめられるからです。

JavaScriptのハッシュテーブル

ハッシュテーブルを自分で書くことはめったにありません。JavaScriptには Map と Set があるからです。ECMAScriptの仕様には、これらは「ハッシュテーブルか、平均して要素数に対して線形未満のアクセス時間を与えるほかのしくみを使って実装しなければならない」とあります。つまり map.get(key) や set.has(x) は、集まり全体を探すより速くなければなりません。MDNによると、Mapはキーを挿入した順に保ち、ふつうのオブジェクトとちがって、自分のキーとぶつかるような既定のキーを持ちません。

const price = new Map();
price.set("apple", 1.2);
price.set("bread", 2.5);
console.log(price.get("bread")); // 2.5、リストを探さない
console.log(price.has("milk"));  // false
const seen = new Set([4, 8, 15]);
console.log(seen.has(8));        // true

背景ハッシュの考えは、IBMのハンス・ピーター・ルーンが生んだとされています。ドナルド・クヌースによる探索の歴史には、1953年1月にルーンがIBMの社内メモを書き、記録を番号つきのバケットに入れ、衝突したものはチェインでつなぐことを提案したと記されています。彼のハッシュ関数は数字の桁を使うもので、隣り合う2桁ずつを足し、それぞれの和の一の位を残します。こうして31415926は4548になります。IBM 701にとりくんでいたほかのIBMの技術者たちも同じころ同じ考えにたどり着き、最初に公表された説明は1956年のアーノルド・デューミーによるものでした。

ハッシュ関数	キーを 0 から m − 1 までのバケット番号に変えます。たとえば k mod m。
衝突	ちがう2つのキーが同じバケットになること。キーがバケットより多ければ避けられません。
チェイン法	各バケットが、そこにハッシュされたすべてのキーのリストを持ちます。
負荷率	n/m。チェインの平均の長さ。
Map と Set	JavaScriptに組みこまれたキーつきの集まり。平均して線形より速いことが求められます。

h(k) = k mod 7 のとき、47はどのバケットに入りますか？
表には 12、25、33、47、70 がこの順に挿入されていて、m = 7 です。47を探すのは何ステップですか（ハッシュに1と、比べたキーの数）？
同じ表で、12を探すのは何ステップですか？
同じ表で、19は保存されていません。19を探すのは何ステップですか？
同じ表で、負荷率 n/m はいくつですか？（小数第2位まで）
衝突とは何ですか？
- 大きすぎるキー
- ちがう2つのキーが同じバケットにハッシュされること
- キーを2回削除すること
- キーが1つもない表
ありうるキーがバケットより多いとき、どんなハッシュ関数でも衝突を避けられないのはなぜですか？
- コンピューターが数を丸めるから
- 鳩の巣原理
- キーはいつも偶数だから
- チェインが短すぎるから
すべてのキーが同じバケットに入ると、キーの検索はどうなりますか？
- それでも1ステップ
- n 個のキーの連結リストを探すのと同じ
- できなくなる
- 二分探索と同じ
ECMAScriptの仕様は、Mapのアクセス時間に何を求めていますか？
- ちょうど1ステップ
- 平均して要素数に対して線形未満
- Θ(n log n)
- 何も求めていない
1953年のルーンのハッシュは、隣り合う2桁ずつを足し、それぞれの和の一の位を残しました。31415926は何になりますか？

ポイント

ハッシュ関数はキーをバケット番号に変えます。k mod m はかんたんな例です。
衝突は避けられません。チェイン法では各バケットにリストを持たせます。
負荷率 n/m を小さく保てば、検索・挿入・削除は平均して一定のステップで済みます。
JavaScriptの Map と Set は、平均して線形より速くなければなりません。

このコースの出典 (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