一、常用集合类型及概念
 
1.基本关系
 
许多泛型集合类型均为非泛型类型的直接模拟。
 
Dictionary< TKey, TValue> 是 Hashtable 的泛型版本；它使用枚举的泛型结构KeyValuePair< TKey, TValue> 而不是DictionaryEntry
 
List< T> 是 ArrayList 的泛型版本
 Queue< T>对应Queue
 Stack< T>对应Stack
 
SortedList< TKey, TValue> 对应SortedList，这两个版本均为字典和列表的混合
 
SortedDictionary< TKey, TValue> 泛型类是一个纯字典，并且没有任何非泛型对应项
 
LinkedList< T>泛型类是真正的链接的列表，并具有任何非泛型对应项
 
2.常用集合类型
 
1）ArrayList
 
ArrayList是List接口的可变数组非同步实现，并允许包括null在内的所有元素，相当于List < object>
 
2）List < T >
 
泛型的List 类是一个不限长度的集合类型，它内部实际就是一个数组，初始长度是4，每次数组到达限制，就会把现有容量翻倍，它提供用于对集合进行搜索、排序和操作等方法
 List是数组链表，数组链表访问快,复杂度O(1),但是添加删除复杂度O(n)
 
3）LinkedList
 
LinkedList是List接口的双向链表非同步实现，并允许包括null在内的所有元素。
 底层的数据结构是基于双向链表的，
 LinkedList是指针链表，指针链表访问复杂度是O(n),但是添加删除很快O(1),如果对这个集合在中间的添加删除操作非常频繁的话，就建议使用LinkedList。
 
4）Dictionary < K, V>
 
存储键值对的关联性集合，查询等操作速度很快,因为它的时间复杂度是O(1)
 ，单线程中推荐使用Dictionary,有泛型优势,且读取速度较快,容量利用更充分.
 
5）Hashtable
 
Hashtable是System.Collections命名空间提供的一个容器，用于处理和表现类似key/value的键值对
 基本概念
 Hashtable使用了闭散列法来解决冲突，它通过一个结构体bucket来表示哈希表中的单个元素，这个结构体中有三个成员：
 　（1） key ：表示键，即哈希表中的关键字。
 　（2） val ：表示值，即跟关键字所对应值。
 　（3） hash_coll ：它是一个int类型，用于表示键所对应的哈希码。
 
哈希表的所有元素存放于一个名称为buckets（又称为数据桶） 的bucket数组之中
 优点：
 　（1）在使用哈希表保存集合元素（一种键/值对）时，首先要根据键自动计算哈希代码，以确定该元素的保存位置，再把元素的值放入相应位置所指向的存储桶中。在查找时，再次通过键所对应的哈希代码到特定存储桶中搜索，这样将大大减少为查找一个元素进行比较的次数
 
（2）多线程程序中推荐使用Hashtable，对Hashtable进一步调用Synchronized()方法可以获得完全线程安全的类型
 
Dictionary< TKey, TValue> 是 Hashtable 的泛型版本，它们之间实现上区别不大，运行效率上有一些差别
 Hashtable由于键值类型都object，所以涉及装箱拆箱操作，在添加数据的效率上要差一些，但是频繁使用数据时效率更高，HashTable的优点就在于其索引的方式，速度非常快。如果以任意类型键值访问其中元素会快于其他集合，特别是当数据量特别大的时候，效率差别尤其大。
 
6）SortedList
 
表示基于相关的 IComparer 实现按键进行排序的键/值对的集合,与哈希表类似，区别在于SortedList中的Key数组排好序的
 
7）堆栈（Stack）
 
表示对象的简单的后进先出非泛型集合。Push方法入栈，Pop方法出栈
 
8）队列（Queue）
 
队列先进先出,enqueue方法入队列，dequeue方法出队列
 
9）SortedList< TKey,TValue>
 
SortedList< TKey,TValue>是支持排序的关联性集合，将数据存储在数组中的。
 　　也就是说添加和移除操作都是线性的，时间复杂度是O(n)，因为操作其中的元素可能导致所有的数据移动。
 　　但是因为在查找的时候利用了二分搜索，所以查找的性能会好一些，时间复杂度是O(log n)。
 　　所以推荐使用场景是这样地：如果你想要快速查找，又想集合按照key的顺序排列，最后这个集合的操作（添加和移除）比较少的话，就是SortedList了。
 　　集合中的数据是有序的。可以通过key来匹配数据，也可以通过int下标来获取数据。
 
