16. Từ điển và Bộ

Từ điển và bộ là các vùng chứa bảng băm chính của CPython. Một từ điển ánh xạ các khóa tới các giá trị. Một bộ lưu trữ các khóa không có giá trị liên quan.

Chúng được sử dụng ở mọi nơi trong Python:```text id="cp7dx7" module globals class namespaces instance attributes keyword arguments function annotations import caches memoization tables membership indexes deduplication sets

## 16.1 Từ điển Ngữ nghĩa

Một từ điển ánh xạ các khóa có thể băm thành các giá trị.```python id="cvrlq9"
d = {
    "name": "Ada",
    "age": 36,
}

print(d["name"])    # Ada
```Khóa phải có thể băm được. Giá trị có thể là bất kỳ đối tượng nào.```python id="mb4tqx"
d = {}

d["x"] = []
d[42] = object()
d[(1, 2)] = "tuple key"
```Một khóa có thể băm được khi nó có giá trị băm ổn định và hỗ trợ so sánh đẳng thức tương thích với hàm băm đó.```python id="100k2v"
hash("name")        # works
hash((1, 2))        # works
hash([1, 2])        # TypeError
```Danh sách không thể băm được vì nội dung của chúng có thể thay đổi.

## 16.2 Đặt ngữ nghĩa

Một bộ lưu trữ các phần tử có thể băm duy nhất.```python id="a9i1rs"
seen = set()

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

print(seen)         # {'x'}
```Một tập hợp rất hữu ích khi bạn cần kiểm tra tư cách thành viên, loại bỏ trùng lặp hoặc tập hợp đại số.```python id="utkml3"
a = {"red", "green", "blue"}
b = {"green", "yellow"}

print(a & b)        # intersection
print(a | b)        # union
print(a - b)        # difference
```MỘT`frozenset`là bất biến và có thể băm được nếu tất cả các phần tử đều có thể băm được.```python id="8f3u4m"
key = frozenset(["read", "write"])
d = {key: "permissions"}
```## 16.3 Bảng băm

Từ điển và bộ là bảng băm.

Bảng băm sử dụng giá trị băm để tìm vị trí của một đối tượng trong bảng nội bộ.

Để tra cứu từ điển:```text id="kobvyn"
hash key
find candidate slot
compare stored key with lookup key
return value if equal
```Đối với thành viên được thiết lập:```text id="hbs3i1"
hash element
find candidate slot
compare stored element with lookup element
return present or absent
```Tra cứu trường hợp trung bình là thời gian không đổi:```text id="qme3op"
d[key]      average O(1)
key in d    average O(1)
x in set    average O(1)
```Hành vi trong trường hợp xấu nhất có thể suy giảm khi nhiều khóa va chạm, nhưng CPython bao gồm khả năng xử lý va chạm và bảo vệ ngẫu nhiên hàm băm.

## 16.4 Hợp đồng băm và bình đẳng

Hợp đồng băm là:```text id="u4q6w3"
if a == b, then hash(a) == hash(b)
```Không cần phải làm ngược lại:```text id="2ibsgd"
if hash(a) == hash(b), a may still be different from b
```Xung đột xảy ra khi hai đối tượng không bằng nhau có cùng hàm băm.

Từ điển xử lý xung đột bằng cách so sánh các khóa.

Ví dụ về khóa tùy chỉnh:```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)
```Nếu bạn xác định`__eq__`, xác định một tương thích`__hash__`chỉ khi đối tượng đủ bất biến để băm.

## 16.5 Khóa có thể thay đổi rất nguy hiểm

Hàm băm của khóa phải duy trì ổn định trong khi khóa nằm trong từ điển hoặc bộ.

Điều này thật tệ:```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"
```Sau khi đột biến, đối tượng có thể không còn tìm thấy trong bảng nữa.```python id="u2wkp9"
print(d.get(k))     # may fail unexpectedly
```Từ điển đặt khóa theo hàm băm cũ. Tra cứu sử dụng hàm băm mới.

Sử dụng dữ liệu khóa bất biến.```python id="mzfzuj"
key = ("user", 123)
```## 16.6 Bố cục đối tượng từ điển

Đối tượng từ điển CPython lưu trữ siêu dữ liệu và trỏ đến dữ liệu bảng.

Về mặt khái niệm:```text id="36zah2"
PyDictObject
    object header
    used count
    version tag
    keys table pointer
    values pointer for split-table dicts
