java - 为什么我的自定义封闭哈希集中会发生如此多的冲突？

Question

我有一个自定义的封闭哈希集/开放寻址(即没有链表)类。它非常符合我的需求 - 它不是通用的(仅适用于正长数)，需要预定义要插入的记录数量，并且不支持删除 - 但它意味着尽可能少占用空间.

由于它的功能很少，所以它是一个非常小且简单的类。但是由于某种原因，当我插入许多条目时，冲突的数量变得太多太多太快了。

一些代码(Java):

public class MyHashSet
{
    private long[] _entries;

    public MyHashSet(int numOfEntries)
    {
        int neededSize = (int)(numOfEntries / 0.65D);
        _entries = new long[neededSize];
    }

    public void add(long num)
    {
        int cell = ((Long) (num % _entries.length)).intValue();

        while (_entries[cell] != 0)
        {
            if (++cell >= _entries.length)  
                cell = 0;                   
        }

        _entries[cell] = num;
    }
...

我有一个 main，它以 1000 万作为参数实例化一个 MyHashSet 对象，然后使用不同的随机生成(但为正)Long 数调用 add() 1000 万次。在普通的 Java HashSet 上，这个插入整体需要大约 1 秒，而 MyHashSet 则需要大约 13 秒才能完成。我为碰撞添加了一个计数器，实际上，碰撞次数为 3-60 亿次 - 远远超过预期(我猜预计会有 30-4000 万次)。

我做错了什么吗？散列本身有问题吗？为什么会有这么多碰撞，我该怎么办？

谢谢!

P.S.:代码中的数字 0.65 表示该表只会填充 65%，我知道这应该在封闭的哈希集中运行良好。对于这个问题，即使我将它设置为 20%，插入仍然需要 > 10 秒..

-- 编辑--

承认这一点非常尴尬，但我的测试代码在循环的每次迭代中重新创建了 Random 对象(以 System.currentTimeMillis() 作为种子)，而不是在整个运行过程中使用相同的对象..

修复后，大约需要 2-3 秒才能完成插入。相比之下，这似乎仍然太多了——为什么默认的 java HashSet 只需要一秒钟的时间就可以插入，而它比 MyHashSet 更“复杂”？我现在只有大约 900 万次碰撞。我还尝试关闭日志记录代码以查看它是否有帮助，但它仍然不会有所作为。如果有任何想法，我将不胜感激，对于之前的困惑，我再次深表歉意。

Answer 1

我首先注意到的是线上的无偿拳击

int cell = ((Long) (num % _entries.length)).intValue();

比

慢得多

int cell = (int) (num % _entries.length);

(请注意，num % _entries.length 将始终适合 int，因为 _entries.length 本身就是一个 int 。)

诚然，Java 的 HashSet 无论如何都会遭受类似的开销，但这至少是一个明显需要解决的问题。

此外，确保表格大小为质数可能对您有利。最简单的方法是 BigInteger.valueOf((int)(numOfEntries/0.65)).nextProbablePrime().intValue()，因为这是一次性成本，所以不会影响整体性能太差了。

或者，Java 的 HashSet 使用 2 的幂哈希表大小，因此它可以使用掩码(value & (_entries.length - 1)，基本上)而不是 %，后者通常更昂贵。