16. 辞書とセット

#16. 辞書とセット

ディクショナリとセットは、CPython の主要なハッシュ テーブル コンテナです。辞書はキーを値にマッピングします。セットには、値が関連付けられていないキーが格納されます。

これらは Python のあらゆる場所で使用されます。```text id="cp7dx7" module globals class namespaces instance attributes keyword arguments function annotations import caches memoization tables membership indexes deduplication sets

## 16.1 辞書の意味論

辞書はハッシュ可能なキーを値にマッピングします。```python id="cvrlq9"
d = {
    "name": "Ada",
    "age": 36,
}

print(d["name"])    # Ada
```キーはハッシュ可能である必要があります。値には任意のオブジェクトを指定できます。```python id="mb4tqx"
d = {}

d["x"] = []
d[42] = object()
d[(1, 2)] = "tuple key"
```キーが安定したハッシュ値を持ち、そのハッシュと互換性のある等価比較をサポートしている場合、キーはハッシュ可能です。```python id="100k2v"
hash("name")        # works
hash((1, 2))        # works
hash([1, 2])        # TypeError
```リストは内容が変更される可能性があるため、ハッシュ化できません。

## 16.2 セットのセマンティクス

セットには、一意のハッシュ可能な要素が格納されます。```python id="a9i1rs"
seen = set()

seen.add("x")
seen.add("x")

print(seen)         # {'x'}
```セットは、メンバーシップのテスト、重複排除、またはセット代数が必要な場合に便利です。```python id="utkml3"
a = {"red", "green", "blue"}
b = {"green", "yellow"}

print(a & b)        # intersection
print(a | b)        # union
print(a - b)        # difference
```あ`frozenset`すべての要素がハッシュ可能であれば、不変かつハッシュ可能です。```python id="8f3u4m"
key = frozenset(["read", "write"])
d = {key: "permissions"}
```## 16.3 ハッシュテーブル

ディクショナリとセットはハッシュ テーブルです。

ハッシュ テーブルは、ハッシュ値を使用して、内部テーブル内のオブジェクトが存在する場所を見つけます。

辞書検索の場合:```text id="kobvyn"
hash key
find candidate slot
compare stored key with lookup key
return value if equal
```セットメンバーシップの場合:```text id="hbs3i1"
hash element
find candidate slot
compare stored element with lookup element
return present or absent
```平均的なケースのルックアップは定数時間です。```text id="qme3op"
d[key]      average O(1)
key in d    average O(1)
x in set    average O(1)
```多くのキーが衝突すると最悪の場合の動作が低下する可能性がありますが、CPython には衝突処理とハッシュのランダム化防御機能が含まれています。

## 16.4 ハッシュと等価契約

ハッシュコントラクトは次のとおりです。```text id="u4q6w3"
if a == b, then hash(a) == hash(b)
```逆は必要ありません。```text id="2ibsgd"
if hash(a) == hash(b), a may still be different from b
```2 つの等しくないオブジェクトが同じハッシュを持つ場合、衝突が発生します。

辞書はキーを比較することによって衝突を処理します。

カスタムキーの例:```python id="7h6xvk"
class Key:
    def __init__(self, value):
        self.value = value

    def __eq__(self, other):
        return isinstance(other, Key) and self.value == other.value

    def __hash__(self):
        return hash(self.value)
```定義すると`__eq__`、互換性のあるものを定義します`__hash__`オブジェクトがハッシュ化できるほど不変である場合にのみ。

## 16.5 可変キーは危険です

キーが辞書またはセットにある間、キーのハッシュは安定したままでなければなりません。

これはダメです：```python id="51z0wo"
class BadKey:
    def __init__(self, value):
        self.value = value

    def __eq__(self, other):
        return isinstance(other, BadKey) and self.value == other.value

    def __hash__(self):
        return hash(self.value)

k = BadKey("a")
d = {k: "value"}

k.value = "b"
```突然変異の後、オブジェクトはテーブル内で見つからなくなる可能性があります。```python id="u2wkp9"
print(d.get(k))     # may fail unexpectedly
```辞書は古いハッシュに従ってキーを配置しました。ルックアップでは新しいハッシュが使用されます。

不変のキーデータを使用します。```python id="mzfzuj"
key = ("user", 123)
```## 16.6 辞書オブジェクトのレイアウト

CPython 辞書オブジェクトはメタデータを保存し、テーブル データを指します。

概念的には:```text id="36zah2"
PyDictObject
    object header
    used count
    version tag
    keys table pointer
    values pointer for split-table dicts
