Day 4: ハッシュテーブル

今日学ぶこと

• ハッシュテーブルの仕組み
• ハッシュ関数の役割
• 衝突（コリジョン）の解決方法
• JavaScriptの Map と Set

---

ハッシュテーブルとは

ハッシュテーブルは、キーと値のペアを格納し、キーから値を O(1) で検索できるデータ構造です。

flowchart LR
    K1["key: 'name'"] --> HF["ハッシュ関数"]
    HF --> I["index: 3"]
    I --> B["バケット[3]"]
    B --> V["value: 'Alice'"]
    style HF fill:#3b82f6,color:#fff
    style B fill:#22c55e,color:#fff

仕組み

1. キー をハッシュ関数に渡す
2. ハッシュ関数が インデックス（数値） を生成
3. そのインデックスの位置にデータを格納

---

ハッシュ関数

ハッシュ関数は、任意のデータを固定長の数値に変換します。良いハッシュ関数の条件：

• 決定的: 同じ入力には常に同じ出力
• 均一分布: 出力がバケット全体に均等に分散
• 高速: 計算が速い

// Simple hash function for strings
function hash(key, tableSize) {
  let total = 0;
  for (let i = 0; i < key.length; i++) {
    total += key.charCodeAt(i);
  }
  return total % tableSize;
}

console.log(hash("name", 10));  // Deterministic index
console.log(hash("age", 10));   // Different index

より良いハッシュ関数

// Better hash function using prime number multiplication
function betterHash(key, tableSize) {
  const PRIME = 31;
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash = (hash * PRIME + key.charCodeAt(i)) % tableSize;
  }
  return hash;
}

---

ハッシュテーブルの実装

class HashTable {
  constructor(size = 53) {
    this.table = new Array(size);
    this.size = size;
    this.count = 0;
  }

  _hash(key) {
    const PRIME = 31;
    let hash = 0;
    for (let i = 0; i < Math.min(key.length, 100); i++) {
      hash = (hash * PRIME + key.charCodeAt(i)) % this.size;
    }
    return hash;
  }

  // Set a key-value pair: O(1) average
  set(key, value) {
    const index = this._hash(key);
    if (!this.table[index]) {
      this.table[index] = [];
    }
    // Update existing key
    const existing = this.table[index].find(pair => pair[0] === key);
    if (existing) {
      existing[1] = value;
    } else {
      this.table[index].push([key, value]);
      this.count++;
    }
  }

  // Get value by key: O(1) average
  get(key) {
    const index = this._hash(key);
    if (!this.table[index]) return undefined;
    const pair = this.table[index].find(pair => pair[0] === key);
    return pair ? pair[1] : undefined;
  }

  // Delete a key: O(1) average
  delete(key) {
    const index = this._hash(key);
    if (!this.table[index]) return false;
    const pairIndex = this.table[index].findIndex(pair => pair[0] === key);
    if (pairIndex === -1) return false;
    this.table[index].splice(pairIndex, 1);
    this.count--;
    return true;
  }

  has(key) {
    return this.get(key) !== undefined;
  }

  keys() {
    const result = [];
    for (const bucket of this.table) {
      if (bucket) {
        for (const [key] of bucket) {
          result.push(key);
        }
      }
    }
    return result;
  }
}

const ht = new HashTable();
ht.set("name", "Alice");
ht.set("age", 30);
console.log(ht.get("name")); // "Alice"
console.log(ht.has("age"));  // true

---

衝突（コリジョン）

異なるキーが同じインデックスに割り当てられることを衝突といいます。

flowchart TB
    subgraph Collision["衝突の例"]
        K1["'abc'"] --> H["hash()"] --> I3["index: 3"]
        K2["'cab'"] --> H2["hash()"] --> I3
    end
    style Collision fill:#ef4444,color:#fff

解決方法1: チェイニング（Separate Chaining）

同じインデックスに複数の要素をリストで格納します（上の実装で使用）。

flowchart TB
    subgraph Table["ハッシュテーブル"]
        B0["[0]"] --> L0["null"]
        B1["[1]"] --> P1["('name','Alice')"] --> P2["('email','alice@example.com')"]
        B2["[2]"] --> L2["null"]
        B3["[3]"] --> P3["('age', 30)"]
    end
    style Table fill:#3b82f6,color:#fff

解決方法2: オープンアドレス法（Open Addressing）

衝突時に別の空きスロットを探します。

class OpenAddressingHashTable {
  constructor(size = 53) {
    this.table = new Array(size);
    this.size = size;
  }

  _hash(key) {
    const PRIME = 31;
    let hash = 0;
    for (let i = 0; i < Math.min(key.length, 100); i++) {
      hash = (hash * PRIME + key.charCodeAt(i)) % this.size;
    }
    return hash;
  }

