为什么元组(set([1,"a","b","c","z","f"]))==元组(set(["a","b","c", "z","f",1]))85%的时间启用了哈希随机化？

Question

鉴于比雷埃夫斯对另一个问题的回答,我们有这个

x = tuple(set([1, "a", "b", "c", "z", "f"]))
y = tuple(set(["a", "b", "c", "z", "f", 1]))
print(x == y)

True在启用哈希随机化的情况下打印大约85%的时间.为什么85%？

Answer 1

我将假设这个问题的任何读者都读过这两个:

• 零比雷埃夫斯的回答和

• 我对CPython词典的解释.

首先要注意的是,哈希随机化取决于解释器启动.

对于两个集合,每个字母的散列都是相同的,因此唯一重要的是如果存在冲突(订单将受到影响).

通过扣除第二个链接,我们知道这些集合的后备数组从8开始:

_ _ _ _ _ _ _ _

在第一种情况下,我们插入1:

_ 1 _ _ _ _ _ _

然后插入其余部分:

? 1 ? ? ? ? ? ?

然后重新调整为32:

    1 can't collide with ? as ? is an even hash
  ? so 1 is inserted at slot 1 first
? 1 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

在第二种情况下,我们插入其余的:

? ? ? ? ? ? ? ?

然后尝试插入1:

    Try to insert 1 here, but will
  ? be rehashed if ? exists
? ? ? ? ? ? ? ?

然后它将重新开始:

    Try to insert 1 here, but will
    be rehashed if ? exists and has
  ? not rehashed somewhere else
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

因此,迭代次序是否不同仅取决于β是否存在.

β的几率是5个字母中的任何一个将散列为1个模8 并散列到1个模32的机会.

因为任何哈希到1模32的哈希值也都是1模8,我们希望找到32个槽的机会,其中五个槽位于槽1中:

5 (number of letters) / 32 (number of slots)

5/32是0.15625,因此两组结构中订单的概率为15.625%.

根本不奇怪,这正是比雷埃夫斯所测量的.

_{¹技术上即使这并不明显.由于线性探测,我们可以假装5个哈希中的每一个,但由于线性探测,它实际上更有可能发生"聚束"结构......但是因为我们只关注单个槽是否被占用,这不是实际上对我们有影响.}