为什么我的自定义封闭散列集中会有这么多冲突？

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对象，然后用一个不同的随机生成的(仍为正的)长数字调用add() 1000万次。在普通的Java HashSet上，整个插入大约需要一秒钟，而对于MyHashSet，大约需要13秒才能完成。我为冲突添加了一个计数器，实际上，冲突的数量是30-60亿，比预期的要多(我猜测大约是3,000-4,000万)。

我做错了什么吗？散列本身有什么问题吗？为什么会有这么多冲突，我能做些什么呢？

谢谢!

附注:代码中的数字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))而不是%，后者通常更昂贵。

Answer 2

首先:修改你的模函数。否则你会得到ArrayOutOfBounds异常，而且它很容易修复，而不需要实际的性能成本(只需要一个and)。另外，如果你正在做这件事，按照路易的建议去做，去掉无用的长时间投射。

无论如何，真正的问题是，如果单元格已经被占用，那么您正在使用一个可怕的next函数。线性探测通常是一个糟糕的想法，而且你甚至会因为只进入一个方向而使情况变得更糟。如果你的数字没有完全统一地排列，你会得到很多冲突。双重散列在实践中工作得很好，但您也可以修复您的线性探测并测试这是否有帮助。

然后，你应该像路易斯建议的那样，使用一个质数作为表大小，这有一些(理论上可以证明)的优点，但速度更慢，或者使用2的下一个幂。目前，你正在结合这两种方法的缺点。