ハッシュテーブル — 10万件のincludesで止まる

ハッシュテーブル。鍵のカードと分類された引き出し、虫眼鏡。

10万件の配列をincludesで探すと止まります。ハッシュテーブルを自作して、なぜSetやMapが速いのかを確かめます。

前回: スタックとキュー — call stack size exceeded の正体

これは【深掘り】の記事です。本線の順路ではありません。 本線のデータ構造を自作する回で「配列は先頭への挿入が遅い」ところまでやった人が、「では、なぜ 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ナノ秒)は、要求が正反対であること

この記事でやること

  1. ~/cslab/hash/ を作り、10万件の includes と Set.has を実測する。 件数を10倍ずつ変えて、差が何倍まで開くかを表にする
  2. ハッシュ関数(FNV-1a と djb2)を自分で書く。 同じ入力で必ず同じ数字が出ることを確かめ、割った余りが置き場所になるところまで手で見る
  3. ハッシュテーブル(set / get / delete / has)を書き、dump() でバケットの中身を表示する。 どのキーがどこに入ったかを目で見る
  4. わざと衝突させる。 チェイン法とオープンアドレス法の2つを実装し、オープンアドレス法の削除が壊れることを実演する。バケット数を変えて最悪の鎖の長さを測り、O(1) が O(n) に落ちる表を作る
  5. 負荷率とリサイズを実装し、リサイズが起きた回数と、そのときだけ遅くなることを実測する
  6. わざと悪いハッシュ関数(必ず0を返す)に差し替えて、ハッシュテーブルがただの配列になることを測る
  7. sha256sum / md5sum / base64 を実際に打ち、ハッシュ・暗号化・エンコードを1枚の表に分ける
  8. 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) は比例して増える。本線の計算量の回でやりました

① まず、止まるコードを自分で書く

説明の前に、困ってから始めます。 困っていないと、仕組みの話は頭に入りません。

作業場所を作る

bash
$ mkdir -p ~/cslab/hash
$ cd ~/cslab/hash
$ node -v
v22.14.0

v20 以上なら大丈夫です。 出ない場合は本線のnpmの回に戻ってください。

この記事では npm install を1回もしません。 ライブラリを入れたら、正体を確かめるという目的が消えます。

package.json だけ置きます。import を使うためです。

bash
$ cat > package.json <<'EOF'
  { "type": "module" }
  EOF
$ cat package.json
{ "type": "module" }

10万件を用意して、両方で探す

bash
$ cat > bench-includes.js <<'EOF'
  function run(N, TRY) {
    const keys = [];
    for (let i = 0; i < N; i++) keys.push('user-' + i);
  
    const arr = keys.slice();
    const set = new Set(keys);
  
    // 探す相手を先に決めておく(乱数の生成時間を測らないため)
    const targets = [];
    for (let i = 0; i < TRY; i++) targets.push('user-' + Math.floor(Math.random() * N));
  
    let t = performance.now();
    let hit = 0;
    for (const q of targets) if (arr.includes(q)) hit++;
    const t1 = performance.now() - t;
  
    t = performance.now();
    hit = 0;
    for (const q of targets) if (set.has(q)) hit++;
    const t2 = performance.now() - t;
  
    console.log(
      String(N).padStart(9), '件  includes',
      t1.toFixed(1).padStart(8), 'ms   has',
      t2.toFixed(2).padStart(6), 'ms   倍率',
      String(Math.round(t1 / t2)).padStart(5)
    );
  }
  
  console.log('探索回数はすべて 10000 回');
  run(10_000, 10_000);
  run(100_000, 10_000);
  run(1_000_000, 10_000);
  EOF
$ node bench-includes.js

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 ms1.52 ms91倍
10万1307.3 ms2.92 ms448倍
100万20478.4 ms5.45 ms3754倍

