【python源码探究】dict的key不能是list-阿里云开发者社区

开发者社区> 开发与运维> 正文

【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对象的类型名,这样才可能打印出完整的抛错信息:

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

虽然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
本文作者:枉信焕
本文来自:“掘金”,了解相关信息可以关注“掘金”

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

其他文章