为什么是哈希集.除了以两倍的速度迭代和检查另一个集合上的包含

Question

我刚刚做了一些优化，却被这个问题搞糊涂了。

我的原始代码看起来像这样:

   HashSet<IExampleAble> alreadyProcessed;//a few million items
    void someSetRoutineSlower(HashSet<IExampleAble> exampleSet)
    {
        foreach (var item in exampleSet)
        {
            if (!alreadyProcessed.Contains(item))
            {
                // do Stuff
            }
        }
    }

这需要大约120万个滴答来处理。

然后我尝试了相同的exceptwith:

 void someSetRoutineFaster(HashSet<IExampleAble> exampleSet)
    {
        exampleSet.ExceptWith(alreadyProcessed);//doesnt this have to check each item of it's collection against the other one, thus actually looping twice?
        foreach (var item in exampleSet)
        {
            // do Stuff
        }
    }

以0.4 -0.7mil的节拍运行

exceptwith中正在进行什么样的优化?它不也必须像我在第一个代码片段中所做的那样检查所有项目吗?

Answer 1

根据。net Framework 4.7.2中HashSet ExceptWith方法的参考来源是这样的:

public void ExceptWith(IEnumerable<T> other) {
        if (other == null) {
            throw new ArgumentNullException("other");
        }
        Contract.EndContractBlock();
        // this is already the enpty set; return
        if (m_count == 0) {
            return;
        }
        // special case if other is this; a set minus itself is the empty set
        if (other == this) {
            Clear();
            return;
        }
        // remove every element in other from this
        foreach (T element in other) {
            Remove(element);
        }
    }

方法中的显式优化只适用于set为空或与自身"例外"的特殊情况。

您所经历的速度可能来自调用Contains(T)和遍历所有元素之间的差异，当调用Contains(T)的次数与集合大小相当时。从表面上看，它似乎应该显式地执行称为Contains(T)的旧实现，新实现在Remove(T)中执行相同类型的搜索。不同之处在于，当元素从集合中移除时，它的内部结构变得更加稀疏。这导致统计上每个桶的条目(每个源代码符号的插槽)更少，并且查找元素变得更快，如果存在，则它是桶中的第一项。

这完全取决于对象的哈希函数的质量。理想情况下，每个对象都应该单独在它的桶中，但大多数实际的哈希函数会分布上百万个有碰撞的元素(多个元素在同一个桶中)。