【源码小读】为何python字典的key不能是list类型

一条面试题

本文源自一条最常见的python面试题：

问：list对象能不能做dict的key？tuple呢？

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

咱们做个实验，从dict的赋值代码抛错来感受一下上面的答案：

>>> d={'a':1}
>>> 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上的区别：

>>> list.__dict__
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=[1,2,3]
>>> 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源码，代码如下：

// 文件位置：Modules/_ctypes/_ctypes.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对象的类型名，这样才可能打印出完整的抛错信息：

TypeError: unhashable type: ‘list’

至此，我们知道了PyObject_HashNotImplemented()函数就是dict在赋值操作时，key为Mutable类型导致抛错的源头，接着只要跟踪这个函数在哪里被调用就可以知道dict具体判断key是否hashable的逻辑了。实际上，函数名PyObject_HashNotImplemented给了很多信息，隐约告诉我们，答案很可能就是一开始的推测——__hash__没有实现。

根据调用链逐步往上摸

顺腾摸瓜，寻找``PyObject_HashNotImplemented()`函数被调用的地方，源码中有很多地方都有调用，但这个函数引起了我的注意，它的实现中带有对类型的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);
    /* 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实现😂，代码如下：

// 文件位置：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;
    }
    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()究竟会在哪里被调用吧🤔。

// 文件位置：Objects/dictobject.c
// 为了阅读的方便，下面的变量、函数摆放的前后顺序做了调整

// 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下发现了这样的注释说明：

…The equivalent C API call to dict.__setitem__(obj, k, v) is PyDict_SetItem(obj, k, v). This illustrates how subclasses in C call the base class’s methods, since there is no equivalent of super() in the C API.

虽然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函数。代码如下，结果符合预期：

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

PyTypeObject PyList_Type = {
    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函数外还有无更多区别。

【TODO】确认Mutable与Immutable的区别细节？为什么会有这样的区别？

参考资料

https://wiki.python.org/moin/DictionaryKeys