Python の set vs C++ の unordered_set（実装思想の違い）

Python の set と C++ の std::unordered_set はどちらもハッシュテーブルを基盤とするが、言語の設計思想により実装の詳細が大きく異なる。

基本的な設計思想

Python set

汎用性重視。任意のハッシュ可能オブジェクトを格納。動的型付け。GC による自動メモリ管理。

C++ unordered_set

パフォーマンス重視。テンプレートによる型特化。手動メモリ管理（または RAII）。コンパイル時最適化。

C++ はゼロコスト抽象化を追求し、Python は開発者の利便性を優先している。

衝突解決アルゴリズム

両者は衝突解決の方法が異なる。

Python set（オープンアドレス法）

衝突時にテーブル内の別スロットを探索。キャッシュ効率がよい。テーブルの使用率は約 66% に制限。

C++ unordered_set（チェイン法）

衝突時にリンクリストで要素を繋ぐ。使用率（load_factor）は 1.0 まで許容。バケット数とは別に要素を格納。

# Python のオープンアドレス法（概念）
def find_slot(table, key):
    index = hash(key) % len(table)
    perturb = hash(key)
    while table[index] is not EMPTY:
        if table[index] == key:
            return index
        index = (5 * index + perturb + 1) % len(table)
        perturb >>= 5
    return index

C++ のチェイン法では、各バケットがリンクリストを持つ。

// C++ のチェイン法（概念）
template<typename T>
struct Bucket {
    std::forward_list<T> chain;
};

template<typename T>
class SimpleUnorderedSet {
    std::vector<Bucket<T>> buckets;
    
    size_t find_bucket(const T& key) {
        return std::hash<T>{}(key) % buckets.size();
    }
};

メモリレイアウト

メモリ配置の違いはキャッシュ効率に影響する。

Python の set は要素をテーブルに直接（ポインタとして）格納する。連続したメモリ領域を走査するため、CPU キャッシュを効率的に使える。

C++ の unordered_set はバケット配列と、各バケットから伸びるリンクリストで構成される。リンクリストはメモリ上に散らばるため、キャッシュミスが発生しやすい。

# メモリアクセスパターンの違い
# Python: table[0] → table[1] → table[2] ...（連続）
# C++: bucket[0] → node_a → node_b（ポインタ追跡）

ただし、C++ の実装によっては小さなバケットをインライン化するなどの最適化が行われている。

ハッシュ関数のカスタマイズ

C++ ではテンプレート引数でハッシュ関数を指定できる。

#include <unordered_set>
#include <string>

// カスタムハッシュ
struct CaseInsensitiveHash {
    size_t operator()(const std::string& s) const {
        size_t h = 0;
        for (char c : s) {
            h ^= std::tolower(c) + 0x9e3779b9 + (h << 6) + (h >> 2);
        }
        return h;
    }
};

struct CaseInsensitiveEqual {
    bool operator()(const std::string& a, const std::string& b) const {
        return std::equal(a.begin(), a.end(), b.begin(), b.end(),
            [](char c1, char c2) { return std::tolower(c1) == std::tolower(c2); });
    }
};

std::unordered_set<std::string, CaseInsensitiveHash, CaseInsensitiveEqual> ci_set;

Python では __hash__ と __eq__ をクラスに定義する。

class CaseInsensitiveString:
    def __init__(self, s):
        self.s = s
        self._lower = s.lower()
    
    def __hash__(self):
        return hash(self._lower)
    
    def __eq__(self, other):
        return self._lower == other._lower

s = {CaseInsensitiveString("Hello"), CaseInsensitiveString("HELLO")}
print(len(s))  # 1

C++ はコンパイル時に型が確定するため、ハッシュ関数がインライン展開される。Python は動的ディスパッチになる。

パフォーマンス比較

同じ操作でも、C++ は Python より数倍〜数十倍高速だ。

// C++ のベンチマーク例
#include <unordered_set>
#include <chrono>

int main() {
    std::unordered_set<int> s;
    auto start = std::chrono::high_resolution_clock::now();
    
    for (int i = 0; i < 1000000; ++i) {
        s.insert(i);
    }
    
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    // 通常 20-50ms 程度
}

import time

s = set()
start = time.perf_counter()

for i in range(1000000):
    s.add(i)

print(f"{time.perf_counter() - start:.4f}s")
# 通常 0.1-0.2秒程度

この差は、Python のオブジェクトオーバーヘッド、インタプリタのディスパッチ、GC の影響による。

リサイズ戦略

両者ともテーブルが一定の使用率を超えるとリサイズする。

項目	Python set	C++ unordered_set
リサイズ閾値	約 66%	load_factor（デフォルト 1.0）
成長率	約 4 倍	約 2 倍
縮小	自動では行わない	rehash() で手動

C++ では max_load_factor() や reserve() で制御できる。

std::unordered_set<int> s;
s.max_load_factor(0.5);  // 使用率 50% でリサイズ
s.reserve(1000);          // 1000 要素分を事前確保

Python では明示的な制御はできない。

イテレータの安定性

C++ の unordered_set では、挿入・削除によってイテレータが無効化される場合がある。

std::unordered_set<int> s = {1, 2, 3};
auto it = s.begin();

s.insert(4);  // リサイズが発生すると it は無効化される可能性

// 安全でない
// std::cout << *it;  // 未定義動作の可能性

Python の set でも、イテレーション中の変更は禁止されている。

s = {1, 2, 3}
for x in s:
    s.add(x * 10)  # RuntimeError: Set changed size during iteration

型安全性

C++ は静的型付けにより、コンパイル時に型エラーを検出する。

std::unordered_set<int> s;
s.insert(42);
s.insert("hello");  // コンパイルエラー

Python は動的型付けなので、実行時まで問題が発覚しない。

s = set()
s.add(42)
s.add("hello")  # 動作する（混在可能）

型安全性を求めるなら、Python では型ヒントと静的解析ツールを使う。

from typing import Set

def process(items: Set[int]) -> None:
    for item in items:
        print(item * 2)

使い分けの観点

Python set が適切な場面

開発速度を優先。プロトタイピング。スクリプト的な用途。異なる型の混在が必要。

C++ unordered_set が適切な場面

ミリ秒単位の性能が必要。組み込みシステム。ゲームエンジン。大規模データ処理。

Python から C++ の性能が必要な場合、Cython や pybind11 で拡張モジュールを書くアプローチもある。

# Cython での高速 set（概念）
# cdef unordered_set[int] cpp_set
# for i in range(1000000):
#     cpp_set.insert(i)

両言語の強みを理解し、適材適所で使い分けることが重要だ。