集合

选择集合

一般情况下，应使用泛型集合。 下表介绍了一些常用的集合方案和可用于这些方案的集合类。 如果你是使用泛型集合的新手，此表将帮助你选择最适合你的任务的泛型集合。

HashSet 类是用于包含唯一元素的无序集合。SortedSet 类提供在执行插入、删除和搜索操作之后让数据一直按排序顺序排列的自平衡树。

抽象基类 KeyedCollection 的行为类似列表和字典。

 ConcurrentStack、ConcurrentQueue和ConcurrentBag类型内部是使用链表实现的。因此，其内存利用不如非并发的Stack和Queue高效。但是它们适用于并发访问，因为链表更容易实现无锁算法或者少锁的算法。

 ConcurrentBag 表示对象的线程安全的无序集合，与集不同，包支持重复项。ConcurrentBag 可以接受 null 作为引用类型的有效值。

一个ConcurrentBag对象上的每一个线程都有自己的私有链表。线程在调用Add方法时会将元素添加到自己的私有链表中，因此不会出现竞争。当我们枚举集合中的元素时，其枚举器会遍历每一个线程的私有链表，依次返回

在调用Take时，ConcurrentBag首先会查询当前线程的私有列表，如果列表中至少有一个元素存在[插图]，那么该操作就可以在不引入竞争的情况下完成。但是，如果私有列表是空的，则必须从其他线程的私有列表中“窃取”一个元素，而这种操作可能造成竞争。
因此，准确地说，Take方法将返回调用线程在集合中最近添加的元素。如果该线程上已经没有任何元素，它会返回其他线程（随机挑选）最近添加的元素。

集合的算法复杂性

不可变的集合类型通常性能较低，但却提供了不可变性，这通常是一种非常有效的优点。

由于其索引器的 O(log n) 时间，ImmutableList 在 for 循环内的效果较差。 使用 foreach 循环枚举 ImmutableList 很有效，因为 ImmutableList 使用二进制树来存储其数据，而不是像 List 那样使用简单数组。 数组可以非常快速地编入索引，但必须向下遍历二进制树，直到找到具有所需索引的节点。

此外，SortedSet 与 ImmutableSortedSet 的复杂性相同。 这是因为它们都使用了二进制树。 当然，显著的差异在于 ImmutableSortedSet 使用不可变的二进制树。 由于 ImmutableSortedSet 还提供了一个允许变化的 System.Collections.Immutable.ImmutableSortedSet.Builder 类，因此可以同时实现不可变性和保障性能。

检查是否相等

诸如 Contains、 IndexOf、 LastIndexOf和 Remove 的方法将相等比较器用于集合元素。 如果集合是泛型的，则按照以下原则比较项是否相等：

• 如果类型 T 实现 IEquatable 泛型接口，则相等比较器是该接口的 Equals 方法。

• 如果类型 T 未实现 IEquatable，则使用 Object.Equals 。

此外，字典集合的某些构造函数重载接受 IEqualityComparer 实现，用于比较键是否相等。 

确定排序顺序

对于比较对象，有 default comparer 和 explicit comparer的概念。

默认比较器依赖至少一个正在被比较的对象来实现 IComparable 接口。 在用作列表集合的值或字典集合的键的所有类上实现 IComparable 不失为一个好办法。 对泛型集合而言，等同性比较是根据以下内容确定的：

• 如果类型 T 实现 System.IComparable 泛型接口，则默认比较器是该接口的 IComparable.CompareTo(T) 方法。

• 如果类型 T 实现非泛型 System.IComparable 接口，则默认比较器是该接口的 IComparable.CompareTo(Object) 方法。

• 如果类型 T 未实现任何接口，则没有默认比较器，必须显式提供一个比较器或比较委托。

为了提供显式比较，某些方法接受 IComparer 实现作为参数。 例如， List.Sort 方法接受 System.Collections.Generic.IComparer 实现。

