Terms Privacy

© Rollpie

MathPython
24 Dec 2025

Python の set と dict の内部構造の違い

Python の set と dict はどちらもハッシュテーブルを基盤としているが、内部実装にはいくつかの違いがある。

基本的な構造の違い

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 bytes

dict のほうが値を格納する分だけ大きくなる。ただし、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_SHIFT

dict は 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 bytes

Python 3.6 以降の dict はコンパクトな初期サイズを持つ。set は従来の設計を維持しているため、空でも比較的大きなメモリを使う。

どちらを使うべきか

単に要素の存在確認だけが必要なら set を使う。キーと値の対応付けが必要なら dict を使う。

set が適切な場面

重複排除、存在確認、集合演算が必要な場合。値との対応が不要。

dict が適切な場面

キーから値を引く必要がある場合。順序を保持したい場合にも dict が有利。

パフォーマンス面では、両者の検索速度はほぼ同等だ。目的に合った方を選べば問題ない。

7 views