从HashSet中减去元素（并返回一个副本）？

Question

我有一个 HashSet 集合，

var universe = new HashSet<int>();

还有很多子集，

var sets = new List<HashSet<int>>(numSets);

我想要减去一个块，我可以像这样做：

var remaining = universe.ExceptWith(sets[0]);

ExceptWith 是就地操作的。我不想修改 universe。我应该首先克隆它，还是有更好的方法？

- mpen

---

你的意思是想知道如何克隆一个哈希集合？ - kennytm

@KennyTM：我的意思是我想知道如何完成这项工作。如果这意味着克隆，那么是的，如果有更好的方法，那么不需要。 - mpen

Answer 1

我猜我应该先克隆它？我该怎么做？

var universe = new HashSet<int>();
var subset = new HashSet<int>();
...

// clone the universe
var remaining = new HashSet<int>(universe);
remaining.ExceptWith(subset);

与 Except 扩展方法不一样简单，但可能更快（你应该运行一些性能测试来确保）

- Thomas Levesque

---

很不幸，您正在使用的new HashSet<T>(IEnumerable<T>)并没有利用现有集合仅包含不同元素这一事实，并为每个单独的元素调用昂贵的“Add(item)”方法，而不是有效地浅克隆内部数据结构。也就是说，在具有越来越大的universe`的情况下，这比它本应该更慢。因此，对于您的后续问题Efficient way to clone a HashSet<T>?，我给出+1。 - Evgeniy Berezovsky

Answer 2

那 Except() 呢？

var x = new HashSet<int>();
var y = new HashSet<int>();

var xminusy = new HashSet<int>(x.Except(y));

- James McNellis

---

但是Except是一个扩展方法，而ExceptWith专门用于与HashSets一起使用...这样做是否同样有效？ - mpen

@Mark，这肯定比仅仅使用ExceptWith不够高效，但它的效率与首先克隆它然后调用ExceptWith大致相同。 - Kirk Woll

@Kirk：我终于有时间测试一下了。不对。它仍然慢了大约40%。http://programanddesign.com/cs/subtracting-sets/ - mpen

@Ralph：非常有趣。这就是为什么我通常只回答C++的问题的原因;-) - James McNellis

在需要使用IEqualityComparer的情况下，Except方法更为优越（比如使用两组序列化对象，它们的内容相同但HashCode不同的情况下），不幸的是，ExceptWith方法不支持自定义的IEqualityComparer，但是Except扩展方法可以。当涉及到像这里一样的整数时，这当然不是一个问题。 - Joris

@Joris：但是HashSet的构造函数接受自定义的IEqualityComparer。 - StriplingWarrior

Answer 3

我对Linq的Except方法进行了基准测试，与克隆并使用HashSet原生函数ExceptWith进行了比较。以下是测试结果。

static class Program
{
    public static HashSet<T> ToSet<T>(this IEnumerable<T> collection)
    {
        return new HashSet<T>(collection);
    }

    public static HashSet<T> Subtract<T>(this HashSet<T> set, IEnumerable<T> other)
    {
        var clone = set.ToSet();
        clone.ExceptWith(other);
        return clone;
    }

    static void Main(string[] args)
    {
        var A = new HashSet<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        var B = new HashSet<int> { 2, 4, 6, 8, 10 };
        var sw = new Stopwatch();

        sw.Restart();
        for (int i = 0; i < 1000000; ++i)
        {
            var C = A.Except(B).ToSet();
        }
        sw.Stop();
        Console.WriteLine("Linq: {0} ms", sw.ElapsedMilliseconds);

        sw.Restart();
        for (int i = 0; i < 1000000; ++i)
        {
            var C = A.Subtract(B);
        }
        sw.Stop();
        Console.WriteLine("Native: {0} ms", sw.ElapsedMilliseconds);

        Console.ReadLine();
    }
}

Linq: 1297毫秒
Native: 762毫秒

http://programanddesign.com/cs/subtracting-sets/

- mpen

Answer 4

一个哈希集合必须跟踪其哈希算法常量和溢出桶。集合中的元素通过引用保存。使用Thomas Levesque建议的复制构造函数创建新哈希表会创建一个overhead的浅拷贝，速度应该很快。按照James McNellis的建议使用Except()首先创建一个匿名副本，然后将其传递给复制构造函数，该构造函数使用匿名字段初始化自己的字段。正如Thomas所说，您可能需要进行一些性能测试，但从理论上讲，他的答案应该击败James的答案。顺便说一下，我认为浅拷贝不是克隆，因为我认为克隆意味着也要复制底层元素。具有共同元素的哈希集合在修改时使用复制策略。

- verisimilidude

---

是的，你说得对，我也不认为我需要深度复制。虽然这个例子中使用的是int，但在实践中它们将是类；引用就足够了。 - mpen

Answer 5

回答虽晚，但有时可能会有用。

@mpen使用Linq的Except(IEnumerable<>)进行了回答。

这使得Linq循环遍历IEnumerable并检查其是否包含。

那么如何处理呢？

setA.Where(i => !setB.Contains(i))

- kitta

Answer 6

显然，在某些情况下，手动在循环中添加项目比复制整个集合然后删除项目更有效率。我能想到的一个例子是...

// no more set ops planned? then returning list is an option
public static List<T> ExceptWith<T>(HashSet<T> allObjects, Hashset<T> minus)
{
    //  Set Capacity of list   (allObjects.Count-minus.Count?)
    List<T> retlst = new List<T>(allObjects.Count); 

    foreach( var obj in allObjects) {
        if( minus.Contains(obj)==false)
            retlst.Add(obj);
    }
    return retlst;
}

// Special case where quantity of copying will be high
// more expensive in fact than just adding
public static HashSet<T> ExceptWith<T>(HashSet<T> allObjects, HashSet<T> minus)
{
    if( minus.Count > allObjects.Count * 7/8 )
    {
        HashSet<T> retHash = new HashSet<T>(); 

        foreach( var obj in allObjects) {
            if( minus.Contains(obj)==false)
                retHash.Add(obj);
        }
        return retHash;

    }
    else
    {
        // usual clone and remove
    }
}

- PJJ