添加操作比ArrayList，Hashtable略慢；查找、删除操作比ArrayList快，比Hashtable慢
 
#####10）SortedDictioanry< TKey,TValue>
 
SortedDictionary< TKey,TValue>和Dictionary< TKey,TValue>大致上是类似的，但是在实现方式上有一点点区别
 　　SortedDictionary< TKey,TValue>用二叉树作为存储结构的。并且按key的顺序排列
 　　SortedDictionary< TKey,TValue>相比于SortedList< TKey,TValue>其性能优化了
 　　SortedList< TKey,TValue>其内部维护的是数组而SortedDictionary< TKey,TValue>内部维护的是**红黑树(平衡二叉树)**的一种，因此其占用的内存，性能都好于SortedDictionary< TKey,TValue>
 　　唯一差在不能用下标取值。
 
11）HashSet< T>
 
HashSet是一个无序的能够保持唯一性的集合,不支持下标访问。
 
12）SortedSet< T>
 
SortedSet内部也是一个二叉树，用来支持按顺序的排列元素。
 　　算法，存储结构都与哈希表相同，主要是设计用来做高性能集运算的，例如对两个集合求交集、并集、差集等。集合中包含一组不重复出现且无特定顺序的元素。
 
13）BitArray
 
BitArray用于二进制运算，“或”、“非”、“与”、"异或非"等这种操作，只能存true或false；
 
14）ListDictionary
 
单向链表，每次添加数据时都要遍历链表，数据量大时效率较低，数据量较大且插入频繁的情况下，不宜选用
 
15）HybridDictionary
 
HybridDictionary的类，充分利用了Hashtable查询效率高和ListDictionary占用内存空间少的优点，内置了Hashtable和ListDictionary两个容器，添加数据时内部逻辑如下：
 
当数据量小于8时，Hashtable为null，用ListDictionary保存数据。
 
当数据量大于8时，实例化Hashtable，数据转移到Hashtable中，然后将　　ListDictionary置为null。
 
下一篇再写一下每一种集合的内部实现，及具体的运行效率比较
 
我会在我的公众号上推送新的博文，也可以帮大家解答问题
 微信公众号 Andy and Unity 搜索名称或扫描二维码
 
 希望我们能共同成长，共同进步

常用的三大类集合：Set、List、Map。
 
 

1 Set
 
1) Set 集合属于单列集合，不允许包含重复元素；
2) 判断元素是否重复的标准为对象的 equals 方法，存在时返回 false，不存在返回 true；
3) 元素的排序规则，由相应的实现类决定，分为无序、元素大小排序、写入顺序排序；
4) 初始化大小，扩容参考 HashMap。
 

1.1 Set 接口、实现类:
 
名称
类型
线程同步
描述
Set
接口
继承了Collection接口
SortedSet
接口
继承了Set接口
HashSet
实现类
不同步
继承了AbstractSet类，实现了Set、Cloneable、Serializable接口
TreeSet
实现类
不同步
继承了AbstractSet类，实现了NavigableSet(继承了SortedSet)、Cloneable、Serializable接口
LinkedHashSet
实现类
不同步
继承了HashSet类，实现了Set、Cloneable、Serializable接口
 

1.2 HashSet
 
1) HashSet 实现了 Set 接口，继承了 AbstractSet 类，由哈希表支持，看源码可以发现是一个 HashMap 实例。
2) HashSet 不保证集合内元素的迭代顺序，特别是不保证迭代顺序永久不变，该集合运行 null 元素存在。
3) HashSet 中的元素，作为 HashMap 键值对的 Key 存储，而 Value 由一个统一的值保存。 
4) HashSet 默认初始化大小为 16，扩容加载因子为 0.75，扩容大小为原来的一倍。即一个初始化size为16的
   HashSet，元素添加到12个的时候会进行扩容，扩容后的大小为32。
备注：具体添加、读取、删除等规则需要参考 HashMap 的具体实现。
 

1.3 TreeSet
 
