基于输入数据的线性探测的哈希表碰撞次数存在巨大差异

Question

我正在哈希表上运行性能测试，同时尝试两种不同的数据集和数组大小。

第一个数据集包含 100 000 个随机整数，转换为字符串 fe。 “-52917”“12345678”像这样计算：

  public static String[] prepareRandomWords() {
        Set<String> words = new HashSet<>();
        int maxNumOfWords = 100_000;
        int seed = 123;
        Random rand = new Random(seed);

        while (words.size() < maxNumOfWords) {
            words.add(String.valueOf(rand.nextInt()));
        }

        return words.toArray(new String[0]);
    }

第二个数据集是 MIT 的 100 000 个单词列表，可以在这里找到：https://www.mit.edu/~ecprice/wordlist.100000

这是我用来将元素插入表的 put 函数：

@Override
    public void put(T newElem) {
        validateInputElem(newElem);
        resizeIfNeeded();

        int key = newElem.hashCode(); // java's native String.hashCode()
        int i = 0;
        int hashId = hashFunc(key, i);

        while (hashElems[hashId] != nil) {
            collisionsAmount++; // added
            if (i + 1 == size) {
                doubleResize();
                i = -1;
            }
            i = (i + 1) % size;
            hashId = hashFunc(key, i);
        }

        hashElems[hashId] = newElem;
        nElems++;
    }

如果数组已满，resizeIfNeeded() 会将数组的大小加倍，然后继续将所有元素散列到新索引上。

现在您可以从上面的 put 函数推断出，每次发生冲突时都会调用 hashFunc(key,i) 方法。当数组调整大小以将元素放入新内存时也会使用它，但这些调用不会会计入测试中。

hashFunc 实现：

@Override
    int hashFunc(int key, int i) {
        int m = getSize();

        key = key & Integer.MAX_VALUE;

        int hash = (key % m + i) % m;

        return hash;
    }

我使用 NetBeans 中的 Profiler 运行了一些测试，并将数据导出到 Excel。然后我意识到，对于最初保留的内存（大小列）的许多值，MIT 数据的冲突次数为数百万，而对于字符串形式的随机整数，其冲突次数始终小于 300k。 （红色的值与我有关）

与 randomIntegersAsString 数据相比，对 MIT 数据进行哈希处理时出现如此大量冲突的原因是什么？

我尝试寻找答案：

经过进一步调查，我得出的结论是，这可能是由于 MIT 数据中文本分布不均匀造成的，因为英语并不完美，有些字母比其他字母出现的频率更高。

而在其他测试中，数据分布更加均匀。

我意识到 MIT 数据可能会产生更大的主聚类风险，因为 Java 的 hashCode() 方法用于字符串对象（hashcode = s[0]*31^(n-1) + s[1]*31^ (n-2) + ... + s[n-1] 如果我错了请纠正我？？）似乎不会让碰撞如此容易发生，并且对于如此大量的数据。

我感觉被困住了，不知道去哪里寻找推理。

Answer 1

两种情况出现差异的可能原因是java字符串哈希函数的质量不太好。 如果我们分析生成的散列值的分布（扩散），我们会注意到，在源自随机数的字符串的情况下，不存在模式，而在文件中单词的散列的情况下，我们注意到存在图案。

在第二种情况下，您可以清楚地看到分布不均匀，并且有许多垂直“线”。

解决方案是使用比java具有更好特性的哈希函数，它始终保证均匀分布和不存在模式。我建议使用mzHash32()，它简单、快速、冲突次数最少，并保证哈希值的最佳分布

public static int mzHash32(final byte[] data, int start, int length, int seed) {
    int hash = 0x95DE1432 ^ seed;
    for(int i = 0; i < length; i++)
        hash = (0xA8657C5B * (i + data[start + i])) ^ (hash << 2) ^ (hash >>> 2);
    return hash;
}

public static int mzHash32(String str) {
    byte[] data = str.getBytes();
    return mzHash32(data, 0, data.length, 0);
}

注意两种情况下的均匀分布