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 はこちらを採用している。メモリ局所性が良く、キャッシュ効率が高い。
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__() メソッドが常に同じ値を返す必要があります。可変オブジェクトはこの条件を満たせません。
__eq__() メソッドが定義されている必要があります。ハッシュ値が同じでも実際のキーが異なる場合があるため、等価比較で最終確認を行います。
a == b なら hash(a) == hash(b) でなければなりません。逆は成り立たなくても構いません（衝突は許容される）。
リストや辞書、集合といった可変オブジェクトは、中身が変わるとハッシュ値も変わってしまうため、意図的に __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__ を正しく実装し、「等しいオブジェクトは同じハッシュ値を持つ」という原則を守ることが重要です。
