dict工作的查找功能如何

Question

众所周知，可变类型不能是字典的关键。

但是，如果您使用的是C ，则常规地图让您使用向量和数组作为地图键，因为将常规地图实现为树。

但是，C 还可以让您使用数组作为无序地图的钥匙，它在精神上更接近Python词典，因为它只要您提供类型的哈希功能，它就不知道如何提供键到哈希。

所以我想知道只要您提供__hash__方法，Python是否会让您做同样的事情。

In [1]: b = {}
In [2]: class hlist(list):
   ...:     def __hash__(self):
   ...:         temp = []
   ...:         for item in self:
   ...:             print item
   ...:             temp.append(item)
   ...:         return hash(tuple(temp))
   ...:
In [3]: a = hlist([1,2,3,4])
In [4]: c = hlist([1,2,3,4])
In [5]: b[a] = "car"
1
2
3
4
In [6]: b[c]
1
2
3
4
Out[6]: 'car'
In [7]: a.append(5)
In [8]: b[c]
1
2
3
4
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
<ipython-input-8-013e994efe63> in <module>()
----> 1 b[c]
KeyError: [1, 2, 3, 4]

我在__hash__内添加了print，以找出正在调用的函数以及何时调用函数。

就在抛出KeyError之前，打印了c的内容，表明c只是hash。现在不应该仅检查一个键是否的哈希值之一？为什么会丢下密钥错误？

如果它也是一个一个一个键，以弄清楚其中一个键是否与查询不应工作的查询相同的哈希值？

In [11]: b[hlist([1,2,3,4,5])]
1
2
3
4
5
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
<ipython-input-11-09593553a69b> in <module>()
----> 1 b[hlist([1,2,3,4,5])]
KeyError: [1, 2, 3, 4, 5]

如果您确定具有与CPP相似的半稳健哈希功能的可变键？

Answer 1

dict如何存储在内存中？(简化版本(

• 对于dict中的每个键，计算hash，然后将密钥和值存储在由哈希定义的位置
定义的位置
• 如果多个键具有相同的哈希(或指向同一存储目的地的哈希(，则该位置中将有一个键值对列表

如何从内存中读取dict值？(简化版本(

• 计算键的hash，并根据哈希>计算内存中的位置
• 键值对从该位置逐一读取，并与使用==操作员进行比较

结论

要在dict中找到键(称为 key1(，dict应包含一个键(调用 key2(， hash(key1) == hash(key2) and key1 == key2。

那么，为什么Mutable键是个坏主意？

因为当键写入dict时计算hash(key)，并且在该时间点匹配key的值，但是如果key是可突变的，并且在dict中进行突变，则不会重新计算hash(key)，因此，将不再有可能找到钥匙。