如何创建无重复项的ConcurrentQueue？

Question

我需要一个并发集合，不允许有重复的元素（用于在 BlockingCollection 中作为 Producer/Consumer）。

我不需要元素的严格顺序。

另一方面，我希望最大程度地减少元素在集合中的“存活”时间。也就是说，集合不应该是 LIFO，理想情况下应该是 FIFO。

我觉得我需要没有重复的ConcurrentQueue，但没有重复的ConcurrentBag也可能可行。

为什么 C# 没有类似的东西，可能已经有人创建了吗？

这个问题是我之前的问题的结果：What type of IProducerConsumerCollection<T> to use for my task?

- Oleg Vazhnev

---

C#只是一种语言，您需要寻找库来获取类似的功能，像.NET框架中的ConcurrentQueue/Bag。像这样编写代码的人从未被考虑过，它注定会失败。因为您无法准确预测生产者何时生产和消费者何时消费。决定何时消除重复项大致类似于根据Random.Next()的返回值做出决策。无论您实现这样的功能有什么原因：它都注定要失败。 - Hans Passant

我不明白为什么它注定会失败。我可以使用ConcurrentDictionary来模拟Set（我只会使用key，value将始终为null）。我不想消除重复项。不应该有重复项。 - Oleg Vazhnev

此外，“C# in Nutshell”指出，可以编写并发堆栈：“如果您编写了自己的并发集合来禁止重复项，则可以使TryAdd在元素已经存在时返回false（例如，如果您编写了一个并发集）。” - Oleg Vazhnev

相关：如何将ConcurrentDictionary包装在BlockingCollection中？简而言之，你不能这样做。BlockingCollection<T>类期望底层集合始终接受提供的项，否则它会抛出异常并变得损坏。 - Theodor Zoulias

相关链接：并发集合和唯一元素。 - Theodor Zoulias

Answer 1

没有内置的.Net库可以将这一集合规则组合起来。您有三个选择：

1. 编写自己的集合类
2. 使用两个集合：编写一个自定义类，该类使用一个ConcurrentQueue和任何基于Set的集合，自动检查重复项；当添加到Set成功时，运行并添加到ConcurrentQueue；每次添加/删除成功时都会向两个集合添加
3. 使用ConcurrentQueue但遍历整个列表以检查重复项

后两种方法效率不高（一种是内存，另一种是CPU、I/O、锁定），因为需要显式锁定而更加混乱，但可以完成任务。它们将更快地实现，但如果权衡不符合您的要求，您将不得不选择选项＃1。

- Jon Adams

Answer 2

如果你严格要求没有重复项，那么你需要使用“集合（Sets）”。例如，NHibernate使用Iesi.Collections来提供这样的功能。通过使用Iesi，你可以围绕提供的“Set”类（DictionarySet、HashSet、SortedSet）构建自己的功能。来源：http://www.codeproject.com/KB/recipes/sets.aspx

- Teoman Soygul

---

.Net确实有一个HashSet<T>。就我遇到的情况而言，NHibernate使用Iesi.Collections来代替ISet<T>（在.Net库中没有很好的替代品）。 - svick

是的，需要使用 .net 3.5 或更高版本。 - Teoman Soygul

Answer 3

你可以简单地使用一个ConcurrentQueue，在调用Enqueue之前通过调用ConcurrentQueue.Contains<>方法检查数据是否在队列中。我猜Contains<>扩展方法已经被相当优化了。

编辑： 正如其他人所指出的那样，为了使其工作，您必须在Contains<>方法和Enqueue方法周围使用诸如互斥锁等的锁定机制，就像这样：

get mutex
if not Contains<>
{
    Enqueue
}
release mutex

- Chimera

---

我认为这样做行不通，因为竞态条件可能会导致另一个线程在调用Contains和Enqueue之间对“相同”的对象进行入队操作。我们真的需要一个ConcurrentSet<>才能正确地解决这个问题。 - ALEXintlsos

在这种情况下，您不需要队列对象的并发版本。我认为原帖作者正在寻找一个ConcurrentSet，它可以原子地防止重复。 - ALEXintlsos

是的，那正是海报所需要的。但是为了达到这个目的，他/她将不得不编写一个类或拼凑一个解决方案，使用提供的类和一些线程安全逻辑，因为C#目前还没有提供ConcurrentSet。 - Chimera

你的解决方案仍然可能在队列中创建重复项。 - Martin Mulder

我的答案已经编辑，包括在 Contains<> 和 Enqueue 之间需要一个锁机制。 - Chimera