与顺序无关的哈希算法

Question

我目前正在为我的自定义编程语言开发一个集合库。我已经有几种数据类型（Collection、List、Map、Set）和它们的实现（可变和不可变），但到目前为止我缺少的是 hashCode 和 equals。虽然这些对于列表来说不是问题，因为它们是有序的集合，但对于集合和映射来说它们扮演着特殊的角色。如果两个 Set 具有相同的大小和相同的元素，则它们被认为是相等的，并且 Set 维护它们的顺序不应该对它们的相等性产生影响。由于 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 具有相同的值？

Answer 1

这是可能实现的伪代码：

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

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

此实现意味着集合的哈希码将与其最长元素的哈希码一样长。因为您正在对这些位进行异或运算，所以无论元素的顺序如何，最后哈希码都是相同的。但是，与任何哈希实现一样，将有可能发生冲突。

Answer 2

JDK自己针对这个问题提出了如下解决方案。 java.util.Set 接口的契约声明：

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 algorithm (cf. the private scala.util.hashing.MurmurHash3 class) to implement the hashCode (or ##) method of its immutable sets 和类似集合的顺序不变版本。

Answer 3

您可以计算哈希总和，按字母顺序对集合进行排序。

这里有 C# 示例 - 希望您能翻译成 Java :)

static String GetHash(List<String> l)
{
    using (System.Security.Cryptography.MD5 md5 = System.Security.Cryptography.MD5.Create())
    {
        return BitConverter.ToString(md5.ComputeHash(l.OrderBy(p => p).SelectMany(s => System.Text.Encoding.ASCII.GetBytes(s + (char)0)).ToArray())).Replace("-", "");
    }
}

与顺序无关的哈希算法

Order-independent Hash Algorithm

java

algorithm

hash

set