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

问：

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

第一个数据集包含 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]);
    }

第二个数据集是麻省理工学院的 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 数据可能会因此产生更大的主要聚类风险，但是 Java 的字符串对象 hashCode（） 方法（hashcode = s[0]*31^（n-1） + s[1]*31^（n-2） + ... + s[n-1] 如果我错了，请纠正我？？）似乎不会让冲突如此容易地发生，并且对于如此大量的数据。

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