Python內建類型dict源碼分析

Python內建類型dict源碼分析

1. 引言

Python中的字典（dict）是一種非常常用的數據結構，它提供了高效的鍵值對存儲和查找功能。字典的實現涉及到許多底層的數據結構和算法，理解這些內容對于深入掌握Python的內部機制非常有幫助。本文將深入分析Python中dict類型的源碼實現，探討其內部結構、哈希表的工作原理、沖突解決策略、內存管理以及性能優化等方面。

2. 字典的基本概念

在Python中，字典是一種可變容器模型，可以存儲任意類型的對象。字典中的每個元素都是一個鍵值對，鍵必須是不可變類型，而值可以是任意類型。字典的主要操作包括插入、刪除、查找等，這些操作的平均時間復雜度都是O(1)。

2.1 字典的創建

字典可以通過多種方式創建，最常見的方式是使用花括號{}或dict()構造函數：

# 使用花括號創建字典
d1 = {'name': 'Alice', 'age': 25}

# 使用dict()構造函數創建字典
d2 = dict(name='Bob', age=30)

2.2 字典的基本操作

字典支持多種操作，包括插入、刪除、查找、更新等：

# 插入
d1['gender'] = 'female'

# 刪除
del d1['age']

# 查找
name = d1['name']

# 更新
d1['name'] = 'Alice Smith'

3. 字典的內部結構

Python中的字典是通過哈希表（Hash Table）實現的。哈希表是一種通過哈希函數將鍵映射到索引的數據結構，它能夠在平均情況下提供O(1)的查找、插入和刪除操作。

3.1 哈希表的基本概念

哈希表的核心思想是通過哈希函數將鍵轉換為一個整數索引，然后將鍵值對存儲在該索引對應的位置。哈希函數的設計對于哈希表的性能至關重要，一個好的哈希函數應該能夠將鍵均勻地分布在整個哈希表中，從而減少沖突的發生。

3.2 Python字典的哈希表實現

Python中的字典是通過一個名為PyDictObject的結構體實現的。該結構體定義在Include/cpython/dictobject.h文件中：

typedef struct {
    PyObject_HEAD
    Py_ssize_t ma_used;  // 已使用的條目數
    Py_ssize_t ma_version_tag;  // 版本標簽，用于快速失敗
    PyDictKeysObject *ma_keys;  // 鍵對象
    PyObject **ma_values;  // 值數組
} PyDictObject;

PyDictObject結構體包含以下幾個重要字段：

• ma_used：表示字典中已使用的條目數。
• ma_version_tag：用于快速失敗的版本標簽。
• ma_keys：指向鍵對象的指針。
• ma_values：指向值數組的指針。

3.3 哈希表的存儲結構

Python的哈希表是通過一個名為PyDictKeysObject的結構體實現的。該結構體定義在Include/cpython/dictobject.h文件中：

typedef struct {
    Py_ssize_t dk_refcnt;  // 引用計數
    Py_ssize_t dk_size;  // 哈希表的大小
    Py_ssize_t dk_usable;  // 可用的條目數
    Py_ssize_t dk_nentries;  // 已使用的條目數
    uint8_t dk_indices[];  // 索引數組
} PyDictKeysObject;

PyDictKeysObject結構體包含以下幾個重要字段：

• dk_refcnt：引用計數，用于內存管理。
• dk_size：哈希表的大小。
• dk_usable：可用的條目數。
• dk_nentries：已使用的條目數。
• dk_indices：索引數組，用于存儲哈希表的索引。

3.4 哈希表的索引數組

哈希表的索引數組dk_indices是一個動態數組，它存儲了哈希表的索引。每個索引對應一個哈希表的槽位，槽位中存儲了鍵值對的索引。如果槽位為空，則存儲一個特殊的值DKIX_EMPTY（通常為-1）。

3.5 哈希表的鍵值對存儲

哈希表的鍵值對存儲在ma_values數組中。每個鍵值對由一個PyObject指針和一個PyObject指針組成，分別指向鍵和值。

4. 哈希函數與沖突解決

哈希函數是哈希表的核心，它將鍵轉換為一個整數索引。Python中的哈希函數是通過PyObject_Hash函數實現的，該函數定義在Objects/object.c文件中：

Py_hash_t
PyObject_Hash(PyObject *v)
{
    PyTypeObject *tp = Py_TYPE(v);
    if (tp->tp_hash != NULL)
        return (*tp->tp_hash)(v);
    if (tp->tp_dict == NULL) {
        if (PyType_Ready(tp) < 0)
            return -1;
        if (tp->tp_hash != NULL)
            return (*tp->tp_hash)(v);
    }
    return PyObject_HashNotImplemented(v);
}

PyObject_Hash函數首先檢查對象的類型是否定義了哈希函數，如果定義了則調用該哈希函數，否則返回PyObject_HashNotImplemented。

4.1 哈希沖突

哈希沖突是指兩個不同的鍵通過哈希函數計算得到相同的索引。哈希沖突是不可避免的，因為哈希函數的輸出空間通常小于鍵的空間。Python中的哈希表通過開放尋址法（Open Addressing）來解決哈希沖突。

