云栖号资讯：【点击查看更多行业资讯】
在这里您可以找到不同行业的第一手的上云资讯，还在等什么，快来！
一条面试题
本文源自一条最常见的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对象的类型名，这样才可能打印出完整的抛错信息：
![1]( "1")
至此，我们知道了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下发现了这样的注释说明：
![2]( "2")
虽然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
本文作者：枉信焕
本文来自：“掘金”，了解相关信息可以关注“掘金”