```Bố cục bên trong được tối ưu hóa và dành riêng cho từng phiên bản, nhưng ý tưởng chính là:```text id="kpjby5"
dictionary object
    controls a hash table
    stores keys and values
    resizes as needed
```Từ điển không lưu trữ các đối tượng khóa và giá trị nội tuyến dưới dạng giá trị thô. Nó lưu trữ các tham chiếu đến các đối tượng Python.```text id="jxgd18"
dict entry
    key pointer   ---> Python object
    value pointer ---> Python object
    hash value
```## 16.7 Bảng kết hợp và chia tách

Từ điển CPython có thể sử dụng các bố cục nội bộ khác nhau.

Một bảng kết hợp lưu trữ các khóa và giá trị cùng nhau.```text id="kswrs2"
entry
    hash
    key pointer
    value pointer
```Bảng phân chia tách các khóa dùng chung khỏi các giá trị theo từng phiên bản.

Điều này rất hữu ích cho các từ điển ví dụ của các đối tượng cùng lớp.

Ví dụ:```python id="pr3ahp"
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

a = Point(1, 2)
b = Point(3, 4)
```Cả hai trường hợp đều có thuộc tính`x`Và`y`.

CPython có thể chia sẻ siêu dữ liệu chính cho bố cục phiên bản của lớp trong khi mỗi phiên bản lưu trữ các giá trị riêng.

Về mặt khái niệm:```text id="4gdmgx"
shared keys table
    "x"
    "y"

instance a values
    1
    2

instance b values
    3
    4
```Điều này làm giảm mức sử dụng bộ nhớ cho nhiều phiên bản có cùng tên thuộc tính.

## 16.8 Thứ tự chèn

Từ điển giữ nguyên thứ tự chèn.```python id="jf7ccx"
d = {}
d["a"] = 1
d["b"] = 2
d["c"] = 3

print(list(d))      # ['a', 'b', 'c']
```Cập nhật khóa hiện có sẽ không di chuyển khóa đó:```python id="2d4s8h"
d["b"] = 20
print(list(d))      # ['a', 'b', 'c']
```Việc xóa và chèn lại sẽ tạo ra vị trí chèn mới:```python id="2tmw4q"
del d["b"]
d["b"] = 200

print(list(d))      # ['a', 'c', 'b']
```Thứ tự chèn là hành vi ngôn ngữ cho từ điển trong Python hiện đại, không chỉ đơn thuần là chi tiết CPython ngẫu nhiên.

## 16.9 Tra cứu từ điển

Tra cứu từ điển có nhiều giai đoạn.```python id="fq8zvc"
value = d[key]
```Về mặt khái niệm:```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
```Danh tính được kiểm tra trước sự bình đẳng khi có thể. Nếu sử dụng cùng một đối tượng làm khóa, việc tra cứu có thể tránh được công việc bình đẳng.```python id="b3vf1x"
key = "name"
d = {key: "Ada"}

print(d[key])
```Đối với chuỗi, hàm băm và nội bộ được lưu trong bộ nhớ đệm có thể giúp việc tra cứu đặc biệt nhanh chóng.

## 16.10 Xử lý va chạm

Các khóa khác nhau có thể có cùng hàm băm.```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
```Tất cả các phiên bản băm thành`1`.

```python id="sn5hoa"
d = {}
for i in range(100):
    d[Collide(i)] = i
```Từ điển vẫn hoạt động nhưng hiệu suất bị ảnh hưởng vì cần nhiều thăm dò và kiểm tra tính bằng nhau.

Tính năng ngẫu nhiên hóa hàm băm giúp bảo vệ các khóa giống chuỗi khỏi các cuộc tấn công xung đột có thể dự đoán được trong các chương trình đối mặt với mạng.

## 16.11 Thay đổi kích thước

Từ điển sẽ thay đổi kích thước khi nó quá đầy.

Mục tiêu là duy trì việc tra cứu hiệu quả bằng cách duy trì khoảng trống trong bảng.

Về mặt khái niệm:```text id="km324o"
insert key
    if table load is high:
        allocate larger table
        reinsert active entries
    insert new key