```内部レイアウトは最適化され、バージョンごとに異なりますが、重要な考え方は次のとおりです。```text id="kpjby5"
dictionary object
    controls a hash table
    stores keys and values
    resizes as needed
```ディクショナリは、キーと値のオブジェクトを生の値としてインラインで保存しません。 Python オブジェクトへの参照を保存します。```text id="jxgd18"
dict entry
    key pointer   ---> Python object
    value pointer ---> Python object
    hash value
```## 16.7 テーブルの結合と分割

CPython 辞書はさまざまな内部レイアウトを使用できます。

結合テーブルには、キーと値が一緒に格納されます。```text id="kswrs2"
entry
    hash
    key pointer
    value pointer
```分割テーブルは、共有キーをインスタンスごとの値から分離します。

これは、同じクラスのオブジェクトの辞書の場合に便利です。

例：```python id="pr3ahp"
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

a = Point(1, 2)
b = Point(3, 4)
```両方のインスタンスに属性があります`x`そして`y`。

CPython は、各インスタンスが独自の値を保存しながら、クラスのインスタンス レイアウトの主要なメタデータを共有できます。

概念的には:```text id="4gdmgx"
shared keys table
    "x"
    "y"

instance a values
    1
    2

instance b values
    3
    4
```これにより、同じ属性名を持つ多数のインスタンスのメモリ使用量が削減されます。

## 16.8 広告掲載オーダー

辞書は挿入順序を保持します。```python id="jf7ccx"
d = {}
d["a"] = 1
d["b"] = 2
d["c"] = 3

print(list(d))      # ['a', 'b', 'c']
```既存のキーを更新しても移動しません。```python id="2d4s8h"
d["b"] = 20
print(list(d))      # ['a', 'b', 'c']
```削除して再挿入すると、新しい挿入位置が作成されます。```python id="2tmw4q"
del d["b"]
d["b"] = 200

print(list(d))      # ['a', 'c', 'b']
```挿入順序は、最新の Python における辞書の言語動作であり、単なる CPython の偶然の詳細ではありません。

## 16.9 辞書検索

辞書検索にはいくつかの段階があります。```python id="fq8zvc"
value = d[key]
```概念的には:```text id="5w58mp"
compute hash(key)
choose initial table slot
inspect slot
    if empty: key missing
    if stored hash differs: continue probing
    if stored key is key: found
    if stored key == key: found
    otherwise continue probing
```可能な場合、同一性は等価性の前にチェックされます。同じオブジェクトがキーとして使用される場合、ルックアップは等価性の作業を回避できます。```python id="b3vf1x"
key = "name"
d = {key: "Ada"}

print(d[key])
```文字列の場合、キャッシュされたハッシュとインターニングにより、検索が特に高速になります。

## 16.10 衝突処理

異なるキーが同じハッシュを持つことができます。```python id="u61im9"
class Collide:
    def __init__(self, value):
        self.value = value

    def __hash__(self):
        return 1

    def __eq__(self, other):
        return isinstance(other, Collide) and self.value == other.value
```すべてのインスタンスのハッシュ`1`。```python id="sn5hoa"
d = {}
for i in range(100):
    d[Collide(i)] = i
```辞書は引き続き機能しますが、多くのプローブと等価性チェックが必要になるため、パフォーマンスが低下します。

ハッシュのランダム化は、ネットワークに面したプログラムにおける予測可能な衝突攻撃から文字列のようなキーを保護するのに役立ちます。

## 16.11 サイズ変更

辞書がいっぱいになると、サイズが変更されます。

目標は、テーブル内の空のスペースを維持することで検索の効率を維持することです。

概念的には:```text id="km324o"
insert key
    if table load is high:
        allocate larger table
        reinsert active entries
    insert new key
```サイズ変更のコスト`O(n)`現時点ではそれが発生していますが、挿入は平均して効率的です。

これは、リストの過剰割り当てと精神的に似ています。コンテナーは、一般的な操作を高速に保つために追加のメモリを使用します。

## 16.12 削除とダミーエントリ

辞書キーを削除しても、スロットを単に空としてマークできるとは限りません。

なぜ？

ルックアップはプローブ チェーンに依存する可能性があるためです。削除によってチェーンが切れた場合、後のキーに到達できなくなる可能性があります。

そのため、ハッシュ テーブルでは、削除されたスロットにダミー マーカーを使用することがよくあります。

概念的には:```text id="o8jbeg"
active slot
    contains key and value

