Python の set と dict の内部構造の違い
Python の set と dict はどちらもハッシュテーブルを基盤としているが、内部実装にはいくつかの違いがある。
基本的な構造の違い
set はキーのみを格納し、dict はキーと値のペアを格納する。この違いが内部構造に反映されている。
ハッシュ値と要素自体を格納。キーのみの存在確認に特化。
ハッシュ値、キー、値を格納。キーから値へのマッピングを提供。
CPython のソースコードでは、set は setobject.c、dict は dictobject.c で実装されている。
メモリレイアウト
dict は Python 3.6 以降、挿入順序を保持する設計に変更された。これにより、内部構造が大きく変わっている。
# dict の内部構造（概念）
# インデックス配列: [None, 0, None, 1, None, None, 2, None]
# エントリ配列: [(hash_a, key_a, value_a),
# (hash_b, key_b, value_b),
# (hash_c, key_c, value_c)]dict は 2 つの配列を持つ。インデックス配列は疎で、実際のデータはエントリ配列に密に格納される。この設計により、挿入順序の保持とメモリ効率の両立を実現している。
一方、set は従来どおり 1 つのテーブルに直接要素を格納する。
# set の内部構造（概念）
# テーブル: [None, entry_a, None, entry_b, entry_c, None, None, None]メモリ使用量の比較
同じ要素数でも、set と dict ではメモリ使用量が異なる。
import sys
n = 1000
s = set(range(n))
d = {i: None for i in range(n)}
print(f"set: {sys.getsizeof(s):,} bytes") # set: 32,984 bytes
print(f"dict: {sys.getsizeof(d):,} bytes") # dict: 36,960 bytesdict のほうが値を格納する分だけ大きくなる。ただし、dict の新設計では空のスロットが値を持たないため、以前よりメモリ効率が改善されている。
挿入順序の保持
Python 3.7 以降、dict は挿入順序を言語仕様として保証している。set にはこの保証がない。
d = {}
d['c'] = 1
d['a'] = 2
d['b'] = 3
print(list(d.keys())) # ['c', 'a', 'b']（挿入順）
s = set()
s.add('c')
s.add('a')
s.add('b')
print(list(s)) # 順序は不定set のイテレーション順序はハッシュテーブルのレイアウトに依存し、実装の詳細として扱われる。
ハッシュ衝突時の挙動
衝突解決のアルゴリズムは基本的に同じオープンアドレス法だが、プロービングの詳細は若干異なる。
# 両者とも擬似ランダムなプロービングを使用
# perturb = hash
# index = (5 * index + perturb + 1) % size
# perturb >>= PERTURB_SHIFTdict は Python 3.6 でコンパクト化されたため、衝突解決がインデックス配列上で行われる。set は依然としてメインテーブル上で解決する。
削除時の挙動
要素を削除すると、そのスロットは「削除済みマーカー」で埋められる。これは次の検索で衝突チェーンを正しくたどるために必要だ。
s = {1, 2, 3, 4, 5}
s.remove(3)
# 内部的には 3 のスロットに DUMMY マーカーが置かれる
d = {1: 'a', 2: 'b', 3: 'c'}
del d[2]
# 同様に削除済みマーカーが使われる削除が多いと、テーブルが「汚染」されて効率が下がる可能性がある。Python は適切なタイミングでテーブルをリサイズし、削除済みスロットを整理する。
キー比較のコスト
set と dict の両方で、要素の検索には hash() と __eq__() が使われる。
class Verbose:
def __init__(self, value):
self.value = value
def __hash__(self):
print(f"hash({self.value})")
return hash(self.value)
def __eq__(self, other):
print(f"{self.value} == {other.value}")
return self.value == other.value
s = set()
s.add(Verbose(1))
s.add(Verbose(2))
print("--- checking ---")
Verbose(1) in sまず hash() でスロットを特定し、そこに既存の要素があれば __eq__() で一致を確認する。ハッシュが一致しても値が異なる場合（衝突）、__eq__() が呼ばれる。
空の状態でのサイズ
空の set と dict でもメモリは消費される。
import sys
print(sys.getsizeof(set())) # 216 bytes
print(sys.getsizeof(dict())) # 64 bytesPython 3.6 以降の dict はコンパクトな初期サイズを持つ。set は従来の設計を維持しているため、空でも比較的大きなメモリを使う。
どちらを使うべきか
単に要素の存在確認だけが必要なら set を使う。キーと値の対応付けが必要なら dict を使う。
重複排除、存在確認、集合演算が必要な場合。値との対応が不要。
キーから値を引く必要がある場合。順序を保持したい場合にも dict が有利。
パフォーマンス面では、両者の検索速度はほぼ同等だ。目的に合った方を選べば問題ない。
