Python 辞書のハッシュテーブル実装：オープンアドレス法と hashable の意味

Python の辞書がなぜ高速なのか、その秘密はハッシュテーブルという仕組みにあります。キーを指定して値を取り出す操作は、要素数がいくら増えても平均 O(1) の計算量で完了します。この記事では、CPython がどのようにハッシュテーブルを実装しているのか、衝突をどう解決しているのか、そしてなぜキーには「hashable」な値しか使えないのかを解説します。

ハッシュテーブルの基本的な考え方

ハッシュテーブルは、キーから「ハッシュ値」と呼ばれる整数を計算し、その値を使って配列のどの位置にデータを格納するかを決める仕組みです。

# Python でハッシュ値を確認する
print(hash("apple"))   # 例: 2324522789372603423
print(hash("banana"))  # 例: -8872142557351543024
print(hash(42))        # 42（小さい整数は自身がハッシュ値）

ハッシュ値がわかれば、配列のインデックスは hash(key) % table_size のような計算で求められます。リストのように先頭から順に探す必要がないため、要素数に関係なく一定時間でアクセスできるわけです。

オープンアドレス法による衝突解決

異なるキーが同じインデックスを指すことを「衝突」と呼びます。たとえば、テーブルサイズが 8 のとき、hash(key) % 8 が同じ値になるキーが複数存在する可能性があります。

衝突を解決する方法は大きく分けて 2 つあります。

CPython が採用しているオープンアドレス法では、最初に計算したインデックスが埋まっていたら、一定の規則に従って次の候補スロットを探します。この「次を探す」処理をプロービング（probing）と呼びます。

CPython のプロービング手法

単純に「次のスロット」を見ていく線形プロービングでは、連続した領域が埋まりやすく、性能が劣化します。CPython は擬似ランダムプロービングを採用しており、ハッシュ値の全ビットを活用して次の候補位置を決定します。

# CPython の probing 計算（概念的な疑似コード）
perturb = hash_value
index = perturb % table_size

while slot_is_occupied(index):
    perturb >>= 5
    index = (index * 5 + perturb + 1) % table_size

perturb 変数がハッシュ値の上位ビットを順次取り込むことで、同じ初期インデックスを持つキーでも異なる経路でスロットを探索します。これにより、クラスタリング（連続した領域が埋まる現象）を防ぎ、検索効率を維持しています。

負荷率とリサイズ

ハッシュテーブルが埋まりすぎると、空きスロットを見つけるまでのプロービング回数が増え、性能が悪化します。CPython は負荷率（使用中スロット数 ÷ テーブルサイズ）が約 2/3 を超えると、テーブルサイズを拡張してすべてのエントリを再配置します。

import sys

d = {}
print(sys.getsizeof(d))  # 64（空の辞書）

for i in range(10):
    d[i] = i
print(sys.getsizeof(d))  # 352（リサイズ後）

リサイズは O(n) のコストがかかりますが、頻繁には発生しないため、償却計算量としては O(1) が維持されます。

なぜキーは hashable でなければならないのか

ハッシュテーブルが正しく機能するには、同じキーは常に同じハッシュ値を返す必要があります。もしキーの中身が変わってハッシュ値が変わると、以前格納した場所を見つけられなくなってしまいます。

# リストはハッシュ化できない
try:
    hash([1, 2, 3])
except TypeError as e:
    print(e)  # unhashable type: 'list'

# タプルはハッシュ化できる（中身がすべて hashable なら）
print(hash((1, 2, 3)))  # 529344067295497451

Python では、オブジェクトが hashable であるための条件は次のとおりです。

リストや辞書、集合といった可変オブジェクトは、中身が変わるとハッシュ値も変わってしまうため、意図的に __hash__ が定義されていません。

カスタムクラスを辞書のキーにする

自作クラスのインスタンスをキーにしたい場合、__hash__ と __eq__ を適切に実装する必要があります。

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    
    def __hash__(self):
        return hash((self.x, self.y))
    
    def __eq__(self, other):
        return isinstance(other, Point) and self.x == other.x and self.y == other.y

p1 = Point(1, 2)
p2 = Point(1, 2)

d = {p1: "first"}
print(d[p2])  # "first"（p1 == p2 かつ hash(p1) == hash(p2) なので同じキー扱い）

注意点として、__eq__ をオーバーライドすると、デフォルトの __hash__（id() ベース）は無効化されます。__hash__ を明示的に定義しないと TypeError が発生するため、両方をセットで実装するのが基本です。

ハッシュ値の衝突と等価比較

ハッシュ値が同じでも、キーが等しいとは限りません。この状況を処理するため、CPython は以下の手順でキーを照合します。

ハッシュ値の比較は整数同士の比較なので非常に高速です。等価比較は重い処理になりうるため、ハッシュ値が異なれば即座に「別のキー」と判断できる仕組みになっています。

# ハッシュ値が同じでも等しくない例
class AlwaysSameHash:
    def __init__(self, value):
        self.value = value
    def __hash__(self):
        return 1  # 常に同じハッシュ値
    def __eq__(self, other):
        return isinstance(other, AlwaysSameHash) and self.value == other.value

a = AlwaysSameHash("A")
b = AlwaysSameHash("B")

print(hash(a) == hash(b))  # True
print(a == b)              # False

d = {a: 1, b: 2}
print(len(d))  # 2（別々のキーとして格納される）

この例では全キーが同じインデックスに衝突しますが、等価比較で区別されるため正しく動作します。ただし、プロービングが頻発するため性能は大幅に悪化します。

まとめ

Python の辞書は、ハッシュテーブルとオープンアドレス法を組み合わせることで、高速なキー検索を実現しています。キーが hashable でなければならない理由は、ハッシュ値が変わると格納場所を見失ってしまうからです。カスタムクラスをキーにする際は、__hash__ と __eq__ を正しく実装し、「等しいオブジェクトは同じハッシュ値を持つ」という原則を守ることが重要です。