  // Linear probing
  set(key, value) {
    let index = this._hash(key);
    while (this.table[index] !== undefined && this.table[index][0] !== key) {
      index = (index + 1) % this.size;
    }
    this.table[index] = [key, value];
  }

  get(key) {
    let index = this._hash(key);
    while (this.table[index] !== undefined) {
      if (this.table[index][0] === key) {
        return this.table[index][1];
      }
      index = (index + 1) % this.size;
    }
    return undefined;
  }
}

---

負荷率とリサイズ

負荷率（Load Factor） = 要素数 / テーブルサイズ

負荷率が高くなると衝突が増え、性能が低下します。一般的に、負荷率が 0.7〜0.75 を超えたらリサイズします。

負荷率	性能
< 0.5	高速
0.5 - 0.75	良好
> 0.75	衝突が増加、リサイズ推奨

---

JavaScriptの Map と Set

Map

const map = new Map();

// Set
map.set("name", "Alice");
map.set(42, "answer");
map.set(true, "boolean key");

// Get
console.log(map.get("name")); // "Alice"

// Has
console.log(map.has(42)); // true

// Delete
map.delete(true);

// Size
console.log(map.size); // 2

// Iterate
for (const [key, value] of map) {
  console.log(`${key}: ${value}`);
}

Set

const set = new Set();

set.add(1);
set.add(2);
set.add(2); // Duplicate ignored
set.add(3);

console.log(set.has(2)); // true
console.log(set.size);   // 3

set.delete(2);

// Convert array to unique values
const unique = [...new Set([1, 2, 2, 3, 3, 4])];
console.log(unique); // [1, 2, 3, 4]

Object vs Map

特徴	Object	Map
キーの型	文字列/Symbol	任意の型
順序保証	挿入順（制限あり）	挿入順
サイズ取得	Object.keys(o).length	map.size
イテレーション	間接的	直接（for...of）
性能（頻繁な追加/削除）	低い	高い

---

実践例

1. 出現回数のカウント

function countFrequency(arr) {
  const freq = new Map();
  for (const item of arr) {
    freq.set(item, (freq.get(item) || 0) + 1);
  }
  return freq;
}

const fruits = ["apple", "banana", "apple", "cherry", "banana", "apple"];
console.log(countFrequency(fruits));
// Map { 'apple' => 3, 'banana' => 2, 'cherry' => 1 }

2. 二数の和（Two Sum）

function twoSum(nums, target) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map.has(complement)) {
      return [map.get(complement), i];
    }
    map.set(nums[i], i);
  }
  return [];
}

console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]

3. アナグラム判定

function isAnagram(s, t) {
  if (s.length !== t.length) return false;
  const count = new Map();
  for (const char of s) {
    count.set(char, (count.get(char) || 0) + 1);
  }
  for (const char of t) {
    const c = count.get(char);
    if (!c) return false;
    count.set(char, c - 1);
  }
  return true;
}

console.log(isAnagram("listen", "silent")); // true
console.log(isAnagram("hello", "world"));   // false

---

ハッシュテーブルの計算量

操作	平均	最悪
検索	O(1)	O(n)
挿入	O(1)	O(n)
削除	O(1)	O(n)

最悪ケースは全ての要素が同じバケットに入った場合です。良いハッシュ関数と適切なリサイズにより、実質的に O(1) を維持できます。

---

まとめ

概念	説明
ハッシュテーブル	キーから値をO(1)で取得するデータ構造
ハッシュ関数	キーを数値インデックスに変換する関数
衝突	異なるキーが同じインデックスに割り当てられること
チェイニング	衝突をリストで解決する方法
負荷率	性能の指標、0.75超でリサイズ推奨

重要ポイント

1. ハッシュテーブルは平均 O(1) で検索・挿入・削除ができる
2. 良いハッシュ関数は衝突を最小化する
3. JavaScriptでは Map と Set が組み込みで利用可能
4. 頻繁な追加・削除には Object より Map が適している

---

練習問題

問題1: 基本

文字列内で最初に重複しない文字を見つける関数を実装してください。

問題2: 応用

2つの配列の共通要素を返す関数を、Set を使って実装してください。

チャレンジ問題

文字列の中で、重複なしの最長部分文字列の長さを求める関数を実装してください（ヒント：スライディングウィンドウ + ハッシュマップ）。

---

参考リンク

• MDN - Map
• MDN - Set
• Wikipedia - Hash table

---

次回予告: Day 5では「再帰と分割統治法」について学びます。問題を分割して解く強力な手法を理解しましょう。