Java中的无序哈希

Question

我想在Java中计算一组字符串的哈希值。 是的，我可以对字符串进行排序并使用digest.update迭代地计算MD5哈希值。 但我更喜欢省略排序并使用类似于combineUnordered的东西，详情请见https://github.com/google/guava/wiki/HashingExplained。有很多类似的问题，例如Order-independant Hash Algorithm，但没有一个提供一个简单的示例来展示如何在Java中迭代地计算一个无序哈希值。

- Marmite Bomber

---

为什么需要覆盖集合的哈希算法？ - Szigyártó Mihály

@SzigyártóMihály 不需要覆盖，我正在寻找一个简单的例子。我知道MD5是有序的，而MurmurHash则不应该有序，但我找不到使用它的例子。 - Marmite Bomber

该集合使用项哈希的总和，不依赖于顺序。 - Szigyártó Mihály

Answer 1

只需对每个哈希进行XOR运算，顺序并不重要，而且哈希大小将固定，而不会随着集合大小的增加而增长。

使用内置的Java字符串hashcode生成哈希码：

int hashcode = strings.stream()
        .mapToInt(Object::hashCode)
        .reduce(0, (left, right) -> left ^ right);

使用guava和MD5生成哈希码，就像问题所要求的那样：

Optional<byte[]> hash = strings.stream()
        .map(s -> Hashing.md5().hashString(s, Charset.defaultCharset()))
        .map(HashCode::asBytes)
        .reduce((left, right) -> xor(left, right));


static byte[] xor(byte[] left, byte[] right) {
    if(left.length != right.length) {
        throw new IllegalArgumentException();
    }
    byte[] result = new byte[left.length];
    for(int i=0; i < result.length; i++) {
        result[i] = (byte) (left[i] ^ right[i]);
    }
    return result;
}

- Magnus

---

这是首选的方法。异或哈希比将它们相加更好。 - Luke Joshua Park

是的，这对于集合来说是正确的，但对于可以包含重复项的袋子来说，XOR不适用，因为重复项会将其重置为零 @LukeJoshuaPark，因此必须使用一些SUM（封装）。 - Marmite Bomber

Answer 2

你可以分别计算每个字符串的MD5哈希值，然后将它们相加以获得单个哈希值。这将是无序的，因为加法运算是可交换的。

以下是一个示例（假设我们有一个方法md5Hex(String str)，用于计算给定字符串的MD5哈希值并以十六进制格式返回结果）：

String[] strings = {"str1", "str2", "str3", ...};

BigInteger hashSum = BigInteger.ZERO;
for(String s : strings) {
    String hexHash = md5Hex(s);
    hashSum = hashSum.add(new BigInteger(hexHash, 16));
}

String finalHash = hashSum.toString(16);

- elyor

---

是的，谢谢；问题的背景（虽然被踩了）是我是否应该走这条路或使用一些替代哈希算法，可以组合未排序的数据并可能减少冲突。 - Marmite Bomber

@MarmiteBomber，已添加一个示例。 - elyor

Answer 3

这是一个使用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();
}

- DanyloStackylo