为什么tuple（set（[1，“a”，“b”，“c”，“z”，“f”]）==tuple（set（[“a”，“b”，“c”，“z”，“f”，1]）在启用散列随机化的情况下占85%的时间？

Question

Given Zero Piraeus' answer to another question我们有

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

在启用hash randomization的情况下，大约85%的时间打印True。为什么是85%？

Answer 1

我假设这个问题的读者都读过：

• Zero Piraeus' answer和

• My explanation of CPython's dictionaries。

首先要注意的是散列随机化取决于解释器的启动。

每个字母的散列对于这两个集合都是相同的，所以唯一重要的是是否存在冲突（顺序将受到影响）。

---

通过第二个链接的推导，我们知道这些集合的后备数组从长度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
? β ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

因此迭代顺序是否不同，完全取决于β是否存在。

---

aβ的几率是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个散列中的每一个都是唯一的，因为重新散列，但由于线性探测，实际上更可能出现“束”结构。。。但因为我们只看一个插槽是否被占用，所以这实际上并不影响我们。