Terms Privacy

© Rollpie

MathPython
24 Dec 2025

Python の集合とハッシュテーブル（なぜ検索が O(1) なのか）

Python の set は内部でハッシュテーブルを使っている。これにより、要素の検索・追加・削除が平均 O(1) の計算量で実行できる。

ハッシュテーブルの基本原理

ハッシュテーブルは配列とハッシュ関数を組み合わせたデータ構造だ。要素を格納する際、ハッシュ関数で計算した値を配列のインデックスとして使う。

# 概念的なイメージ
value = "apple"
hash_value = hash(value)  # ハッシュ値を計算
index = hash_value % table_size  # テーブルサイズで割った余りがインデックス

ハッシュ値からインデックスを直接計算できるため、配列の該当位置にアクセスするだけで要素を見つけられる。これが O(1) の理由だ。

Python のハッシュ関数

Python の組み込み hash() 関数は、オブジェクトのハッシュ値を返す。

print(hash(42))         # 42
print(hash("hello"))    # -5217281280629498012（実行ごとに変わる）
print(hash((1, 2, 3)))  # 529344067295497451

文字列やタプルのハッシュ値は Python の起動ごとにランダム化される。これはセキュリティ対策（ハッシュ衝突攻撃の防止）のためだ。

# 環境変数 PYTHONHASHSEED で固定可能
# PYTHONHASHSEED=0 python script.py

set の内部構造

CPython の set は、要素のハッシュ値と要素自体を格納するテーブルを持つ。概念的には以下のような構造だ。

# 概念的な内部構造（実際の実装とは異なる）
class SimpleSet:
    def __init__(self, size=8):
        self.table = [None] * size
        self.size = size
    
    def _find_slot(self, item):
        index = hash(item) % self.size
        return index
    
    def add(self, item):
        index = self._find_slot(item)
        self.table[index] = item
    
    def __contains__(self, item):
        index = self._find_slot(item)
        return self.table[index] == item

実際の CPython 実装では、初期サイズは 8 で、使用率が約 2/3 を超えるとテーブルサイズが拡張される。

衝突の解決

異なる要素が同じインデックスに割り当てられることを衝突（collision）という。Python はオープンアドレス法で衝突を解決する。

# 衝突時の探索（概念）
def find_slot_with_probing(table, item):
    size = len(table)
    index = hash(item) % size
    perturb = hash(item)
    
    while table[index] is not None and table[index] != item:
        # 次の候補位置を探す
        index = (index * 5 + perturb + 1) % size
        perturb >>= 5
    
    return index

CPython は線形探索ではなく、擬似乱数的なプロービングを使う。これにより、特定のパターンでの衝突連鎖を避けられる。

チェイン法

衝突時にリンクリストで要素を繋ぐ。メモリ効率が悪い。

オープンアドレス法

衝突時に別のスロットを探す。Python はこちらを採用。

リストとの比較

リストで要素を検索する場合、先頭から順番に調べる必要がある。

# リストの in 演算：O(n)
items = [1, 2, 3, 4, 5]
if 3 in items:  # 最悪で全要素を調べる
    pass

# set の in 演算：O(1)
items_set = {1, 2, 3, 4, 5}
if 3 in items_set:  # ハッシュ計算と配列アクセスのみ
    pass

要素数が増えるほど差は顕著になる。

import time

n = 1000000
items_list = list(range(n))
items_set = set(range(n))

# リストで検索
start = time.time()
for i in range(1000):
    999999 in items_list
print(f"list: {time.time() - start:.4f}s")

# set で検索
start = time.time()
for i in range(1000):
    999999 in items_set
print(f"set: {time.time() - start:.4f}s")

100 万要素で検索すると、リストは数秒かかるが set は一瞬で終わる。

最悪計算量

ハッシュテーブルの最悪計算量は O(n) だ。すべての要素が同じインデックスに衝突すると、線形探索と同じになる。

# 意図的に衝突させる例（教育目的）
class BadHash:
    def __init__(self, value):
        self.value = value
    
    def __hash__(self):
        return 1  # 常に同じハッシュ値
    
    def __eq__(self, other):
        return self.value == other.value

ただし通常の使用では、ハッシュ関数が適切に分散するため、平均 O(1) が保証される。

ハッシュ可能の条件

set に格納できるのはハッシュ可能なオブジェクトだけだ。オブジェクトがハッシュ可能であるには以下の条件を満たす必要がある。

不変であること

オブジェクトの生存期間中、ハッシュ値が変わらないこと。リストは変更可能なためハッシュ不可。

__hash__ が定義されていること

hash() で呼び出されるメソッド。None でないこと。

カスタムクラスはデフォルトでハッシュ可能だが、__eq__ を定義すると __hash__ が None になる。

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

p = Point(1, 2)
# hash(p)  # TypeError: unhashable type: 'Point'

テーブルの拡張

set の要素数が増えると、テーブルサイズが自動的に拡張される。

import sys

s = set()
prev_size = sys.getsizeof(s)
print(f"0 elements: {prev_size} bytes")

for i in range(100):
    s.add(i)
    size = sys.getsizeof(s)
    if size != prev_size:
        print(f"{len(s)} elements: {size} bytes")
        prev_size = size

拡張時にはすべての要素を新しいテーブルに再配置（rehash）する必要がある。この操作は O(n) だが、償却計算量では O(1) に収まる。頻繁には発生しないためだ。

22 views