empty slot
    never used

dummy slot
    used before, now deleted
```挿入ではダミースロットを再利用できます。ルックアップではそれらをスキップする必要があります。

ダミー スロットが多すぎるとパフォーマンスが低下する可能性があるため、サイズ変更または再構築することでスロットをクリーンアップできます。

## 16.13 辞書ビュー

ディクショナリ ビュー オブジェクトは、キー、値、または項目の動的なビューを公開します。```python id="ovth2c"
d = {"a": 1, "b": 2}

keys = d.keys()
values = d.values()
items = d.items()
```ビューには後の変更が反映されます。```python id="bjim9l"
keys = d.keys()

d["c"] = 3

print(keys)     # dict_keys(['a', 'b', 'c'])
```ビューはコピーを回避します。これらは辞書を指す軽量のオブジェクトです。

スナップショットを作成するには、以下を明示的にコピーします。```python id="k65165"
keys_snapshot = list(d.keys())
```## 16.14 辞書の反復

辞書を反復するとキーが生成されます。```python id="ra7i88"
for key in d:
    print(key)
```同等：```python id="4hpn52"
for key in d.keys():
    print(key)
```反復中に辞書のサイズを変更するとエラーが発生します。```python id="4085f6"
for key in d:
    d["new"] = 1      # RuntimeError
```通常、キーを変更せずに値を変更することは許可されます。```python id="t0n9jz"
for key in d:
    d[key] += 1
```イテレータは、一貫性を保つ辞書構造に依存します。

## 16.15 辞書バージョンのタグ

CPython 辞書は、辞書が変更されると変更されるバージョン情報を維持できます。

バージョン タグは、実行時の最適化、特にキャッシュに役立ちます。

たとえば、属性ルックアップとグローバル ルックアップは、ディクショナリが変更されていない場合でも情報をキャッシュできます。

概念的には:```text id="pfdsrf"
dict version = 100
cache lookup result for name "x"

later:
    if dict version still 100:
        cached result may be valid
    else:
        redo lookup
```これは、Python のセマンティクスを変更せずに動的検索を高速化するための主要なツールです。

## 16.16 グローバルは辞書です

モジュールのグローバル名前空間は辞書です。```python id="h0m5e5"
x = 10

globals()["x"] = 20

print(x)        # 20
```Python コードがグローバル変数を読み取ると、CPython は組み込みへのフォールバックを使用して、モジュール グローバルで辞書検索を実行します。

概念的には:```text id="v5m31f"
LOAD_GLOBAL name
    look in globals dict
    if missing, look in builtins dict
```グローバルは辞書であるため、グローバル変数へのアクセスは辞書のパフォーマンスに依存します。 CPython はインライン キャッシュとバージョン タグを使用して、このパスを高速化します。

## 16.17 インスタンス属性は多くの場合辞書になります

通常のオブジェクト インスタンスは、属性を辞書に保存します。```python id="zdzzxk"
class User:
    pass

u = User()
u.name = "Ada"
u.age = 36

print(u.__dict__)
```出力：```text id="ijc7p2"
{'name': 'Ada', 'age': 36}
```属性アクセス:```python id="6pnbk6"
u.name
```多くの場合、記述子チェックと型レベルの検索の後、辞書検索になります。

CPython は、分割辞書、共有キー、属性キャッシュを使用してこれを大幅に最適化します。

## 16.18 クラス名前空間は辞書です

クラス本体は名前空間マッピングで実行されます。```python id="d3f5st"
class User:
    species = "human"

    def greet(self):
        return "hello"
```クラス名前空間は以下を収集します。```text id="y3ded7"
species
greet
__module__
__qualname__
```次に、メタクラスはその名前空間からクラス オブジェクトを作成します。

結果として得られるクラスには、属性の辞書のようなマッピングが含まれます。```python id="mtwgd9"
print(User.__dict__)
```クラス ディクショナリは読み取り専用で公開されます。`mappingproxy`ビュー。

##16.19`mappingproxy`あ`mappingproxy`マッピングの読み取り専用ビューです。```python id="t40d69"
class C:
    x = 1

print(C.__dict__)
```マッピングプロキシを介して直接割り当てることはできません。```python id="a5po6e"
C.__dict__["y"] = 2      # TypeError
```ただし、通常のクラス属性構文を使用して割り当てることができます。```python id="j36rbw"
C.y = 2
```プロキシは、内部クラス ディクショナリの直接の変更を防ぎながら、イントロスペクションを可能にします。

## 16.20 キーワード引数

キーワード引数は、マッピングのようなメカニズムを使用して表現されます。```python id="7yetex"
def f(**kwargs):
    print(kwargs)

