一、常用集合类型及概念

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 搜索名称或扫描二维码

希望我们能共同成长，共同进步

Java中所有的类都位于java.util包下，主要由两个接口派生出来，分别是Collection和Map.Collection包含了List和Set两大分支。Map是一个映射接口。Set 、Map、List可以看做集合的三大类。
而遍历集合的工具有Iterator和Enumeration；
Arrays和Collection是操作数组集合的两个工具类。

一、Java中的集合主要分为四类：

1、List列表：有序的，可重复的；
2、Queue队列：有序，可重复的；
3、Set集合：不可重复；
4、Map映射：无序，键唯一，值不唯一。

二、集合类下包含的主要的实现类：

1 List列表：有序，可重复

1.1 ArrayList数组列表，有序，可重复，内部是通过Array实现。对数据列表进行插入、删除操作时都需要对数组进行拷贝并重排序。因此在知道存储数据量时，尽量初始化初始容量，提升性能。

1.2 LinkedList双向链表，每个元素都有指向前后元素的指针。顺序读取的效率较高，随机读取的效率较低。

1.3 Vector向量，线程安全的列表，与ArrayList一样也是通过数组实现的，不同的是Vector是线程安全的，也即同一时间下只能有一个线程访问Vector，线程安全的同时带来了性能的耗损，所以一般都使用ArrayList。

1.4 Stack栈，后进先出（LIFO），继承自Vector，也是数组，线程安全的栈。但作为栈数据类型，不建议使用Vector中与栈无关的方法，尽量只用Stack中的定义的栈相关方法，这样不会破坏栈数据类型。

1.5 ArrayQueue数组队列，先进先出（FIFO）

2 Queue队列，有序、可重复

2.1 ArrayDeque数组实现的双端队列，可以在队列两端插入和删除元素

2.2 LinkedList也是双向链表

2.3 PriorityQueue优先队列，数组实现的二叉树，完全二叉树实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值）

3 Map映射/字典，无序，键值对，键唯一

3.1 HashMap哈希映射/字典，无序字典，键值对数据，key是唯一的，Key和Value都可以为null

3.2 TreeMap红黑树实现的key->value融合，可排序，红黑树是一种自平衡二叉查找树。

3.3 LinkedHashMap链表映射/字典，继承了hashmap的所有特性，同时又实现了双向链表的特性，保留了元素插入顺序。

4 Set集合，不可重复

4.1 HashSet基于HashMap实现的集合，对HashMap做了一些封装。与HaspMap不同的是元素的保存为链表形式，插入数据时遍历链表查看是否有相同数据，有则返回false，没有则返回true.

4.2 LinkedHashSet链表集合，继承自HashSet与LinkedHashMap相似，是对LinkedHashMap的封装。

4.3 TreeSet红黑树集合，与TreeMap相似，是对TreeMap的封装。

比较：

你所知道的集合类都有哪些？主要方法？

大家好，我是酷酷的韩~

1.最常用的集合类是 List 和 Map。 List的具体实现包括 ArrayList和 Vector，它们是可变大小的列表，比较适合构建、存储和操作任何类型对象的元素列表。 List适用于按数值索引访问元素的情形。

2.Map 提供了一个更通用的元素存储方法。 Map集合类用于存储元素对（称作"键"和"值"），其中每个键映射到一个值。

3.它们都有增删改查的方法。
(1)对于set，大概的方法是add,remove, contains等
(2)对于map，大概的方法就是put,remove，contains等

4.List类会有get(int index)这样的方法，因为它可以按顺序取元素，而set类中没有get(int index)这样的方法。List和set都可以迭代出所有元素，迭代时先要得到一个iterator对象，所以，set和list类都有一个iterator方法，用于返回那个iterator对象。map可以返回三个集合，一个是返回所有的key的集合，另外一个返回的是所有value的集合，再一个返回的key和value组合成的EntrySet对象的集合，map也有get方法，参数是key，返回值是key对应的value，这个自由发挥，也不是考记方法的能力，这些编程过程中会有提示，结合他们三者的不同说一下用法就行。

越努力，越幸运。 ------酷酷的韩~