4.2 開放尋址法

開放尋址法是一種解決哈希沖突的方法，當發生沖突時，它會嘗試在哈希表中尋找下一個可用的槽位。Python中的開放尋址法是通過線性探測（Linear Probing）實現的。

線性探測的基本思想是，當發生沖突時，依次檢查下一個槽位，直到找到一個可用的槽位為止。Python中的線性探測是通過lookdict函數實現的，該函數定義在Objects/dictobject.c文件中：

static Py_ssize_t
lookdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject ***value_addr)
{
    PyDictKeysObject *dk = mp->ma_keys;
    Py_ssize_t i, perturb;
    PyObject *k;
    Py_ssize_t mask = DK_SIZE(dk) - 1;
    i = hash & mask;
    for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
        Py_ssize_t ix = dk->dk_indices[i];
        if (ix == DKIX_EMPTY) {
            *value_addr = NULL;
            return i;
        }
        if (ix >= 0) {
            k = DK_ENTRIES(dk)[ix].me_key;
            if (k == key || (dk->dk_lookup == lookdict && PyObject_RichCompareBool(k, key, Py_EQ))) {
                *value_addr = &DK_ENTRIES(dk)[ix].me_value;
                return i;
            }
        }
        i = (i << 2) + i + perturb + 1;
        i &= mask;
    }
}

lookdict函數首先計算鍵的哈希值，然后通過哈希值計算索引。如果索引對應的槽位為空，則返回該槽位的索引。如果槽位不為空，則檢查鍵是否匹配，如果匹配則返回該槽位的索引，否則繼續探測下一個槽位。

4.3 哈希表的擴容

當哈希表中的條目數超過一定閾值時，哈希表需要進行擴容。Python中的哈希表擴容是通過dictresize函數實現的，該函數定義在Objects/dictobject.c文件中：

static int
dictresize(PyDictObject *mp, Py_ssize_t minused)
{
    PyDictKeysObject *oldkeys = mp->ma_keys;
    Py_ssize_t oldsize = DK_SIZE(oldkeys);
    Py_ssize_t newsize = PyDict_MINSIZE;
    while (newsize <= minused && newsize > 0)
        newsize <<= 1;
    if (newsize <= 0)
        return -1;
    PyDictKeysObject *newkeys = new_keys_object(newsize);
    if (newkeys == NULL)
        return -1;
    mp->ma_keys = newkeys;
    mp->ma_values = NULL;
    mp->ma_used = 0;
    mp->ma_version_tag = DICT_NEXT_VERSION();
    if (oldkeys->dk_nentries > 0) {
        Py_ssize_t i;
        for (i = 0; i < oldsize; i++) {
            Py_ssize_t ix = oldkeys->dk_indices[i];
            if (ix >= 0) {
                PyObject *key = DK_ENTRIES(oldkeys)[ix].me_key;
                PyObject *value = DK_ENTRIES(oldkeys)[ix].me_value;
                Py_INCREF(key);
                Py_INCREF(value);
                if (insertdict(mp, key, value, oldkeys->dk_indices[i]) < 0) {
                    Py_DECREF(key);
                    Py_DECREF(value);
                    return -1;
                }
            }
        }
    }
    Py_DECREF(oldkeys);
    return 0;
}

dictresize函數首先計算新的哈希表大小，然后創建一個新的哈希表，并將舊的哈希表中的條目插入到新的哈希表中。最后，釋放舊的哈希表。

5. 字典的內存管理

Python中的字典是通過引用計數進行內存管理的。每個字典對象都有一個引用計數，當引用計數為0時，字典對象會被釋放。

5.1 引用計數

引用計數是Python內存管理的核心機制之一。每個Python對象都有一個引用計數，表示有多少個指針指向該對象。當引用計數為0時，對象會被釋放。

字典對象的引用計數是通過Py_INCREF和Py_DECREF宏進行管理的。Py_INCREF宏用于增加引用計數，Py_DECREF宏用于減少引用計數。

5.2 字典的內存釋放

當字典對象的引用計數為0時，字典對象會被釋放。字典對象的內存釋放是通過dict_dealloc函數實現的，該函數定義在Objects/dictobject.c文件中：

static void
dict_dealloc(PyDictObject *mp)
{
    PyDictKeysObject *keys = mp->ma_keys;
    PyObject **values = mp->ma_values;
    Py_ssize_t i, n;
    PyObject_GC_UnTrack(mp);
    if (values != NULL) {
        n = DK_SIZE(keys);
        for (i = 0; i < n; i++) {
            Py_XDECREF(values[i]);
        }
        PyMem_FREE(values);
    }
    if (keys != NULL) {
        n = DK_SIZE(keys);
        for (i = 0; i < n; i++) {
            Py_XDECREF(DK_ENTRIES(keys)[i].me_key);
            Py_XDECREF(DK_ENTRIES(keys)[i].me_value);
        }
        PyMem_FREE(keys);
    }
    Py_TYPE(mp)->tp_free((PyObject *)mp);
}