[スクリーンショット: 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段でやります。

  1. 文字列を、なにか大きな数字にする ← これがハッシュ関数
  2. その数字を、配列の長さで割った余りにする ← これで必ず範囲内に収まる

2段目は割り算の余り(%)だけです。 8で割った余りは必ず 0〜7 になります。だから、バケットが8個なら添字は必ず有効です。

1段目に必要な性質は、たった1つです。

同じ文字列を渡したら、必ず同じ数字が返ること。

これだけです。 逆に言うと、戻せる必要はまったくありません。 数字から元の文字列を復元する必要は、置き場所を決めるだけなら1度もありません。ここが⑦で整理する話の入口です。

FNV-1a を書く

有名な短いハッシュ関数を2つ書きます。どちらも10行以下です。

bash
$ cat > hash.js <<'EOF'
  // FNV-1a(32bit)
  export function fnv1a(str) {
    let h = 0x811c9dc5;                 // 決め打ちの初期値
    for (let i = 0; i < str.length; i++) {
      h = h ^ str.charCodeAt(i);        // 1文字ぶん混ぜる(排他的論理和)
      h = Math.imul(h, 0x01000193);     // 決め打ちの数で掛ける(32bit掛け算)
    }
    return h >>> 0;                     // 符号なし32bitにする
  }
  
  // djb2
  export function djb2(str) {
    let h = 5381;
    for (let i = 0; i < str.length; i++) {
      h = Math.imul(h, 33) + str.charCodeAt(i);
    }
    return h >>> 0;
  }
  EOF

やっていることは、1文字ずつ数字にして混ぜているだけです。

  • str.charCodeAt(i) はその位置の文字の番号です。'a' なら 97。文字が番号であることは、文字コードの回でやりました
  • ^(排他的論理和)はビットごとに混ぜる演算です。ここでは「前の結果に新しい文字を混ぜ込む」ために使っています
  • Math.imul は 32bitとして掛け算する関数です。* を使ってはいけません(つまずき1で書きます)
  • >>> 0 は結果を 0以上の32bit整数にする決まり文句です。これを忘れるとマイナスの値が返って、% の結果もマイナスになり、添字として使えません

0x811c9dc5 と 0x01000193 の意味を、私は説明できません。 FNV-1a の仕様で決められている定数です。「散らばりが良くなるように選ばれた数」というところまでが、私の理解です。 自分で選ぶ話ではないので、そのまま使います。

同じ入力なら同じ数字が出ることを確かめる

bash
$ cat > try-hash.js <<'EOF'
  import { fnv1a, djb2 } from './hash.js';
  
  const words = ['apple', 'banana', 'cherry', 'a', 'b', 'ab', 'ba', ''];
  
  console.log('key      fnv1a         djb2');
  for (const w of words) {
    console.log(JSON.stringify(w).padEnd(9), String(fnv1a(w)).padStart(11), String(djb2(w)).padStart(11));
  }
  
  console.log('');
  console.log('同じ入力を3回:');
  console.log(fnv1a('apple'), fnv1a('apple'), fnv1a('apple'));
  
  console.log('');
  console.log('8で割った余り(バケット8個ぶんの置き場所):');
  for (const w of words) {
    console.log(JSON.stringify(w).padEnd(9), fnv1a(w) % 8);
  }
  EOF
$ node try-hash.js
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

確かめられたことを並べます。

  1. fnv1a('apple') は3回とも 280767167。 乱数ではありません。 何度打っても、別のマシンで打っても同じです。「同じキーを渡したら同じ場所」が保証されるので、置いた場所に取りに行けます
  2. 'a' と 'b' は1文字違うだけで、38億と38億でも桁は同じですが値は全然違います。 1文字変えたら結果が大きく変わるのが、良い散らばりの条件です
  3. 'ab' と 'ba' は違う値。 文字を足すだけの雑なハッシュだと、これが同じになります(つまずき2で失敗しました)
  4. 空文字列でも値が出ます。 初期値がそのまま返るだけです

そして、いちばん大事なのは最後のブロックです。

banana と cherry は、どちらも 0 になりました。

もう衝突しています。 キーが3個しかない段階で、です。

これは私のハッシュ関数が下手だからではありません。 3649609552 と 1232791672 という全然違う数字を、8で割った余りにしたからです。8種類しか出口が無いところに、40億通りの数字を押し込んでいます。

衝突は、避けられません。 8個のバケットに9個のキーを入れれば、どんなに優秀なハッシュ関数でも必ず衝突します。 出口が足りないからです。 だから、ハッシュテーブルの実装は「衝突をどう処理するか」がほぼ全部です。

これで、この記事の山場(④)の準備ができました。まず動くものを作ります。


③ ハッシュテーブルを実装する(そして中身を目で見る)

40行で書ける

set / get / has / delete を書きます。衝突は、いちばん素直な方法(チェイン法)で処理します。 各バケットに配列を持って、そこに並べるだけです。

bash
$ cat > table.js <<'EOF'
  import { fnv1a } from './hash.js';
  
  export class HashTableChain {
    #buckets;
    #size = 0;
  
    constructor(bucketCount = 8, hashFn = fnv1a) {
      this.#buckets = new Array(bucketCount);
      for (let i = 0; i < bucketCount; i++) this.#buckets[i] = [];
      this.hashFn = hashFn;
    }
  
    // ここが全部。キー → 添字
    #indexOf(key) {
      return this.hashFn(key) % this.#buckets.length;
    }
  
    set(key, value) {
      const bucket = this.#buckets[this.#indexOf(key)];
      for (const pair of bucket) {
        if (pair[0] === key) { pair[1] = value; return this; }   // 既にあれば上書き
      }
      bucket.push([key, value]);
      this.#size++;
      return this;
    }
  
    get(key) {
      const bucket = this.#buckets[this.#indexOf(key)];
      for (const pair of bucket) if (pair[0] === key) return pair[1];
      return undefined;
    }
  
    has(key) {
      const bucket = this.#buckets[this.#indexOf(key)];
      for (const pair of bucket) if (pair[0] === key) return true;
      return false;
    }
  
    delete(key) {
      const bucket = this.#buckets[this.#indexOf(key)];
      for (let i = 0; i < bucket.length; i++) {
        if (bucket[i][0] === key) {
          bucket.splice(i, 1);
          this.#size--;
          return true;
        }
      }
      return false;
    }
  
    get size() { return this.#size; }
    get bucketCount() { return this.#buckets.length; }
  
    // ⚠️ 中身を目で見るための関数。実務では要らないが、この記事では主役
    dump() {
      console.log(`件数 ${this.#size} / バケット ${this.#buckets.length}`);
      this.#buckets.forEach((bucket, i) => {
        const body = bucket.length === 0
          ? '(空)'
          : bucket.map(([k, v]) => `${k}=${v}`).join(' -> ');
        console.log(`  [${String(i).padStart(2)}] ${body}`);
      });
    }
  
    stats() {
      const lens = this.#buckets.map((b) => b.length);
      return {
        size: this.#size,
        buckets: this.#buckets.length,
        empty: lens.filter((n) => n === 0).length,
        max: lens.reduce((a, b) => (b > a ? b : a), 0),
        load: (this.#size / this.#buckets.length).toFixed(2),
      };
    }
  }
  EOF

dump() を最初に書いたことが、この記事でいちばん役に立ちました。 ハッシュテーブルは中身が見えないから魔法に見えるのです。見えれば、驚くところが1つも無くなります。

動かして、中身を見る

bash
$ cat > use-table.js <<'EOF'
  import { HashTableChain } from './table.js';
  
  const t = new HashTableChain(8);
  t.set('apple', 100);
  t.set('banana', 200);
  t.set('cherry', 300);
  t.set('durian', 400);
  t.dump();
  
  console.log('');
  console.log("get('banana') :", t.get('banana'));
  console.log("get('grape')  :", t.get('grape'));
  console.log("has('apple')  :", t.has('apple'));
  console.log("delete('apple'):", t.delete('apple'));
  console.log("delete('apple'):", t.delete('apple'));
  console.log('');
  t.dump();
  EOF
$ node use-table.js
件数 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万件を入れて、最悪の鎖の長さと探索時間を測ります。

bash
$ cat > bench-buckets.js <<'EOF'
  import { HashTableChain } from './table.js';
  
  const N = 100_000;
  const keys = [];
  for (let i = 0; i < N; i++) keys.push('user-' + i);
  
  const TRY = 10_000;
  const targets = [];
  for (let i = 0; i < TRY; i++) targets.push('user-' + Math.floor(Math.random() * N));
  
  console.log('バケット数    負荷率   最長の鎖   空バケット   10000回の探索');
  for (const bc of [1, 8, 64, 1024, 16384, 131072]) {
    const t = new HashTableChain(bc);
    for (let i = 0; i < N; i++) t.set(keys[i], i);
    const s = t.stats();
  
    const st = performance.now();
    let sum = 0;
    for (const q of targets) sum += t.get(q);
    const el = performance.now() - st;
  
    console.log(
      String(bc).padStart(9),
      String(s.load).padStart(9),
      String(s.max).padStart(9),
      String(s.empty).padStart(11),
      (el.toFixed(1) + ' ms').padStart(14)
    );
  }
  EOF
$ node bench-buckets.js

最初の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回実質
11000001000004959.1 msただの配列
812500125041365.2 ms配列の8分の1
6415621583348.5 ms配列の64分の1
102497.713028.5 msまだ鎖が長い
163846.1186.9 msほぼ O(1)
1310720.7666.9 ms増やしても速くならない

読み方を4つ書きます。

  1. バケット1個のハッシュテーブルは、4959ミリ秒。 ①で測った配列の includes(10万件で1307ミリ秒、探索1万回)と同じ桁です。ハッシュテーブルを名乗っていても、全部同じバケットに入るなら、先頭から順に見る配列と何も変わりません
  2. バケット数を8倍にすると、時間がだいたい8分の1になります(4959 → 1365 → 348)。鎖の長さに比例している、つまり O(n) の n がバケット数で割られているだけです
  3. 16384 で 6.9ミリ秒になり、131072 にしても 6.9ミリ秒でした。 鎖が「ほぼ1件」になった時点で、それ以上は速くなりません。 ここが O(1) の上限です
  4. 131072 のとき、62532マスが空でした。メモリの半分が空です。バケットを増やすのは無料ではありません

結論を1行にすると、こうです。

O(1) は、ハッシュテーブルの性質ではありません。 「負荷率を低く保っている」という運用が成り立っているときの性質です。

だから⑤で、負荷率を自動で保つ仕組みを実装します。それが無いハッシュテーブルは、件数が増えると勝手に O(n) に落ちます。

もう1つの解き方:オープンアドレス法

チェイン法は「バケットの中に配列を持つ」でした。もう1つのやり方は、「空いている次のマスにずらして置く」です。

こちらのほうが速いことがあります。 配列が1本で済むので、メモリの並びが素直だからです。代わりに、削除が本当に面倒です。

bash
$ cat > open.js <<'EOF'
  import { fnv1a } from './hash.js';
  
  const EMPTY = Symbol('empty');   // まだ何も入っていない
  const TOMB  = Symbol('tomb');    // ⚠️ 消したが、通り道としては生きている(墓標)
  
  export class HashTableOpen {
    #keys;
    #values;
    #size = 0;
  
    constructor(bucketCount = 8, hashFn = fnv1a) {
      this.#keys = new Array(bucketCount).fill(EMPTY);
      this.#values = new Array(bucketCount).fill(undefined);
      this.hashFn = hashFn;
    }
  
    // 空きか目的のキーが見つかるまで、1マスずつ後ろへずらして見る
    #probe(key) {
      const n = this.#keys.length;
      let i = this.hashFn(key) % n;
      let steps = 1;
      let firstTomb = -1;
      while (true) {
        const k = this.#keys[i];
        if (k === EMPTY) return { index: i, found: false, steps, firstTomb };
        if (k === TOMB) { if (firstTomb < 0) firstTomb = i; }
        else if (k === key) return { index: i, found: true, steps, firstTomb };
        i = (i + 1) % n;      // 端まで行ったら 0 に戻る
        steps++;
        if (steps > n) return { index: -1, found: false, steps, firstTomb };
      }
    }
  
    set(key, value) {
      const r = this.#probe(key);
      if (r.found) { this.#values[r.index] = value; return this; }
      if (r.index < 0 && r.firstTomb < 0) throw new Error('満杯です');
      const i = r.firstTomb >= 0 ? r.firstTomb : r.index;   // 墓標を再利用する
      this.#keys[i] = key;
      this.#values[i] = value;
      this.#size++;
      return this;
    }
  
    get(key) {
      const r = this.#probe(key);
      return r.found ? this.#values[r.index] : undefined;
    }
  
    has(key) { return this.#probe(key).found; }
  
    // 何マス見たかを外から見られるようにしておく(衝突の観察用)
    steps(key) { return this.#probe(key).steps; }
  
    delete(key) {
      const r = this.#probe(key);
      if (!r.found) return false;
      this.#keys[r.index] = TOMB;      // ⚠️ EMPTY にしてはいけない
      this.#values[r.index] = undefined;
      this.#size--;
      return true;
    }
  
    get size() { return this.#size; }
  
    dump() {
      console.log(`件数 ${this.#size} / マス ${this.#keys.length}`);
      this.#keys.forEach((k, i) => {
        const label = k === EMPTY ? '(空)' : k === TOMB ? '★墓標' : `${k}=${this.#values[i]}`;
        console.log(`  [${String(i).padStart(2)}] ${label}`);
      });
    }
  }
  EOF
$ cat > use-open.js <<'EOF'
  import { HashTableOpen } from './open.js';
  
  const t = new HashTableOpen(8);
  t.set('apple', 100);
  t.set('banana', 200);
  t.set('cherry', 300);
  t.set('durian', 400);
  t.dump();
  
  console.log('');
  console.log('cherry を探すのに見たマスの数:', t.steps('cherry'));
  console.log('durian を探すのに見たマスの数:', t.steps('durian'));
  
  console.log('');
  console.log('--- banana を削除 ---');
  t.delete('banana');
  t.dump();
  
  console.log('');
  console.log("delete後の get('cherry'):", t.get('cherry'));
  console.log("delete後の get('durian'):", t.get('durian'));
  EOF
$ node use-open.js
件数 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 個)

「見たマスの数」がそのままコストです。 チェイン法の「鎖の長さ」と、同じものを別の形で数えているだけです。

墓標が無いと何が起きるか(実演します)

「消したら空に戻す」で何が悪いのか、口で言っても納得できませんでした。 壊れたものを作って動かします。

bash
$ cat > open-broken.js <<'EOF'
  import { fnv1a } from './hash.js';
  const EMPTY = Symbol('empty');
  
  export class HashTableOpenBroken {
    #keys; #values; #size = 0;
    constructor(bucketCount = 8) {
      this.#keys = new Array(bucketCount).fill(EMPTY);
      this.#values = new Array(bucketCount).fill(undefined);
    }
    #find(key) {
      const n = this.#keys.length;
      let i = fnv1a(key) % n;
      for (let s = 0; s < n; s++) {
        if (this.#keys[i] === EMPTY) return { index: i, found: false };
        if (this.#keys[i] === key) return { index: i, found: true };
        i = (i + 1) % n;
      }
      return { index: -1, found: false };
    }
    set(key, value) {
      const r = this.#find(key);
      if (!r.found) this.#size++;
      this.#keys[r.index] = key;
      this.#values[r.index] = value;
      return this;
    }
    get(key) { const r = this.#find(key); return r.found ? this.#values[r.index] : undefined; }
    delete(key) {
      const r = this.#find(key);
      if (!r.found) return false;
      this.#keys[r.index] = EMPTY;        // ⚠️ ここ。空に戻すだけ
      this.#values[r.index] = undefined;
      this.#size--;
      return true;
    }
  }
  EOF
$ cat > broken-demo.js <<'EOF'
  import { HashTableOpenBroken } from './open-broken.js';
  
  const t = new HashTableOpenBroken(8);
  t.set('apple', 100);
  t.set('banana', 200);
  t.set('cherry', 300);
  t.set('durian', 400);
  
  console.log('削除前 cherry:', t.get('cherry'));
  console.log('削除前 durian:', t.get('durian'));
  
  t.delete('banana');
  console.log('banana を削除しました');
  
  console.log('削除後 cherry:', t.get('cherry'));
  console.log('削除後 durian:', t.get('durian'));
  EOF
$ node broken-demo.js
削除前 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倍にして、全部入れ直す。

「全部入れ直す」が要ることに注意してください。 バケット数が変わると % の結果が変わるので、今までの置き場所が全員間違いになります。 配列を伸ばすだけでは済みません。

実装する(リサイズの記録も取る)

bash
$ cat > table2.js <<'EOF'
  import { fnv1a } from './hash.js';
  
  export class HashTable {
    #buckets;
    #size = 0;
    #maxLoad;
    resizeCount = 0;
    resizeLog = [];
  
    constructor(bucketCount = 8, maxLoad = 0.75, hashFn = fnv1a) {
      this.#buckets = Array.from({ length: bucketCount }, () => []);
      this.#maxLoad = maxLoad;
      this.hashFn = hashFn;
    }
  
    #indexOf(key, n = this.#buckets.length) {
      return this.hashFn(key) % n;
    }
  
    set(key, value) {
      const bucket = this.#buckets[this.#indexOf(key)];
      for (const pair of bucket) {
        if (pair[0] === key) { pair[1] = value; return this; }
      }
      bucket.push([key, value]);
      this.#size++;
      if (this.#size / this.#buckets.length > this.#maxLoad) this.#resize();
      return this;
    }
  
    #resize() {
      const t0 = performance.now();
      const old = this.#buckets;
      const n = old.length * 2;
      this.#buckets = Array.from({ length: n }, () => []);
      for (const bucket of old) {
        for (const pair of bucket) {
          this.#buckets[this.#indexOf(pair[0], n)].push(pair);   // ⚠️ 全員の置き場所を再計算
        }
      }
      this.resizeCount++;
      this.resizeLog.push({ at: this.#size, buckets: n, ms: +(performance.now() - t0).toFixed(2) });
    }
  
    get(key) {
      const bucket = this.#buckets[this.#indexOf(key)];
      for (const pair of bucket) if (pair[0] === key) return pair[1];
      return undefined;
    }
    has(key) {
      const bucket = this.#buckets[this.#indexOf(key)];
      for (const pair of bucket) if (pair[0] === key) return true;
      return false;
    }
    delete(key) {
      const bucket = this.#buckets[this.#indexOf(key)];
      for (let i = 0; i < bucket.length; i++) {
        if (bucket[i][0] === key) { bucket.splice(i, 1); this.#size--; return true; }
      }
      return false;
    }
  
    get size() { return this.#size; }
    get bucketCount() { return this.#buckets.length; }
    stats() {
      const lens = this.#buckets.map((b) => b.length);
      return {
        size: this.#size,
        buckets: this.#buckets.length,
        max: lens.reduce((a, b) => (b > a ? b : a), 0),
        empty: lens.filter((n) => n === 0).length,
        load: (this.#size / this.#buckets.length).toFixed(2),
      };
    }
  }
  EOF
$ cat > bench-resize.js <<'EOF'
  import { HashTable } from './table2.js';
  
  const N = 100_000;
  const t = new HashTable(8, 0.75);
  
  const start = performance.now();
  for (let i = 0; i < N; i++) t.set('user-' + i, i);
  const total = performance.now() - start;
  
  console.log('入れた件数        :', t.size);
  console.log('最終バケット数    :', t.bucketCount);
  console.log('リサイズ回数      :', t.resizeCount);
  console.log('合計時間          :', total.toFixed(1), 'ms');
  console.log('1件あたり         :', (total / N * 1000).toFixed(3), 'マイクロ秒');
  console.log('');
  console.log('リサイズが起きた瞬間(最後の6回):');
  console.log('  件数     新バケット数   かかった時間');
  for (const r of t.resizeLog.slice(-6)) {
    console.log(String(r.at).padStart(8), String(r.buckets).padStart(13), (r.ms + ' ms').padStart(15));
  }
  console.log('');
  console.log('リサイズに使った合計時間:', t.resizeLog.reduce((a, r) => a + r.ms, 0).toFixed(1), 'ms');
  console.log('最終の状態:', JSON.stringify(t.stats()));
  EOF
$ node bench-resize.js
入れた件数        : 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件ずつ測ります。

bash
$ cat > bench-spike.js <<'EOF'
  import { HashTable } from './table2.js';
  
  const N = 100_000;
  const t = new HashTable(8, 0.75);
  const times = new Float64Array(N);
  
  for (let i = 0; i < N; i++) {
    const a = performance.now();
    t.set('user-' + i, i);
    times[i] = performance.now() - a;
  }
  
  let sum = 0;
  for (let i = 0; i < N; i++) sum += times[i];
  const avg = sum / N;
  
  const idx = Array.from({ length: N }, (_, i) => i)
    .sort((a, b) => times[b] - times[a])
    .slice(0, 6);
  
  console.log('1件あたりの平均   :', (avg * 1000).toFixed(3), 'マイクロ秒');
  console.log('');
  console.log('遅かった6件:');
  console.log('  何件目     かかった時間      平均の何倍');
  for (const i of idx) {
    console.log(
      String(i + 1).padStart(8),
      (times[i].toFixed(2) + ' ms').padStart(15),
      String(Math.round(times[i] / avg)).padStart(13)
    );
  }
  
  let over = 0;
  for (let i = 0; i < N; i++) if (times[i] > avg * 100) over++;
  console.log('');
  console.log('平均の100倍を超えた件数:', over, '/', N);
  EOF
$ node bench-spike.js
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つだけ

散らばること

ハッシュテーブルの性能は、ハッシュ関数の散らばりで決まります。 ④で見たとおり、鎖が長くなればそれだけ遅くなるからです。

散らばりを絵で見ます。

bash
$ cat > spread.js <<'EOF'
  import { fnv1a } from './hash.js';
  const firstChar = (s) => (s.length ? s.charCodeAt(0) : 0);
  
  function histogram(name, fn, n = 16, count = 1600) {
    const bins = new Array(n).fill(0);
    for (let i = 0; i < count; i++) bins[fn('user-' + i) % n]++;
    const ideal = count / n;
    console.log(name + '  (理想は各 ' + ideal + ' 件)');
    bins.forEach((c, i) => {
      console.log('  [' + String(i).padStart(2) + '] ' + String(c).padStart(5) + ' '
        + '#'.repeat(Math.min(40, Math.round(c / ideal * 20))));
    });
    const worst = bins.reduce((a, b) => (b > a ? b : a), 0);
    console.log('  最多 ' + worst + ' 件 / 理想の ' + (worst / ideal).toFixed(2) + ' 倍');
    console.log('');
  }
  
  histogram('fnv1a', fnv1a);
  histogram('先頭1文字', firstChar);
  EOF
$ node spread.js
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 は、コンストラクタでハッシュ関数を受け取るように書いてあります。 差し替えて測ります。

bash
$ cat > bad-hash.js <<'EOF'
  import { HashTableChain } from './table.js';
  import { fnv1a, djb2 } from './hash.js';
  
  const zero       = () => 0;                                    // ⚠️ 必ず0
  const firstChar  = (s) => (s.length ? s.charCodeAt(0) : 0);
  const lengthOnly = (s) => s.length;
  
  const N = 20_000;
  const keys = [];
  for (let i = 0; i < N; i++) keys.push('user-' + i);
  const TRY = 2_000;
  const targets = [];
  for (let i = 0; i < TRY; i++) targets.push('user-' + Math.floor(Math.random() * N));
  
  function run(name, fn) {
    const t = new HashTableChain(1024, fn);
    const b0 = performance.now();
    for (let i = 0; i < N; i++) t.set(keys[i], i);
    const build = performance.now() - b0;
    const s = t.stats();
  
    const g0 = performance.now();
    let sum = 0;
    for (const q of targets) sum += t.get(q);
    const get = performance.now() - g0;
  
    console.log([name, s.buckets - s.empty, s.max, build.toFixed(1) + 'ms', get.toFixed(1) + 'ms'].join(' | '));
  }
  
  console.log('件数 ' + N + ' / バケット 1024 で固定 / 探索 ' + TRY + '回');
  console.log('hash | 使ったバケット | 最長の鎖 | 構築 | 探索');
  run('fnv1a', fnv1a);
  run('djb2', djb2);
  run('first-char', firstChar);
  run('length-only', lengthOnly);
  run('always-zero', zero);
  EOF
$ node bad-hash.js
件数 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
ハッシュ関数使ったバケット最長の鎖構築探索
fnv1a1024 / 10243513.5 ms4.0 ms
djb21018 / 10244010.1 ms3.5 ms
先頭1文字120000906.1 ms84.5 ms
文字数だけ510000533.9 ms54.8 ms
必ず0120000950.8 ms95.2 ms

「必ず0を返すハッシュ関数」でも、ハッシュテーブルは動きます。 バグは出ません。遅いだけです。 1024個のバケットのうち1個しか使わず、そこに20000件が鎖になりました。 ハッシュテーブルという名前の、ただの配列です。

そして怖いのは「先頭1文字」です。 これは悪意ではなく、素人の善意で書けるハッシュ関数です。必ず0を返す関数を書く人はいません。 でも「先頭の文字コードでいいだろう」は、書きます。私は書きました。

結果は「必ず0」とほぼ同じでした。 キーが user- や 2026- のような共通の接頭辞を持つのは、実データではむしろ普通です。

速いこと

もう1つの条件は速さです。 ハッシュ関数は set でも get でも毎回呼ばれるので、ここが遅いと全部遅くなります。

bash
$ cat > hash-speed.js <<'EOF'
  import { fnv1a, djb2 } from './hash.js';
  import { createHash } from 'node:crypto';
  
  const keys = [];
  for (let i = 0; i < 200_000; i++) keys.push('user-' + i);
  
  function bench(name, fn) {
    const t = performance.now();
    let acc = 0;
    for (const k of keys) acc += fn(k);
    const el = performance.now() - t;
    console.log([name, el.toFixed(1) + 'ms', (el / keys.length * 1e6).toFixed(0) + 'ns/回'].join(' | '));
  }
  
  console.log('20万件の文字列をハッシュする時間');
  console.log('hash | 合計 | 1回あたり');
  bench('fnv1a', fnv1a);
  bench('djb2', djb2);
  bench('sha256', (s) => createHash('sha256').update(s).digest()[0]);
  bench('md5', (s) => createHash('md5').update(s).digest()[0]);
  EOF
$ node hash-speed.js
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 / fnv1aAES / RSA / TLS の中身Base64 / URLエンコード / UTF-8
秘密を守れるか用途次第鍵を守れば守れる1つも守れない

いちばん多い誤解は、いちばん下の行です。

Base64 は暗号化ではありません。 読めない見た目になるだけです。

実際に打って確かめる

Base64 が誰でも戻せることを、まず見ます。

bash
$ echo -n "password123" | base64
cGFzc3dvcmQxMjM=

では戻します。

bash
$ echo "cGFzc3dvcmQxMjM=" | base64 -d
password123

鍵を1つも渡していません。 -d を付けただけです。Base64 は「戻し方が公開されている変換」です。秘密にする機能は、最初から入っていません。

設定ファイルに Base64 で書いてある値を見て「暗号化されている」と思ってはいけません。 base64 -d を打てば読めます。 Kubernetes の Secret がそうです(詳しくは深掘りの別コースの話なので、ここでは名前だけ)。

次に、ハッシュです。

bash
$ echo -n "password123" | sha256sum
$ echo -n "password124" | sha256sum
$ echo -n "" | sha256sum
ef92b778bafe771e89245b89ecbc08a44a4e166c06659911881f383d4473e94f  -
33631376724e5d5480fa397dfcf03b66ad47b934ab495174d7058c38f2bb0087  -
e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855  -

3つとも 64文字です。 - は「標準入力から読んだ」という印です。

見てほしいのは2つです。

  1. password123 と password124 は1文字違いですが、結果は最初の1文字から全然違います。 「少し似た入力なら少し似た出力」にはなりません(これは意図的な設計です)
  2. 空文字列でも64文字出ます。 入力が0バイトでも64文字。1GBのファイルでも64文字です。 これが「固定長」です

入力の長さによらず64文字なら、当然こうなります。

戻せません。 1GBの情報を64文字に押し込んでいるので、捨てられた情報が復元できるはずがありません。 そして、違う入力が同じ結果になる組み合わせも、必ず存在します。 出口の数(有限)より入口の数(無限)のほうが多いからです。②で banana と cherry が同じ 0番に入ったのと、同じ理屈です。

ファイルが同じかどうかを確かめる

「戻せない」が役に立つ場面が、これです。

bash
$ printf 'hello\n' > a.txt
$ printf 'hello\n' > b.txt
$ printf 'hellO\n' > c.txt
$ sha256sum a.txt b.txt c.txt
5891b5b522d5df086d0ff0b110fbd9d21bb4fc7163af34d08286a2e846f6be03  a.txt
5891b5b522d5df086d0ff0b110fbd9d21bb4fc7163af34d08286a2e846f6be03  b.txt
0655937a5582c55b9ac610ed7ce474ed9be0a0fbefe9afcba31b36040be5530b  c.txt

a.txt と b.txt は完全に同じ値。 c.txt は最後の1文字が大文字なだけで、まったく違う値です。

これで「1GBのファイルをダウンロードしたが、途中で壊れていないか」を、64文字を比べるだけで確かめられます。 中身を送り直して比べる必要がありません。これがハッシュのいちばん素直な用途です。

bash
$ md5sum a.txt b.txt c.txt
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 のキーは文字列になる

bash
$ cat > js-maps.js <<'EOF'
  console.log('--- 1. Object のキーは文字列になる ---');
  const obj = {};
  obj[1] = 'number の 1';
  obj['1'] = 'string の 1';
  console.log('obj:', obj);
  console.log('件数:', Object.keys(obj).length);
  
  const map = new Map();
  map.set(1, 'number の 1');
  map.set('1', 'string の 1');
  console.log('map.size:', map.size);
  console.log('map.get(1) :', map.get(1));
  console.log("map.get('1'):", map.get('1'));
  
  console.log('');
  console.log('--- 2. オブジェクトをキーにすると ---');
  const k1 = { id: 1 };
  const k2 = { id: 2 };
  const o2 = {};
  o2[k1] = 'A';
  o2[k2] = 'B';
  console.log('o2:', o2);
  const m2 = new Map();
  m2.set(k1, 'A');
  m2.set(k2, 'B');
  console.log('m2.size:', m2.size, '/ m2.get(k1):', m2.get(k1), '/ m2.get(k2):', m2.get(k2));
  
  console.log('');
  console.log('--- 3. 順番 ---');
  const o3 = {};
  o3['b'] = 1; o3[2] = 1; o3['a'] = 1; o3[1] = 1;
  console.log('Object:', Object.keys(o3));
  const m3 = new Map();
  m3.set('b', 1); m3.set(2, 1); m3.set('a', 1); m3.set(1, 1);
  console.log('Map   :', [...m3.keys()]);
  
  console.log('');
  console.log('--- 4. Object には最初から中身がある ---');
  const o4 = {};
  console.log("'toString' in o4         :", 'toString' in o4);
  console.log("typeof o4['toString']    :", typeof o4['toString']);
  console.log('new Map().has("toString"):', new Map().has('toString'));
  const o5 = Object.create(null);
  console.log("Object.create(null) は    :", 'toString' in o5);
  
  console.log('');
  console.log('--- 5. NaN をキーにする ---');
  const m5 = new Map();
  m5.set(NaN, 'あり');
  console.log('map.get(NaN):', m5.get(NaN));
  console.log('NaN === NaN :', NaN === NaN);
  EOF
$ node js-maps.js
--- 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 は何のためにあるのか

bash
$ cat > weak.js <<'EOF'
  const strong = new Map();
  const weak = new WeakMap();
  
  let user = { name: 'sato' };
  strong.set(user, '強い参照');
  weak.set(user, '弱い参照');
  
  console.log('strong.get(user):', strong.get(user));
  console.log('weak.get(user)  :', weak.get(user));
  console.log('strong.size     :', strong.size);
  console.log('weak.size       :', weak.size);
  console.log('weak.keys       :', typeof weak.keys);
  
  user = null;
  console.log('');
  console.log('user = null にしました');
  console.log('strong.size     :', strong.size, '(まだ1件。オブジェクトは解放されない)');
  console.log('weak は数えられないので size がありません');
  
  try {
    new WeakMap().set('文字列キー', 1);
  } catch (e) {
    console.log('');
    console.log('WeakMap に文字列キー:', e.constructor.name + ':', e.message);
  }
  EOF
$ node weak.js
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つです。

  1. size が無く、中身を列挙できません。 keys も undefined です
  2. キーはオブジェクトだけ。 文字列を入れると TypeError になります
  3. キーのオブジェクトが他から参照されなくなったら、WeakMap の中の項目も消えます

なぜ「列挙できない」のか。 3番のせいです。いつ消えるかが決まっていないので、size を返したら、返した値が信用できません。 「列挙できないのは不便な仕様」ではなく、「消えるものは数えられない」という筋の通った制約でした。

そして、Map のほうを見てください。 user = null にしたのに strong.size は 1 のままです。

Map にオブジェクトをキーとして入れると、Map がそのオブジェクトを掴んで離しません。 他の変数を全部 null にしても、Map に入っている限りメモリから消えません。 これが「Map を使ったメモリリーク」の形です。 DOM要素や、リクエストごとのオブジェクトを Map に溜めると、delete を呼び忘れた分がずっと残ります。

WeakMap は、これを避けるためにあります。 「そのオブジェクトが生きている間だけ覚えておきたい」場合に使います。

自作と本物を比べる

最後に、自分で書いたものが本物とどれくらい違うのかを測ります。

bash
$ cat > bench-final.js <<'EOF'
  import { HashTable } from './table2.js';
  
  const N = 100_000;
  const keys = [];
  for (let i = 0; i < N; i++) keys.push('user-' + i);
  const TRY = 100_000;
  const targets = [];
  for (let i = 0; i < TRY; i++) targets.push('user-' + Math.floor(Math.random() * N));
  
  function bench(name, build, get) {
    const b0 = performance.now();
    const h = build();
    const bt = performance.now() - b0;
    const g0 = performance.now();
    let sum = 0;
    for (const q of targets) sum += get(h, q);
    const gt = performance.now() - g0;
    console.log([name, bt.toFixed(1) + 'ms', gt.toFixed(1) + 'ms'].join(' | '));
  }
  
  console.log('件数 ' + N + ' / 探索 ' + TRY + '回');
  console.log('実装 | 構築 | 探索');
  bench('自作HashTable', () => { const t = new HashTable(8); for (let i = 0; i < N; i++) t.set(keys[i], i); return t; }, (t, q) => t.get(q));
  bench('Map', () => { const m = new Map(); for (let i = 0; i < N; i++) m.set(keys[i], i); return m; }, (m, q) => m.get(q));
  bench('Object', () => { const o = Object.create(null); for (let i = 0; i < N; i++) o[keys[i]] = i; return o; }, (o, q) => o[q]);
  bench('配列 indexOf', () => keys.slice(), (a, q) => a.indexOf(q));
  EOF
$ node bench-final.js

最後の行で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 との比
自作 HashTable330.1 ms81.9 ms1.5倍
Map24.3 ms55.5 ms1倍
Object77.9 ms41.5 ms0.75倍
配列 indexOf0.3 ms104200.0 ms1878倍

自作の JavaScript で書いたハッシュテーブルが、C++ で書かれた Map の1.5倍で済みました。

これは私が上手いからではありません。 同じアルゴリズムだからです。 配列の indexOf との差(1878倍)は、実装の質ではなく、O(n) と O(1) の差です。

①で見た「3754倍」の正体が、ここで完全につながりました。 Set が速かったのではなく、私が O(n) の道具で O(1) の仕事をしていただけでした。

構築が自作だけ遅い(330ms)のは、⑤で見たとおりリサイズの分です。 Map はもっと賢く(そして低いレイヤで)やっています。

判断表

やりたいこと使うもの理由
「その値が入っているか」だけ知りたいSet値だけ持てばいい。includes は使わない
キーと値を対応させたい(キーは文字列)Map または Object迷ったら Map。落とし穴が少ない
キーがオブジェクトMapObject だと全部 [object Object] になる
キーが数値MapObject は文字列に変換してしまう
入れた順に処理したいMapObject は整数キーを勝手に前に並べる
外から来た文字列をキーにするMap または Object.create(null){} は toString などを最初から持っている
キーが消えたら中身も消えてほしいWeakMapMap に入れると掴んで離さない(リークの形)
JSONにしたい・そのまま送りたいObjectMap は 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つ書きました。

bash
$ cat > naive.js <<'EOF'
  const naive = (s) => {
    let h = 0;
    for (let i = 0; i < s.length; i++) h += s.charCodeAt(i);
    return h;
  };
  console.log('ab :', naive('ab'));
  console.log('ba :', naive('ba'));
  console.log('abc:', naive('abc'));
  console.log('cba:', naive('cba'));
  EOF
$ node naive.js
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 で書いたことがあります。 平文で書いたのと、まったく同じです。 「変換」と「保護」を混ぜていました。この記事の⑦を書いた理由はこれです。


後片づけ

この記事で作ったものを、全部消します。

まず、何があるか確認します。

bash
$ cd ~/cslab/hash
$ ls
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回もしていないので、消すものは自分で書いたファイルだけです。

消す前に、場所を確かめます。

bash
$ pwd
/home/user/cslab/hash

pwd で必ず確認してください。 これから rm -rf を打ちます。別の場所で打つと、消してはいけないものが消えます。 rm で消したものは戻りません(本線の基本コマンドの回で扱いました)。

bash
$ cd ~
$ rm -rf ~/cslab
$ ls ~

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にしたいから」がほとんどだった。そして「順番が意味を持ち、端しか触らない」なら、それはハッシュテーブルではなくスタックかキュー

参考リンク


次に読む

この記事は 【深掘り】コンピュータ科学 の 7 / 25 本目です。

記事
← 前の記事スタックとキュー — call stack size exceeded の正体
→ 次の記事二分探索木と3つの巡回 — 木にしたのに一直線になる

上から順に読めば積み上がるように並べています。 飛ばしても構いませんが、詰まったら前の回に戻ってください。

全体の順路は はじめに にあります。

roadmap.sh のどこをやっているか

›CS — Hash Table
  • ハッシュ関数と衝突を自分で作る
  • ハッシュ・暗号化・エンコードは別物

この記事は、上の項目を実際に手を動かして確かめる回です。

よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!

コメント

コメントする

目次