如何实现像.NET的ConcurrentBag <T>这样的类？

Question

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

当订购无关紧要时,袋子可用于存放物品,与套装不同,袋子支持重复.

我的问题是:这个想法如何实施？大多数集合我熟悉基本量(引擎盖下)某种形式的阵列,其中为了不得"的事情,"但有是一个订单(这就是为什么,尽管它并不需要,枚举几乎总是要经过一个不变的集合,可以是List,Queue,Stack,等以相同的顺序).

如果我不得不猜测,我可能会建议在内部它可能是一个Dictionary<T, LinkedList<T>>; 但实际上这似乎是非常可疑的,因为将任何类型T用作关键都没有意义.

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

编辑:

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

1. 当您没有针对相关类型的合适哈希码函数时,哈希表并不是那么有用.
2. 简单地跟踪对象在集合中的"计数"与存储对象不同.

正如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>,你会发现它在内部基本上是一个定制的链表.

由于包可以包含重复项,并且索引无法访问,因此双重链表是实现的非常好的选择.这允许锁定对于插入和移除而言相当精细(您不必锁定整个集合,只需要锁定插入/移除的位置周围的节点).由于您不担心重复,因此不涉及散列.这使得双链表完美无缺.