在Python字典中计算碰撞次数

Question

在Python字典中计算碰撞次数

pythonoptimizationdictionary

16

第一次在这里发布问题，希望我提问的方式是正确的。

在添加元素到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个冲突）。但是，如果使用return id(self)，则没有冲突。

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

编辑：我可能已经解决了这个问题。

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

- Adam Nellis

1

你的意思是想知道内部字典算法是否进行了哈希表探测来查找元素吗？你所说的“collision”是这个意思吗？ - S.Lott

1

一些半相关的信息：hash（-1）== hash（-2）。除此之外，区间-sys.maxint-1 <= x <= sys.maxint 中的所有 int 值都具有唯一的哈希值。关于哈希长整型的算法在这里描述：http://effbot.org/zone/python-hash.htm。 - unutbu

哈希值-1是保留的（它用于标记C实现中的错误）。如果哈希算法生成此值，我们只需使用-2。哎呀。 - UncleZeiv

@unutbu：（1）OP的键是对象ID，而不是长整数。这是另一回事。(2) 城市传说：唯一哈希意味着没有冲突。这是错误的。请参见我的答案。 - John Machin

重新查看代码，我发现它确实比较了实际的哈希值，除非它们是相同的哈希值，否则不会调用'eq'。因此，我的计划行不通。 :( - Winston Ewert

显示剩余2条评论

2个回答

5

注意：该想法实际上不可行，详见问题中的讨论。

快速查看Python的C实现显示，解决哈希碰撞的代码没有计算或存储碰撞数量。

然而，它将在键上调用PyObject_RichCompareBool以检查是否匹配。这意味着每次发生碰撞时都会调用键上的__eq__。

因此：

将您的键替换为定义__eq__并在调用时递增计数器的对象。这样做会更慢，因为要涉及跳转到Python进行比较的开销。但是，这应该给您一个有关发生多少次碰撞的想法。

请确保使用不同的对象作为键，否则Python会采取捷径，因为对象始终等于自身。此外，请确保对象与原始键散列到相同的值。

- Winston Ewert

这是一个非常酷的想法 - 谢谢！我会尝试一下，看看与@John Machin的实验相比有多少碰撞。 - Adam Nellis

我尝试了你的建议，但它并没有完全达到我的预期！请查看我问题中的编辑。 - Adam Nellis

一个小代码片段比解释如何做更有帮助。 - user1767754

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- John Machin · Accepted Answer

简短回答：

通过将随机整数作为字典键无法模拟使用对象ID作为字典键。它们具有不同的哈希函数。

碰撞确实会发生。对于某些“thingy”的值，“拥有唯一的thingies意味着没有碰撞”是错误的。

您不应该担心碰撞。

详细回答：

以下解释源自阅读源代码：

字典实现为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
>>>