顺序无关的哈希算法

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

JDK本身针对这个问题提出了以下解决方案。 java.util.Set接口的契约指出：

返回该集合的哈希码值。集合的哈希码定义为集合中元素的哈希码之和，其中空元素的哈希码定义为零。这确保了 s1.equals(s2) 意味着对于任何两个集合 s1 和 s2 s1.hashCode()==s2.hashCode()，正如 Object.hashCode() 的一般契约所要求的。

使用条目哈希码总和的另一种方法是使用

^

(XOR) 运算符。

Scala 语言使用 Murmurhash 算法的排序不变版本（参见私有

scala.util.hashing.MurmurHash3

类）来实现其

不可变集

和类似集合的

hashCode

（或 ##）方法.

Answer 2

这是可能实现的伪代码：

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

xor

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

此实现意味着集合的 hashCode 将与其最长元素的 hashCode 一样长。因为您对位进行异或，所以无论元素的顺序如何，最终哈希码都将相同。然而，与任何哈希实现一样，都有可能发生冲突。

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("-", "");
    }
}

Answer 4

如果您正在寻找开箱即用的解决方案，可以使用Guava：

import java.util.Set;

import com.google.common.base.Charsets;
import com.google.common.hash.HashCode;
import com.google.common.hash.HashFunction;
import com.google.common.hash.Hashing;

...

public String hash(final Set<String> strings) {
    final HashFunction function = Hashing.murmur3_128();

    // Hashing.combineUnordered will throw an exception if input is empty.
    if (strings.isEmpty()) {
        return function.newHasher()
            .hash()
            .toString();
    }

    final List<HashCode> stringsHashes = strings.stream()
            .map(string -> function.newHasher()
                    .putString(string, Charsets.UTF_8)
                    .hash())
            .toList();

    return Hashing.combineUnordered(stringsHashes).toString();
}

解决作者的担忧：

...冲突可能性较小的哈希算法。

可以使用

sha256 代替

murmur3_128

。

此外，您可以使用 Funnels 将其适应任何输入类型，而不仅仅是字符串。