1) TreeSet 实现了 NavigableSet 接口，继承了AbstractSet类，由哈希表支持，看源码可以发现是一个 TreeMap 实例。
2) TreeSet 中的元素有序的，排序规则遵照元素本身的大小进行排序，元素不能重复。
3) TreeSet 中的元素，作为 TreeMap 键值对的 Key 存储，而 Value 由一个统一的值保存。 
备注：具体添加、读取、删除等规则需要参考 TreeMap 的具体实现。
 

1.4 LinkedHashSet
 
1) LinkedHashSet 实现了 Set 接口，继承了HashSet类，由哈希表支持，看源码可以发现是一个 LinkedHashMap 实例。
2) LinkedHashSet 中的元素有序的，排序规则遵照元素写入顺序进行排序，元素不能重复。
3) LinkedHashSet 中的元素，作为 LinkedHashMap 键值对的 Key 存储，而 Value 由一个统一的值保存。 
备注：具体添加、读取、删除等规则需要参考 LinkedHashMap、HashMap 的具体实现，LinkedHashMap继承了HashMap。
 

1.5 线程安全
 
由于 HashSet、TreeSet、LinkedHashSet的底层实现为HashMap、TreeMap、LinkedHashMap，所以Set集合是非线程安全的。
如果要实现 Set 集合的线程安全，可以使用 ConcurrentHashMap 实现一个Set集合。
 

2 List
 
1) List 集合属于单列、有序的、允许元素重复、可以为 null 的集合；
2) List 接口的实现类主要有三种：ArrayList、LinkedList、Vector。
 

2.1 List 接口、实现类:
 
名称
类型
线程同步
描述
List
接口
继承了Collection接口
ArrayList
实现类
不同步
继承了AbstractList类，实现了List、RandomAccess、Cloneable、Serializable接口
LinkedList
实现类
不同步
继承了AbstractSequentialList类，实现了List、Deque、Cloneable、Serializable接口
Vector
实现类
同步
继承了AbstractList类，实现了List、RandomAccess、Cloneable、Serializable接口
 

2.2 ArrayList
 
1) ArrayList 实现了 List 接口，继承了 AbstractList 类，由一个 Object[] 实例实现，即底层为数组结构；
2) 默认初始化长度为 10，扩容规则为 0.5倍的原容量加1，即一次扩容后的长度为 16；
3) 特点：查询速度快，添加、删除相对于LinkedList较慢、线程不同步(不安全)。
 

2.2 LinkedList
 
1) LinkedList 实现了 List 接口，继承了 AbstractSequentialList 类，由一个 Node 节点链表实现，即底层为链表结构；
2) 由于LinkedList 数据结构为链表，无预扩容机制；
3) 特点：添加、删除速度快，查询相对于ArrayList较慢、线程不同步(不安全)。
 

2.3 Vector
 
1) Vector实现了 List 接口，继承了 AbstractList 类，由一个 Object[] 实例实现，即底层为数组结构；
2) 默认初始化长度为 10，扩容加载因子为 1，当元素长度大于原容量时进行扩容，默认为 10，一次扩容后容量为 20；
3) 特点：线程安全，但是速度慢；在实现的方法上，用 synchronized 关键字进行了修饰，即在方法上实现了同步锁。
备注：具体实现细节请查看源码。
 

3 Map
 
1) Map 集合属于双列Key-value键值对的集合，Key不允许重复，是否允许为 null 根据实现类而定，Value 随意；
2) Map 接口的实现类主要有三种：HashMap、LinkedHashMap、TreeMap、Hashtable、ConcurrentHashMap。
 

3.1 Map 接口、实现类:
 
名称
类型
线程同步
描述
Map
接口
HashMap
实现类
不同步
继承了AbstractMap类，实现了Map、Cloneable、Serializable接口
LinkedHashMap
实现类
不同步
继承了HashMap类，实现了Map接口
TreeMap
实现类
不同步
继承了AbstractMap类，实现了NavigableMap(继承了SortedMap)、Cloneable、
Serializable接口
Hashtable
实现类
同步
继承了Dictionary类，实现了Map、Cloneable、Serializable接口
ConcurrentHashMap
实现类
同步
继承了AbstractMap类，实现了ConcurrentMap(继承了Map)、Serializable接口
 

3.2 HashMap
 
1) HashMap实现了 Map接口，继承了 AbstractMap类，数据结构采用的位桶数组，底层采用链表或红黑树进行存储；
2) 默认初始化长度为 16，扩容加载因子为 0.75，一旦大于 0.75*16之后，就会调用resize()进行扩容，扩容2倍，即32；
3) JDK1.7中，数据结构采用：位桶数组+链表结构；
   JDK1.8中，数据结构采用：位桶数组+(链表/红黑树)；
