Python の set のメモリレイアウトとオブジェクト構造（PySetObject の解剖）
CPython の set は Objects/setobject.c で実装されている。内部構造を理解することで、パフォーマンス特性や制約の理由が明確になる。
PySetObject の構造
CPython 3.x における set オブジェクトは以下の構造体で定義されている。
typedef struct {
PyObject_HEAD
Py_ssize_t fill; /* アクティブ + ダミーエントリ数 */
Py_ssize_t used; /* アクティブエントリ数 */
Py_ssize_t mask; /* テーブルサイズ - 1（2^n - 1）*/
setentry *table; /* ハッシュテーブル */
Py_hash_t hash; /* frozenset のみ使用 */
Py_ssize_t finger; /* pop() 用のインデックス */
setentry smalltable[PySet_MINSIZE]; /* 小さいセット用の埋め込みテーブル */
PyObject *weakreflist; /* 弱参照リスト */
} PySetObject;重要なフィールドを順に見ていく。
fill と used の違い
fill と used の区別は、削除されたエントリの扱いに関係する。
実際に格納されている要素数。len(s) で返る値。
アクティブなエントリ + ダミーエントリ（削除済みマーカー）の合計。
要素を削除しても fill は減らない。これはオープンアドレス法の探索を正しく動作させるためだ。
s = {1, 2, 3, 4, 5}
# used=5, fill=5
s.remove(3)
# used=4, fill=5（3 の位置にダミーマーカー）fill が閾値を超えるとリサイズが発生し、ダミーエントリも整理される。
setentry の構造
各エントリは以下の構造を持つ。
typedef struct {
PyObject *key; /* 格納されている要素（またはNULL/ダミー）*/
Py_hash_t hash; /* 要素のハッシュ値（キャッシュ）*/
} setentry;ハッシュ値をキャッシュしているのは、探索時に毎回 __hash__ を呼ばないためだ。リサイズ時にも再計算せずに済む。
smalltable の最適化
小さい set のために、オブジェクト内に固定サイズのテーブルを持っている。
#define PySet_MINSIZE 8
setentry smalltable[PySet_MINSIZE];8 要素以下の set は、追加のメモリ確保なしで動作する。これにより、小さい set の作成が高速になる。
import sys
# 空の set でもメモリは確保済み
s = set()
print(sys.getsizeof(s)) # 216 bytes（smalltable を含む）要素数が 8 を超えると、table ポインタが別のメモリ領域を指すようになる。
mask とインデックス計算
mask はテーブルサイズから 1 を引いた値で、常に 2^n - 1 の形になる。
# インデックス計算
index = hash_value & mask
# これは以下と同等だが高速
# index = hash_value % (mask + 1)ビット AND 演算は除算より高速なため、この最適化は重要だ。テーブルサイズが 2 の累乗でなければならない理由がここにある。
テーブルサイズの進行
テーブルは 2 の累乗サイズで拡張される。
# 実際のサイズ変化を観察
import sys
s = set()
prev_size = sys.getsizeof(s)
sizes = [(0, prev_size)]
for i in range(100):
s.add(i)
size = sys.getsizeof(s)
if size != prev_size:
sizes.append((len(s), size))
prev_size = size
for count, size in sizes:
print(f"{count} elements: {size} bytes")出力例として、要素数 0→5→21→85 あたりでサイズが増加する。これはテーブルサイズが 8→32→128→512 と 4 倍ずつ成長していることを示す。
finger フィールド
finger は pop() の最適化に使われる。
Py_ssize_t finger; /* pop() 用のインデックス */pop() はランダムな要素を返すが、毎回テーブルの先頭から探索すると効率が悪い。finger は前回の位置を記憶し、そこから探索を再開する。
s = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
while s:
print(s.pop(), end=' ')
# 出力順序はハッシュテーブルの配置に依存hash フィールド（frozenset 専用）
frozenset はイミュータブルなので、ハッシュ値を一度計算したらキャッシュできる。
Py_hash_t hash; /* frozenset のみ使用 */set はミュータブルなのでこのフィールドは使われない（ハッシュ不可能なため）。
fs = frozenset([1, 2, 3])
print(hash(fs)) # 計算済みの値を返す（2回目以降は即座に返る）メモリレイアウトの可視化
set オブジェクトのメモリ配置を概念的に示す。
# 概念的なメモリ配置
#
# PySetObject:
# +------------------+
# | PyObject_HEAD | (ob_refcnt, ob_type)
# +------------------+
# | fill | 5
# +------------------+
# | used | 4
# +------------------+
# | mask | 7 (テーブルサイズ8の場合)
# +------------------+
# | table | → smalltable または外部テーブルへのポインタ
# +------------------+
# | hash | (frozenset のみ)
# +------------------+
# | finger | pop() 用
# +------------------+
# | smalltable[0] | (key, hash)
# | smalltable[1] | (key, hash)
# | ... |
# | smalltable[7] | (key, hash)
# +------------------+
# | weakreflist |
# +------------------+空スロットとダミーの判別
テーブルのスロットには 3 つの状態がある。
| 状態 | key の値 | 意味 |
|---|---|---|
| 空 | NULL | 一度も使われていない |
| アクティブ | 有効なポインタ | 要素が格納されている |
| ダミー | _PySet_Dummy | 削除された（探索は継続） |
ダミーマーカーがあることで、衝突チェーンが途切れない。
#define EMPTY_TO_MINSIZE(so) do { \
memset((so)->smalltable, 0, sizeof((so)->smalltable)); \
(so)->used = (so)->fill = 0; \
(so)->table = (so)->smalltable; \
(so)->mask = PySet_MINSIZE - 1; \
} while(0)GC との連携
set は他のオブジェクトを参照するため、ガベージコレクタの追跡対象になる。
PyObject_GC_Track(so); /* GC に登録 */循環参照を検出するために、GC は set 内の全要素を走査できる必要がある。tp_traverse コールバックがこれを実現している。
import gc
# 循環参照の例
a = set()
b = [a]
a.add(tuple(b)) # 間接的な循環
# GC が検出して解放できる
gc.collect()この内部構造を理解することで、set の挙動やパフォーマンス特性の理由が明確になる。
