一尘不染

顺序无关的哈希算法

algorithm

我目前正在为我的自定义编程语言开发一个集合库。我已经有几种数据类型(Collection,List,Map,Set)和它们的实现(可变和不可变),但是到目前为止我缺少的是hashCodeand
equals。尽管这些对于列表来说是没有问题的,因为它们是有序的集合,但是它们对于集合和地图起着特殊的作用。如果两个Set具有相同的大小和相同的元素,则认为它们是相等的,并且Sets维护它们的顺序不应在其相等性上有所不同。由于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返回相同值的情况下,实现一种合理的哈希算法?


阅读 361

收藏
2020-07-28

共1个答案

一尘不染

JDK本身针对此问题提出了以下解决方案。java.util.Set接口的协定规定:

返回此集合的哈希码值。集合的哈希码定义为集合中元素的哈希码之和,其中空元素的哈希码定义为零。这可以确保s1.equals(s2)暗示了Object.hashCode()的一般合同要求的任意两个s1和s2集的s1.hashCode()==
s2.hashCode()。

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

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

2020-07-28