ハッシュテーブルとは？仕組み・コード・計算量を解説

ハッシュテーブルが解決する問題

100万件のユーザーレコードを保存していて、メールアドレスで1件探したいとします。リストを走査するとO(n)です。リストをソートしておけば二分探索でO(log n)ですが、挿入が遅くなります。ハッシュテーブルなら、レコード数にかかわらず平均O(1)で見つかり、挿入や削除も同じくらい高速です。

このため、ハッシュテーブルは至るところで使われています。プログラミング言語の辞書やセット、データベースのハッシュインデックス、キャッシュ、コンパイラのシンボルテーブル、重複排除などです。

イメージで理解する

100個の番号付きフックがあるクロークを想像してください。係員は、すべてのフックを探して回る代わりに、あなたの名前からフック番号を計算し、まっすぐそこへ向かいます。この番号を計算する関数がハッシュ関数です。良いハッシュ関数は高速で、同じキーなら常に同じ数値を返し、異なるキーをフックに均等にばらけさせます。

1. h = hash(key)を計算します。
2. バケットを選びます：index = h % capacity。
3. そのバケットの中だけでキーを探します。

具体例：チェイン法での衝突

4個のバケットと、簡易的なハッシュ関数（文字の位置の合計。a = 1、b = 2、…）を持つテーブルを考えます。

actとbeeはcatと衝突します。この状態でbeeを検索するには、bucket 0の3つのエントリを調べることになります。ハッシュ関数が貧弱（文字の合計では順序が無視される）だったり、バケットが少なすぎたりすると、チェーンが長くなってテーブルが遅くなります。実際のハッシュ関数はキーのすべてのビットを混ぜ合わせ、実際のテーブルは満杯に近づくと拡張されます。

チェイン法によるPython実装

各バケットは[key, value]ペアのリストです。要素数がバケット数の0.75倍（負荷率）を超えると、テーブルは容量を2倍にして、すべての要素を再挿入します。

class HashTable:
    def __init__(self, capacity=8):
        self.buckets = [[] for _ in range(capacity)]
        self.size = 0
    def _bucket(self, key):
        return self.buckets[hash(key) % len(self.buckets)]
    def put(self, key, value):
        bucket = self._bucket(key)
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value        # update existing key
                return
        bucket.append([key, value])
        self.size += 1
        if self.size > 0.75 * len(self.buckets):
            self._resize()
    def get(self, key, default=None):
        for k, v in self._bucket(key):
            if k == key:
                return v
        return default
    def delete(self, key):
        bucket = self._bucket(key)
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.size -= 1
                return True
        return False
    def _resize(self):
        old = [pair for bucket in self.buckets for pair in bucket]
        self.buckets = [[] for _ in range(2 * len(self.buckets))]
        self.size = 0
        for k, v in old:
            self.put(k, v)

t = HashTable()
for i, word in enumerate(["red", "green", "blue", "cyan", "pink", "gold", "gray"]):
    t.put(word, i)
t.put("red", 100)
t.delete("blue")
print(t.get("red"), t.get("blue"), t.size, len(t.buckets))  # 100 None 6 16

衝突解決方式の比較

CPythonのdictは、摂動（perturbation）を加えた探査列を使うオープンアドレス法を採用しており、Python 3.7以降は、反復が挿入順に従うことが保証されています。JavaのHashMapはチェイン法を使い、長いチェーンを平衡木に変換します。

時間計算量と空間計算量

平均O(1)は、良いハッシュ関数と、上限のある負荷率を前提としています。Pythonは文字列のハッシュをプロセスごとにランダム化（ハッシュシード）しています。これは、攻撃者が大量に衝突するキーを送り込み、サーバーをリクエストあたりO(n)に遅くするのを防ぐためです。

よくある間違い

• ミュータブルなオブジェクトをキーにする、または__eq__を定義したのに対応する__hash__を定義しない。等しいオブジェクトは、等しいハッシュ値を持たなければなりません。
• ソート順を期待する。ハッシュテーブルが提供するのは高速な検索で、順序ではありません。範囲クエリや最小キーが必要なときは、ソート済みリストや平衡木（二分探索木）を使いましょう。
• 実行をまたいでhash()の値を当てにする。PYTHONHASHSEEDを固定しない限り、文字列のハッシュはPythonプロセスごとに変わります。安定したハッシュにはhashlibを使います。
• ハッシュテーブルをセキュリティ用の部品として扱う。ハッシュテーブルが使うのは高速な非暗号学的ハッシュです。パスワードには専用のパスワードハッシュ関数が必要です。

使いどころと、面接での典型的な使い方

「これは前に見たか？」「このキーに対応する値は何か？」にすばやく答えたいときは、ハッシュテーブルを使います。順序、範囲、最も近いキーも必要なときは、二分探索木かソート済み配列を使います。

定番の問題：two sum（各数値のインデックスを保存し、target - xを検索する）、出現頻度のカウント（collections.Counter）、ソートした文字によるアナグラムのグループ化、重複の検出、動的計画法での結果のメモ化などです。

def two_sum(nums, target):
    seen = {}                      # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:
            return seen[target - x], i
        seen[x] = i
    return None
print(two_sum([2, 7, 11, 15], 9))  # (0, 1)