-2c57ec47146f40cbabf9adc9f224a0a3.jpg)
集合框架学习手册
今天先来一手集合学习，雷霆嘎巴。先来一个类设计图，所有使用的集合实现类中都是Collection和Map的派生。感受一下集合家族的势力范围。无情哈拉少。
两个老祖
这俩个老祖不是别人，就是Collection和Map，可不是Map继承了Collection接口，这么记可真是盖了帽了老北鼻。看看这蜘蛛网一般的家族，我特么心态崩了呀。先从南山不老松Collection看起，首先你得记住List Set Queen是基于Collection派生。
Collection
Collection规定了集合类型的所有行为，包含contains，isEmpty，add remove 等。Collection的模板类AbstractCollection实现了集合类中的contains之类的方法。1.8之后增加了创建Stream的行为。
List
List接口继承Collection接口。并且扩充了List特有的指定下标的操作，依据下标获取集合中的元素，删除指定下表的元素，依据下标获取子集合的行为。还有迭代器的功能
AbstractList
OK 我们来看下这个AbstractList,AbstractList这个抽象模板处理了什么呢。继承了AbstractCollection。实现了List接口，实现了迭代器的接口。同时这个静态内部类只用于list内部的。改迭代器广泛的用于indexOf之流的接口。同时定义了用于集合判断内部元素更改状况的modCount字段。同时还定义了SubList类用于执行sublist方法,当然还有针对集合边界的一系列的校验方法,是否下标越界，以及CMF异常等，唯独没有实现真正的集合的增删改查，这就得让我们去具体的List的实现子类中去观察了.
ArrayList
首先来看ArrayList，不多逼逼，这是个嘛玩意，基于数组的实现，我们看到这个内部的elements素数组，第一点想到了什么。莫大意的哦，沃特玛啥也想不到，看着架势是数组啊，第一点是首先得初始化吧，这就暗示了集合为啥初始化时候要指定容量，这哥们是数组实现啊.第二呢就是要说说扩增机制，往内部elements添加的同时需要去更新modCount，同时记录List的长度的字段size需要递增，当size达到capacity就得去考虑扩容。怎么说呢！ArrayList这里的扩容处理起来也比较骚气，就是新建一个原elements1.5倍的新数组，把原来的数组copy进去，为什么是1.5倍呢看ArrayList#grow方法你就明白了.跑去了上界下界的判断，真正的计算新数组的大小就是int newCapacity = oldCapacity + (oldCapacity >> 1);看明白了。
然后ArrayList这里呢要说一下使用比较多的foreach.，我们使用比较多，需要注意的呢就是不要再迭代的时候抛出来CME异常。
CME异常全名java.util.ConcurrentModificationException，这是为什么会抛出该异常呢。
由于集合内部是以顺序表存储，调用集合本身的每一次的新增或者修改都会修改modCount的结果，发生该异常是由于在当时用迭代器遍历的时候。当初创建迭代器对象会把集合本身的modCount做copy迭代器对象内部，，当你在没有使用迭代器的删除方法时，而使用的集合本身的方法例如remove发生修改时，由于fast-fail机制前置判断。就会在遍历过程中抛出这个运行时异常。
同时呢List为了适配1.8的Stram，他的静态内部类ArrayListSpliterator实现了Spliterator接口，用于了支持流操作。相当于之前的foream的快速失败的原则，在Stream中则是在后置判断的，这一点需要注意。
AbstractSequentialList
数组的逼逼完了，在类设计图中，你看着这个类AbstractSequentialList了吗，他是干啥的，你知道么。打开源代码分析一下。该类抽象了针对集合的两种线性表的数组和链表的支持如数组的随机访问和链表的顺序查找。
LinkedList
LinkedList这个类很强，细心的你可能会发现，他继承了AbstractSequentialList,说明也是拥有随机访问的特点的。就是时间复杂度不是很棒。使用链表我们就关注的是其新增，修改，内部维护一个Node的内部类用来实现链表。而且还偷偷的实现了Deque接口.所以LinkedList你也可以当双端队列来使用哦。言归正传，LinkedList类我们的关注点在哪里呢，由于是链表不存在长度的限制，所以没有数组时候的扩容问题，往链表内部添加默认是尾插法，当然我们也可以指定头插法使用addFirst方法，删除默认是删除头结点，当删除指定位置的节点的时候，Linklist这里处理是判断给定的index的值在链表的前半截还是后半截，前半截使用first指针遍历寻找next，后半段使用last指针遍历找prev, 找到之后解绑对应的节点，进过一系列的边界判断后，使用x.prev.next=x.next来删除。队列的几个方法：offer系列,peek系列,poll系列.都是双向操作。element返回的是头结点这一点LinkedList也没有进行特殊操作。。链表的基本也就是这么多。
Vector
让我们来看下Vector,怎么说呢，同样是基于数组方式的实现，和ArrayList的实现区别在于Vector的操作都是synchronized的。所以针对同一个Vector对象的访问在多线程中是线程安全。这个类在jdk1.2的时候添加进来，如果不需要线程安全的实现，建议使用ArrayList代替Vector。单线程情况可以使用ArrayList，当你在单线程情况下使用Verctor的，由于JDk1.7之后默认开启了逃逸分析，当没有竞争出现的时候会优化锁，达到锁消除。Vector内部的大部分操作的方法都是使用synchronized来修饰，当synchronized修改Vector类内的虚方法的时候，synchronized的监视器对象是以对象维度进行判断的。所有强调针对同一个Vector类进行多线程操作的时候是线程安全的，然而当Synchronized修饰类方法呢，最是锁定的元数据空间中的Klass指针。
Stack
这时候呢我们再来看Stack类，继承于Vector类，这个访问受限的线性表内部做了什么呢，栈我们都知道，所谓的操作只有出栈入栈和返回栈顶元素。所以直接看内部的push，pop，peek 就明白了。push是从开始处把元素插入数组，那pop呢则是使用peek会去到栈顶数据，然后更改Elements数组，把旧的数据做一下移位Copy。
Queen
Queen接口呢也是继承了Collection，但是增加了offer peek remove element的队列行为，这里队列行为主要在于:
peek是返回队列头部的元素，但是不会去出队。
element是返回这个队列的队头，如果不存在就会抛出Nosuch异常
poll会返回队列的头部，并且出队。
offer和add通常都是让元素入队，不同的是offer在队列长度已定的情况下，不会返回异常
AbstractQueue
AbstractQueue这个类干了什么工作呢，这里主要就是把，添加，删除，和清空，做了模板。实际也是使用上面的几个peek和offer系列。
PriorityQueue
PriorityQueue.优先级队列，内部使用数组实现，队列不允许使用 null 元素也不允许插入不可比较的对象(没有实现比较器接口的对象)。同时优先队列在多线程环境不是线程安全的。所以在多线程场景使用优先队列的话，需要处于加锁操作。底层数据结构是二叉堆，默认小顶堆，通过比较器规则可以为大顶堆。根节点总是大于左右子节点（大顶堆），或者是小于左右子节点（小顶堆）。直接定位内部的add方法和remove方法，PriorityQueue的add方法实际上调用的是offer方法，小顶堆的默认实现，如果新增加的数据比队列最后一个元素的父节点小需要把该元素上移，直到满足小顶堆之后，结束。反之比父节点大就直接添加在队列后边。
插入的调整堆结构使用的是siftUp方法。
基于二叉堆的特点我们就可以知道，父节点，左子树和右子树的位置。parent=k>>1, left=parent<<1+1,right=parent<<1+2.这个K是什么呢，在添加场景，就是新入队元素的下标、
public boolean add(E e) {
return offer(e);
}
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);
size = i + 1;
if (i == 0)
queue[0] = e;
else
siftUp(i, e);
return true;
}
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
看完了上面的实现是不是明白了小顶堆插入时候的原理。ok我们再来看删除AbstractQueue#remove方法。直接看默认其实就是调用pool(),是出队queen[0],删除堆顶元素必然导致堆结构发生改变，删除的时候会调用siftDown()来处理结构。siftDown()的执行流程如后图，说白了就是删除堆顶要从队列最后一个元素从后往前比对左右子树中最小的，来赋值，最后通过交换，把小顶堆的结构维护。
public E poll() {
if (size == 0)
return null;
int s = --size;
modCount++;
E result = (E) queue[0];
E x = (E) queue[s];
queue[s] = null;
if (s != 0)
siftDown(0, x);
return result;
}
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
int half = size >>> 1; // loop while a non-leaf
while (k < half) {
int child = (k << 1) + 1; // assume left child is least
Object c = queue[child];
int right = child + 1;
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
if (key.compareTo((E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = key;
}
至于peek就是直接返回堆顶元素queen[0].基于优先队列的LeetCode上的，在未排序的数组中找到第 k个最大的元素。需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。我们可以对其倒序然后取就可以，这里呢我们使用PriorityQueue来实现.思路是什么呢构建一个K个大小的小顶堆，当数据一直添加，当size超过K之后出队堆顶元素，最后返回堆顶元素即可，伪代码如下
PriorityQueue<Integer> heap =new PriorityQueue<Integer>();
for (int n: nums) {
heap.add(n);
if (heap.size() > k)
heap.poll();
}
return heap.poll();
Deque
在俩端支持插入和删除元素的线性集合。这个接口继承了Queue接口。
当Deque是作为队列使用，FIFO(先入先出)行为。元素是添加在结尾处，从开头移除。
| Queue Method | Deque Method |
| Queue#add add(e) | Deque#addLast addLast(e) |
| Queue#offer offer(e) | Deque#offerLast offerLast(e) |
| Queue#remove remove() | Deque#removeFirst removeFirst() |
| Queue#poll poll() | Deque#pollFirst pollFirst() |
| Queue#element element() | Deque#getFirst getFirst() |
| Queue#peek peek() | Deque#peek peekFirst() |
Deque也可以作为后进先出的堆栈使用。当deque被用作堆栈时，元素被推入和弹出deque的开头。
| Stack Method | Deque Method |
| Stack#push push(e) | Deque#addFirst addFirst(e) |
| Stack#pop pop() | Deque#removeFirst removeFirst() |
| Stack#peek peek() | Deque#peekFirst peekFirst() |
if (initialCapacity < 0) // Too many elements, must back off
initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
}
return initialCapacity;
}
规定最小值MIN_INITIAL_CAPACITY = 8，如果入参小于8，数组大小就定义成8；如果大于等于8，这一通右移是啥操作？假如我们传入了15，二进制01111，逐步分析下：
* initialCapacity |= (initialCapacity >>> 1)
> 右移1位作|操作，01111->00111，'或' 操作后01111
* initialCapacity |= (initialCapacity >>> 2)
>接上一步，右移2位作|操作，01111->00011，'或' 操作后01111
* initialCapacity |= (initialCapacity >>> 4)
>接上一步，右移4位作|操作，01111->00000，'或' 操作后 01111
* initialCapacity |= (initialCapacity >>> 8)
>接上一步，右移8位作| 01111->00000 ,01111 | 00000，结果是 01111
* initialCapacity |= (initialCapacity >>> 16)
>接上一步，右移8位作| 01111->00000 ,01111 | 00000，结果还是 01111
* initialCapacity++
>二进制数01111，+1之后10000，转换成十进制16
最终的负值判断（用于处理超int正向范围情况），最终得到了大于入参的2的次幂中最小的一个。那我下面这么写岂不是真香，同样也是获取入参的2的次幂最小的值。
int resultSize = 1;
while (resultSize < capacity) {
resultSize <<= 1;
}
return resultSize;
底层数组始终是2的次幂，为什么如此？说白了就是为了。当数组长度是2的次幂的时候，获取下标的操作 ` x & (length - 1) == x % length`，而对二进制的计算机来说位操作要比取模操作效率高。
### Set
Set接口也是继承了Collection接口，但是Set接口并没有增加集合的操作。
#### AbstractSet
这个类提供了`Set`的模板实现。只提供了removeAll的实现
#### SortedSet
这个接口继承Set接口，规定了实现该接口的实现类内部的元素是实现了比较器接口的。
#### NavigableSet
继承于的`SortedSet`,提供了给定搜索目标的最近匹配的实现
`lower`, `floor`、`ceiling`和` higher`返回元素分别小于、小于或等于、大于或等于，和大于给定元素，如果存在则返回,没有返回null。这几处可以在`TreeSet`中体现出来。
#### NavigableSet
继承于的`SortedSet`,提供了给定搜索目标的最近匹配的实现
`lower`, `floor`、`ceiling`和` higher`返回元素分别小于、小于或等于、大于或等于，和大于给定元素，如果存在则返回,没有返回null。这几处可以在`TreeSet`中体现出来。
#### EnumSet
EnumSet 是一个专为枚举设计的集合类，EnumSet中的所有元素都必须是指定枚举类型的枚举值，枚举类型在创建时需要指定。不存null，关键查看一下` SharedSecrets.getJavaLangAccess()`,使用到SharedSecrets和JavaLangAccess，通过这两个类来获取JVM里面的实例对象信息，然后进行挑选，从而找出调用的类。看到这里发现其调用的是`getEnumConstantsShared`.是从执行枚举类的values中获取所有的枚举值。基于位操作，之后的枚举值的集合处理可以使用，官方推介。下面俩个实现类无需手动指定，是基于`getEnumConstantsShared`的返回元素的数量创建的。
##### JumboEnumSet
巨型枚举集合枚举值的集合元素超过64个之后。
##### RegularEnumSet
巨型枚举集合枚举值的集合元素小于64个。
#### HashSet
##### TreeSet
## Map