```Thay đổi kích thước chi phí`O(n)`tại thời điểm điều đó xảy ra, nhưng tính trung bình, các thao tác chèn vẫn có hiệu quả.

Về mặt tinh thần, điều này tương tự như việc phân bổ quá mức trong danh sách. Vùng chứa sử dụng thêm bộ nhớ để giữ cho các hoạt động chung được nhanh chóng.

## 16.12 Xóa và nhập giả

Việc xóa khóa từ điển không phải lúc nào cũng đánh dấu một vị trí là trống.

Tại sao?

Bởi vì việc tra cứu có thể dựa vào chuỗi thăm dò. Nếu việc xóa làm đứt chuỗi, các khóa sau này có thể không thể truy cập được.

Vì vậy các bảng băm thường sử dụng các điểm đánh dấu giả cho các vị trí đã bị xóa.

Về mặt khái niệm:```text id="o8jbeg"
active slot
    contains key and value

empty slot
    never used

dummy slot
    used before, now deleted
```Việc chèn có thể sử dụng lại các khe giả. Tra cứu phải bỏ qua chúng.

Quá nhiều khe giả có thể ảnh hưởng đến hiệu suất, do đó việc thay đổi kích thước hoặc xây dựng lại có thể làm sạch chúng.

## 16.13 Lượt xem từ điển

Đối tượng dạng xem từ điển hiển thị dạng xem động của khóa, giá trị hoặc mục.```python id="ovth2c"
d = {"a": 1, "b": 2}

keys = d.keys()
values = d.values()
items = d.items()
```Lượt xem phản ánh các đột biến sau này:```python id="bjim9l"
keys = d.keys()

d["c"] = 3

print(keys)     # dict_keys(['a', 'b', 'c'])
```Lượt xem tránh sao chép. Chúng là những vật thể nhẹ trỏ lại từ điển.

Để tạo ảnh chụp nhanh, hãy sao chép rõ ràng:```python id="k65165"
keys_snapshot = list(d.keys())
```## 16.14 Lặp lại một từ điển

Lặp lại một từ điển mang lại các khóa.```python id="ra7i88"
for key in d:
    print(key)
```Tương đương:```python id="4hpn52"
for key in d.keys():
    print(key)
```Trong quá trình lặp lại, việc thay đổi kích thước của từ điển sẽ gây ra lỗi:```python id="4085f6"
for key in d:
    d["new"] = 1      # RuntimeError
```Việc thay đổi giá trị mà không thay đổi khóa thường được cho phép:```python id="t0n9jz"
for key in d:
    d[key] += 1
```Trình vòng lặp dựa vào cấu trúc từ điển để luôn nhất quán.

## 16.15 Phiên bản từ điển Tags

Từ điển CPython có thể duy trì thông tin phiên bản thay đổi khi từ điển thay đổi.

Thẻ phiên bản rất hữu ích cho việc tối ưu hóa thời gian chạy, đặc biệt là bộ đệm.

Ví dụ: tra cứu thuộc tính và tra cứu toàn cục có thể lưu vào bộ đệm thông tin khi từ điển không thay đổi.

Về mặt khái niệm:```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
```Đây là một công cụ chính để tăng tốc độ tra cứu động mà không làm thay đổi ngữ nghĩa Python.

## 16.16 Toàn cầu là từ điển

Không gian tên chung của mô-đun là một từ điển.```python id="h0m5e5"
x = 10

globals()["x"] = 20

print(x)        # 20
```Khi mã Python đọc một biến toàn cục, CPython thực hiện tra cứu từ điển trong các phần tổng quát của mô-đun, với dự phòng cho các phần dựng sẵn.

Về mặt khái niệm:```text id="v5m31f"
LOAD_GLOBAL name
    look in globals dict
    if missing, look in builtins dict
```Bởi vì toàn cầu là từ điển, nên việc truy cập biến toàn cục phụ thuộc vào hiệu suất của lệnh. CPython sử dụng bộ đệm nội tuyến và thẻ phiên bản để tăng tốc đường dẫn này.

## 16.17 Thuộc tính sơ thẩm thường là từ điển

Các thể hiện đối tượng thông thường thường lưu trữ các thuộc tính trong từ điển.```python id="zdzzxk"
class User:
    pass

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

print(u.__dict__)
```Đầu ra:```text id="ijc7p2"
{'name': 'Ada', 'age': 36}
```Truy cập thuộc tính:```python id="6pnbk6"
u.name
```thường trở thành tra cứu từ điển, sau khi kiểm tra bộ mô tả và tra cứu cấp độ loại.

CPython tối ưu hóa điều này rất nhiều với từ điển phân tách, khóa chia sẻ và bộ nhớ đệm thuộc tính.

## 16.18 Không gian tên lớp là từ điển

Nội dung lớp thực thi trong ánh xạ không gian tên.```python id="d3f5st"
class User:
    species = "human"

    def greet(self):
        return "hello"