dict_dealloc函數首先釋放字典對象的值數組，然后釋放字典對象的鍵數組，最后釋放字典對象本身。

6. 字典的性能優化

Python中的字典在實現上進行了一些性能優化，以提高字典的操作效率。

6.1 快速失敗機制

Python中的字典通過ma_version_tag字段實現了快速失敗機制?？焖偈C制是指在字典發生修改時，會更新ma_version_tag字段，從而使得在迭代字典時能夠快速檢測到字典的修改。

6.2 小字典優化

Python中的字典在實現上進行了一些小字典優化。當字典的條目數較少時，字典會使用一種更緊湊的存儲結構，以減少內存的使用。

6.3 哈希表的預分配

Python中的字典在創建時會預分配一定大小的哈希表，以減少哈希表的擴容次數。預分配的大小是根據字典的條目數進行計算的。

7. 字典的源碼分析

7.1 字典的創建

字典的創建是通過PyDict_New函數實現的，該函數定義在Objects/dictobject.c文件中：

PyObject *
PyDict_New(void)
{
    PyDictObject *mp;
    if (numfree) {
        mp = free_list[--numfree];
        _Py_NewReference((PyObject *)mp);
    } else {
        mp = PyObject_GC_New(PyDictObject, &PyDict_Type);
        if (mp == NULL)
            return NULL;
    }
    mp->ma_used = 0;
    mp->ma_version_tag = DICT_NEXT_VERSION();
    mp->ma_keys = new_keys_object(PyDict_MINSIZE);
    if (mp->ma_keys == NULL) {
        Py_DECREF(mp);
        return NULL;
    }
    mp->ma_values = NULL;
    return (PyObject *)mp;
}

PyDict_New函數首先檢查是否有空閑的字典對象，如果有則從空閑列表中獲取一個字典對象，否則創建一個新的字典對象。然后初始化字典對象的字段，并創建一個新的哈希表。

7.2 字典的插入

字典的插入是通過PyDict_SetItem函數實現的，該函數定義在Objects/dictobject.c文件中：

int
PyDict_SetItem(PyObject *op, PyObject *key, PyObject *value)
{
    PyDictObject *mp;
    Py_hash_t hash;
    if (!PyDict_Check(op)) {
        PyErr_BadInternalCall();
        return -1;
    }
    mp = (PyDictObject *)op;
    if (value == NULL) {
        value = Py_None;
    }
    hash = PyObject_Hash(key);
    if (hash == -1)
        return -1;
    return insertdict(mp, key, value, hash);
}

PyDict_SetItem函數首先檢查字典對象是否有效，然后計算鍵的哈希值，最后調用insertdict函數插入鍵值對。

7.3 字典的查找

字典的查找是通過PyDict_GetItem函數實現的，該函數定義在Objects/dictobject.c文件中：

PyObject *
PyDict_GetItem(PyObject *op, PyObject *key)
{
    PyDictObject *mp;
    Py_hash_t hash;
    PyObject **value_addr;
    if (!PyDict_Check(op)) {
        PyErr_BadInternalCall();
        return NULL;
    }
    mp = (PyDictObject *)op;
    hash = PyObject_Hash(key);
    if (hash == -1)
        return NULL;
    if (lookdict(mp, key, hash, &value_addr) < 0)
        return NULL;
    return *value_addr;
}

PyDict_GetItem函數首先檢查字典對象是否有效，然后計算鍵的哈希值，最后調用lookdict函數查找鍵值對。

7.4 字典的刪除

字典的刪除是通過PyDict_DelItem函數實現的，該函數定義在Objects/dictobject.c文件中：

int
PyDict_DelItem(PyObject *op, PyObject *key)
{
    PyDictObject *mp;
    Py_hash_t hash;
    if (!PyDict_Check(op)) {
        PyErr_BadInternalCall();
        return -1;
    }
    mp = (PyDictObject *)op;
    hash = PyObject_Hash(key);
    if (hash == -1)
        return -1;
    return dict_delitem(mp, key, hash);
}

PyDict_DelItem函數首先檢查字典對象是否有效，然后計算鍵的哈希值，最后調用dict_delitem函數刪除鍵值對。

8. 總結

本文詳細分析了Python中dict類型的源碼實現，探討了其內部結構、哈希表的工作原理、沖突解決策略、內存管理以及性能優化等方面。通過深入理解字典的源碼實現，我們可以更好地掌握Python的內部機制，從而編寫出更高效、更可靠的代碼。

字典作為Python中最常用的數據結構之一，其高效的實現對于Python的性能至關重要。通過本文的分析，我們可以看到Python在字典的實現上進行了許多優化，包括快速失敗機制、小字典優化、哈希表的預分配等。這些優化使得Python的字典在實際應用中表現出色，能夠滿足大多數場景的需求。

希望本文能夠幫助讀者更好地理解Python中字典的實現原理，并在實際編程中靈活運用這些知識。