【python源碼探究】dict的key不能是list

雲栖号資訊：【點選檢視更多行業資訊
】

在這裡您可以找到不同行業的第一手的上雲資訊，還在等什麼，快來！

一條面試題

本文源自一條最常見的python面試題：

問：list對象能不能做dict的key？tuple呢？

答：不能，因為list是Mutable類型，不能作為dict的key。而tuple是Immutable類型，可以作為dict的key。

咱們做個實驗，從dict的指派代碼抛錯來感受一下上面的答案：

>>> l=[1,2,3]
>>> d[l]=123
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

抛錯已經說明白了，因為list是unhashable類型，是以能否hashable就是關鍵點，再來看list與tuple之間在hashable上的差別：

mappingproxy({'__repr__': <slot wrapper '__repr__' of 'list' objects>, '__hash__': None, ...})
>>> tuple.__dict__
mappingproxy({'__repr__': <slot wrapper '__repr__' of 'tuple' objects>, '__hash__': <slot wrapper '__hash__' of 'tuple' objects>, ...})

這裡注意到魔法方法__hash__，在list類型中__hash__實作為None，而tuple持有對應的實作。我們大膽猜測一下，tuple之是以hashable是因為實作了__hash__，再做個驗證：

>>> l.__hash__()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'NoneType' object is not callable
>>> t=(1,2,3)
>>> t.__hash__()  # 從輸出的形式來看，這很可能就是對象的hash值
2528502973977326415

這樣子的黑盒試驗終究是沒辦法讓人放心，難道真的隻是因為__hash__方法的實作與否嗎？嘗試看list.__hash__和tuple.__hash__的源碼，由于函數是由python解釋器直接實作，是以無法得到更進一步的結論。為了整明白這個問題，這裡拿官網下載下傳python 3.8.2 的CPython源碼繼續深入探究。我們有兩種思路：

知道dict的指派是調用魔法方法__setitem__，追溯該方法一層一層往下看，尋找出關鍵判斷hashable的條件
按照dict指派的抛錯文案進行全局搜尋，直接定位相關代碼

定位抛錯文案

顯然第二種反推思路效率會更高一些（實際上第一種思路是不通的，因為dict.__setitem__下面就是C源碼，在python層沒法得到更多資訊），通過全局搜尋unhashable type這個文案定位到兩處python的C源碼，代碼如下：

static Py_hash_t PyCData_nohash(PyObject *self)
{
    PyErr_SetString(PyExc_TypeError, "unhashable type");
    return -1;
}

// ******************************分割線****************************** //

// 檔案位置：Objects/object.c
Py_hash_t PyObject_HashNotImplemented(PyObject *v)
{
    PyErr_Format(PyExc_TypeError, "unhashable type: '%.200s'",
                 Py_TYPE(v)->tp_name);
    return -1;
}

很容易就可以判斷源代碼是Objects/object.c檔案的實作，因為看unhashable type文案後面還跟有python對象的類型名，這樣才可能列印出完整的抛錯資訊：

至此，我們知道了PyObject_HashNotImplemented()函數就是dict在指派操作時，key為Mutable類型導緻抛錯的源頭，接着隻要跟蹤這個函數在哪裡被調用就可以知道dict具體判斷key是否hashable的邏輯了。實際上，函數名PyObject_HashNotImplemented給了很多資訊，隐約告訴我們，答案很可能就是一開始的推測——__hash__沒有實作。

根據調用鍊逐漸往上摸

順騰摸瓜，尋找

