转载

Java集合从菜鸟到大牛演变

先来看一张集合概况图，这里从上到下列举了几个最经常用的集合

Java集合从菜鸟到大牛演变

1、集合接口

java.util.Collection 是一个集合接口。它提供了对集合对象进行基本操作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式。声明了适用于JAVA集合（只包括Set和List）的通用方法。Set 和List 都继承了Conllection,Map没有.

2、集合类型

JAVA集合主要分为三种类型： Set (集), List (列表), Map (映射)

Set集合：集合元素是 不能重复 的，元素是 没有顺序 的，所以它不能基于位置访问元素。

List集合：集合元素是 可以重复 的，元素是 有顺序 的，所以它可以基于位置访问元素。

Map：它包含键值对。Map的键是 不能重复 的，可以保证元素的插入顺序，也可以排序。

3、集合介绍

Set(集):

HashSet

HashSet是基于HashMap实现的，它不允许出现重复元素，不保证和政集合中元素的顺序，允许包含值为null的元素，但最多只能有一个null元素。

TreeSet

TreeSet可以实现排序等功能的集合，它在讲对象元素添加到集合中时会自动按照某种比较规则将其插入到有序的对象序列中，并保证该集合元素按照“升序”排列。

LinkedHashSet

具有HashSet的查询速度，且内部使用链表维护元素的顺序(插入的次序),于是在使用迭代器遍历Set时，结果会按元素插入的次序显示。

List(列表):

ArrayList

内部结构基于数组实现，可以对元素进行随机的访问，向ArrayList中插入与删除元素的速度慢。

LinkedList

LinkedList 是一个继承于AbstractSequentialList的双向链表，可以被当作堆栈、队列或双端队列进行操作。LinkedList同时还实现了List、Deque（双端队列）、Cloneable（能克隆）、java.io.Serializable（支持序列化，能通过序列化去传输）等接口，LinkedList是非同步的。

每个节点除含有元素外，还包含向前，向后的指针。

新建一个LinkedList，生成一个头节点（header，就是一个头指针），它的元素为null。

Java集合从菜鸟到大牛演变

它自包含，next和previous指针都指向自己。执行add(Object obj)方法后，会生成一个新节点

Java集合从菜鸟到大牛演变

Header节点的next指向链表的第一个节点，previous指向链表的最后一个节点，在这里都是first，再增加一个对象，它的形状像下面这样。

Java集合从菜鸟到大牛演变

Vector

Vector 是矢量队列，它是JDK1.0版本添加的类。继承于AbstractList，实现了List（支持相关的添加、删除、修改、遍历等）, RandomAccess（随机访问功能）, Cloneable（能被克隆）这些接口。

Vector实际上是通过一个数组去保存数据的。当我们构造Vecotr时；若使用默认构造函数，则Vector的默认容量大小是10。

当Vector容量不足以容纳全部元素时，Vector的容量会增加。若容量增加系数 >0，则将容量的值增加“容量增加系数”；否则，将容量大小增加一倍。Vector的克隆函数，即是将全部元素克隆到一个数组中。和ArrayList不同，Vector中的操作是线程安全的。

Stack

Stack是栈，它的特性是：先进后出(FILO, First In Last Out)。

Stack继承于Vector(矢量队列)的，由于Vector是通过数组实现的，这就意味着，Stack也是通过数组实现的，而非链表。

Map(映射):

Map基于散列表的实现，Map 是一种把键对象和值对象映射的集合，它的每一个元素都包含一对键对象和值对象。

HashMap

HashMap底层就是一个数组结构（叫做Entry Table），数组中的每一项又是一个链表（叫做Bucket,用于解决hash冲突而设计的）。当新建一个HashMap的时候，就会初始化一个数组。插入和查询“键值对”的开销是固定的，可以通过构造器设置容量capacity和负载因子load factor，以调整容器的性能。初始化结构如下：

Java集合从菜鸟到大牛演变

每个bucket包含一个Entry(map自定义的一种结构，包含一个往后的指针)的链表。

在put(key, value)后，它的结构如下：

Java集合从菜鸟到大牛演变

LinkedHashMap

类似于HashMap，但是迭代遍历它时，取得“键值对”的顺序是其插入次序，或者是最近最少使用(LRU)的次序，只比HashMap慢一点。而在迭代访问时发而更快，因为它使用链表维护内部次序。

Java集合从菜鸟到大牛演变

TreeMap

基于红黑树数据结构的实现，查看“键”或“键值对”时，它们会被排序(次序由Comparabel或Comparator决定)。TreeMap的特点在于，你得到的结果是经过排序的。TreeMap是唯一的带有subMap()方法的Map，它可以返回一个子树。

WeakHashMap

弱键(weak key)Map，Map中使用的对象也被允许释放: 这是为解决特殊问题设计的。如果没有map之外的引用指向某个“键”，则此“键”可以被垃圾收集器回收。

IdentifyHashMap

使用==代替equals()对“键”作比较的hash map，专为解决特殊问题而设计。

Hashtable

Hashtable与HashMap类似，Hashtable继承自Dictionary类，实现了Map接口，不同的是它不允许记录的键或者值为空；和HashMap相比，Hashtable是线程同步的，即任一时刻只有一个线程能写Hashtable，因此也导致了 Hashtable在写入时会比较慢。而且Hashtable可以通过Enumeration去遍历。

4、总结

List按对象进入的顺序保存对象，不做排序或编辑操作。

Set对每个对象只接受一次，并使用自己内部的排序方法(通常，你只关心某个元素是否属于Set,而不关心它的顺序--否则应该使用List)。

Map同样对每个元素保存一份，但这是基于"键"的，Map也有内置的排序，因而不关心元素添加的顺序。

如果添加元素的顺序对你很重要，应该使用 LinkedHashSet/TreeSet或者LinkedHashMap/TreeMap.

最后还要提到集合类里面一个很重要的类:Collections，它有很多自己独特的静态方法。当然它主要提供几种特殊集合(List, Map,Set)，可以调用静态方法来获得：Unmodifiable (不可修改集合，不可添加或删除元素)，Synchronize (保持同步集合，它的基本每个方法都加锁，防止并发操作)，Checked (声明之始传入特定类型，以后的操作都会验证加入元素是否属于已定类型)，Singleton (集合中只包含一个元素)。它们都是通过包装集合类中的抽象类获得，产生不同的行为。