与顺序无关的哈希算法

algorithm java set hash

2022-09-02 13:58:39

我目前正在为我的自定义编程语言开发一个集合库。我已经有几种数据类型（集合，列表，地图，集）和它们的实现（可变和不可变），但到目前为止，我缺少的是和。虽然这些对于列表来说没有问题，因为它们是有序的集合，但它们对集合和映射起着特殊的作用。如果两个集合具有相同的大小和相同的元素，则认为它们相等，并且集合保持它们的顺序不应影响它们的相等性。由于 equals-hashCode-contract，实现还必须反映此行为，这意味着具有相同元素但排序不同的两个集合应具有相同的哈希代码。（这同样适用于地图，从技术上讲，地图是一组键值对）hashCodeequalshashCode

示例（伪代码）：

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

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

答案 1

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

返回此集的哈希代码值。集合的哈希代码定义为集合中元素的哈希代码之和，其中 null 元素的哈希代码定义为零。这确保了 s1.equals（s2）意味着对于任何两个集合 s1 和 s2，s1.hashCode（）==s2.hashCode（）是任何两个集合 s1 和 s2，这是 Object.hashCode（）的一般协定所要求的。

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

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

答案 2

以下是可能实现的伪代码：

String hashCode = null;
for(element : elements){
    hashCode = xor(hashCode, getHashCode(element));
}
return hashCode;

该函数应返回一个字符串，该字符串的长度与两个参数中最长的一样长。它将对每个参数中的位进行异或，直到到达其中一个参数的末尾。然后，它将从较长的字符串中获取剩余的位，并将其附加到上面。xor

此实现将意味着集合的哈希码将与其最长元素的哈希码一样长。由于您正在对位进行XOR运算，因此无论元素的顺序如何，哈希码最终都将是相同的。但是，与任何哈希实现一样，将有发生冲突的机会。