`PyObject_HashNotImplemented()

函數被調用的地方，源碼中有很多地方都有調用，但這個函數引起了我的注意，它的實作中帶有對類型的hash函數存在與否的判斷邏輯，代碼如下：

Py_hash_t PyObject_Hash(PyObject *v)
{
    PyTypeObject *tp = Py_TYPE(v);
    if (tp->tp_hash != NULL)
        return (*tp->tp_hash)(v);
    /* To keep to the general practice that inheriting
     * solely from object in C code should work without
     * an explicit call to PyType_Ready, we implicitly call
     * PyType_Ready here and then check the tp_hash slot again
     */
    if (tp->tp_dict == NULL) {
        if (PyType_Ready(tp) < 0)
            return -1;
        if (tp->tp_hash != NULL)
            return (*tp->tp_hash)(v);
    }
    
    // 備注：如果tp_hash為NULL，就會調用PyObject_HashNotImplemented導緻抛錯
    /* Otherwise, the object can't be hashed */
    return PyObject_HashNotImplemented(v);
}

ok，咱們繼續尋找PyObject_Hash()被調用的地方，感覺離真相已經不遠了，同樣，整個源碼中存在大量對它的調用，有很多C檔案從名字上一眼就能識别出跟dict類型不相關，最終這個特殊的C檔案名和函數名吸引了我，簡直就是明明白白告訴我，這裡就是dict的C實作😂，代碼如下：

int PyDict_SetItem(PyObject *op, PyObject *key, PyObject *value)
{
    PyDictObject *mp;
    Py_hash_t hash;
    if (!PyDict_Check(op)) {
        PyErr_BadInternalCall();
        return -1;
    }
    assert(key);
    assert(value);
    mp = (PyDictObject *)op;
    if (!PyUnicode_CheckExact(key) ||
        (hash = ((PyASCIIObject *) key)->hash) == -1)
    {
        // 備注：擷取key的hash函數，如果hash函數為NULL（參考 PyObject_Hash 的實作），則傳回 -1（同時抛出類型錯誤）
        hash = PyObject_Hash(key);
        if (hash == -1)
            return -1;
    }

    if (mp->ma_keys == Py_EMPTY_KEYS) {
        return insert_to_emptydict(mp, key, hash, value);
    }
    /* insertdict() handles any resizing that might be necessary */
    return insertdict(mp, key, hash, value);
}

其實到了這裡已經算真相大白了，已經找到dict的set函數C實作了，裡面有判斷key是否可hash的邏輯，如果key不可hash則向上傳回-1。不過本着打破砂鍋問到底的心态，我們來看看這個PyDict_SetItem()究竟會在哪裡被調用吧🤔。

// 為了閱讀的友善，下面的變量、函數擺放的前後順序做了調整

// 1.跟蹤PyDict_SetItem，這裡封裝dict指派與删值的，對外暴露單一入口
static int dict_ass_sub(PyDictObject *mp, PyObject *v, PyObject *w)
{
    if (w == NULL)
        return PyDict_DelItem((PyObject *)mp, v);
    else
        return PyDict_SetItem((PyObject *)mp, v, w);
}

// 2.跟蹤dict_ass_sub，這是儲存dict函數指針的數組
static PyMappingMethods dict_as_mapping = {
    (lenfunc)dict_length, /*mp_length*/
    (binaryfunc)dict_subscript, /*mp_subscript*/
    (objobjargproc)dict_ass_sub, /*mp_ass_subscript*/
};

// 3.跟蹤dict_as_mapping，最終發現PyDict_Type裡存了這個數組變量
PyTypeObject PyDict_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "dict",
    // ...
    &dict_as_mapping,                           /* tp_as_mapping */
    PyObject_HashNotImplemented,                /* tp_hash */
    // ...
    dict_new,                                   /* tp_new */
    PyObject_GC_Del,                            /* tp_free */
};

// 4.順帶再确認PyDict_Type被調用的地方，dict_new函數應該就是python dict配置設定記憶體時的調用，至此整個追溯過程就結束了
static PyObject *
dict_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
{
    PyObject *self;
    PyDictObject *d;

    // 為dict類型配置設定記憶體空間
    assert(type != NULL && type->tp_alloc != NULL);
    self = type->tp_alloc(type, 0);
    if (self == NULL)
        return NULL;
    d = (PyDictObject *)self;

    /* The object has been implicitly tracked by tp_alloc */
    if (type == &PyDict_Type)
        _PyObject_GC_UNTRACK(d);

    d->ma_used = 0;
    d->ma_version_tag = DICT_NEXT_VERSION();
    d->ma_keys = new_keys_object(PyDict_MINSIZE);
    if (d->ma_keys == NULL) {
        Py_DECREF(self);
        return NULL;
    }
    ASSERT_CONSISTENT(d);
    return self;
}

另外再找了一下，在檔案Objects/odictobject.c下發現了這樣的注釋說明：

雖然odictobject.c與dictobject.c是兩種不同用處的dict的實作，但講道理兩種實作對外的api應該接近一緻，是以上面的注釋側面說明了dict的指派函數就是PyDict_SetItem。

推斷驗證

上面的過程讓我們明确了在dict指派key時會判斷是否實作hash函數，我們還可以在list和tuple的角度驗證一下。list是Mutable類型，它不實作hash函數，tp_hash指向函數PyObject_HashNotImplemented；tuple是Immutable類型，它實作了hash函數，tp_hash指向對應的hash函數。代碼如下，結果符合預期：

PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "tuple",
    // ...
    (hashfunc)tuplehash,                        /* tp_hash */
    // ...
};

PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "list",
    // ...
    PyObject_HashNotImplemented,                /* tp_hash */
    // ...
};

總結

咱們追了好陣子源碼，該總結一下了。

原問題：為什麼dict的key不能是list？

引申問題：為什麼dict的key不能是可變類型，可變與不可變類型的差別是啥？

結論：通過追溯CPython源碼，發現對dict指派時會調用PyDict_SetItem檢查key對象是否實作hash函數，如果沒實作hash函數則抛錯并提示類型unhashable（通過函數指針是否為NULL來判斷是否實作hash函數）。這裡還引出了Mutable與Immutable類型，但本文暫未确定兩者除了hash函數外還有無更多差別。

【雲栖号線上課堂】每天都有産品技術專家分享！

課程位址：
https://yqh.aliyun.com/live
立即加入社群，與專家面對面，及時了解課程最新動态！

【雲栖号線上課堂社群】
https://c.tb.cn/F3.Z8gvnK

原文釋出時間：2020-04-21

本文作者：枉信煥

本文來自：“

掘金

”，了解相關資訊可以關注“掘金”

【python源碼探究】dict的key不能是list

繼續閱讀

來自python的【條件控制/語句循環/break/continue/else/pass】一、條件控制二、語句循環

無法解析的外部符号 wmain，該符号在函數 "void cdecl mainCRTStartupHelper(struct HINSTANCE *,unsigned short con......

TestLink導出用例轉換工具(XML2Excel)

YAML簡介和PyYAML安全操作YAML支援的類型YAML的優點：yaml的基本文法python操作

Small tricks

libsvm for python 安裝

學習軟體測試基礎測試第七天

Zeppelin 配置通路 REST APIApache Zeppelin Configuration REST API

【Torch】最簡潔logging使用指南

27. Remove Element(清單)題目代碼

Cloud Studio初體驗

使用 ctypes 進行 Python 和 C 的混合程式設計

【python】【資料處理】畫多元資料分布圖

【python】netconf協定對接管理裝置

「Python 網絡自動化」NETCONF —— Python 使用 NETCONF 管理配置 H3C 網絡裝置

在python中建立excel并寫入