关联性集合类

 

关联性集合类即我们常说的键值对集合，允许我们通过Key来访问和维护集合。

我们来看一下  .net 为我们提供了哪些泛型的关联性集合类：

1     Dictionary
     
      2     SortedDictionary
      
       3     SortedList
       
      
     

 

Dictionary<TKey,TValue>

 

Dictionary<TKey,TValue>可能是最常用的关联性集合了，它的访问，添加，删除数据所花费的时间是所有集合类里面最快的，

因为它内部用了Hashtable作为存储结构，所以不管存储了多少键值对，查询/添加/删除所花费的时间都是一样的,它的时间复杂度是O(1)。

Dictionary<TKey,TValue>优势是查找插入速度快，那么什么是它的劣势呢？

因为采用Hashtable作为存储结构，就意味着里面的数据是无序的，所以想按一定的顺序去遍历Dictionary<TKey,TValue>里面的数据是要费一点工夫的。

作为TKey的类型必须实现 GetHashCode() 和 Equals() 或者提供一个 IEqualityComparer，否则操作可能会出现问题。

SortedDictioanry<TKey,TValue>

 

SortedDictionary<TKey,TValue> 和 Dictionary<TKey,TValue> 大致上是类似的，但是在实现方式上有一点点区别。

SortedDictionary<TKey,TValue>用二叉树作为存储结构。并且按key的顺序排列。

那么这样的话SortedDictionary<TKey,TValue> 的 TKey 就必须要实现 IComparable<TKey>。

如果想要快速查询的同时又能很好的支持排序的话，那就使用SortedDictionary吧。

SortedList<TKey,TValue>      

 

SortedList<TKey,TValue>是另一个支持排序的关联性集合。不同的地方在于，SortedList实际是将数据存储在数组中的。

也就是说添加和移除操作都是线性的，时间复杂度是O(n)，因为操作其中的元素可能导致所有的数据移动。

但是因为在查找的时候利用了二分搜索，所以查找的性能会好一些，时间复杂度是O(log n)。

所以推荐使用场景是这样地：如果你想要快速查找，又想集合按照key的顺序排列，最后这个集合的操作（添加和移除）比较少的话，就是 SortedList 了。

 

非关联性集合类

非关联性集合就是不用 key 操作的一些集合类，通常我们可以用元素本身或者下标来操作。.net 主要为我们提供了以下几种非关联性的泛型集合类。

1     List
     
      2     LinkedList
      
       3     HashSet
       
        4     SortedSet
        
         5     Stack
         
          6     Queue
          
         
        
       
      
     

List<T>

 

泛型的 List 类提供了不限制长度的集合类型，List在内部维护了一定长度的数组(默认初始长度是4)，

当我们插入元素的长度超过 4 或者初始长度的时候，会去重新创建一个新的数组,这个新数组的长度是初始长度的2倍（不永远是2倍，当发现不断的要扩充的时候，倍数会变大）

然后把原来的数组拷贝过来。所以如果知道我们将要用这个集合装多少个元素的话，可以在创建的时候指定初始值，这样就避免了重复的创建新数组和拷贝值。

另外由于其内部实质是一个数组，所以在List的末尾添加数据是比较快的，但是如果在数据的头或者中间添加删除数据相对来说更低效一些，因为会影响其它数据的重新排列。

LinkedList<T>

 

LinkedList在内部维护了一个双向的链表，也就是说我们在LinkedList的任何位置添加或者删除数据其性能都是很快的。

因为它不会导致其它元素的移动。一般情况下List已经够我们使用了，但是如果对这个集合在中间的添加删除操作非常频繁的话，就建议使用 LinkedList。

HashSet<T>

 

HashSet是一个无序且能够保持唯一性的集合。我们也可以把 HashSe t看作是Dictionary<TKey,TValue>，只不过 TKey 和 TValue 都指向同一个对象。

HashSet非常适合在我们需要保持集合内元素唯一性但又不需要按顺序排列的时候。HashSet不支持下标访问。

HashSet的优点是占内存空间小，在检查一组数据里是否包含一个值的时候，用它就比较合适。

SortedSet<T>

 

SortedSet 和 HashSet 就像 SortedDictionary 和 Dictionary 一样，SortedSet内部也是一个二叉树，用来支持按顺序的排列元素。

 

Stack<T>

后进先出的队列，不支持按下标访问

Queu<T>

 

先进先出的队列，不支持按下标访问

参考：https://www.cnblogs.com/wjcx-sqh/p/6049314.html

　　　0http://www.runoob.com/csharp/csharp-collection.html