为什么dict.items()能快速查找？

Question

假设我们有一个字典 d，它是这样定义的：

d = {i:i for i in range(1,1000001)}

然后我们把 d.items() 存储到 x 里。所以，x 是一个包含每个 d 元素的键值对的元组集合。我用相同的元组做了一个列表，定义如下：

l = [(i, i) for i in range(1,1000001)]

现在，我比较了执行 (1000001, 1000001) in x 和 (1000001, 1000001) in l 所花的时间。时间差异非常明显。我猜这是因为 x 有类似集合的特性，并且在元组上实现了哈希表，因为元组是可以哈希的。

但是，包含列表的元组是不可哈希的，所以我用这个字典尝试了同样的事情：

d = {i:[i,i+1] for i in range(1,1000001)}

结果和我预期的不一样，它仍然能快速查找。

这是怎么回事呢？

附注：这是我用来比较时间的代码

import time

def for_dict_items(n):
    #d = {i:i for i in range(1, n+1)}
    d = {i:[i, i+1] for i in range(1, n+1)}
    di = d.items()
    st = time.time()
    x = (n, [n, n+1]) in di
    et = time.time()
    return (et - st)


def for_tuples_list(n):
    #l = [(i, i) for i in range(1, n+1)]
    l = [(i,[i, i+1]) for i in range(1, n+1)]
    st = time.time()
    x = (n, [n, n+1]) in l
    et = time.time()
    return (et - st)


k = 1000000

t1 = for_dict_items(k)
t2 = for_tuples_list(k)

print(t1, t2, t2/t1, sep = "\n")

Answer 1

因为字典（dict）是非常重要的核心对象，所以它是用C语言实现的，dict_values、dict_keys和dict_items也是如此。下面是CPython中dictitems_contains的实现：

static int
dictitems_contains(PyObject *self, PyObject *obj)
{
    _PyDictViewObject *dv = (_PyDictViewObject *)self;
    int result;
    PyObject *key, *value, *found;
    if (dv->dv_dict == NULL)
        return 0;
    if (!PyTuple_Check(obj) || PyTuple_GET_SIZE(obj) != 2)
        return 0;
    key = PyTuple_GET_ITEM(obj, 0);
    value = PyTuple_GET_ITEM(obj, 1);
    result = PyDict_GetItemRef((PyObject *)dv->dv_dict, key, &found);
    if (result == 1) {
        result = PyObject_RichCompareBool(found, value, Py_EQ);
        Py_DECREF(found);
    }
    return result;
}

如果你不懂C语言，下面是它的工作原理：

• 首先检查视图是否正确，也就是说，它是否有指向底层字典的引用（如果没有，就返回False）。
• 检查输入：如果输入不是一个二元组，就返回False。
• 在底层字典中查找一个键。
• 如果找到了，就检查值是否匹配。如果匹配，就返回True。
• 否则，返回False。

这里的关键是dict.items返回的不是一个列表，而是一个特殊的dict_items 视图。这里的视图意味着它并不是一个副本，而只是一个代理，用来以某种特定的方式获取底层的项目。dict_keys和dict_values也是这样，你可以在这个优秀的文档页面中了解更多相关内容。

请注意，这个内容是针对CPython实现的，其他实现可能会有所不同。