Collection框架
1 Collection
用来存储独立的元素，其中包括List、Set和Queue。
1. List
List是按照插入的顺序保存元素，它是一种线性的列表结构，它继承自Collection接口，是一种有序集合，List中的元素可以根据索引进行检索、删除或者插入操作。
1.1 ArrayList
ArrayList（java.util.ArrayList）是用数组来实现的List，是最常见的列表之一。
它与数组有着同样的特点：
1）随机访问（相对于顺序访问）效率高。
2）读快写慢，由于写的过程中需要涉及元素的移动，因此写操作的效率比较低。
数组存储
1）所有数据块的内存是连续的。
2）所有数据块的长度是相同的。
ArrayList的实现原理：
（1）父类和接口
1）java.util.AbstractList。该抽象类是大部分List的共同父类，它提供了一些基本的方法封装，以及通用的迭代器实现。
2）java.util.List。列表标准接口，列表是一个有序集合，又被称为序列。该接口对它内部的每一个元素的插入位置都有精确控制，用户可以使用整数索引（index）来查询。
3）java.util.RandomAccess。这是一个标记性质的随机访问接口，它没有提供任何方法。
4）java.lang.Cloneable。用于标记可克隆对象，是一个常见接口，没有实现该接口的对象在调用Object.clone()方法时会抛出异常。
5）java.io.Serializable。序列化标记接口，是一个常见接口，被此接口标记的类可以实现Java序列化和反序列化。该接口没有任何内容，但是Java序列化里有一些默认成员变量和默认方法，会在序列化和反序列化的时候调用到。
（2）成员变量和常量
1）成员变量
①private transient Object[] elementData，elementData是该List的数据域，其中被transient修饰表示这个变量不会被序列化，它提供给Serializable接口使用。
②private int size，size表示当前List的长度，elementData的length是必然大于或等于size的。
③protected transient int modCount=0，该成员变量继承自java.util.AbstractList，记录了ArrayList结构性变化的次数。
在ArrayList的所有涉及结构变化的方法中都会增加modCount的值，这些方法包括：add( )、remove()、addAll( )、removeRange( )及clear( )。
2）常量
①private static final long serialVersionUID=8683452581122892189L
序列化版本UID，根据这个名字能判断出它是提供给序列化接口使用的，该UID是为了维持序列化版本一致性的。
②private static final int MAX_ARRAY_SIZE=Integer.MAX_VALUE-8
数组长度的上限，这里设置的是最大整数-8。
（3）构造方法
①public ArrayList(int initialCapacity)
initialCapacity表示初始化的elementData的长度
②public ArrayList()
elementData的长度默认为10
③public ArrayList(Colloction < ? extends E > c)
elementData的长度设置等同为集合的大小，然后再复制集合的所有元素到ArrayList的elementData中
1）indexof/lastIndexof/contains方法实现。
indexof方法用于查询指定对象的索引index，实现的方式是对数组顺序遍历，调用指定元素的equals方法来比对，如果查询不到，那么返回-1。
lastIndexof则于indexof相反，是对数组倒序遍历。
contains方法直接调用indexof方法，根据返回值是否为-1判断代查找的元素是否存在。
2）set/add/addAll方法实现。
set方法的实现很简单，即替换数组里的对应索引处的值。
add和addAll方法的实现相对复杂一些。首先要检查当前elementData的长度，如果添加后的大小超出elementData的长度，那么需要对elementData的容量进行修正。
扩展：elementData容量修正的逻辑。
容量修正主要是两个方向：多余和不足。
方法： grow(int)， int参数指定了“本次扩容所允许的最小容量”。
3）remove/removeAl/retainAll方法实现。
remove方法有两种重载形式：remove(int)和remove(Object)。
当形参为int时，表示移除位于指定index的数据，如果移除的不是最后一位，那么会调用System.arrayCopy方法把index之后的数据向前移动一位，该方法的返回值指向被删除的元素。该方法效率比较低。
当形参为Object时，表示移除指定的对象，该方法会顺序遍历整个数组，找到第一个与之相等对象（使用该对象的equals方法来判断两个对象是否相等），并执行类似remove(int)的操作。该方法的返回值表示删除是否成功。
removeAll方法用于移除指定集合里的所有元素。 等同 batchRemove(Collection,false)
retainAll方法是会保留指定集合里存在的元素。等同 batcRemove(Collection,true)
4）迭代器
使用索引遍历会比迭代器遍历效率更高，迭代器遍历使用java.util.Iterator来实现。
标准写法：
Iterator<String> iterator=list.iterator();
while(iterator.hasNext()){
r = iterator.next();
}
1.2 LinkedList
特性: 顺序访问和写快读慢。
（1）父类和接口
1）java.util.AbstractSequentialList。该抽象类继承自java.util.AbstractList，提供了顺序访问存储结构，只要类似于LinkedList这样的顺序访问List，都可以继承该类。
它提供了get\set\add\addAll\remove等方法的迭代器方式的实现，前提是必须提供对迭代器接口java.util.Iterator的实现。
2）java.util.Deque。双向队列接口，继承自java.util.Queue。
Queue的特性是“先进先出”，可以在尾部增加数据，头部获取数据。Deque则可以同时在头尾处完成读写操作。在此基础上，LinekdList还能操作头尾之间的任意结点，所以LinkedList在实现Deque的同时实现了java.util.List。
3）java.lang.Cloneable、java.util.List和java.lang.Serialiable。
（2）成员变量和常量
1）transient int size=0; 用于标记序列的大小，因为链表由单个结点组成，除了统计结点个数以外并没有办法获取size，所以提供了一个标记量来做记录，来提高效率。
2）transient Nodefirst; 链表的头结点。
3）transient Node last; 链表的尾结点。同时提供头尾结点是为了实现java.util.Deque双向队列接口要求的功能。
4）常量：private static final long serialVersionUID=876323262645176354L;这个常量提供给Serialiable序列化接口使用。
（3）构造方法
1）public LinkedList()。 链表无需初始化任何对象
2）public LinkedList(Collection<? extends E>c)。
（4）Deque双向队列的实现
LinkedList是一个在双向队列基础上搭建的双向链表，双向链表的关键方法：
1）addFirst(E)：在队头添加元素。
2）addLast(E)：在队尾添加元素。
3）E removeFirst()：删除队头元素。
4）E removeLast()：删除队尾元素。
这些方法通过操作成员变量first和last来实现的。first和last的类型是私有类Node。
（5）getFirst/getLast/get方法实现
getFirst：取出头
getLast：取出尾的数据
get(int)：LinkedList是顺序存储结构，要取到第i个数据，必须顺序遍历到i结点，所以这个方法的时间复杂度为O(n)。
（6）set/add/addAll的实现
add的本质是在尾部增加一个结点。addAll(Collection)等价于调用add(E)多次。
set需要遍历查找到指定结点i，并替换之。
（7）removeFirst/removeLast/remove方法实现
removeFirst与removeLast方法用于移除头尾结点并返回数据，remove则是遍历到指定结点，然后移除它。
（8）迭代器
ListIteractorlistIterator()方法返回了一个内部类ListItr，该类即是LinkedList迭代器的实现。
由于LinkedList本身就是顺序结构，该迭代器除了记录nextIndex之外没有做特殊处理。此外LinkedList的迭代器也具备fail-fast特性。
1.2 Vector和Stack
Stack是栈，Vector是矢量
（1）Vector
Vector的实现与ArrayList基本一致，底层使用的也是数组，其迭代也具备fail-fast特性，但它和ArrayList还有一些区别，主要体现在以下特性：
1）Vector是线程安全的，ArrayList不是。这体现在Vector的所有public方法都使用了synchronized关键字。
2）Vector多了一个成员变量capacityIncrement，用于标明扩容的增量，与ArrayList每次固定扩容50%相比，Vector根据capacityIncrement的数值来扩容，capacityIncrement大于0时，增加等同于capacityIncrement的容量，否则增加一倍容量。capacityIncrement由构造方法Vector(int,int)的第二个形参决定。
（2）Stack
Stack是Vector的子类，所以它的实现和Vector是一致的，与Vector相比，它多提供了以下方法以表达栈的含义。
1）E push(E)，入栈，等同在Vector最末位置增加一个元素
2）E pop()，出栈，移除Vector最末位置元素，并返回。
3）E peek()，查看栈顶，返回Vector最末位置元素。
4）empty()，检查栈是否为空。
5）search(E)，查找元素的栈深，注意，栈顶元素的深度为1，当找不到指定元素时，返回-1。算法为size()-lastIndexof(E)。
1.3. Queue按照排队规则来处理容器中的元素。
Queue：一种先入先出（FIFO）的模型
Queue类图
PriorityQueue
PriorityQueue并不遵循FIFO（先入先出）原则，它会根据队列元素的优先级来调整顺序，优先级最高的元素最先出。
（1）成员变量
PriorityQueue的主要成员变量有：
transient Object[] queue; //存值数组
private int size = 0; //元素数量
private final Comparator<? super E> comparator; // 比较器，可以为null，当为null是，E必须实现Comparable
（2）heapify方法和最小堆
最小堆是一种经过排序的完全二叉树，其中任一非终端结点数值均不大于其左孩子和右孩子结点的值。
（3）siftDown(k,x)方法(沉降方法)
siftDown方法用于沉降，根据comparator成员变量是否为null，它的执行方式略有不同。
如果comparator不为null，那么调用comparator进行比较；反之，则把元素视为Comparable进行比较。
如果元素没有实现Comparable接口，那么会抛出ClassCastException。
（4）offer(e)方法
PriorityQueue的offer方法用于把数据入队。
特性：
1）不能存放null数据。
2）与ArrayList留有扩容余量不同，当size达到数组长度极限时，才执行扩容（grow方法）。
3）当队列中有数据时，会执行结点上浮（siftUp），把优先级更高的数据放置在队头。
（5）grow(minCapacity)方法
grow方法用于对PriorityQueue进行扩容。
功能：
①扩容。扩容策略是，如果旧容量小于64，那么增加一倍+2，否则增加50%。
②溢出校验。如果小于0，那么认为溢出，容量最大能支持到最大正整数。
（6）siftUp(k,x)方法
siftUp方法用于上浮结点。新加入的结点一定在数列末位，为了让数列满足最小堆性质，需要对该结点进行上浮操作。
（7）poll()方法
poll方法用来检索并移除此队列的头。
2 Map
用来存储<键，值>对，这个容器允许通过键来查找值。Map是一种由多组key-value（键值对）集合在一起的结构，其中，key值是不能重复的，而value值则无此限定。
其基本接口为java.util.Map，该接口提供了Map结构的关键方法，比如常见的put和get。
2.1 HashMap
HashMap是最常用的Map结构，Map的本质是键值对。它使用数组来存放这些键值对，键值对与数组下标的对应关系由key值的hashCode来决定，这种类型的数据结构可以称之为哈希桶。
哈希桶能存储[0,2的31次方-1]区间的哈希值
2.1.1 Java 8之前的HashMap
HashMap的底层实现是数组和链表
（1）成员变量
transient Entry<K,V> table; //存储数据的核心成员变量
transient int size; //HashMap键值对数量
final float loadFactor; //加载因子，用于决定table的扩容量
table是HashMap的核心成员变量。该数组用于记录HashMap的所有数据，它的每一个下标都对应一条链表。所有哈希冲突的数据，都会被存放到同一条链表中。
Entry<K,V>则是该链表的结点元素。Entry<K,V>包含以下成员变量：
final K key; //存放键值对中的关键字
V value; //存放键值对中的值
Entry<K,V> next; //指向下一个结点的引用
int hash; //key所对应的hashcode
HashMap的核心实现是一个单向链表数组（Entry<K,V>[]table），HashMap的所有方法都是通过操作该数组来完成，HashMap规定了该数组的两个特性：
1）会在特定的时刻，根据需要来扩容。
2）其长度始终保持为2的幂次方。
在HashMap中，数据都是以键值对的形式存在的，其键值所对应的hashCode将会作为其在数组里的下标。
尽可能使键值的hashcode分散，这样可以提高HashMap的查询效率。
（2）常量
static final int DEFAULT_INTIAL_CAPACITY=16; //默认的初始化容量，必须为2的幂次方
static final int MAXMUM_CAPACITY=1<<30; //最大容量，在构造函数指定HashMap容量的时候，用于做比较
static final int DEFAULT_LOAD_FACTOR=0.75f; //默认的加载因子，如果没有构造方法指定，那么loadFactor成员变量就会使用该常量
（3）put(K,V)方法，用于向HashMap中添加元素
执行流程
1）indexFor(int,int)方法，作用是根据hashCode和table长度来计算下标。
2）hash(Object k)方法，用于计算键值k的hashCode。
3）存储数据。对应put方法中for循环之后的部分。
4）addEntry(int,K,V,int)和createEntry(int,K,V,int)，添加键值对。
该方法参数分别为hash值、键值、值以及下标。由于HashMap的核心数据结构是一个数组，所以一定会涉及数组的扩容。
5）resize(int)，用于给HashMap扩充容量。
resize主要完成以下工作：
①根据新的容量，确定新的扩容阈值（threshold）大小。
②确定是否要哈希重构（rehash），判断依据是原有的useAltHashing（是否使用替代哈希算法标识）和新产生的这个值，是否一致。不一致时，需要哈希重构。
③使用新容量来构造新的Entry<K,V>table数组，调用transfer(newTable,rehash)来重新计算当前所有结点转移到新table数组后的下标。
6）transfer(Entry[], boolean)，重新计算转移到新table数组后的Entry下标。
（4）get方法
get方法执行流程
（5）性能优化
1）HashMap执行写操作（put）的时候，比较消耗资源的是遍历链表，扩容数组操作。
2）HashMap执行读操作（get）的时候，比较消耗资源的是遍历链表。
提高HashMap的使用效率：
1）根据实际的业务需求，测试出合理的loadFactor，否则会始终使用Java建议的0.75。
2）合理的重写键值对象的hashCode和equals方法。
2.1.2 Java 8提供的HashMap
代表链表结点的Entry<K,V>换成了Node<K,V>，Node本身具备链表结点的特性，同时，它还有一个子类TreeNode<K,V>。Java 8里的HashMap使用的是数组+树+链表的结构。
（1）put(K,V)方法详解
主体流程：
1）获取key值的hashCode。
2）调用putVal方法进行存值。
3）resize方法。resize方法用于重新规划table长度和阈值，如果table长度发生了变化，那么部分数据结点也需要重新进行排列。
（2）红黑树
1）二叉查找树。
2）平衡二叉树（AVL树）。
3）红黑树（R-B树）。
红黑树也是一种自平衡二叉树，它的实现原理和平衡二叉树类似，但在统计上，它的性能要优于平衡二叉树。
五个特性：
①结点是红色或者黑色。
②根结点是黑色。
③每个叶子结点（NIL结点）为黑色。
④每个红色结点的两个子结点都是黑色
⑤从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。‘’
推论：从根到叶子的最长路径，不超过最短路径的两倍。
（3）红黑树在HashMap中的体现
1）treeifyBin方法。
当table容量小于最小建树容量（64）时，则调整table大小（resize）。由于resize的过程可以分解链表，所以无需转化链表为树。
2）putTreeVal方法用于保存树结点。
该方法执行二叉树查找，每一次都比较当前结点和待插入结点的大小，如果待插入结点较小，那么在当前结点左子树查找，否则在右子树查找。
3）balanceInsertion平衡插入方法。
4）rotateLeft和rotateRight方法。
2.2 TreeMap
与HashMap组合了数组、链表、红黑树不同，TreeMap是完全由红黑树实现的。
（1）成员变量
private final Comparator<? super K> comparator; //比较器，决定了结点在树中的分布
private transient Entry<K,V> root; //树的根节点
private transient int size = 0; //树中包含的实体数目
（2）构造方法
TreeMap有四个构造方法：
1）public TreeMap()。无参构造，初始化comparator=null。
2）public TreeMap(Comparator<? super K>comparator)。比较器构造，使用外部传入的比较器。
3）public TreeMap(Map<? extends K, ? extends V>m)。使用传入的Map初始化TreeMap的内容。
4）public TreeMap(SortedMap<K, ? extends V>m)。使用SortedMap初始化TreeMap内容，同时使用SortedMap的比较器来初始化TreeMap比较器。
（3）put方法
put的实现
1）如果TreeMap是空的，那么使用指定数据作为根结点。
2）反之，如果comparetor不为空，那么使用comparetor来决定插入位置；如果comparetor为空，那么认为key值实现了Comparable，直接调用compareTo方法来决定插入位置；如果key没有实现Comparable，那么抛出ClassCastException。
3）插入完成后，修复红黑树。
2.2.1 Java 8之前的LinkedHashMap
（1）成员变量
private transient Entry<K,V> header; //双向链表的表头
private final boolean accessOrder; //访问顺序，true为顺序访问，false为逆序
（2）createEntry(hash,key,value,index)方法
LinkedHashMap的createEntry除了完成HashMap的功能外，还把该链表结点的引用插入到了header环形链表里。
2.2.2 Java 8里的LinkedHashMap
（1）成员变量
transient LinkdHashMap.Entry<K,V> head; //双向链表表头，最旧的结点
transient LinkdHashMap.Entry<K,V> tail; //双向链表表尾，最新的结点
private final boolean accessOrder; //访问顺序，true为顺序访问，false为逆序
（2）linkNodeLast方法
（3）transferLinks方法
2.3 Hashtable
Hashtable的put过程：
1）计算key值的hashCode。
2）根据hashCode计算下标。
3）如果存在hashCode和key值完全相等的value，那么替换它并返回。
4）反之，如果总数据数超出了扩容阈值，那么对数组扩容，并重新计算所有的数据结点的下标。
5）为新数据创建新结点。
Hashtable是线程安全的，而HashMap是线程不安全的；此外Hashtable不能存放null作为key值，HashMap会把null key存在下标0位置。
2.4 WeakHashMap
WeakHashMap是一种种弱引用的HashMap，弱引用指的是WeakHashMap中的key值如果没有外部强引用，那么在垃圾回收的时候，WeakHashMap的对应内容也会被移除掉。
（1）Java的引用类型
Java中与引用的相关的类：
ReferenceQueue，引用队列
与某个引用类绑定，当引用死亡后，会进入这个队列。
HardReference，强引用
任何以类似String str=new String()建立起来的引用，都是强引用。在str指向另一个对象或者null之前，该String对象都不会被GC（Garbage Collector垃圾回收器）回收。
WeakReference，弱引用
可以通过java.lang.ref.WeakReference来建立弱引用，当GC要求回收对象时，它不会阻止对象被回收，也就是说即使有弱引用存在，该对象也会立刻被回收。（弱引用的对象，如果没有被强引用，那么在垃圾回收后，引用对象会不可达。）
SoftReference，软引用
可以通过java.lang.ref.SoftReference来建立，与弱引用类似，当GC要求回收时，它不会阻止对象被回收，但不同的是该回收过程会被延迟，必须要等到JVM heap内存不够用，接近产生OutOfMemory错误时，才会被回收。
PhantomReference，虚引用
可以通过java.lang.ref.PhantomPeference来建立，这种类型的引用很特别，在大多数时间里，无法通过它拿到其引用的对象，但是，当这个对象死亡的时候，该引用还是会进入ReferenceQueue队列。（虚引用非常弱，以至于它自己也找不到自己的引用内容。）
（2）WeakHashMap的实现方式
WeakHashMap利用了ReferenceQueue和WeakReference来实现它的核心功能：当key值没有强引用的时候，会从WeakHashMap里移除。
3 Set
Set是一个接口，这个接口约定了在其中的数据是不能重复的，它有许多不同的实现类。
3.1 HashSet
①HashSet中不会有重复的元素。
②HashSet中最多只允许有一个null。
特性：
①HashSet不是线程安全的，如果想使用线程安全的Set，那么可以使用CopyOnWrite ArraySet、Collections.synchronizedSet(Set set)、ConcurrentSkipListSet和Collections.newSetFromMap(NewConcurrentHashMap)。
②HashSet不会维护数据插入的顺序，如果想维护插入顺序，那么可以使用LinkedHashSet。
③HashSet也不会对数据进行排序，如果想对数据进行排序，那么可以使用TreeSet。
3.2 LinkedHashSet
LinkedHashSet是HashSet的扩展，HashSet并不维护数据的顺序，而LinkedHashSet维护了数据插入的顺序。HashSet在内部是使用HashMap来实现的，而LinkedHashSet内部通过LinkedHashMap来实现。
3.3 TreeSet
TreeSet中的数据是有序的，它默认使用的是数据的自然顺序，当然在创建TreeSet的时候也可以指定Comparator来对数据进行排序。