密钥的地址彼此存储得非常远

Question

我想探索哈希表,

In [1]: book = {"apple":0.67, "milk":1.49, "avocado":1.49, "python":2}   
In [5]: [hex(id(key)) for key in book]                                                                            
Out[5]: ['0x10ffffc70', '0x10ffffab0', '0x10ffffe68', '0x10ee1cca8']

地址告诉我们密钥彼此相距很远,特别是关键的"python",
我以为它们彼此相邻.

怎么会发生这种情况？它是否以高性能运行？

Answer 1

有两种方法我们可以解释你的困惑:要么你希望它id()是键的哈希函数,要么你期望键被重新定位到哈希表,因为在CPython中id()值是一个内存位置,id()值将是说一下哈希表的大小.我们可以通过谈论Python的字典实现以及Python如何处理一般的对象来解决这两个问题.

Python字典被实现为哈希表,这是一个有限大小的表.为了存储密钥,哈希函数生成一个整数(相同值的相同整数),并使用模数函数将密钥存储在基于该数字的槽中:

slot = hash(key) % len(table)

这可能会导致冲突,因此从散列函数中选择大范围的数字将有助于减少发生此类冲突的可能性.无论如何你仍然需要处理碰撞,但是你想要最小化碰撞.

Python在这里不使用id()函数作为哈希函数,因为这不会为相等的值产生相同的哈希值!如果没有产生对相等的值相同的散列,那么你可以不使用多个"hello world"字符串,以找到合适的插槽的手段再次,作为dictionary["hello world"] = "value"然后"hello world" in dictionary将产生不同的id()值,从而散列到不同的插槽,你不会,具体字符串值已被用作键.

相反,期望对象实现一个__hash__方法,您可以看到该方法为具有该hash()函数的各种对象生成的内容.

因为存储在字典中的键必须保持不变,所以Python不允许您将可变类型存储在字典中.否则,如果你可以改变它们的值,它们将不再等于具有旧值和羞耻哈希的另一个这样的对象,并且你不会在它们的新哈希将映射到的槽中找到它们.

请注意,Python将所有对象放在动态堆中,并使用各处的引用来关联对象.字典包含对键和值的引用; 将密钥放入字典不会将密钥重新定位到内存id()中,密钥的密钥也不会改变.如果重新定位了密钥,则会id()违反对该函数的要求,文档说明:这是一个整数,对于该对象的生命周期,该整数保证是唯一且恒定的.

至于那些冲突:Python通过寻找具有固定公式的新槽来处理冲突,在可预测但伪随机系列的槽号中找到一个空槽; 如果您想了解详细信息,请参阅dictobject.c源代码注释.随着表填满,Python将动态增长表以适应更多元素,因此总会有空插槽.