4) 支持克隆，无序，线程不同步，非安全。
 

3.3 LinkedHashMap
 
1) LinkedHashMap 实现了 Map 接口，继承了 HashMap 类；
   引用实现;
3) 迭代顺序由 accessOrder 属性的决定，默认为 false，以插入顺序访问；设置为 true 则按上次读取顺序访问(每次访问
   元素时会把元素移动到链表末尾方便下次访问，结构会时刻变化)。
4) 默认初始化长度为 16，扩容加载因子为 0.75，一旦>0.75*16之后，就会调用resize(）进行扩容，与HashMap一致；
5) 支持克隆，有序，线程不同步，非安全。
 

3.4 TreeMap
 
1) TreeMap实现了 NavigableMap接口，继承了 AbstractMap 类；
2) 数据结构基于红黑树实现；
3) 该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法；
4) 无初始化长度；
5) 支持克隆，有序，线程不同步，非安全。
 

3.5 Hashtable
 
1) Hashtable实现了 Map 接口，继承了 Dictionary类；
2) 数据结构:也是一个散列表，数据结构与HashMap相同,key、value都不可以为 null;
3) 该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法；
4) 默认初始化长度为 11，扩容加载因子为 0.75，一旦>0.75*11之后，就会进行扩容，扩容到2n+1,即23；
5) 支持克隆，无序，线程同步，安全。在实现的方法上，用 synchronized 关键字进行了修饰，即在方法上实现了同步锁。
6) 支持 Enumeration 遍历方式。
 

3.6 ConcurrentHashMap
 
1) ConcurrentHashMap实现了 ConcurrentMap接口，继承了 AbstractMap类；
2) 默认初始化长度为 16，扩容加载因子为 0.75，一旦大于 0.75*16之后，就会调用resize()进行扩容，扩容2倍，即32；
3) 数据结构：由Segment数组结构和HashEntry数组结构组成，一个ConcurrentHashMap中包含一个Segment数组，
   Segment的结构和HashMap类似，是一种数组和链表结构。
4) 使用了锁分段技术，Segment是一种可重入锁ReentrantLock，每个Segment拥有一个锁，当对HashEntry数组的
   数据进行修改时，必须先获得对应的Segment锁
5) 不支持克隆，无序，线程同步，安全。

常用集合类都有哪些？主要方法？
 
常见的集合
 ArrayList,LinkedList,HashSet,HashMap,TreeSet 等等
 常见方法：
 size()
 add()
 remove()
 等等

转自：https://www.cnblogs.com/DragonStart/p/7526663.html
 
 
 
在C#里面我们常用各种集合,数组,List,Dictionary,Stack等,然而这些集合都是非线程安全的,当多线程同时读写这些集合的时候,有可能造成里面的数据混乱,为此微软从Net4.0开始专门提供了另一套线程安全的版本(放在System.Collections.Concurrent命名空间).
 
都有这些:
 
当有多个线程并发访问集合时，应使用这些类代替 System.Collections 和 System.Collections.Generic 命名空间中的对应类型。
 
 
 
 
类
说明
BlockingCollection<T>
为实现 IProducerConsumerCollection<T> 的线程安全集合提供阻塞和限制功能。
ConcurrentBag<T>
表示对象的线程安全的无序集合。
ConcurrentDictionary<TKey, TValue>
表示可由多个线程同时访问的键值对的线程安全集合。
ConcurrentQueue<T>
表示线程安全的先进先出 (FIFO) 集合。
ConcurrentStack<T>
表示线程安全的后进先出 (LIFO) 集合。
OrderablePartitioner<TSource>
表示将一个可排序数据源拆分成多个分区的特定方式。
Partitioner
提供针对数组、列表和可枚举项的常见分区策略。
Partitioner<TSource>
表示将一个数据源拆分成多个分区的特定方式。
 
 
接口
说明
IProducerConsumerCollection<T>
定义供制造者/使用者用来操作线程安全集合的方法。此接口提供一个统一的表示（为生产者/消费者集合），从而更高级别抽象如System.Collections.Concurrent.BlockingCollection<T> 可以使用集合作为基础的存储机制。