10万件の配列をincludesで探すと止まります。ハッシュテーブルを自作して、なぜSetやMapが速いのかを確かめます。
これは【深掘り】の記事です。本線の順路ではありません。 本線のデータ構造を自作する回で「配列は先頭への挿入が遅い」ところまでやった人が、「では、なぜ Set や Map は探すのが速いのか」を、魔法で済ませずに確かめるための記事です。飛ばしても本線は進みます。
この記事のコマンドは、VMの中(Ubuntu Server)で打ちます。 Windows の PowerShell ではありません。 VM に Node.js が入っている必要があります。 入れ方は本線のnpmの回にあります。
node -vで v20 以上が出れば大丈夫です。 作業場所は~/cslab/hash/です。 この記事のためだけに新しく作り、最後に全部消します。 既存のプロジェクトには触りません。 記事に出てくる測定値は私のVMの数字です。 皆さんの数字とは違います。見てほしいのは絶対値ではなく、件数を10倍にしたときに何倍になるかです。
対象レベル: 中級〜上級 / 区分: 発展
「Setは速い」で納得して、半年間なにも分かっていなかった
最初に、失敗した日の話をします。
CSVから読んだ会員番号の一覧があって、「この番号はもう登録済みか」を1万回くらい判定するコードを書きました。件数は10万件でした。
素直にこう書きました。
if (registered.includes(id)) { /* 登録済み */ }
動きませんでした。 正確には、動いたのですが、画面が20秒くらい黙りました。 私は最初、通信が詰まったと思って Ctrl+C を押しました。
検索して、こう直しました。
const registeredSet = new Set(registered);
if (registeredSet.has(id)) { /* 登録済み */ }
一瞬で終わりました。 体感で「待ち時間ゼロ」でした。
そして私は、この件をここで終わりにしました。 覚えたことは1行です。
「たくさん探すときは
Setにする。Setは速い」
これが半年続きました。動いていたので、困りませんでした。
困ったのは、面接の練習で「なぜ Set は速いんですか」と聞かれたときです。私はこう答えました。
「内部でハッシュテーブルになっていて、O(1) で引けるからです」
言葉としては合っています。 そして、私は何も分かっていませんでした。 続けて聞かれたら1つも答えられません。
- なぜ「1回」で見つかるのか。 探さずに場所が分かるのはおかしくないか
- 同じ場所に2つ来たらどうなるのか
- 中身が増えたらどうなるのか。 場所の数は最初に決めたのでは
- O(1) が壊れることはあるのか
「O(1) だから速い」は、説明ではありません。 「速いから速い」と言い換えているだけです。
この記事は、そこを埋めます。やることは1つだけです。
ハッシュテーブルを自分で書いて、O(1) が壊れるところまで見る。
壊れるところを見ないと、O(1) は魔法のままです。 壊し方が分かって初めて、「速い」が条件付きの性質だと分かります。
そして、この記事のもう半分は言葉の整理です。
「ハッシュ」という言葉は、まったく違う2つの場面で使われます。 ここで使う「置き場所を決めるためのハッシュ」と、パスワードやファイルの検証で出てくる「戻せないハッシュ」です。私はこの2つを長く混ぜていました。 ⑦で1枚の表に分けます。
この記事でわかること
- 配列の
includesとSetのhasの差は、件数に比例して開くこと。1万件で91倍、10万件で448倍、100万件で3754倍。これは「Setが速い」ではなく「配列が件数ぶん遅くなる」話 - 「一発で見つかる」の正体は、探していないからだということ。キーを数字にして、配列の長さで割った余りを添字にする。計算1回で置き場所が決まるので、探す作業そのものが無い
- 違うキーが同じ場所に来る(衝突する)のは、事故ではなく必ず起きること。
bananaとcherryは、バケット8個だと両方 0番に入りました - O(1) は無条件ではないこと。バケット数を1個にしたハッシュテーブルは、ただの配列と同じ 4959ミリ秒になりました。O(1) は「衝突が少ないこと」に賭けた上での話
- リサイズ(バケットの作り直し)は本当に遅いこと。10万件を入れる間に15回起き、そのうち1回は平均の3万倍かかりました。それでも1件あたりでならすと O(1)(償却)になる
- ハッシュ・暗号化・エンコードは、まったく別のものであること。Base64 は暗号化ではありません。
base64 -dは誰でも打てます Objectのキーは文字列に変換されること。obj[1]とobj['1']は同じキーで、片方が消えます。Mapでは別のキー- ハッシュテーブルを速くするハッシュ(fnv1a、127ナノ秒)と、守るためのハッシュ(sha256、3274ナノ秒)は、要求が正反対であること
この記事でやること
~/cslab/hash/を作り、10万件のincludesとSet.hasを実測する。 件数を10倍ずつ変えて、差が何倍まで開くかを表にする- ハッシュ関数(FNV-1a と djb2)を自分で書く。 同じ入力で必ず同じ数字が出ることを確かめ、割った余りが置き場所になるところまで手で見る
- ハッシュテーブル(
set/get/delete/has)を書き、dump()でバケットの中身を表示する。 どのキーがどこに入ったかを目で見る - わざと衝突させる。 チェイン法とオープンアドレス法の2つを実装し、オープンアドレス法の削除が壊れることを実演する。バケット数を変えて最悪の鎖の長さを測り、O(1) が O(n) に落ちる表を作る
- 負荷率とリサイズを実装し、リサイズが起きた回数と、そのときだけ遅くなることを実測する
- わざと悪いハッシュ関数(必ず0を返す)に差し替えて、ハッシュテーブルがただの配列になることを測る
sha256sum/md5sum/base64を実際に打ち、ハッシュ・暗号化・エンコードを1枚の表に分けるObject/Map/Set/WeakMapの違いを実演し、判断表にまとめて~/cslab/を消す
先に知る言葉
この記事で初めて出てくる言葉です。 基本的な言葉は用語集にもまとめてあります。
| 言葉 | 意味 |
|---|---|
| ハッシュ関数 | どんな長さのデータを入れても、決まった範囲の数字を1つ返す関数。同じ入力なら必ず同じ数字。違う入力でも同じ数字になることはある |
| ハッシュ値 | ハッシュ関数が返した数字。ダイジェストとも言う |
| ハッシュテーブル | キーをハッシュ関数に通して置き場所を決める入れ物。Map や Set や Python の辞書の中身 |
| バケット(bucket) | ハッシュテーブルの内部にある、値を置くマス。「バケット数」は、そのマスの個数 |
| 衝突(collision) | 違うキーが、同じバケットに割り当てられること。避けられないので、必ず対処が要る |
| チェイン法 | 衝突したら、そのバケットの中に一覧(配列やリスト)を持って並べるやり方 |
| オープンアドレス法 | 衝突したら、空いている次のマスへずらして置くやり方。削除が難しい |
| 墓標(tombstone) | オープンアドレス法で「ここは消したが、通り道としては生きている」印。これが無いと後ろの要素が行方不明になる |
| 負荷率(load factor) | 入っている件数 ÷ バケット数。これが上がると衝突が増える。0.7〜0.8 を超えたら作り直すのが普通 |
| 償却計算量(amortized) | たまに重い処理が入るが、回数でならすと軽いという測り方。「毎回速い」ではなく「平均すれば速い」 |
| O(1) / O(n) | 件数が増えたときに時間がどう増えるか。O(1) は増えない、O(n) は比例して増える。本線の計算量の回でやりました |
① まず、止まるコードを自分で書く
説明の前に、困ってから始めます。 困っていないと、仕組みの話は頭に入りません。
作業場所を作る
v22.14.0
v20 以上なら大丈夫です。 出ない場合は本線のnpmの回に戻ってください。
この記事では npm install を1回もしません。 ライブラリを入れたら、正体を確かめるという目的が消えます。
package.json だけ置きます。import を使うためです。
{ "type": "module" }
10万件を用意して、両方で探す
100万件のところは20秒ほど黙ります。 これが、あの日の「止まった」です。待ってください。
探索回数はすべて 10000 回
10000 件 includes 139.4 ms has 1.52 ms 倍率 91
100000 件 includes 1307.3 ms has 2.92 ms 倍率 448
1000000 件 includes 20478.4 ms has 5.45 ms 倍率 3754
1行目と3行目を見比べてください。
| 件数 | includes 合計 | has 合計 | 倍率 |
|---|---|---|---|
| 1万 | 139.4 ms | 1.52 ms | 91倍 |
| 10万 | 1307.3 ms | 2.92 ms | 448倍 |
| 100万 | 20478.4 ms | 5.45 ms | 3754倍 |
[スクリーンショット: 01_桁が違う.png] — node bench-includes.js の3行の出力が全部写るように撮ります。20478.4 ms と 5.45 ms が同じ画面に並ぶことが大事です。
この表の読み方が、この記事の全部です
「Setは速い」と読むと、何も分かりません。 見るべきはここです。
includesは、件数が10倍になると時間も約10倍(139 → 1307 → 20478)。これが O(n) の顔ですhasは、件数が100倍になっても 1.52 → 5.45 ミリ秒。ほとんど増えていません。これが O(1) の顔です- だから倍率は、件数を増やすほど開きます。 91 → 448 → 3754。「何倍速いか」は固定の値ではありません
includesが遅い理由は、はっきりしています。 先頭から順に、見つかるまで全部比べているからです。10万件なら平均5万回です。遅いというより、素直です。分からないのは
hasのほうです。 100万件あっても増えないということは、100万件のうちどれと比べたのかという話になります。答えは「1つとしか比べていない」です。 そしてその1つを、探さずに当てています。
「探さずに当てる」が、これから作るものです。
② ハッシュ関数を自分で書く(ここが「一発で見つかる」の正体)
考え方は、拍子抜けするほど単純
やりたいことを日本語で書きます。
キー(
'user-500'のような文字列)を渡したら、置き場所(配列の添字)が1回の計算で出てほしい。
これができれば、探す作業は消えます。 添字が分かっているなら、arr[3] は一瞬です。件数が100万でも1000万でも変わりません。配列の添字アクセスが O(1) なのは、前回までにやりました。
問題は1つだけです。
文字列を、どうやって添字(0以上の整数)にするのか。
これを2段でやります。
- 文字列を、なにか大きな数字にする ← これがハッシュ関数
- その数字を、配列の長さで割った余りにする ← これで必ず範囲内に収まる
2段目は割り算の余り(%)だけです。 8で割った余りは必ず 0〜7 になります。だから、バケットが8個なら添字は必ず有効です。
1段目に必要な性質は、たった1つです。
同じ文字列を渡したら、必ず同じ数字が返ること。
これだけです。 逆に言うと、戻せる必要はまったくありません。 数字から元の文字列を復元する必要は、置き場所を決めるだけなら1度もありません。ここが⑦で整理する話の入口です。
FNV-1a を書く
有名な短いハッシュ関数を2つ書きます。どちらも10行以下です。
やっていることは、1文字ずつ数字にして混ぜているだけです。
str.charCodeAt(i)はその位置の文字の番号です。'a'なら 97。文字が番号であることは、文字コードの回でやりました^(排他的論理和)はビットごとに混ぜる演算です。ここでは「前の結果に新しい文字を混ぜ込む」ために使っていますMath.imulは 32bitとして掛け算する関数です。*を使ってはいけません(つまずき1で書きます)>>> 0は結果を 0以上の32bit整数にする決まり文句です。これを忘れるとマイナスの値が返って、%の結果もマイナスになり、添字として使えません
0x811c9dc5 と 0x01000193 の意味を、私は説明できません。 FNV-1a の仕様で決められている定数です。「散らばりが良くなるように選ばれた数」というところまでが、私の理解です。 自分で選ぶ話ではないので、そのまま使います。
同じ入力なら同じ数字が出ることを確かめる
key fnv1a djb2
"apple" 280767167 253337143
"banana" 3649609552 4086421542
"cherry" 1232791672 4133553618
"a" 3826002220 177670
"b" 3876335077 177671
"ab" 1294271946 5863208
"ba" 1009493708 5863240
"" 2166136261 5381
同じ入力を3回:
280767167 280767167 280767167
8で割った余り(バケット8個ぶんの置き場所):
"apple" 7
"banana" 0
"cherry" 0
"a" 4
"b" 5
"ab" 2
"ba" 4
"" 5
確かめられたことを並べます。
fnv1a('apple')は3回とも280767167。 乱数ではありません。 何度打っても、別のマシンで打っても同じです。「同じキーを渡したら同じ場所」が保証されるので、置いた場所に取りに行けます'a'と'b'は1文字違うだけで、38億と38億でも桁は同じですが値は全然違います。 1文字変えたら結果が大きく変わるのが、良い散らばりの条件です'ab'と'ba'は違う値。 文字を足すだけの雑なハッシュだと、これが同じになります(つまずき2で失敗しました)- 空文字列でも値が出ます。 初期値がそのまま返るだけです
そして、いちばん大事なのは最後のブロックです。
bananaとcherryは、どちらも 0 になりました。
もう衝突しています。 キーが3個しかない段階で、です。
これは私のハッシュ関数が下手だからではありません。 3649609552 と 1232791672 という全然違う数字を、8で割った余りにしたからです。8種類しか出口が無いところに、40億通りの数字を押し込んでいます。
衝突は、避けられません。 8個のバケットに9個のキーを入れれば、どんなに優秀なハッシュ関数でも必ず衝突します。 出口が足りないからです。 だから、ハッシュテーブルの実装は「衝突をどう処理するか」がほぼ全部です。
これで、この記事の山場(④)の準備ができました。まず動くものを作ります。
③ ハッシュテーブルを実装する(そして中身を目で見る)
40行で書ける
set / get / has / delete を書きます。衝突は、いちばん素直な方法(チェイン法)で処理します。 各バケットに配列を持って、そこに並べるだけです。
dump() を最初に書いたことが、この記事でいちばん役に立ちました。 ハッシュテーブルは中身が見えないから魔法に見えるのです。見えれば、驚くところが1つも無くなります。
動かして、中身を見る
件数 4 / バケット 8
[ 0] banana=200 -> cherry=300 -> durian=400
[ 1] (空)
[ 2] (空)
[ 3] (空)
[ 4] (空)
[ 5] (空)
[ 6] (空)
[ 7] apple=100
get('banana') : 200
get('grape') : undefined
has('apple') : true
delete('apple'): true
delete('apple'): false
件数 3 / バケット 8
[ 0] banana=200 -> cherry=300 -> durian=400
[ 1] (空)
[ 2] (空)
[ 3] (空)
[ 4] (空)
[ 5] (空)
[ 6] (空)
[ 7] (空)
[スクリーンショット: 02_衝突を目で見る.png] — node use-table.js の最初の dump() が写るように撮ります。[ 0] に3つ並び、他の6マスが空という偏りが1枚で分かります。
この出力で分かること
4件しか入れていないのに、状態がかなり悪いです。
[0]に3つ入っている(banana/cherry/durian)[7]に1つ(apple)- 残りの6マスは空
get('durian') を呼ぶと、バケット0の中を3件ぶん見ます。 これはO(1) ではありません。 バケット0に入っている件数に比例します。
つまり、ハッシュテーブルの
getの実際のコストは、こうです。「ハッシュ計算1回」+「そのバケットの中の件数ぶんの比較」
前半は件数によらず一定です。 問題は後半です。バケットの中が1件なら O(1)、n件なら O(n) です。
O(1) と言えるのは、「バケットの中がだいたい1件で収まっている」という条件が成り立っているときだけでした。
get('grape') が undefined を返し、2回目の delete('apple') が false を返すのも見てください。入っていないキーの扱いも、同じ仕組みで自然に決まります。 バケットを見て、無ければ無いのです。
これで、④に行く準備ができました。「バケットの中がだいたい1件」を、どうやって守るのかが残っている問題です。
④ 衝突をわざと起こして、O(1) を壊す
まず、壊れたところを数字で見る
バケット数を変えながら、10万件を入れて、最悪の鎖の長さと探索時間を測ります。
最初の2行で10秒くらいかかります。 それが見たいものです。
バケット数 負荷率 最長の鎖 空バケット 10000回の探索
1 100000.00 100000 0 4959.1 ms
8 12500.00 12504 0 1365.2 ms
64 1562.50 1583 0 348.5 ms
1024 97.66 130 0 28.5 ms
16384 6.10 18 42 6.9 ms
131072 0.76 6 62532 6.9 ms
この表が、この記事の核心です。 上から下まで、コードは1文字も変えていません。 バケット数だけを変えました。
| バケット数 | 負荷率 | 最長の鎖 | 探索10000回 | 実質 |
|---|---|---|---|---|
| 1 | 100000 | 100000 | 4959.1 ms | ただの配列 |
| 8 | 12500 | 12504 | 1365.2 ms | 配列の8分の1 |
| 64 | 1562 | 1583 | 348.5 ms | 配列の64分の1 |
| 1024 | 97.7 | 130 | 28.5 ms | まだ鎖が長い |
| 16384 | 6.1 | 18 | 6.9 ms | ほぼ O(1) |
| 131072 | 0.76 | 6 | 6.9 ms | 増やしても速くならない |
読み方を4つ書きます。
- バケット1個のハッシュテーブルは、4959ミリ秒。 ①で測った配列の
includes(10万件で1307ミリ秒、探索1万回)と同じ桁です。ハッシュテーブルを名乗っていても、全部同じバケットに入るなら、先頭から順に見る配列と何も変わりません - バケット数を8倍にすると、時間がだいたい8分の1になります(4959 → 1365 → 348)。鎖の長さに比例している、つまり O(n) の n がバケット数で割られているだけです
- 16384 で 6.9ミリ秒になり、131072 にしても 6.9ミリ秒でした。 鎖が「ほぼ1件」になった時点で、それ以上は速くなりません。 ここが O(1) の上限です
- 131072 のとき、62532マスが空でした。メモリの半分が空です。バケットを増やすのは無料ではありません
結論を1行にすると、こうです。
O(1) は、ハッシュテーブルの性質ではありません。 「負荷率を低く保っている」という運用が成り立っているときの性質です。
だから⑤で、負荷率を自動で保つ仕組みを実装します。それが無いハッシュテーブルは、件数が増えると勝手に O(n) に落ちます。
もう1つの解き方:オープンアドレス法
チェイン法は「バケットの中に配列を持つ」でした。もう1つのやり方は、「空いている次のマスにずらして置く」です。
こちらのほうが速いことがあります。 配列が1本で済むので、メモリの並びが素直だからです。代わりに、削除が本当に面倒です。
件数 4 / マス 8
[ 0] banana=200
[ 1] cherry=300
[ 2] durian=400
[ 3] (空)
[ 4] (空)
[ 5] (空)
[ 6] (空)
[ 7] apple=100
cherry を探すのに見たマスの数: 2
durian を探すのに見たマスの数: 3
--- banana を削除 ---
件数 3 / マス 8
[ 0] ★墓標
[ 1] cherry=300
[ 2] durian=400
[ 3] (空)
[ 4] (空)
[ 5] (空)
[ 6] (空)
[ 7] apple=100
delete後の get('cherry'): 300
delete後の get('durian'): 400
②で見たとおり、banana cherry durian は全員 0番が本来の場所です。
bananaは 0 が空いていたので 0番cherryは 0 が埋まっていたので 1番(見たマス 2 個)durianは 0 と 1 が埋まっていたので 2番(見たマス 3 個)
「見たマスの数」がそのままコストです。 チェイン法の「鎖の長さ」と、同じものを別の形で数えているだけです。
墓標が無いと何が起きるか(実演します)
「消したら空に戻す」で何が悪いのか、口で言っても納得できませんでした。 壊れたものを作って動かします。
削除前 cherry: 300
削除前 durian: 400
banana を削除しました
削除後 cherry: undefined
削除後 durian: undefined
bananaを1件消したら、触っていないcherryとdurianが消えました。
原因は1行です。 0番を EMPTY に戻したので、cherry を探す処理が0番を見た瞬間に「ここが空だから、以降に無い」と判断して打ち切ったからです。
これは、私がハッシュテーブルを自分で書くまで想像できなかった種類の不具合です。
- エラーは出ません。
undefinedが返るだけです - 消したキーとは無関係のキーが消えます
- バケット数が多いうちは、まず起きません。 衝突していないので。件数が増えて衝突が始まったときだけ出ます
「テストでは通って、本番のデータ量で壊れる」不具合の、いちばん分かりやすい標本でした。 だから墓標が要ります。「消した」と「最初から無い」を、別の状態として持たないといけません。
チェイン法とオープンアドレス法の比較
| チェイン法 | オープンアドレス法 | |
|---|---|---|
| 衝突したら | バケットの中の配列に並べる | 空いている次のマスへずらす |
| 負荷率 | 1を超えてもいい(鎖が伸びるだけ) | 1を超えられない(マスが無い) |
| 削除 | 配列から抜くだけ。素直 | 墓標が必要。上のとおり壊れる |
| メモリの並び | 配列がバケットごとに散る | 1本の配列。まとまっている |
| 実装の難しさ | やさしい | 難しい。墓標・満杯・再配置 |
| 詰まったときの症状 | 特定のバケットだけ遅くなる | 周辺のマスまで巻き込んで遅くなる(かたまりができる) |
自分で書くならチェイン法です。 オープンアドレス法は、速さのために正しさの難易度を上げる取引です。そう決めた理由が説明できるときだけ選ぶものだと思いました。
以降は、チェイン法で進めます。
⑤ 負荷率とリサイズ(O(1) を保つ仕組み)
バケット数を最初に決めるのは無理
④で分かったのは、バケット数と件数の比(負荷率)を低く保てば O(1)、ということでした。
では、バケット数をいくつにすればいいのか。
決められません。 何件入るか、作る時点では分からないからです。8個で作って10万件入れたら、④の2行目(1365ミリ秒)になります。
答えは「途中で作り直す」です。
負荷率が決めた値(0.75 など)を超えたら、バケット数を2倍にして、全部入れ直す。
「全部入れ直す」が要ることに注意してください。 バケット数が変わると % の結果が変わるので、今までの置き場所が全員間違いになります。 配列を伸ばすだけでは済みません。
実装する(リサイズの記録も取る)
入れた件数 : 100000
最終バケット数 : 262144
リサイズ回数 : 15
合計時間 : 363.7 ms
1件あたり : 3.637 マイクロ秒
リサイズが起きた瞬間(最後の6回):
件数 新バケット数 かかった時間
3073 8192 3.25 ms
6145 16384 10.48 ms
12289 32768 18.55 ms
24577 65536 25.57 ms
49153 131072 37.22 ms
98305 262144 119.8 ms
リサイズに使った合計時間: 220.9 ms
最終の状態: {"size":100000,"buckets":262144,"max":4,"empty":176940,"load":"0.38"}
分かることを並べます。
- バケットは 8 から始めて、15回倍にして 262144 になりました。 8 × 2の15乗 = 262144。バケット数を1度も指定していないのに、10万件に見合う数まで自分で育ちました
- 最長の鎖は 4 件。 ④の表で「16384バケットで最長18」だったのより良い状態です。負荷率 0.38 に保たれているからです
- 合計363.7ミリ秒のうち、220.9ミリ秒がリサイズでした。 6割がリサイズです
- 最後の1回だけで 119.8ミリ秒。 10万件を全部入れ直しているので当然です
リサイズの瞬間だけ遅くなることを、1件ずつ測る
「合計で6割」では、体感としてどうなのか分かりません。 1件ずつ測ります。
1件あたりの平均 : 2.254 マイクロ秒
遅かった6件:
何件目 かかった時間 平均の何倍
98305 69.03 ms 30627
24577 23.80 ms 10562
49153 21.88 ms 9706
12289 13.92 ms 6175
50839 10.82 ms 4803
56979 9.21 ms 4085
平均の100倍を超えた件数: 15 / 100000
[スクリーンショット: 03_リサイズの瞬間.png] — node bench-spike.js の出力全体を撮ります。「30627倍」と「15 / 100000」が同じ画面に写ることが大事です。
98305件目の1件が、平均の 30627倍かかりました。 そして、平均の100倍を超えたのは 10万件のうち 15件だけでした。リサイズの回数と一致しています。
これが「償却 O(1)」という言い方の中身です。
- 1回1回を見れば、O(1) ではありません。 リサイズの回だけ O(n) です
- 回数でならすと O(1) です。 リサイズは件数が2倍になるたびにしか起きないので、n件を入れる間に起きる総コストは、n に比例する程度にとどまります
- 「平均すれば速い」なので、「1回の応答時間の上限」を約束しないと困る場面では使えません
これが、私が実務で1回踏んだ話につながります。 リクエストの処理中に巨大な
Mapを作っていて、たまに1リクエストだけ極端に遅いことがありました。監視のグラフでは平均は綺麗なのに、上位1%の応答時間だけ跳ねるという形です。 平均値だけ見ていると、絶対に見つかりません。 「たまに遅い」は、償却の裏側から出てくることがあります。
なお、.slice(-6) と sort を使った上の集計は、100万件でやると別の問題が出ます。 つまずき4に書きました。
⑥ 良いハッシュ関数の条件は2つだけ
散らばること
ハッシュテーブルの性能は、ハッシュ関数の散らばりで決まります。 ④で見たとおり、鎖が長くなればそれだけ遅くなるからです。
散らばりを絵で見ます。
fnv1a (理想は各 100 件)
[ 0] 95 ###################
[ 1] 101 ####################
[ 2] 97 ###################
[ 3] 95 ###################
[ 4] 106 #####################
[ 5] 97 ###################
[ 6] 97 ###################
[ 7] 106 #####################
[ 8] 104 #####################
[ 9] 97 ###################
[10] 104 #####################
[11] 104 #####################
[12] 96 ###################
[13] 104 #####################
[14] 101 ####################
[15] 96 ###################
最多 106 件 / 理想の 1.06 倍
先頭1文字 (理想は各 100 件)
[ 0] 0
[ 1] 0
[ 2] 0
[ 3] 0
[ 4] 0
[ 5] 1600 ########################################
[ 6] 0
[ 7] 0
[ 8] 0
[ 9] 0
[10] 0
[11] 0
[12] 0
[13] 0
[14] 0
[15] 0
最多 1600 件 / 理想の 16.00 倍
fnv1a は 95〜106 件。理想の1.06倍が最悪です。 一方、先頭1文字は 1600件が1マスに固まりました。 キーが全部 user- で始まっているので、先頭の文字はいつも u です。
「先頭1文字」は、ハッシュ関数としては最速です。 1回の charCodeAt で終わります。そして役に立ちません。
わざと悪いハッシュ関数に差し替える
HashTableChain は、コンストラクタでハッシュ関数を受け取るように書いてあります。 差し替えて測ります。
件数 20000 / バケット 1024 で固定 / 探索 2000回
hash | 使ったバケット | 最長の鎖 | 構築 | 探索
fnv1a | 1024 | 35 | 13.5ms | 4.0ms
djb2 | 1018 | 40 | 10.1ms | 3.5ms
first-char | 1 | 20000 | 906.1ms | 84.5ms
length-only | 5 | 10000 | 533.9ms | 54.8ms
always-zero | 1 | 20000 | 950.8ms | 95.2ms
| ハッシュ関数 | 使ったバケット | 最長の鎖 | 構築 | 探索 |
|---|---|---|---|---|
| fnv1a | 1024 / 1024 | 35 | 13.5 ms | 4.0 ms |
| djb2 | 1018 / 1024 | 40 | 10.1 ms | 3.5 ms |
| 先頭1文字 | 1 | 20000 | 906.1 ms | 84.5 ms |
| 文字数だけ | 5 | 10000 | 533.9 ms | 54.8 ms |
| 必ず0 | 1 | 20000 | 950.8 ms | 95.2 ms |
「必ず0を返すハッシュ関数」でも、ハッシュテーブルは動きます。 バグは出ません。遅いだけです。 1024個のバケットのうち1個しか使わず、そこに20000件が鎖になりました。 ハッシュテーブルという名前の、ただの配列です。
そして怖いのは「先頭1文字」です。 これは悪意ではなく、素人の善意で書けるハッシュ関数です。必ず0を返す関数を書く人はいません。 でも「先頭の文字コードでいいだろう」は、書きます。私は書きました。
結果は「必ず0」とほぼ同じでした。 キーが user- や 2026- のような共通の接頭辞を持つのは、実データではむしろ普通です。
速いこと
もう1つの条件は速さです。 ハッシュ関数は set でも get でも毎回呼ばれるので、ここが遅いと全部遅くなります。
20万件の文字列をハッシュする時間
hash | 合計 | 1回あたり
fnv1a | 25.4ms | 127ns/回
djb2 | 16.5ms | 82ns/回
sha256 | 654.8ms | 3274ns/回
md5 | 682.2ms | 3411ns/回
sha256 は fnv1a の26倍遅いです。
そして sha256 のほうが、散らばりは間違いなく良いです。 それでもハッシュテーブルには使いません。 26倍遅いハッシュ関数を毎回呼んだら、鎖が短くなった分を打ち消します。
ここで、この記事のもう半分に入ります。
sha256 は「悪いハッシュ関数」ではありません。 要求が違うのです。
– ハッシュテーブル用のハッシュに要るのは、散らばりと速さ。戻せないことは要らない – 検証や保護のためのハッシュに要るのは、戻せないこと・当てられないこと。速いことは、むしろ都合が悪い場合がある
同じ「ハッシュ」という言葉が、正反対の要求を指しています。 ここを混ぜていたのが、私の混乱の正体でした。
⑦ ハッシュ・暗号化・エンコードは、全部違う
1枚の表
| ハッシュ | 暗号化 | エンコード | |
|---|---|---|---|
| 何のため | 同じかどうかを比べる・置き場所を決める | 鍵を持つ人だけが読めるようにする | 別の形式で表せるようにする |
| 元に戻せるか | 戻せない(設計上そうなっている) | 鍵があれば戻せる | 誰でも戻せる |
| 出力の長さ | 入力の長さによらず固定(sha256 なら常に64文字) | 入力の長さに応じて変わる | 入力の長さに応じて変わる |
| 鍵 | 無い | ある(これが本体) | 無い |
| 例 | sha256 / md5 / bcrypt / fnv1a | AES / RSA / TLS の中身 | Base64 / URLエンコード / UTF-8 |
| 秘密を守れるか | 用途次第 | 鍵を守れば守れる | 1つも守れない |
いちばん多い誤解は、いちばん下の行です。
Base64 は暗号化ではありません。 読めない見た目になるだけです。
実際に打って確かめる
Base64 が誰でも戻せることを、まず見ます。
cGFzc3dvcmQxMjM=
では戻します。
password123
鍵を1つも渡していません。 -d を付けただけです。Base64 は「戻し方が公開されている変換」です。秘密にする機能は、最初から入っていません。
設定ファイルに Base64 で書いてある値を見て「暗号化されている」と思ってはいけません。
base64 -dを打てば読めます。 Kubernetes の Secret がそうです(詳しくは深掘りの別コースの話なので、ここでは名前だけ)。
次に、ハッシュです。
ef92b778bafe771e89245b89ecbc08a44a4e166c06659911881f383d4473e94f -
33631376724e5d5480fa397dfcf03b66ad47b934ab495174d7058c38f2bb0087 -
e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855 -
3つとも 64文字です。 - は「標準入力から読んだ」という印です。
見てほしいのは2つです。
password123とpassword124は1文字違いですが、結果は最初の1文字から全然違います。 「少し似た入力なら少し似た出力」にはなりません(これは意図的な設計です)- 空文字列でも64文字出ます。 入力が0バイトでも64文字。1GBのファイルでも64文字です。 これが「固定長」です
入力の長さによらず64文字なら、当然こうなります。
戻せません。 1GBの情報を64文字に押し込んでいるので、捨てられた情報が復元できるはずがありません。 そして、違う入力が同じ結果になる組み合わせも、必ず存在します。 出口の数(有限)より入口の数(無限)のほうが多いからです。②で
bananaとcherryが同じ 0番に入ったのと、同じ理屈です。
ファイルが同じかどうかを確かめる
「戻せない」が役に立つ場面が、これです。
5891b5b522d5df086d0ff0b110fbd9d21bb4fc7163af34d08286a2e846f6be03 a.txt
5891b5b522d5df086d0ff0b110fbd9d21bb4fc7163af34d08286a2e846f6be03 b.txt
0655937a5582c55b9ac610ed7ce474ed9be0a0fbefe9afcba31b36040be5530b c.txt
a.txt と b.txt は完全に同じ値。 c.txt は最後の1文字が大文字なだけで、まったく違う値です。
これで「1GBのファイルをダウンロードしたが、途中で壊れていないか」を、64文字を比べるだけで確かめられます。 中身を送り直して比べる必要がありません。これがハッシュのいちばん素直な用途です。
b1946ac92492d2347c6235b4d2611184 a.txt
b1946ac92492d2347c6235b4d2611184 b.txt
db2480e33cac4bf29fb0803af567ab19 c.txt
md5 は32文字。 これも同じ判定ができています。
守る側として、何を選ぶか
ここは、選び方だけ書きます。 破り方の話は書きません。
| やりたいこと | 使うもの | 使ってはいけないもの |
|---|---|---|
| ハッシュテーブルの置き場所を決める | fnv1a / xxHash など速いもの | sha256(26倍遅く、必要な性質が余っている) |
| ダウンロードしたファイルが壊れていないか | sha256sum / md5sum、どちらでもよい | ― |
| 配布物が改ざんされていないか | sha256 以上+署名 | md5 / sha1(改ざん検知の用途では使わない) |
| パスワードの保存 | bcrypt / scrypt / Argon2 など、わざと遅いもの | sha256 も md5 も不適切。速いから |
| 秘密の値を人に渡して、あとで読ませたい | 暗号化(鍵を別に管理する) | Base64。暗号化ではない |
| URLに変な文字を入れて壊れないようにする | エンコード(URLエンコード) | ― |
上から4行目が、いちばん引っかかったところです。
パスワードの保存に、速いハッシュを使ってはいけません。
ハッシュテーブルでは「速いこと」が長所でした。パスワードでは、それがそのまま短所になります。 本線のパスワード保存の回で、なぜ「わざと遅い」ものを使うのかを扱っています。⑥で sha256 が26倍遅いのを「遅い」と書きましたが、この用途では26倍でも全然足りません。
そして、3行目と2行目の違いも大事です。
md5 と sha1 は「もう使ってはいけない」と一律に言われがちですが、それは正確ではありません。
- 改ざんを防ぐ目的(配布物の検証、署名、証明書)では、md5 と sha1 は使いません
- 偶然の破損を見つける目的(コピーが壊れていないか、重複ファイルの検出、キャッシュのキー)では、md5 は今も普通に使われています。速く、短いからです
「そのハッシュは、誰から何を守っているのか」で決まります。 相手が悪意のある人間なら sha256 以上。 相手が通信エラーやディスクの不調なら md5 でも足ります。 「md5 は禁止」と丸暗記すると、この違いが説明できません。
⑧ JavaScript での使い分け(Object / Map / Set / WeakMap)
ここまでで、Map と Set の中身は分かりました。 最後に、どれを使うかを決められるようにします。
Object のキーは文字列になる
--- 1. Object のキーは文字列になる ---
obj: { '1': 'string の 1' }
件数: 1
map.size: 2
map.get(1) : number の 1
map.get('1'): string の 1
--- 2. オブジェクトをキーにすると ---
o2: { '[object Object]': 'B' }
m2.size: 2 / m2.get(k1): A / m2.get(k2): B
--- 3. 順番 ---
Object: [ '1', '2', 'b', 'a' ]
Map : [ 'b', 2, 'a', 1 ]
--- 4. Object には最初から中身がある ---
'toString' in o4 : true
typeof o4['toString'] : function
new Map().has("toString"): false
Object.create(null) は : false
--- 5. NaN をキーにする ---
map.get(NaN): あり
NaN === NaN : false
5つとも、知らないと事故ります。順に見ます。
1. obj[1] と obj['1'] は同じキー。
2件入れたのに1件になりました。 Object のキーは必ず文字列(か Symbol)に変換されるので、数値の 1 は文字列の '1' になります。Map では別のキーとして2件残ります。
これは「
"1"と1は等しい」という、JavaScriptの最初の落とし穴と同じ根っこの話です。 IDが数値のデータをObjectに入れると、黙って文字列キーになります。 その後Numberに戻し忘れると、型だけがズレたバグになります
2. オブジェクトをキーにすると、全部同じキーになる。
o2 は { '[object Object]': 'B' } です。k1 と k2 が、両方 '[object Object]' という同じ文字列になって、後から入れた B が上書きしました。
Map は2件のまま、正しく引けています。 Map の存在理由の半分がこれです。「オブジェクトをキーにできる」
3. 順番。
Objectは['1', '2', 'b', 'a']— 整数っぽいキーが先に、しかも小さい順に並び替えられましたMapは['b', 2, 'a', 1]— 入れた順そのまま
Objectは挿入順を完全には保ちません。 整数キーだけ勝手に前に来て昇順に並びます。 「入れた順に処理したい」ならMapです。 これは好みではなく、仕様の違いです
4. Object には最初から中身がある。
空の {} に対して 'toString' in obj が true です。 プロトタイプから継承しているからです。
ユーザーが入力した文字列をキーにする場合、これは実害になります。 'toString' や 'constructor' という名前のキーを引くと、入れていないのに値が返ります。
対処は2つです。
Mapを使う。new Map().has('toString')はfalseでしたObject.create(null)で作る。 これは継承が無いのでfalseになります
外から来た文字列をキーにするなら、Object リテラル({})は使わない、が私の結論です。
5. NaN をキーにできる。
NaN === NaN は false なのに、map.get(NaN) は値を返します。 Map のキー比較は === ではなく SameValueZero という規則で、NaN は NaN と同じものとして扱われます。
ここは「知っておく」だけで十分です。 ただし、Map のキー比較が === と完全に同じではないことは覚えておく価値があります。
WeakMap は何のためにあるのか
strong.get(user): 強い参照
weak.get(user) : 弱い参照
strong.size : 1
weak.size : undefined
weak.keys : undefined
user = null にしました
strong.size : 1 (まだ1件。オブジェクトは解放されない)
weak は数えられないので size がありません
WeakMap に文字列キー: TypeError: Invalid value used as weak map key
WeakMap の性質は3つです。
sizeが無く、中身を列挙できません。keysもundefinedです- キーはオブジェクトだけ。 文字列を入れると
TypeErrorになります - キーのオブジェクトが他から参照されなくなったら、
WeakMapの中の項目も消えます
なぜ「列挙できない」のか。 3番のせいです。いつ消えるかが決まっていないので、size を返したら、返した値が信用できません。 「列挙できないのは不便な仕様」ではなく、「消えるものは数えられない」という筋の通った制約でした。
そして、Map のほうを見てください。 user = null にしたのに strong.size は 1 のままです。
Mapにオブジェクトをキーとして入れると、Mapがそのオブジェクトを掴んで離しません。 他の変数を全部nullにしても、Mapに入っている限りメモリから消えません。 これが「Mapを使ったメモリリーク」の形です。 DOM要素や、リクエストごとのオブジェクトをMapに溜めると、deleteを呼び忘れた分がずっと残ります。
WeakMapは、これを避けるためにあります。 「そのオブジェクトが生きている間だけ覚えておきたい」場合に使います。
自作と本物を比べる
最後に、自分で書いたものが本物とどれくらい違うのかを測ります。
最後の行で100秒くらいかかります。 待つ価値があります。
件数 100000 / 探索 100000回
実装 | 構築 | 探索
自作HashTable | 330.1ms | 81.9ms
Map | 24.3ms | 55.5ms
Object | 77.9ms | 41.5ms
配列 indexOf | 0.3ms | 104200.0ms
| 実装 | 構築 | 探索10万回 | Map との比 |
|---|---|---|---|
| 自作 HashTable | 330.1 ms | 81.9 ms | 1.5倍 |
| Map | 24.3 ms | 55.5 ms | 1倍 |
| Object | 77.9 ms | 41.5 ms | 0.75倍 |
配列 indexOf | 0.3 ms | 104200.0 ms | 1878倍 |
自作の JavaScript で書いたハッシュテーブルが、C++ で書かれた
Mapの1.5倍で済みました。これは私が上手いからではありません。 同じアルゴリズムだからです。 配列の
indexOfとの差(1878倍)は、実装の質ではなく、O(n) と O(1) の差です。①で見た「3754倍」の正体が、ここで完全につながりました。
Setが速かったのではなく、私が O(n) の道具で O(1) の仕事をしていただけでした。
構築が自作だけ遅い(330ms)のは、⑤で見たとおりリサイズの分です。 Map はもっと賢く(そして低いレイヤで)やっています。
判断表
| やりたいこと | 使うもの | 理由 |
|---|---|---|
| 「その値が入っているか」だけ知りたい | Set | 値だけ持てばいい。includes は使わない |
| キーと値を対応させたい(キーは文字列) | Map または Object | 迷ったら Map。落とし穴が少ない |
| キーがオブジェクト | Map | Object だと全部 [object Object] になる |
| キーが数値 | Map | Object は文字列に変換してしまう |
| 入れた順に処理したい | Map | Object は整数キーを勝手に前に並べる |
| 外から来た文字列をキーにする | Map または Object.create(null) | {} は toString などを最初から持っている |
| キーが消えたら中身も消えてほしい | WeakMap | Map に入れると掴んで離さない(リークの形) |
| JSONにしたい・そのまま送りたい | Object | Map は JSON.stringify で {} になる |
| 件数が数十件で、キーが固定 | Object | 差は測れない。読みやすさで選ぶ |
| 順番が意味を持つ・端しか触らない | どちらでもない | それはスタックかキュー。前回の話 |
質問は2つ
1. キーは文字列か?
いいえ → Map(数値でもオブジェクトでも)
はい → 2へ
2. そのままJSONにして送るか?
はい → Object
いいえ → Map
迷ったら Map で、ほぼ間違いません。Object を選ぶ理由は「JSONにしたいから」がほとんどでした。
つまずいたところ
遠回りした部分を、消さずに残します。
1. Math.imul を使わず * で書いて、ハッシュが偏った
②で最初、こう書いていました。
h = h * 0x01000193; // ⚠️ 間違い
動きます。 そして散らばりが壊れます。
JavaScript の数値は64bit浮動小数点なので、大きな掛け算をすると下位のビットが失われます。 ハッシュ関数は下位のビットを % で使うので、そこが失われると偏ります。
Math.imul(a, b) は「32bit整数として掛けて、あふれた分を捨てる」関数です。 C言語などで書かれた仕様どおりの挙動を、JavaScriptで再現するための関数でした。「精度が落ちるのを避ける」ではなく「意図的にあふれさせる」ために使います。
2. 「文字コードを足すだけ」のハッシュを書いて、ab と ba が同じになった
②の前に、自分で1つ書きました。
ab : 195
ba : 195
abc: 294
cba: 294
並べ替えただけの文字列が、全部同じハッシュになります。
足し算は順番を無視するからです。 FNV-1a や djb2 が毎回掛け算を挟んでいる理由がこれでした。 「前の結果を大きく動かしてから次を混ぜる」ので、順番が結果に残ります。
人名やIDの並べ替えは、実データでは普通に発生します。 これは実害のあるバグでした。
3. Math.max(...lens) で Maximum call stack size exceeded が出た
④の stats() を、最初こう書いていました。
max: Math.max(...lens),
バケット 16384 までは動いて、131072 で落ちました。
RangeError: Maximum call stack size exceeded
at HashTableChain.stats
... で配列を展開すると、要素の数だけ引数を渡すことになります。 131072個の引数は、コールスタックに載りません。
前回の記事で扱ったエラーが、まったく別の理由でここに出ました。 直し方はこうです。
max: lens.reduce((a, b) => (b > a ? b : a), 0),
Math.max(...arr) は、配列が大きいと壊れる書き方でした。「要素数が数万を超える配列にスプレッドを使わない」は、覚える価値のある1行です。
4. sort で最遅の6件を出す集計が、100万件で破綻した
⑤の bench-spike.js を、最初は100万件でやろうとしました。Array.from({length: N}, ...).sort(...) が非常に遅く、しかもメモリを食いました。
「最遅の6件だけ欲しい」のに、100万件を全部並べ替えていました。 6件だけなら並べ替えは要りません。
記事では10万件に下げて sort のまま残しました。 「測るためのコードが、測る対象より遅い」という、笑えない失敗の記録として残します。
5. リサイズの実装で、置き場所を再計算せず配列を伸ばして壊した
⑤の #resize() を、最初こう書きました。
this.#buckets.length = n; // ⚠️ 長さだけ伸ばす
for (let i = old.length; i < n; i++) this.#buckets[i] = [];
エラーは出ませんでした。 そして get が undefined を返し始めました。
バケット数が変わると % の結果が変わるので、すでに入っているキーの正しい置き場所が全部変わります。 8個のときに fnv1a(key) % 8 = 3 だったキーは、16個になると % 16 で 3 か 11 のどちらかです。3 に置いたままだと、半分が行方不明になります。
リサイズは「配列を伸ばす」ではなく「全員の住所を再計算して引っ越す」です。 遅い理由がここにあります。⑤で119.8ミリ秒かかったのは、手抜きではなく必要な作業でした。
6. 「衝突が0になるバケット数」を探そうとして、時間を溶かした
④の表を作るとき、最長の鎖が 1 になるバケット数を探しました。 見つかりません。
131072バケットに10万件(負荷率0.76)で、最長は 6 でした。 バケットを100万にしても、鎖が 2〜3 のところは残ります。
バケットを件数の何倍にしても、衝突は0にはなりません。 完全にばらけるわけではないので、偏りは必ず残ります。
理解が変わりました。 目標は「衝突を0にする」ではなく、「最長の鎖を小さな定数で押さえる」でした。6件の鎖は、6回比べるだけなので O(1) と呼んで差し支えありません。 O記法の「定数は無視する」が、ここで実用的な意味を持ちました。
7. Object に IDを入れて、型が変わっていることに1時間気づかなかった
⑧の実験は、実際に困ってから書きました。
APIから来た { id: 12, name: 'sato' } の配列を Object に入れて、byId[user.id] = user としていました。あとで Object.keys(byId) を回したら、id が文字列になっていて === の比較が全部 false になりました。
Object に入れた瞬間に、キーは文字列です。 Object.keys が返すのも文字列です。入れたときは数値だったので、疑いませんでした。
Map にしたら消えました。 これは「Map のほうが速いから」ではなく「型が変わらないから」の理由で Map を選ぶ、初めての経験でした。
8. Base64 を「一応隠してある」と思って設定ファイルに書いた
⑦で base64 -d を実際に打つまで、私はBase64 を「読みにくくする処理」くらいには思っていました。
1つも隠れていません。 -d を付ければ戻ります。鍵はありません。
過去に、社内ツールの設定ファイルにトークンを Base64 で書いたことがあります。 平文で書いたのと、まったく同じです。 「変換」と「保護」を混ぜていました。この記事の⑦を書いた理由はこれです。
後片づけ
この記事で作ったものを、全部消します。
まず、何があるか確認します。
a.txt bench-resize.js hash.js open.js table.js
b.txt bench-spike.js hash-speed.js package.json table2.js
bad-hash.js broken-demo.js js-maps.js spread.js try-hash.js
bench-buckets.js c.txt naive.js use-open.js use-table.js
bench-final.js bench-includes.js open-broken.js weak.js
node_modules はありません。 この記事では npm install を1回もしていないので、消すものは自分で書いたファイルだけです。
消す前に、場所を確かめます。
/home/user/cslab/hash
pwd で必ず確認してください。 これから rm -rf を打ちます。別の場所で打つと、消してはいけないものが消えます。 rm で消したものは戻りません(本線の基本コマンドの回で扱いました)。
cslab が消えていれば終わりです。
sha256sum md5sum base64 は Ubuntu に最初から入っているコマンドなので、何も入れていません。 apt も触っていません。これで完全に元通りです。
残しておきたい場合は、
hash.jsとtable2.jsの2つだけコピーしておくと使い回せます。 実務でこれを使うことはありませんが、「なぜMapが速いのか」を思い出したいときに、90行を読み返すのがいちばん速いと思いました。
まとめ — 理解できたこと
- ①の「3754倍」は「
Setが速い」話ではなかった。includesが件数10倍で時間10倍(139 → 1307 → 20478ミリ秒)になる一方、hasは100倍の件数でも 1.52 → 5.45ミリ秒しか増えない。倍率は件数を増やすほど開くので、「何倍速い」という固定の答えは存在しない - 「一発で見つかる」の正体は、探していないこと。 キーをハッシュ関数で数字にして、バケット数で割った余りを添字にする。計算1回で置き場所が決まるので、比較の回数が件数によらない
- ハッシュ関数に必要な性質は「同じ入力なら必ず同じ数字」の1つだけ。 戻せる必要はまったくない。
fnv1a('apple')は何度打っても280767167 - 衝突は事故ではなく必然。 キー3個の段階で
bananaとcherryが両方 0番に入った。40億通りの数字を8個の出口に押し込めば当然で、8個のバケットに9個入れれば、どんな優秀なハッシュ関数でも必ず衝突する getの本当のコストは「ハッシュ計算1回 + そのバケットの中の件数ぶんの比較」。 だから O(1) はハッシュテーブルの性質ではなく、負荷率を低く保っているという運用の結果だった- バケットを1個にしたハッシュテーブルは 4959ミリ秒で、ただの配列と同じだった。 バケット数を8倍にすると時間が8分の1になり(4959 → 1365 → 348)、鎖が「ほぼ1件」になった時点で、それ以上増やしても速くならない(16384と131072がどちらも6.9ミリ秒)
- バケットを増やすのは無料ではない。 131072バケットのとき、62532マスが空だった。メモリの半分が空
- オープンアドレス法で「消したら空に戻す」と、触っていないキーが消える。
bananaを1件消したらcherryとdurianがundefinedになった。エラーは出ず、衝突が始まる件数になってから出る。 だから墓標が要る - リサイズは「配列を伸ばす」ではなく「全員の住所を再計算して引っ越す」。 バケット数が変わると
%の結果が変わるので、既存の全キーの置き場所が無効になる - 10万件を入れる間にリサイズが15回起き、うち1件は平均の30627倍かかった。 そして平均の100倍を超えたのは10万件中15件だけ。これが償却 O(1) の中身で、「平均は綺麗なのに上位1%だけ跳ねる」の正体でもある
- 「必ず0を返すハッシュ関数」でもハッシュテーブルは動く。バグは出ず、遅いだけ。 そして「先頭1文字」という素人の善意で書ける関数が、それとほぼ同じ結果になった(1024バケットのうち1個しか使わず、鎖が20000件)
- 良いハッシュ関数の条件は「散らばること」と「速いこと」の2つ。 sha256 は散らばりは最高だが fnv1a の26倍遅いので、ハッシュテーブルには使わない
- ハッシュ・暗号化・エンコードは全部違う。 戻せない・固定長/鍵があれば戻せる/誰でも戻せる。Base64 は暗号化ではなく、
base64 -dを打てば誰でも読める - 「そのハッシュは誰から何を守っているのか」で選ぶものが変わる。 相手が悪意なら sha256 以上、相手が通信エラーやディスクの不調なら md5 でも足りる。「md5 は禁止」と丸暗記すると、この違いが説明できない
- ハッシュテーブルでは長所だった「速さ」が、パスワード保存ではそのまま短所になる。 同じ「ハッシュ」という言葉が、正反対の要求を指している
Objectのキーは文字列に変換される。obj[1]とobj['1']は同じキーで片方が消え、オブジェクトをキーにすると全部[object Object]になり、整数キーは勝手に前に並べ替えられる。Mapは全部そのままMapにオブジェクトを入れると掴んで離さない。 他の参照を全部消しても解放されない。これがMapによるメモリリークの形で、WeakMapはそれを避けるためにある。 列挙できないのは不便な仕様ではなく、消えるものは数えられないという制約- 自作の JavaScript のハッシュテーブルが、本物の
Mapの1.5倍(81.9ms 対 55.5ms)で済んだ。 一方、配列のindexOfは 1878倍(104200ms)。差は実装の質ではなく O(n) と O(1) の差で、①の3754倍がここで完全につながった - 迷ったら
Map。Objectを選ぶ理由は「そのままJSONにしたいから」がほとんどだった。そして「順番が意味を持ち、端しか触らない」なら、それはハッシュテーブルではなくスタックかキュー
参考リンク
- roadmap.sh — Computer Science — このコースがどの項目を扱っているかの地図
- MDN — Map — ⑧で見た挿入順とキー比較の一次情報
- MDN — Set — ①で
includesの3754倍速かったもの - MDN — WeakMap —
sizeが無い理由の公式の説明 - MDN — Math.imul — つまずき1で必要だった32bit掛け算
- MDN — 等値比較と同一性 —
Mapのキー比較(SameValueZero)が===と違う理由 - MDN — Object.keys — ⑧で整数キーが前に並んだ挙動の仕様
- NIST — Secure Hashing — ⑦で使った sha256 の一次情報と、用途ごとの推奨
- RFC 4648 — The Base16, Base32, and Base64 Data Encodings — Base64 が「エンコード」として定義されている一次情報
- Node.js 公式 — crypto.createHash — ⑥で sha256 と md5 の速度を測るのに使った
次に読む
この記事は 【深掘り】コンピュータ科学 の 7 / 25 本目です。
上から順に読めば積み上がるように並べています。 飛ばしても構いませんが、詰まったら前の回に戻ってください。
全体の順路は はじめに にあります。
roadmap.sh のどこをやっているか
- ハッシュ関数と衝突を自分で作る
- ハッシュ・暗号化・エンコードは別物
この記事は、上の項目を実際に手を動かして確かめる回です。

コメント