与顺序无关的哈希算法

Question

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

示例(伪代码):

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上面例子中的s返回相同的值？

Answer 1

JDK本身提出了以下解决此问题的方法.java.util.Set接口的契约声明:

返回此set的哈希码值.集合的哈希码被定义为集合中元素的哈希码的总和,其中空元素的哈希码被定义为零.这确保了s1.equals(s2)意味着对于任何两个集合s1和s2的s1.hashCode()== s2.hashCode(),如Object.hashCode()的常规协定所要求的那样.

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

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