代码之家 › 专栏 › 技术社区 › kedenk

Python:如果key不在字典中,为什么不调用?

built-in hashmap python-3.x python

2

kedenk · 技术社区 · 7 年前

目前,我对Python的内置类型做了一些研究。我搞不清调用什么方法来检查字典中是否有密钥。例如,如果我检查 int 在字典里 __eq__() 方法仅在以下情况下在后台调用字典.keys包含它。如果没有 __情商 未调用。

下面是一个代码示例:

dict = {
  1: "Hello",
  2: "World", 
  4: "Foo"
}

assert 1 in dict.keys() # the __eq__() method of int is invoked
assert not(3 in dict.keys()) # no __eq__() method of int is invoked

我知道,字典里有一个哈希(key)、key和value的元组。但我有点困惑,为什么 __情商 在第二个断言中未调用。

为了测试我从 内景 并设置一些断点。这是我的习惯摘录 内景 班级:

tint(int):
    def __new__(cls, value, *args, **kw):
        return super(tint, cls).__new__(cls, value)

    def __init__(self, value):
        super().__init__()

    def __eq__(self, other):
        return super().__eq__(other) # with breakpoints

    def __ne__(self, other):
        return super().__ne__(other) # with breakpoints

    def __hash__(self):
        return tint(super().__hash__()) # with breakpoints

我在Ubuntu 18.04.1lts上使用Python版本3.6.5。

1 回复 | 直到 7 年前

1

4

Amadan 7 年前

要在dict中查找密钥,首先要通过散列来查找候选项,然后再查看它是fluke(尽管散列相同,但对象不同)还是真正想要的密钥。所以如果你在这个杂凑下找不到任何东西,那就没什么好对付的了。

想象一下你在聚会上找一个熟人,却不知道她在不在。她有一头红头发。通常,你会寻找红发女孩,然后去面对他们,看看是否真的是她。如果派对上还没有红发女郎来,那就没有必要检查每一个人。(假设你的朋友不从事日常染色工作。)

编辑:CPython将dict存储在一个数组中,其中主数组的位置由散列决定;如果该位置被占用,它将以数学上确定的方式跳转到下一个候选位置。由于填充的位置可以因此保存“正确的”散列或不相关的散列,当查找散列时,CPython将从主位置开始,然后继续比较散列,直到它确定不可能存在搜索到的密钥。散列现在是普通的低级整数,而不是Python对象,这解释了为什么散列比较不会触发 __eq__ .

注意源代码中的一个可爱的优化:对于每个候选对象,CPython首先检查对象标识;然后才检查散列是否仍然相同,如果仍然相同,则转到慢速检查以查看对象是否相等(使用 PyObject_RichCompareBool ,最终 __情商__ ). 为什么这很重要?看这里:

class Foo:
    def __eq__(self, other):
        return False             # This shouldn't match...
    def __hash__(self):
        return 7

f = Foo()
d = { f: "Yes!" }
print(d[f])                      # ...and yet it does! :)
# => "Yes!"