f(a=1, b=2)
```関数内では、`kwargs`辞書です。

呼び出しが一般的であるため、キーワード引数の受け渡しはパフォーマンスに依存します。

CPython には、可能な限り不必要な辞書の作成を避けるための特殊な呼び出し規則がありますが、`**kwargs`が必要な場合、辞書が実体化されます。

## 16.21 セットでもハッシュ テーブルを使用する

セットは値のない辞書に似ています。```python id="j5dt5t"
s = {"a", "b", "c"}
```概念的には:```text id="1c2tu2"
set table entry
    hash
    key pointer
```メンバーシップ:```python id="gc0h7j"
"x" in s
```辞書検索などのハッシュとプローブを使用します。

概念としては、セットのサイズ変更と衝突の処理も同様です。

## 16.22 集合演算

セット操作は内部的にハッシュ テーブル メンバーシップを使用します。```python id="d85y3h"
a = {1, 2, 3}
b = {3, 4, 5}

print(a & b)    # {3}
print(a | b)    # {1, 2, 3, 4, 5}
print(a - b)    # {1, 2}
```パフォーマンスは入力サイズに依存します。

交差の場合は、通常、小さいセットを反復処理し、大きいセットのメンバーシップをテストする方が適切です。

概念的には:```text id="s5h98o"
intersection(a, b)
    for each item in smaller set:
        if item in larger set:
            add to result
```CPython の実装では、このようなサイズを意識した戦略が使用されます。

## 16.23 反復順序の設定

セットは挿入順序を保証するものではありません。```python id="fmu4b8"
s = {"a", "b", "c"}
print(list(s))
```順序は、ハッシュ、テーブル サイズ、挿入履歴、実行時のハッシュのランダム化によって異なります。

設定された反復順序に依存するコードを作成しないでください。

順序が重要な場合は、順序付けされたメンバーシップ マップとして辞書を使用するか、明示的に並べ替えます。```python id="jc3ogv"
ordered_unique = list(dict.fromkeys(items))
```##16.24`dict.fromkeys`一般的な重複排除パターンは次のとおりです。```python id="0og08r"
items = ["b", "a", "b", "c", "a"]

unique = list(dict.fromkeys(items))

print(unique)   # ['b', 'a', 'c']
```これは、辞書の挿入順序を使用して最初の出現を保持します。

セットは重複排除されますが、順序は失われます。```python id="nozz18"
set(items)
```セマンティクスが要件に一致するコンテナを使用します。

## 16.25 デフォルト値と欠落しているキー

いくつかの辞書 API は欠落したキーを処理します。```python id="860ztd"
d.get("key", default)

get挿入せずにデフォルトを返します。```python id="kkfpw8" d.setdefault("key", [])

`setdefault`キーが欠落している場合はデフォルトを挿入します。

よくあるパターン:```python id="t4jd1i"
groups = {}

for item in items:
    groups.setdefault(item.category, []).append(item)
```繰り返しグループ化する場合は、`collections.defaultdict`多くの場合、より明確です:```python id="27x3y1"
from collections import defaultdict

groups = defaultdict(list)

for item in items:
    groups[item.category].append(item)
```## 16.26 辞書内包表記

辞書内包表記は、反復可能オブジェクトから辞書を構築します。```python id="uxw8zk"
squares = {x: x * x for x in range(10)}
```重複キーが表示された場合、最初のキーの挿入位置は保持されたまま、後の値で前の値が置き換えられます。```python id="yct6sa"
d = {x % 2: x for x in range(5)}

print(d)        # {0: 4, 1: 3}
```鍵`0`そして`1`早期に挿入され、その後値が更新されました。

## 16.27 集合内包表記

集合内包表記により集合が構築されます。```python id="3sgagh"
mods = {x % 10 for x in range(100)}
```重複は崩壊します。

集合内包表記は、一意の計算値を抽出するのに役立ちます。```python id="n3vtrw"
domains = {url.split("/")[2] for url in urls}
```繰り返しますが、反復順序は意味を保証するものではありません。

## 16.28 ハッシュのランダム化

CPython は、文字列やバイトなどの一部のハッシュ可能な型に対してハッシュのランダム化を使用します。

これは、ハッシュ値がプロセス間で異なる可能性があることを意味します。```python id="og1g48"
print(hash("name"))
```プログラムを 2 回実行すると、値が異なる場合があります。

固執しないでください`hash()`プロセス全体にわたる価値観。これらを安定した ID として使用しないでください。

安定したハッシュを行うには、定義されたハッシュ関数を使用します。```python id="0clx65"
import hashlib

