ハッシュテーブル - データサイエンス関連+αのメモ

ハッシュテーブル（Hash Table） は、キーと値のペアを格納するデータ構造（例：Pythonのdict）

ハッシュ関数でキーをインデックスに変換し、配列に値を格納することで高速なアクセスを実現する

特徴：

検索・挿入・削除の平均計算量は $O(1)$
ハッシュ衝突が発生すると最悪 $O(n)$ になる
キーの順序は保持されない

操作：

insert(key, value): キーと値のペアを挿入する
search(key): キーに対応する値を返す
delete(key): キーに対応するエントリを削除する

ハッシュ関数¶

ハッシュ関数はキーを受け取り、配列のインデックスを返す関数

良いハッシュ関数の条件：

決定性: 同じキーには常に同じハッシュ値を返す
一様分布: ハッシュ値が均一に分散される
高速計算: 計算コストが低い

最もシンプルな例として、整数キーに対する除算法（Division Method）がある：

h(k) = k \mod m

(1)

$m$ はハッシュテーブルのサイズ（素数が望ましい）

衝突（コリジョン）¶

異なるキーが同じハッシュ値を持つことを 衝突（collision） という

衝突の解決策：

方法	概要	長所	短所
チェイン法	同じインデックスの要素をリストで管理	実装が簡単、負荷率に柔軟	キャッシュ効率が低い
オープンアドレス法	空きスロットを探して格納	キャッシュ効率が良い	負荷率が高いと性能劣化

チェイン法による実装¶

class HashTableChaining:
    def __init__(self, size=11):
        self.size = size
        self.table = [[] for _ in range(size)]

    def _hash(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        idx = self._hash(key)
        for i, (k, _) in enumerate(self.table[idx]):
            if k == key:
                self.table[idx][i] = (key, value)  # 上書き
                return
        self.table[idx].append((key, value))

    def search(self, key):
        idx = self._hash(key)
        for k, v in self.table[idx]:
            if k == key:
                return v
        raise KeyError(key)

    def delete(self, key):
        idx = self._hash(key)
        self.table[idx] = [(k, v) for k, v in self.table[idx] if k != key]

    def __repr__(self):
        return "\n".join(f"[{i}]: {chain}" for i, chain in enumerate(self.table) if chain)

ht = HashTableChaining()
ht.insert("apple", 100)
ht.insert("banana", 200)
ht.insert("cherry", 300)
ht.insert("apple", 150)  # 上書き

print("apple  ->", ht.search("apple"))
print("banana ->", ht.search("banana"))

ht.delete("banana")
print("\nbanana削除後のテーブル:")
print(ht)

オープンアドレス法（線形探索）による実装¶

衝突時に次の空きスロットを線形にたどる方法（Linear Probing）

h(k, i) = (h'(k) + i) \mod m

(2)

$i$ は探索回数、 $h'$ は補助ハッシュ関数

クラスタリング（連続した埋まりスロット）が発生しやすいため、二次探索（Quadratic Probing）やダブルハッシングが代替として使われる

_DELETED = object()  # 削除済みスロットのセンチネル


class HashTableOpenAddressing:
    def __init__(self, size=11):
        self.size = size
        self.table = [None] * size
        self.count = 0

    def _hash(self, key):
        return hash(key) % self.size

    def _probe(self, key):
        idx = self._hash(key)
        for i in range(self.size):
            yield (idx + i) % self.size

    def insert(self, key, value):
        if self.count / self.size > 0.7:
            raise RuntimeError("負荷率が高すぎます。リサイズが必要です。")
        for idx in self._probe(key):
            slot = self.table[idx]
            if slot is None or slot is _DELETED:
                self.table[idx] = (key, value)
                self.count += 1
                return
            if slot[0] == key:
                self.table[idx] = (key, value)  # 上書き
                return
        raise RuntimeError("テーブルが満杯です")

    def search(self, key):
        for idx in self._probe(key):
            slot = self.table[idx]
            if slot is None:
                raise KeyError(key)
            if slot is not _DELETED and slot[0] == key:
                return slot[1]
        raise KeyError(key)

    def delete(self, key):
        for idx in self._probe(key):
            slot = self.table[idx]
            if slot is None:
                raise KeyError(key)
            if slot is not _DELETED and slot[0] == key:
                self.table[idx] = _DELETED
                self.count -= 1
                return
        raise KeyError(key)

    def __repr__(self):
        rows = []
        for i, slot in enumerate(self.table):
            if slot is None:
                label = "None"
            elif slot is _DELETED:
                label = "<deleted>"
            else:
                label = str(slot)
            rows.append(f"[{i:2d}]: {label}")
        return "\n".join(rows)

ht2 = HashTableOpenAddressing()
ht2.insert("apple", 100)
ht2.insert("banana", 200)
ht2.insert("cherry", 300)

print("apple  ->", ht2.search("apple"))

ht2.delete("banana")
print("\nbanana削除後:")
print(ht2)

計算量まとめ¶

負荷率 $\alpha = n / m$ （ $n$ : 要素数, $m$ : テーブルサイズ）

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

負荷率を一定以下（例: $\alpha \le 0.7$ ）に保つことで平均 $O(1)$ を維持できる

NOTE: Pythonのdictはハッシュテーブル

CPythonのdictはオープンアドレス法（ランダム探索）で実装されており、Python 3.7以降は挿入順序を保持する

特性	Python `dict`
検索・挿入・削除（平均）	$O(1)$
順序の保持	挿入順（3.7以降）
キーの制約	ハッシュ可能（immutable）なオブジェクト