您现在的位置是：首页 > 文章详情

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

日期：2020-04-20点击：451收藏

云栖号资讯：【点击查看更多行业资讯】
在这里您可以找到不同行业的第一手的上云资讯，还在等什么，快来！

一条面试题

本文源自一条最常见的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函数外还有无更多区别。