SortedList 类与 SortedDictionary 类之间的一些区别。

对于必须可通过多个线程并发访问的已排序列表或字典，可以向派生自 ConcurrentDictionary 的类添加排序逻辑

并发集合类型使用轻量同步机制，如 SpinLock、SpinWait、SemaphoreSlim 和 CountdownEvent，这些机制是 .NET Framework 4 中的新增功能。 这些同步类型通常在将线程真正置于等待状态之前，会在短时间内使用忙旋转。 预计等待时间非常短时，旋转比等待所消耗的计算资源少得多，因为后者涉及资源消耗量大的内核转换。 对于使用旋转的集合类，这种效率意味着多个线程能够以非常快的速率添加和删除项。

BlockingCollection 是一个线程安全集合类，可提供实现制造者-使用者模式。多个线程或任务可同时向集合添加项，如果集合达到其指定最大容量，则制造线程将发生阻塞，直到移除集合中的某个项。 多个使用者可以同时移除项，如果集合变空，则使用线程将发生阻塞，直到制造者添加某个项。 制造线程可调用 CompleteAdding 来指示不再添加项。 使用者将监视 IsCompleted 属性以了解集合何时为空且不再添加项。

创建 BlockingCollection 时，不仅可以指定上限容量，而且可以指定要使用的集合类型。 例如，可为先进先出 (FIFO) 行为指定 ConcurrentQueue，也可为后进先出 (LIFO) 行为指定 ConcurrentStack。 可使用实现 IProducerConsumerCollection 接口的任何集合类。 BlockingCollection 的默认集合类型为 ConcurrentQueue。

在使用者需要同时取出多个集合中的项的情况下，可以创建 BlockingCollection 的数组并使用静态方法，如 TakeFromAny 和 AddToAny 方法，这两个方法可以在该数组的任意集合中添加或取出项。 如果一个集合发生阻塞，此方法会立即尝试其他集合，直到找到能够执行该操作的集合。

//Generate some source data.
      BlockingCollection[] sourceArrays = new BlockingCollection[5];
      for(int i = 0; i < sourceArrays.Length; i++)
          sourceArrays[i] = new BlockingCollection(500);
      Parallel.For(0, sourceArrays.Length * 500, (j) =>
                          {
                              int k = BlockingCollection.TryAddToAny(sourceArrays, j);
                              if(k >=0)
                                  Console.WriteLine("added {0} to source data", j);
                          });

      foreach (var arr in sourceArrays)
          arr.CompleteAdding();

ConcurrentDictionary 专为多线程方案而设计。 无需在代码中使用锁定即可在集合中添加或移除项。 但始终可能出现以下情况：一个线程检索一个值，而另一线程通过为同一键赋予新值来立即更新集合。

此外，尽管 ConcurrentDictionary 的所有方法都是线程安全的，但并非所有方法都是原子的，尤其是 GetOrAdd 和 AddOrUpdate。 为避免未知代码阻止所有线程，传递给这些方法的用户委托将在词典的内部锁之外调用。 因此，可能发生以下事件序列：

1. threadA 调用 GetOrAdd，未找到项，通过调用 valueFactory 委托创建要添加的新项。

2. threadB 并发调用 GetOrAdd，其 valueFactory 委托受到调用，并且它在 threadA 之前到达内部锁，并将其新键值对添加到词典中 。

3. threadA 的用户委托完成，此线程到达锁位置，但现在发现已有项存在。

4. threadA 执行“Get”，返回之前由 threadB 添加的数据 。

因此，无法保证 GetOrAdd 返回的数据与线程的 valueFactory 创建的数据相同。 调用 AddOrUpdate 时可能发生相似的事件序列。

Microsoft.Extensions.ObjectPool 命名空间下已存在 Microsoft.Extensions.ObjectPool.ObjectPool 类型。  在需要某个类的多个实例并且创建或销毁该类的成本很高的情况下，对象池可以改进应用程序性能。