```Không gian tên lớp thu thập:```text id="y3ded7"
species
greet
__module__
__qualname__
```Sau đó siêu dữ liệu sẽ tạo đối tượng lớp từ không gian tên đó.

Lớp kết quả có ánh xạ các thuộc tính giống như từ điển.```python id="mtwgd9"
print(User.__dict__)
```Từ điển lớp được hiển thị thông qua chế độ chỉ đọc`mappingproxy`xem.

## 16.19`mappingproxy`MỘT`mappingproxy`là chế độ xem chỉ đọc của bản đồ.```python id="t40d69"
class C:
    x = 1

print(C.__dict__)
```Bạn không thể chỉ định trực tiếp thông qua proxy ánh xạ:```python id="a5po6e"
C.__dict__["y"] = 2      # TypeError
```Nhưng bạn có thể gán thông qua cú pháp thuộc tính lớp thông thường:```python id="j36rbw"
C.y = 2
```Proxy ngăn chặn sự đột biến trực tiếp của từ điển lớp nội bộ trong khi vẫn cho phép xem xét nội tâm.

## 16.20 Đối số từ khóa

Đối số từ khóa được biểu diễn bằng cơ chế giống như ánh xạ.```python id="7yetex"
def f(**kwargs):
    print(kwargs)

f(a=1, b=2)
```Bên trong hàm,`kwargs`là một cuốn từ điển.

Việc truyền đối số từ khóa phụ thuộc vào hiệu suất vì các cuộc gọi là phổ biến.

CPython có các quy ước gọi chuyên dụng để tránh việc tạo từ điển không cần thiết khi có thể, nhưng khi`**kwargs`là cần thiết, một từ điển được hiện thực hóa.

## 16.21 Bộ cũng sử dụng bảng băm

Một bộ tương tự như một từ điển không có giá trị.```python id="j5dt5t"
s = {"a", "b", "c"}
```Về mặt khái niệm:```text id="1c2tu2"
set table entry
    hash
    key pointer
```Thành viên:```python id="gc0h7j"
"x" in s
```sử dụng hàm băm và thăm dò, giống như tra cứu dict.

Đặt thay đổi kích thước và xử lý xung đột tương tự như trong khái niệm.

## 16.22 Thiết lập hoạt động

Các thao tác thiết lập sử dụng tư cách thành viên bảng băm trong nội bộ.```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}
```Hiệu suất phụ thuộc vào kích thước đầu vào.

Đối với giao điểm, tốt hơn là lặp lại tập hợp nhỏ hơn và kiểm tra tư cách thành viên trong tập hợp lớn hơn.

Về mặt khái niệm:```text id="s5h98o"
intersection(a, b)
    for each item in smaller set:
        if item in larger set:
            add to result
```Việc triển khai CPython sử dụng các loại chiến lược nhận biết kích thước này.

## 16.23 Đặt thứ tự lặp lại

Các bộ không hứa hẹn thứ tự chèn.```python id="fmu4b8"
s = {"a", "b", "c"}
print(list(s))
```Thứ tự có thể phụ thuộc vào hàm băm, kích thước bảng, lịch sử chèn và ngẫu nhiên hàm băm thời gian chạy.

Không viết mã phụ thuộc vào thứ tự lặp đã đặt.

Nếu thứ tự quan trọng, hãy sử dụng từ điển làm bản đồ thành viên được sắp xếp theo thứ tự hoặc sắp xếp một cách rõ ràng.```python id="jc3ogv"
ordered_unique = list(dict.fromkeys(items))
```## 16,24`dict.fromkeys`Một mô hình chống trùng lặp phổ biến:```python id="0og08r"
items = ["b", "a", "b", "c", "a"]

unique = list(dict.fromkeys(items))

print(unique)   # ['b', 'a', 'c']
```Điều này sử dụng thứ tự chèn từ điển để duy trì lần xuất hiện đầu tiên.

Một bộ sẽ bị trùng lặp nhưng mất thứ tự:```python id="nozz18"
set(items)
```Sử dụng vùng chứa có ngữ nghĩa phù hợp với yêu cầu.

## 16.25 Giá trị mặc định và khóa bị thiếu

Một số API từ điển xử lý các khóa bị thiếu.```python id="860ztd"
d.get("key", default)