java - 与顺序无关的哈希算法

Question

我目前正在为我的自定义编程语言开发一个集合库。我已经有了几种数据类型(Collection、List、Map、Set)和它们的实现(可变和不可变)，但到目前为止我缺少的是 hashCode 和 equals .虽然这些对于列表来说不是问题，因为它们是有序的集合，但对于集合和映射来说它们扮演着特殊的角色。如果两个 Set 具有相同的大小和相同的元素，则它们被认为是相等的，并且 Set 维护它们的顺序不应该对它们的相等性产生影响。由于 equals-hashCode-contract，hashCode 实现也必须反射(reflect)此行为，这意味着具有相同元素但不同顺序的两个集合应具有相同的哈希码。 (这同样适用于 map ，它在技术上是一组键值对)

示例(伪代码):

let set1: Set<String> = [ "a", "b", "c" ]
let set2: Set<String> = [ "b", "c", "a" ]
set1 == set2       // should return true
set1.hashCode == set2.hashCode // should also return true

我如何实现一个相当好的哈希算法，使上面示例中的 hashCode 返回相同的值？

Answer 1

JDK本身针对这个问题提出了如下解决方案。 java.util.Set的契约(Contract)接口(interface)状态:

Returns the hash code value for this set. The hash code of a set is defined to be the sum of the hash codes of the elements in the set, where the hash code of a null element is defined to be zero. This ensures that s1.equals(s2) implies that s1.hashCode()==s2.hashCode() for any two sets s1 and s2, as required by the general contract of Object.hashCode().

使用条目哈希码总和的替代方法是使用例如 ^ (XOR) 运算符。

Scala 语言使用 Murmurhash 的顺序不变版本算法(参见私有(private) scala.util.hashing.MurmurHash3 类)来实现其 immutable sets 的 hashCode(或 ##)方法和类似的集合。