digest = hashlib.sha256(b"name").hexdigest()

hash()これはインプロセス ハッシュ テーブル用であり、永続的な ID 用ではありません。

16.29 一般的なパフォーマンスパターン

16.30 よくある間違い

頻繁にメンバーになるためのリストの使用:python id="89pu6v" if user_id in user_ids: ... もしuser_idsサイズが大きく、検索が頻繁に発生する場合は、セットを使用します。python id="2yd104" user_ids = set(user_ids) 可変オブジェクトを概念キーとして使用する:python id="wotz0s" key = [1, 2] d[key] = "value" # TypeError タプルを使用します。python id="lpvy37" key = (1, 2) d[key] = "value" セットの順序に応じて:```python id="hmuq1q" first = next(iter(my_set))

永続的`hash()`:

```python id="pchqlg"
id_value = hash(username)
```代わりに安定したハッシュ関数を使用してください。

## 16.31 C API スケッチ

辞書の作成:```c id="eclt1e"
PyObject *d = PyDict_New();
if (d == NULL) {
    return NULL;
}
```項目を設定する：```c id="lk7i25"
PyObject *key = PyUnicode_FromString("name");
PyObject *value = PyUnicode_FromString("Ada");

if (key == NULL || value == NULL) {
    Py_XDECREF(key);
    Py_XDECREF(value);
    Py_DECREF(d);
    return NULL;
}

if (PyDict_SetItem(d, key, value) < 0) {
    Py_DECREF(key);
    Py_DECREF(value);
    Py_DECREF(d);
    return NULL;
}

Py_DECREF(key);
Py_DECREF(value);

PyDict_SetItem参照を盗みません。保存する内容が増加します。呼び出し元は、所有する参照を解放する必要があります。

アイテムを取得すると、API に応じて借用した参照を返すことができます。```c id="m18ydq" PyObject *value = PyDict_GetItemWithError(d, key); if (value == NULL) { if (PyErr_Occurred()) { return NULL; } Py_RETURN_NONE; }

/* borrowed reference */ Py_INCREF(value); return value;

## 16.32 C API スケッチの設定

セットの作成:```c id="l7rkf0"
PyObject *s = PySet_New(NULL);
if (s == NULL) {
    return NULL;
}
```アイテムを追加する:```c id="gjqb0m"
PyObject *item = PyUnicode_FromString("x");
if (item == NULL) {
    Py_DECREF(s);
    return NULL;
}

if (PySet_Add(s, item) < 0) {
    Py_DECREF(item);
    Py_DECREF(s);
    return NULL;
}

Py_DECREF(item);
```セットは、挿入後に独自の参照を所有します。ローカル参照はまだリリースされています。

メンバーシップ:```c id="b4gg5h"
int present = PySet_Contains(s, item);
if (present < 0) {
    return NULL;
}
```結果は次のとおりです。```text id="eari3m"
1 if present
0 if absent
-1 on error
```## 16.33 メンタルモデル

このモデルを使用します。```text id="78tgbw"
dict
    hash table mapping keys to values
    keys must be hashable
    insertion order preserved
    stores references to keys and values
    used throughout CPython runtime

set
    hash table storing keys only
    keys must be hashable
    no insertion-order guarantee
    optimized for membership and set algebra
```両方のコンテナの場合:```text id="e36bns"
hash chooses where to look
equality confirms the key
collisions are handled by probing
resizing keeps lookup efficient
mutation changes table structure
iteration depends on table state
```## 16.34 Summary

ディクショナリとセットはハッシュ テーブル コンテナです。ディクショナリはハッシュ可能なキーを値にマップし、挿入順序を保持します。セットには、一意のハッシュ可能な要素が格納され、メンバーシップのテストとセットの操作が最適化されます。

CPython は、グローバル、属性、クラス、モジュール、キーワード引数、およびキャッシュのコア ランタイム構造としてディクショナリを使用します。その実装には、ハッシュ キャッシュ、衝突処理、サイズ変更、分割テーブル レイアウト、バージョン タグ、順序の保存が含まれます。

ディクショナリとセットを理解すると、Python の速度、オブジェクト モデル、属性検索、名前空間の動作、および一般的なパフォーマンス パターンの多くが説明されます。