Effective C# 原则40：根据需求选择集合

核心提示： .Net中的集合没有包含链表(linked list)结构，垃圾回收器的高效使得列表(list)结构在实际使用是占用时间最小，Effective C# 原则40：根据需求选择集合(6)，因此也让它成为了最佳选择，如果你确实须要链表的行为，BitArray 是一个为位操作进行优化了的容器；经

.Net中的集合没有包含链表(linked list)结构。垃圾回收器的高效使得列表(list)结构在实际使用是占用时间最小，因此也让它成为了最佳选择。如果你确实须要链表的行为，你有两个选择。如果你因为希望经常添加和删除里面的元素而选择了列表，那么使用null引用的字典类。简单的存储关键字，你就可以使用ListDictionary 类了，而且它用键/值对应方式实现了单向链表。或者你可以选择HybridDictionary类，这是一个为小集合使用了ListDictionary的类，而且对于大集合会转化到HashTable上来。这些集合以及很多其它内容都在 System.Collections.Specialized 名字空间里。然而，如果因为用户想控制次序而你想使用列表结构，你可以使用ArrayList 集合。ArrayList 可以在任何位置上执行插入操作，即使它的内部是使用的数组存储方式。

另外两个类支持基于字典的集合：SortedList 和Hashtable。它们都是包含键/值对应的。SortedList以键进行排序，而Hashtable则没有。Hashtable在给定的键上进行查找时更快，但SortedList提供了基于键的有序迭代。Hashtable 通过键的散列值进行查找。如果散列值是高效的，它的查找时间是一个常量，O(1)。有序列表是使用的折半查找算法来查找关键值。这中一个对数的算法操作 ：O(ln n)。

最后，就是BitArray类。正如它的名字所说的，它存储位数值。BitArray是以整数的数组来存储数据的。每个整型存储一个32位的二进制值。这让BitArray类是压缩的，但它还是会降低性能。BitArray 上的每个get和set操作要在存储的整数上完成位操作，这要查找另外的31个位。BitArray 包含的一些方法在很多值类型上实现了立即的Boolean操作：OR, XOR, AND, 和NOT。这些方法用BitArray做为参数，而且BitArray可以用于快速的多位mask操作，BitArray 是一个为位操作进行优化了的容器；经常使用mask操作时，要存储这些位标记的数据时应该使用它。但不要用它灰替换一般用图和Boolean值数组。