Python 中的字典是如何實現(xiàn)的？

Python 中的字典（dictionary）是一種非常常用的數(shù)據(jù)類型，它可以快速地存取和操作數(shù)據(jù)。愛掏網(wǎng) - it200.com與其他語言不同的是，Python 中的字典實現(xiàn)方式是哈希表（hash table）。愛掏網(wǎng) - it200.com

哈希表是一種通過計算值在數(shù)組中的存儲位置而直接訪問數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。愛掏網(wǎng) - it200.com它的基本思想是將關(guān)鍵字映射到一個固定大小的表中，以便能夠快速查找記錄。愛掏網(wǎng) - it200.com哈希表的查找、插入和刪除的時間復(fù)雜度都是 O(1)。愛掏網(wǎng) - it200.com

Python 中的字典采用了哈希表的實現(xiàn)方式，使用哈希函數(shù)將鍵（key）映射到哈希表中的下標（index），可以快速地查找字典中的值（value）。愛掏網(wǎng) - it200.com

字典的創(chuàng)建和訪問

Python 中的字典是用花括號 {} 來表示的，鍵值對之間用冒號 : 連接。愛掏網(wǎng) - it200.com

# 創(chuàng)建字典
my_dict = {'apple': 5, 'banana': 2, 'orange': 8}

# 訪問字典
print(my_dict['apple']) # 輸出 5

在訪問字典時，如果鍵不存在，會拋出 KeyError 異常。愛掏網(wǎng) - it200.com可以使用 get() 方法來避免這種情況。愛掏網(wǎng) - it200.com

# 使用 get() 方法訪問字典
print(my_dict.get('watermelon', 0)) # 輸出 0

字典的添加、修改和刪除

向字典中添加新的鍵值對，可以使用賦值語句。愛掏網(wǎng) - it200.com如果字典中已經(jīng)存在該鍵，賦值語句會更新該鍵對應(yīng)的值。愛掏網(wǎng) - it200.com

# 添加鍵值對
my_dict['watermelon'] = 3
print(my_dict)

# 修改鍵值對
my_dict['apple'] = 6
print(my_dict)

可以使用 del 語句從字典中刪除鍵值對。愛掏網(wǎng) - it200.com

# 刪除鍵值對
del my_dict['orange']
print(my_dict)

字典的遍歷

字典中的鍵值對是無序的，我們可以使用 for 循環(huán)遍歷字典中的所有鍵值對。愛掏網(wǎng) - it200.com可以用 items() 方法獲取鍵值對。愛掏網(wǎng) - it200.com

# 遍歷字典
for key, value in my_dict.items():
    print(key, value)

字典的實現(xiàn)方式

Python 中的字典不是數(shù)組的實現(xiàn)方式，而是哈希表的實現(xiàn)方式。愛掏網(wǎng) - it200.com在 Python 源代碼中，字典的實現(xiàn)可以在 dictobject.c 文件中找到。愛掏網(wǎng) - it200.com

字典的主要結(jié)構(gòu)是 PyDictObject，它包含了一個指針 d_table，指向一個哈希表結(jié)構(gòu)體 PyDictKeysObject。愛掏網(wǎng) - it200.com哈希表結(jié)構(gòu)體中包含了一個指針 dk_entries，指向 PyDictKeyEntry 結(jié)構(gòu)體數(shù)組，每個 PyDictKeyEntry 結(jié)構(gòu)體儲存了哈希表中一個格子里的信息。愛掏網(wǎng) - it200.com

以下是哈希表結(jié)構(gòu)體 PyDictKeysObject 的定義：

typedef struct {
    Py_ssize_t dk_refcnt;               /* 引用計數(shù) */
    Py_ssize_t dk_size;                 /* 哈希表大小 */
    dictentry dk_lookup[PyDict_MINSIZE]; /* 最小哈希表大小 */
    PyDictKeyEntry *dk_entries;         /* 格子信息 */
    Py_ssize_t dk_usable;               /* 實際可用的哈希表大小 */
} PyDictKeysObject;

dk_lookup 數(shù)組用來實現(xiàn)哈希表中的沖突解決。愛掏網(wǎng) - it200.com當哈希表中的一個格子已經(jīng)被占用時，就會使用線性探測來從 dk_lookup 數(shù)組中找到下一個空閑的位置。愛掏網(wǎng) - it200.com

dk_entries 數(shù)組中保存了所有的鍵值對信息。愛掏網(wǎng) - it200.com每個 PyDictKeyEntry 結(jié)構(gòu)體都包含了鍵和值的信息，以及哈希表中的位置。愛掏網(wǎng) - it200.com以下是 PyDictKeyEntry 結(jié)構(gòu)體的定義：

typedef struct {
    PyObject *me_key;       /* 鍵 */
    PyDictValueUnion me_value;  /* 值 */
    Py_ssize_t me_hash;         /* 哈希值 */
} PyDictKeyEntry;

在哈希表中查找一個鍵值對時，首先計算鍵的哈希值，然后根據(jù)哈希值計算鍵在哈希表中的位置。愛掏網(wǎng) - it200.com如果該位置上的鍵值對不是要查詢的鍵值對，就繼續(xù)向后查找，一直到找到該鍵值對或者遇到空位置。愛掏網(wǎng) - it200.com

哈希表的大小不是固定的，而是會根據(jù)需要動態(tài)地調(diào)整。愛掏網(wǎng) - it200.com當哈希表中的鍵值對數(shù)量達到了一定的比例時，Python 會自動擴大哈希表的大小，以便更好地分配鍵值對。愛掏網(wǎng) - it200.com