Scala集合的哈希码

Question

假设我们有三组Scala字符串。其中一个元素为A，B，C。二有元素B，C，D。而三则有元素J，K，I。

我的第一个问题是，这三个集合中的任意两个集合的哈希码是否可能相同？ 我的第二个问题是，如果我将D添加到One中并将A添加到Two中以获得新的集合One.n和Two.n，则One.n和Two.n的哈希码是否相同？

- user592419

---

你的问题有一半可以通过使用 REPL 仅用 3 分钟来回答。 - Kim Stebel

Answer 1

问题1）通常情况下，完全可能。哈希码是有限数量的字节长。集合可以是任意大小。因此哈希码不能保证唯一性（尽管通常它们是唯一的）。

问题2）为什么不试试呢？

scala> val One = collection.mutable.Set[String]("A", "B", "C")
One: scala.collection.mutable.Set[String] = Set(A, B, C)

scala> One.hashCode
res3: Int = 1491157345

scala> val Two = collection.mutable.Set[String]("B", "C", "D")
Two: scala.collection.mutable.Set[String] = Set(B, D, C)

scala> Two.hashCode
res4: Int = -967442916

scala> One += "D"
res5: One.type = Set(A, B, D, C)

scala> Two += "A"
res6: Two.type = Set(B, D, A, C)

scala> One.hashCode
res7: Int = -232075924

scala> Two.hashCode
res8: Int = -232075924

所以，正如你所期望的那样，它们是相等的，因为你期望==方法对这两个实例返回true。

- Luigi Plinge

---

在提问之前，我确实尝试过。我应该说，“... One.n 和 Two.n 总是相同的吗？”它是否仍然不变？ - user592419

hashCode 的规则是：如果你的对象 a 和 b 报告相等，即 a.equals(b)，那么 a.hashCode == b.hashCode（但反之不成立）。 - Dirk

@user592419 是的，但你可能不应该依赖它，因为哈希码是实现细节，而不是指定的公共类成员。例如，有人可以创建一个子类，重写hashCode方法以返回一个随机数。 - Luigi Plinge

也许这是另一个完全不同的问题，但我正在使用hashCode作为缓存策略。尽管我怀疑它不应该失败，但在这个小项目中似乎出了问题。你能给我指点一种不同的策略吗？基本上，我需要缓存中集合的这个特性（无论添加顺序如何，只要集合中的所有项相同，就返回相同的值）。 - user592419

Luigi: 如果有人重写 hashCode 方法返回一个随机数，他们就违反了 hashCode/equals 的约定。@user592419 如果你想要使用哈希来进行缓存，你必须使用具有更小（很多很多）碰撞概率的加密哈希算法。 - Draemon

Answer 2

设置相同且没有任何奇怪的东西（即具有不稳定哈希代码或哈希代码与等于不一致的任何内容）的集合应具有相等的哈希代码。如果这不是真的，并且集合是相同类型的集合，则这是一个错误，应该报告。如果集合是不同类型的集合，则具有不同哈希代码可能是一个错误（但在任何情况下都应符合等式）。我不知道有任何不相等的情况（例如，即使可变位集与不可变集相同），但是有不同的集合实现。

因此：

1. hashCode永远不能保证唯一，但应该很好地分布，以使碰撞的概率很低 2. 集合的hashCode应始终与equals一致（只要您放入集合中的所有内容都具有与equals一致的hashCode），即相等的集合具有相等的哈希码。（由于第1点，反之不成立。） 3. 集合只关心内容的标识，而不关心添加到集合中的顺序（这就是使用集合而不是List的原因）。

- Rex Kerr

---

第二点不完全正确：只有当equals为true时，hashcode才会始终与其一致。equals可能为false，但hashcode可能相同。 - Luigi Plinge

@LuigiPlinge - 这就是我打算传达的。 我会修正措辞。 - Rex Kerr