.net - 如何实现像 .NET 的 ConcurrentBag 这样的类？

Question

我发现自己对 ConcurrentBag<T> 的存在很感兴趣。即将推出的 .NET 4.0 框架中的类:

Bags are useful for storing objects when ordering doesn't matter, and unlike sets, bags support duplicates.

我的问题是:这个想法如何实现？我熟悉的大多数集合基本上相当于(在引擎盖下)某种形式的数组，其中的顺序可能并不“重要”，但是有一个顺序(这就是为什么，即使它不需要，枚举也会几乎总是经过一个不变的集合，无论是 List 、 Queue 、 Stack 等等，都以相同的顺序)。

如果我不得不猜测，我可能会建议在内部它可能是 Dictionary<T, LinkedList<T>> ;但这实际上似乎很可疑，因为仅使用任何类型都没有意义 T作为 key 。

我所期待/希望的是，这实际上是一种已经在某处“弄清楚”的既定对象类型，并且知道这种既定类型的人可以告诉我。这对我来说太不寻常了——在现实生活中很容易理解的概念之一，但作为开发人员很难转化为可用的类——这就是为什么我对可能性感到好奇。

编辑 :

一些响应者建议使用 Bag内部可能是哈希表的一种形式。这也是我最初的想法，但我预见到这个想法有两个问题:

当您没有适合相关类型的哈希码函数时，哈希表并不是那么有用。

简单地跟踪集合中对象的“计数”与存储对象不同。

正如 Meta-Knight 所建议的那样，也许一个例子可以更清楚地说明这一点:

public class ExpensiveObject() {
    private ExpensiveObject() {
        // very intense operations happening in here
    }

    public ExpensiveObject CreateExpensiveObject() {
        return new ExpensiveObject();
    }
}

static void Main() {
    var expensiveObjects = new ConcurrentBag<ExpensiveObject>();

    for (int i = 0; i < 5; i++) {
        expensiveObjects.Add(ExpensiveObject.CreateExpensiveObject());
    }

    // after this point in the code, I want to believe I have 5 new
    // expensive objects in my collection

    while (expensiveObjects.Count > 0) {
        ExpensiveObject expObj = null;
        bool objectTaken = expensiveObjects.TryTake(out expObj);
        if (objectTaken) {
            // here I THINK I am queueing a particular operation to be
            // executed on 5 separate threads for 5 separate objects,
            // but if ConcurrentBag is a hashtable then I've just received
            // the object 5 times and so I am working on the same object
            // from 5 threads at the same time!
            ThreadPool.QueueUserWorkItem(DoWorkOnExpensiveObject, expObj);
        } else {
            break;
        }
    }
}

static void DoWorkOnExpensiveObject(object obj) {
    ExpensiveObject expObj = obj as ExpensiveObject;
    if (expObj != null) {
        // some work to be done
    }
}

Answer 1

如果你看ConcurrentBag<T>的详情，你会发现它在内部基本上是一个定制的链表。

由于 Bags 可以包含重复项，并且不能通过索引访问，因此双向链表是一个非常好的实现选择。这允许对插入和删除的锁定进行相当细粒度的锁定(您不必锁定整个集合，只需锁定您插入/删除位置周围的节点)。由于您不担心重复，因此不涉及散列。这使得双链表完美。