在Python字典中计数碰撞

Question

这是我第一次在这里发帖，希望我问的问题方式是对的。

我想知道，在给一个Python字典添加元素后，能不能让Python告诉我，添加这个元素时是否发生了冲突？（还有在找到放置这个元素的位置之前，冲突解决策略探查了多少个位置？）

我的问题是：我在一个更大的项目中使用字典，经过详细的性能分析，我发现代码中最慢的部分是处理一个用字典实现的稀疏距离矩阵。

我使用的键是Python对象的ID，这些ID是唯一的整数，所以我知道它们的哈希值都是不同的。但把它们放进字典里，原则上还是可能会发生冲突。我不认为字典冲突是导致我的程序变慢的原因，但我想排除这个可能性。

比如，给定以下字典：

d = {}
for i in xrange(15000):
    d[random.randint(15000000, 18000000)] = 0

你能让Python告诉你在创建它时发生了多少次冲突吗？

我的实际代码和应用程序纠缠在一起，但上面的代码创建了一个与我正在使用的字典非常相似的字典。

再说一遍：我不认为冲突是导致我的代码变慢的原因，我只是想通过证明我的字典没有很多冲突来排除这个可能性。

谢谢你的帮助。

编辑：一些代码来实现@Winston Ewert的解决方案：

n = 1500
global collision_count
collision_count = 0

class Foo():

    def __eq__(self, other):
        global collision_count
        collision_count += 1
        return id(self) == id(other)

    def __hash__(self):
        #return id(self) # @John Machin: yes, I know!
        return 1

objects = [Foo() for i in xrange(n)]

d = {}
for o in objects:
    d[o] = 1

print collision_count

注意，当你在一个类中定义__eq__时，如果你没有同时定义__hash__函数，Python会给你一个TypeError: unhashable instance的错误。

它的运行结果并不是我预期的那样。如果你让__hash__函数返回1，那么你会得到很多冲突，正如预期的那样（在我的系统上，n=1500时发生了1125560次冲突）。但如果返回id(self)，那么就没有冲突了。

有人知道为什么会显示0次冲突吗？

编辑：我可能弄明白了。

这是不是因为__eq__只有在两个对象的__hash__值相同的时候才会被调用，而不是它们的“压缩版本”（正如@John Machin所说的）？

Answer 1

这个想法其实行不通，具体情况可以看问题讨论。

简单看一下Python的C实现，你会发现处理冲突的代码并没有计算或存储冲突的次数。

不过，它会对键使用 PyObject_RichCompareBool 来检查它们是否匹配。这意味着每次发生冲突时，键的 __eq__ 方法都会被调用。

所以：

你可以用定义了 __eq__ 方法的对象来替换你的键，并在这个方法被调用时增加一个计数器。这样做会慢一些，因为需要进入Python去比较。不过，这样可以让你大致了解发生了多少次冲突。

确保你使用不同的对象作为键，否则Python会走捷径，因为一个对象总是和它自己相等。另外，确保这些对象的哈希值和原始键的哈希值相同。

Answer 2

简短回答：

你不能用随机整数作为字典的键来模拟对象ID，因为它们的哈希函数不同。

碰撞是会发生的。“拥有唯一的东西就意味着没有碰撞”这个说法在很多情况下都是错的。

你不需要担心碰撞的问题。

详细回答：

以下是一些解释，来源于源代码的阅读：

字典是以一个大小为2的i次方的表格实现的，其中i是一个整数。

字典的使用率不会超过2/3。因此，对于15000个键，i必须是15，而2的i次方是32768。

当o是一个没有定义__hash__()的方法的类的实例时，hash(o)不等于id(o)。因为地址的低位3或4位可能是零，所以哈希值是通过将地址向右旋转4位来构建的；具体可以查看源文件Objects/object.c中的_Py_HashPointer函数。

如果低位有很多零，那就会成问题，因为要访问大小为2的i次方的表（例如32768），哈希值（通常远大于这个值）必须被压缩到合适的大小，这个过程是通过简单快速地取哈希值的低位i（例如15）位来完成的。

因此，碰撞是不可避免的。

不过，这并不需要你感到恐慌。哈希值的其余部分会被用来计算下一个探测的位置。需要进行第三次等探测的可能性应该相对较小，特别是因为字典的使用率从来不会超过2/3。多次探测的成本被首次和后续探测的计算成本所抵消。

下面的代码是一个简单的实验，展示了上述大部分讨论。它假设在字典达到最大大小后进行随机访问。在Python2.7.1中，15000个对象大约会有2000次碰撞（13.3%）。

总之，你真的应该把注意力转移到其他地方。碰撞不是你的问题，除非你以某种极不正常的方式为对象获取内存。你应该关注如何使用字典，例如使用k in d或try/except，而不是d.has_key(k)。考虑将一个字典作为d[(x, y)]访问，而不是两个层级的d[x][y]。如果你需要这方面的帮助，可以单独提问。

更新：在Python 2.6上测试后的结果：

地址旋转的功能直到Python 2.7才引入；有关全面讨论和基准测试，请参见这个错误报告。基本结论在我看来仍然有效，并可以通过“如果可以的话更新”来补充。

>>> n = 15000
>>> i = 0
>>> while 2 ** i / 1.5 < n:
...    i += 1
...
>>> print i, 2 ** i, int(2 ** i / 1.5)
15 32768 21845
>>> probe_mask = 2 ** i - 1
>>> print hex(probe_mask)
0x7fff
>>> class Foo(object):
...     pass
...
>>> olist = [Foo() for j in xrange(n)]
>>> hashes = [hash(o) for o in olist]
>>> print len(set(hashes))
15000
>>> probes = [h & probe_mask for h in hashes]
>>> print len(set(probes))
12997
>>>