Collections之Map&List&Set详解完整版

HashMap
数据结构
源码原理分析
重要成员变量
内部的执行机制源码
Jdk7-扩容死锁分析
单线程扩容
多线程扩容
Jdk8-扩容
ConcurrentHashMap
数据结构
并发安全控制
源码原理分析
重要成员变量
协助扩容helpTransfer
扩容transfer
总结
CopyOnWrite机制
源码原理
HashMap
数据结构
数组+链表+(红黑树jdk>=8)
源码原理分析
重要成员变量
DEFAULT_INITIAL_CAPACITY = 1 << 4; Hash表默认初始容量
MAXIMUM_CAPACITY = 1 << 30; 最大Hash表容量
DEFAULT_LOAD_FACTOR = 0.75f；默认加载因子
TREEIFY_THRESHOLD = 8；链表转红黑树阈值
UNTREEIFY_THRESHOLD = 6；红黑树转链表阈值
MIN_TREEIFY_CAPACITY = 64；链表转红黑树时hash表最小容量阈值，达不到优先扩容。
内部的执行机制源码
见课堂讲解。
HashMap是线程不安全的，不安全的具体原因就是在高并发场景下，扩容可能产生死锁(Jdk1.7存在)以及get操作可能带来的数据丢失。
Jdk7-扩容死锁分析
死锁问题核心在于下面代码，多线程扩容导致形成的链表环!
```void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry e : table) { while (null != e) { Entry next = e.next;//第一行 if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity);//第二行 e.next = newTable[i];//第三行 newTable[i] = e;//第四行 e = next;//第五行 } }}```
去掉了一些冗余的代码，层次结构更加清晰了。
第一行：记录oldhash表中e.next
第二行：rehash计算出数组的位置(hash表中桶的位置)
第三行：e要插入链表的头部，所以要先将e.next指向new hash表中的第一个元素
第四行：将e放入到new hash表的头部
第五行：转移e到下一个节点，继续循环下去
单线程扩容
假设：hash算法就是简单的key与length(数组长度)求余。hash表长度为2，如果不扩容，那么元素key为3,5,7按照计算(key%table.length)的话都应该碰撞到table[1]上。
扩容：hash表长度会扩容为4重新hash，key=3会落到table[3]上(3%4=3)，当前e.next为key(7),继续while循环重新hash，key=7会落到table[3]上(7%4=3),产生碰撞，这里采用的是头插入法，所以key=7的Entry会排在key=3前面(这里可以具体看while语句中代码)当前e.next为key(5),继续while循环重新hash，key=5会落到table[1]上(5%4=3)，当前e.next为null,跳出while循环，resize结束。
如下图所示
https://share.note.youdao.com/yws/public/resource/1101e17b43e1d8f57a7de05e2464fb8a/xmlnote/BF5FC4BE6C174E918B6177C7E27D37D7/51165
多线程扩容
下面就是多线程同时put的情况了，然后同时进入transfer方法中：假设这里有两个线程同时执行了put()操作，并进入了transfer()环节
```while (null != e) { Entry next = e.next;//第一行，线程1执行到此被调度挂起 int i = indexFor(e.hash, newCapacity);//第二行 e.next = newTable[i];//第三行 newTable[i] = e;//第四行 e = next;//第五行}```
那么此时状态为：
https://share.note.youdao.com/yws/public/resource/1101e17b43e1d8f57a7de05e2464fb8a/xmlnote/E83018E9FC4E4E63BE0E84CEA1C2D184/51168
从上面的图我们可以看到，因为线程1的e指向了key(3)，而next指向了key(7)，在线程2 rehash后，就指向了线程2 rehash后的链表。
然后线程1被唤醒了：
执行e.next = newTable[i]，于是key(3)的next指向了线程1的新Hash表，因为新Hash表为空，所以e.next = null，
执行newTable[i] = e，所以线程1的新Hash表第一个元素指向了线程2新Hash表的key(3)。好了，e处理完毕。
执行e = next，将e指向next，所以新的e是key(7)
然后该执行key(3)的next节点key(7)了:
现在的e节点是key(7)，首先执行Entry next = e.next,那么next就是key(3)了
执行e.next = newTable[i]，于是key(7)的next就成了key(3)
执行newTable[i] = e，那么线程1的新Hash表第一个元素变成了key(7)
执行e = next，将e指向next，所以新的e是key(3)
此时状态为：
https://share.note.youdao.com/yws/public/resource/1101e17b43e1d8f57a7de05e2464fb8a/xmlnote/42A463F4CBC445309B7EC32E33F320AC/51166
然后又该执行key(7)的next节点key(3)了：
现在的e节点是key(3)，首先执行Entry next = e.next,那么next就是null
执行e.next = newTable[i]，于是key(3)的next就成了key(7)
执行newTable[i] = e，那么线程1的新Hash表第一个元素变成了key(3)
执行e = next，将e指向next，所以新的e是key(7)
这时候的状态如图所示：
https://share.note.youdao.com/yws/public/resource/1101e17b43e1d8f57a7de05e2464fb8a/xmlnote/593E2313CA0F4D3BA2F8D09B71825447/51163
很明显，环形链表出现了。
Jdk8-扩容
Java8 HashMap扩容跳过了Jdk7扩容的坑，对源码进行了优化，采用高低位拆分转移方式，避免了链表环的产生。
扩容前：
https://share.note.youdao.com/yws/public/resource/1101e17b43e1d8f57a7de05e2464fb8a/xmlnote/9DA6273513CA4A00A324FB40F1336429/51160
扩容后：
https://share.note.youdao.com/yws/public/resource/1101e17b43e1d8f57a7de05e2464fb8a/xmlnote/ED9E55321DF6443C9C67AC9CFBFE59A6/51162
由于Jdk8引入了新的数据结构，所以put方法过程也有了一定改进，其过程如下图所示。
https://share.note.youdao.com/yws/public/resource/1101e17b43e1d8f57a7de05e2464fb8a/xmlnote/7CB1549D0EAC48D8B16EBA501F6306C9/51164
ConcurrentHashMap
数据结构
ConcurrentHashMap的数据结构与HashMap基本类似，区别在于：1、内部在数据写入时加了同步机制(分段锁)保证线程安全，读操作是无锁操作；2、扩容时老数据的转移是并发执行的，这样扩容的效率更高。
并发安全控制
Java7 ConcurrentHashMap基于ReentrantLock实现分段锁
https://share.note.youdao.com/yws/public/resource/1101e17b43e1d8f57a7de05e2464fb8a/xmlnote/310F2DF77FC54F1BBE41316A8E547354/51169
Java8中ConcurrentHashMap基于分段锁+CAS保证线程安全，分段锁基于synchronized关键字实现；
https://share.note.youdao.com/yws/public/resource/1101e17b43e1d8f57a7de05e2464fb8a/xmlnote/A919D6E53664432B85F6B5DAB0A04ED9/51167
源码原理分析
重要成员变量
ConcurrentHashMap拥有出色的性能,在真正掌握内部结构时,先要掌握比较重要的成员:
LOAD_FACTOR:负载因子,默认75%,当table使用率达到75%时,为减少table的hash碰撞,tabel长度将扩容一倍。负载因子计算:元素总个数%table.lengh
TREEIFY_THRESHOLD:默认8,当链表长度达到8时,将结构转变为红黑树。
UNTREEIFY_THRESHOLD:默认6,红黑树转变回为链表的阈值。
MIN_TRANSFER_STRIDE:默认16,table扩容时,每个线程最少迁移table的槽位个数。
MOVED:值为-1,当Node.hash为MOVED时,代表着table正在扩容
TREEBIN,置为-2,代表此元素后接红黑树。
nextTable:table迁移过程临时变量,在迁移过程中将元素全部迁移到nextTable上。
sizeCtl:用来标志table初始化和扩容的,不同的取值代表着不同的含义:
0:table还没有被初始化
-1:table正在初始化
小于-1:实际值为resizeStamp(n)<1的元素开始迁移,transferIndex代表当前已经迁移的元素下标
ForwardingNode:一个特殊的Node节点,其hashcode=MOVED,代表着此时table正在做扩容操作。扩容期间,若table某个元素为null,那么该元素设置为ForwardingNode,当下个线程向这个元素插入数据时,检查hashcode=MOVED,就会帮着扩容。
ConcurrentHashMap由三部分构成,table+链表+红黑树,其中table是一个数组,既然是数组,必须要在使用时确定数组的大小,当table存放的元素过多时,就需要扩容,以减少碰撞发生次数,本文就讲解扩容的过程。扩容检查主要发生在插入元素(putVal())的过程:
一个线程插完元素后,检查table使用率,若超过阈值,调用transfer进行扩容
一个线程插入数据时,发现table对应元素的hash=MOVED,那么调用helpTransfer()协助扩容。
协助扩容helpTransfer
下面是协助扩容的过程
```final Node[] helpTransfer(Node[] tab, Node f) { //table扩容 Node[] nextTab; int sc; if (tab != null && (f instanceof ForwardingNode) && (nextTab = ((ForwardingNode)f).nextTable) != null) { // 根据length得到一个标识符号 int rs = resizeStamp(tab.length); while (nextTab == nextTable && table == tab && (sc = sizeCtl) >> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || //达到最大的帮助线程 || 判断扩容转移下标是否在调整（扩容结束） sc == rs + MAX_RESIZERS || transferIndex <= 0) break; // 将sizeCtl +1,（表示增加了一个线程帮助其扩容） if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) { transfer(tab, nextTab); break; } } return nextTab; } return table;}```
主要做了如下事情:
检查是否扩容完成
对sizeCtrl = sizeCtrl+1,然后调用transfer()进行真正的扩容。
扩容transfer
扩容的整体步骤就是新建一个nextTab,size是之前的2倍,将table上的非空元素迁移到nextTab上面去。
```private final void transfer(Node[] tab, Node[] nextTab) { int n = tab.length, stride; if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE) // subdivide range，每个线程最少迁移16个槽位，大的话，最多 stride = MIN_TRANSFER_STRIDE; // initiating 才开始初始化新的nextTab if (nextTab == null) { try { @SuppressWarnings("unchecked") Node[] nt = (Node[])new Node[n << 1]; //扩容2倍 nextTab = nt; } catch (Throwable ex) { // try to cope with OOME sizeCtl = Integer.MAX_VALUE; return; } nextTable = nextTab; transferIndex = n;//更新的转移下标， } int nextn = nextTab.length; ForwardingNode fwd = new ForwardingNode(nextTab); //是否能够向前推进到下一个周期 boolean advance = true; // to ensure sweep before committing nextTab，完成状态，如果是，则结束此方法 boolean finishing = false; for (int i = 0, bound = 0;;) { Node f; int fh; while (advance) { //取下一个周期 int nextIndex, nextBound; //本线程处理的区间范围为[bound, i),范围还没有处理完成，那么就继续处理 if (--i >= bound || finishing) advance = false; //目前处理到了这里（从大到小，下线），开始找新的一轮的区间 else if ((nextIndex = transferIndex) stride ? nextIndex - stride : 0))) { bound = nextBound; //一块区间最小桶的下标 i = nextIndex - 1; //能够处理的最大桶的下标 advance = false; } } if (i = n || i + n >= nextn) { //每个迁移线程都能达到这里 int sc; if (finishing) { //迁移完成 nextTable = null; //直接把以前的table丢弃了，上面的MOVE等标志全部丢弃，使用新的 table = nextTab; sizeCtl = (n <>> 1); //扩大2n-0.5n = 1.50n, 更新新的容量阈值 return; } //表示当前线程迁移完成了 if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) { //注意此时sc的值并不等于sizeCtl，上一步，sizeCtl=sizeCtl-1了。这两个对象还是分割的 if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT) return; finishing = advance = true; i = n; // recheck before commit } } //如果对应位置为null，则将ForwardingNode放在对应的地方 else if ((f = tabAt(tab, i)) == null) advance = casTabAt(tab, i, null, fwd); else if ((fh = f.hash) == MOVED) //别的线程已经在处理了，再推进一个下标 advance = true; // already processed，推动到下一个周期，仍然会检查i与bound是否结束 else { //说明位置上有值了， //需要加锁，防止再向里面放值，在放数据时，也会锁住。比如整个table正在迁移，还没有迁移到这个元素，另外一个线程向这个节点插入数据，此时迁移到这里了，会被阻塞住 synchronized (f) { if (tabAt(tab, i) == f) { //判断i下标和f是否相同 Node ln, hn; //高位桶，地位桶 if (fh >= 0) { int runBit = fh & n;//n为2