java - 看似简单的 FNV1 哈希实现导致大量冲突

Question

我正在使用散列表并使用约 350,000 个英语单词的语料库，我想尝试均匀分布这些单词。因此，我尝试将它们装入长度为 810,049 的数组(最接近的素数大于输入大小的两倍)，我很困惑地看到像这样的简单 FNV1 实现:

public int getHash(String s, int mod) {
        final BigInteger MOD = new BigInteger(Integer.toString(mod));
        final BigInteger FNV_offset_basis = new BigInteger("14695981039346656037");
        final BigInteger FNV_prime = new BigInteger("1099511628211");

        BigInteger hash = new BigInteger(FNV_offset_basis.toString());

        for (int i = 0; i < s.length(); i++) {
            int charValue = s.charAt(i);

            hash = hash.multiply(FNV_prime).mod(MOD);
            hash = hash.xor(BigInteger.valueOf((int) charValue & 0xffff)).mod(MOD);
        }

        return hash.mod(MOD).intValue();
    }

导致 64,000 次碰撞，很多，基本上占输入的 20%。我的实现有什么问题？该方法是否存在某种缺陷？

编辑:除此之外，我还尝试并实现了其他散列算法，如 sdbm 和 djb2，它们的性能都完全相同，同样糟糕。在这个语料库上都有这些约 65k 的碰撞。当我将语料库更改为仅 350,000 个表示为字符串的整数时，开始出现一些差异(例如一种算法有 20,000 次碰撞，而另一种算法有 40,000 次)，但碰撞次数仍然高得惊人。为什么？

EDIT2:我刚刚测试过它，Java 的内置 .hashCode() 会导致同样多的冲突，即使你做了一些可笑的天真，比如哈希是所有字符模乘 charcodes 的产物810,049，它的性能仅比所有那些臭名昭著的算法差一半(60k 碰撞与 90k 的天真方法)。

Answer 1

由于 mod 是您的 哈希函数的参数，我认为它是您希望哈希归一化的范围，即对于您期望的特定用例为 810,049。我认为这是因为:

1. 该算法要求以 2ⁿ 为模进行计算，其中 n 是所需散列中的位数。
2. 鉴于偏移量基础和FNV Prime是模块中的常量，并且等于64位散列的参数，的值mod 也应固定为 2⁶⁴。
3. 既然不是，我假设它是所需的最终输出范围。

换句话说，给定固定偏移基和 FNV Prime，没有理由传入 mod 参数——它由其他两个 FNV 参数决定。 如果以上都是正确的，那么实现就是错误的。您应该进行 mod 2⁶⁴ 的计算，并对 810,049 应用最终余数运算。

此外(但这可能并不重要)，该算法要求用 ASCII 字符对低 8 位进行异或运算，而您正在对 16 位进行异或运算。我不确定这是否会有所不同，因为对于 ASCII，高位字节无论如何都将为零，并且它的行为就像您仅对 8 位进行异或运算一样。