大纲
1.为什么要对JDK源码剖析
2.ArrayList源码一：基本原理以及优缺点
3.ArrayList源码二：核心方法的原理
4.ArrayList源码三：数组扩容以及元素拷贝
5.LinkedList源码一：优缺点和使用场景
6.LinkedList源码二：双向链表数据结构
7.LinkedList源码三：插入元素的原理
8.LinkedList源码四：获取元素的原理
9.LinkedList源码五：删除元素的原理
10.Vector和Stack：栈的数据结构和源码
11.HashMap源码一：数组 + 链表 + 红黑树
12.HashMap源码二：核心成员变量的作用
13.HashMap源码三：降低哈希冲突概率的算法
14.HashMap源码四：put操作及哈希寻址算法
15.HashMap源码五：哈希冲突时的链表处理
16.HashMap源码六：引入红黑树优化哈希冲突
17.HashMap源码七：哈希冲突时插入红黑树
18.HashMap源码八：JDK 1.7的数组扩容原理
19.HashMap源码九：JDK 1.8的数组扩容原理
20.HashMap源码十：get与remove操作源码
21.LinkedHashMap有顺序的Map数据结构
22.TreeMap可自定义排序规则的红黑树Map
23.HashSet + LinkedHashSet + TreeSet简介
24.迭代器应对多线程并发修改的Fail-Fast机制
14.HashMap源码四：put操作及哈希寻址算法
(1)HashMap.put()方法的源码
(2)HashMap数组的初始化
(3)通过位与运算的哈希寻址算法设置数组值
(1)HashMap.put()方法的源码
首先会通过HashMap.hash()方法的哈希算法根据key获取其哈希值，然后调用HashMap.putVal()方法把对应的键和值设置到HashMap数组。
public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node[] tab; Node p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0) {
n = (tab = resize()).length;
}
if ((p = tab[i = (n - 1) & hash]) == null) {
tab[i] = newNode(hash, key, value, null);
} else {
Node e; K k;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
e = p;
} else if (p instanceof TreeNode) {
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
} else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) {// -1 for 1st
treeifyBin(tab, hash);
}
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
break;
}
p = e;
}
}
if (e != null) {// existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null) {
e.value = value;
}
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold) {
resize();
}
afterNodeInsertion(evict);
return null;
}
...
} (2)HashMap数组的初始化
HashMap的构造方法只是对HashMap的负载因子和扩容阈值进行赋值，而具体的HashMap的数组初始化则是在执行put()方法时处理的。
假设一开始是通过HashMap的无参构造函数创建一个HashMap对象，然后第一次执行该HashMap对象的put()方法时HashMap的数组为空。
于是在执行"tab = resize()"代码，来对HashMap数组的初始化时，会初始化数组大小为默认16，负载因子为默认0.75，扩容阈值为12。也就是会初始化一个大小为16的、元素为Node的数组。
public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node[] tab; Node p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0) {
n = (tab = resize()).length;
}
...
}
//Initializes or doubles table size.
//If null, allocates in accord with initial capacity target held in field threshold.
//Otherwise, because we are using power-of-two expansion,
//the elements from each bin must either stay at same index,
//or move with a power of two offset in the new table.
final Node[] resize() {
//第一次执行HashMap的put()方法时，table为null
Node[] oldTab = table;//原数组
int oldCap = (oldTab == null) ? 0 : oldTab.length;//原数组大小
int oldThr = threshold;//默认的无参构造函数下，扩容阈值threshold为null
int newCap, newThr = 0;//新数组大小，新扩容阈值
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) {
newThr = oldThr << 1;// double threshold
}
} else if (oldThr > 0) {// initial capacity was placed in threshold
newCap = oldThr;
} else {
//默认的数组大小16
newCap = DEFAULT_INITIAL_CAPACITY;
//扩容阈值 = 16 * 1.75 = 12
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node[] newTab = (Node[])new Node[newCap];
table = newTab;
...
return newTab;
}
...
} (3)通过位与运算的哈希寻址算法设置数组值
接着执行"hash & (n - 1)"代码，其中n是16，所以变成"15 & hash"：
1111 1111 1111 1111 0000 0101 1000 0011
0000 0000 0000 0000 0000 0000 0000 1111位与操作：就是必须都是1，才是1，否则就是0。所以"15 & hash"的结果是：
0000 0000 0000 0000 0000 0000 0000 0011转成10进制就是3，因此index = 3。所以哈希寻址算法并不是直接用hash值对数组大小取模来实现的。因为取模的操作性能不高，而位运算的性能很高，一般会通过位与操作来实现取模的效果。
public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node[] tab; Node p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0) {
n = (tab = resize()).length;
}
if ((p = tab[i = (n - 1) & hash]) == null) {
tab[i] = newNode(hash, key, value, null);
}
...
}
Node newNode(int hash, K key, V value, Node next) {
return new Node<>(hash, key, value, next);
}
//Basic hash bin node, used for most entries.
//(See below for TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
static class Node implements Map.Entry {
final int hash;
final K key;
V value;
Node next;
Node(int hash, K key, V value, Node next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
...
}
...
} JDK1.8对HashMap的一个优化就是：数组刚开始的初始值以及未来每次扩容的值，都是2的n次方。只要保证数组大小是2的n次方，就可以保证："(数组大小 - 1) & hash"与"hash % 数组大小"的结果一样。
注意：a对2的n次方取模等价于a和2的n次方-1的结果进行位与。
通过hash & (n - 1)，就能将任意一个hash值定位到数组的某个index里。直接取模的性能相对较低，所以这是HashMap提升性能的一个优化点，这也是HashMap底层原理里的重要部分。
15.HashMap源码五：哈希冲突时的链表处理
两个key的hash值不同，但通过哈希寻址算法定位到数组的同一个index。此时就会出现典型的哈希冲突，默认情况下会使用单向链表来处理。
public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {
static final int TREEIFY_THRESHOLD = 8;//链表转红黑树的阈值
...
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node[] tab; Node p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0) {
n = (tab = resize()).length;
}
if ((p = tab[i = (n - 1) & hash]) == null) {
//如果通过哈希寻址算法定位到的下标为i的数组元素为空(即tab[i]为空)
//那么就可以直接将一个新创建的Node对象放到数组的tab[i]这个位置；
tab[i] = newNode(hash, key, value, null);
} else {
Node e; K k;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
//通过哈希寻址算法定位到的数组位置已有Node元素
//那么判断是否为相同的key，如果是相同的key则进行value覆盖
e = p;
} else if (p instanceof TreeNode) {
//通过哈希寻址算法定位到的数组位置已有Node元素，而且不是相同的key
//那么通过"p instanceof TreeNode)"，判断数组的tab[i]元素是否是一颗红黑树
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
} else {
//如果通过哈希寻址算法定位到的数组位置已有Node元素，且判断出不是相同的key，且数组的tab[i]元素也不是一颗红黑树
//那么则说明数组的tab[i]元素是一个链表，于是通过"p.next = newNode()"这行代码将新元素串入到链表中
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果链表的长度大于等于8，则将这个链表转换成一个红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) {// -1 for 1st
treeifyBin(tab, hash);
}
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
break;
}
p = e;
}
}
if (e != null) {//existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null) {
e.value = value;
}
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold) {
resize();
}
afterNodeInsertion(evict);
return null;
}
...
} 其中的分支代码"if ((p = tab[i = (n - 1) & hash]) == null)"的意思是：如果通过哈希寻址算法定位到的下标为i的数组元素为空(即tab[i]为空)，那么就可以直接将一个新创建的Node对象放到数组的tab[i]这个位置。
如果通过哈希寻址算法定位到的数组位置已有Node元素，那么会判断是否为相同的key，如果是相同的key则进行value覆盖。如果不是相同的key，那么通过"p instanceof TreeNode)"，判断数组的tab[i]元素是否是一颗红黑树。
如果通过哈希寻址算法定位到的数组位置已有Node元素，且判断出不是相同的key，且数组的tab[i]元素也不是一颗红黑树，那么则说明数组的tab[i]元素是一个链表，于是通过"p.next = newNode()"这行代码将新元素串入到链表尾部。
最后判断当前链表的长度是否已经大于等于8。如果是，则通过调用treeifyBin()方法将这个链表转换成一个红黑树。
16.HashMap源码六：引入红黑树优化哈希冲突
(1)红黑树的查找复杂度比链表的低
(2)链表转红黑树的处理
(3)总结
(1)红黑树的查找复杂度比链表的低
如果出现大量的哈希冲突后，某位置挂的一个链表可能会特别的长。如果链表长度太长，那么就会导致有一些get()操作的时间复杂度就是O(n)。虽然通过table[i]数组索引直接定位元素的时间复杂度是O(1)，但如果链表存在大量元素，会是导致对该链表get()操作的性能急剧下降的。
所以JDK 1.8以后进行了HashMap优化：如果链表的长度达到8，那么就会将链表转换为红黑树。如果对红黑树进行get()操作，那么时间复杂度会变成O(logn)。红黑树查找的O(logn)远比链表查找的O(n)低，性能得到大幅提升。
(2)链表转红黑树的处理
//如果通过哈希寻址算法定位到的数组位置已有Node元素，且判断出不是相同的key，且数组的tab[i]元素也不是一颗红黑树
//那么则说明数组的tab[i]元素是一个链表，于是通过"p.next = newNode()"这行代码将新元素串入到链表中
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果链表的长度大于等于8，则将这个链表转换成一个红黑树；
if (binCount >= TREEIFY_THRESHOLD - 1) {// -1 for 1st
treeifyBin(tab, hash);
}
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
break;
}
p = e;
}当遍历到链表的第7个结点时，binCount是6。当遍历到链表的第8个结点时，binCount是7。当向链表准备挂上第9个结点时，就会发现binCount >= 7了。达到了临界值，此时就会将链表转换为红黑树。
public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {
...
//Replaces all linked nodes in bin at index for given hash unless table is too small, in which case resizes instead.
final void treeifyBin(Node[] tab, int hash) {
int n, index; Node e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) {
resize();
} else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode hd = null, tl = null;
//通过do while循环将Node类型的单向链表转换为TreeNode类型的双向链表
do {
TreeNode p = replacementTreeNode(e, null);
if (tl == null) {
//设置双向链表的头结点
hd = p;
} else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
//调用TreeNode的treeify()方法将TreeNode类型的双向链表转换成一棵红黑树
if ((tab[index] = hd) != null) {
hd.treeify(tab);
}
}
}
//将Node类型的结点转换成TreeNode类型的结点
TreeNode replacementTreeNode(Node p, Node next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
...
} 上面的do while循环执行完之后，只是将Node类型的单向链表转换为TreeNode类型的双向链表，接着会将TreeNode类型的双向链表的头结点设置为数组元素tab[index]，然后执行双向链表头结点的treeify()方法将双向链表转为一棵红黑树。
(3)总结
一.出现哈希冲突的两种情况
情况一：key不一样但hashCode()方法重写出问题，导致Hash值一样
情况二：key不一样且Hash值也不一样，但定位到的数组位置一样
二.出现哈希冲突后的处理
首先会将元素放到单向链表中存放。如果链表长度超过8，则单向链表先变成双向链表，然后再转成红黑树。之后，会将元素放到红黑树中存放。以下是双向链表转红黑树的方法源码：
public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {
...
//Entry for Tree bins.
//Extends LinkedHashMap.Entry (which in turn extends Node) so can be used as extension of either regular or linked node.
static final class TreeNode extends LinkedHashMap.Entry {
TreeNode parent;//red-black tree links
TreeNode left;
TreeNode right;
TreeNode prev;//needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node next) {
super(hash, key, val, next);
}
//Forms tree of the nodes linked from this node.
final void treeify(Node[] tab) {
TreeNode root = null;
for (TreeNode x = this, next; x != null; x = next) {
next = (TreeNode)x.next;
x.left = x.right = null;
if (root == null) {
x.parent = null;
x.red = false;
root = x;
} else {
K k = x.key;
int h = x.hash;
Class kc = null;
for (TreeNode p = root;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h) {
dir = -1;
} else if (ph < h) {
dir = 1;
} else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) {
dir = tieBreakOrder(k, pk);
}
TreeNode xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0) {
xp.left = x;
} else {
xp.right = x;
}
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}
...
}
...
}
public class LinkedHashMap extends HashMap implements Map {
...
static class Entry extends HashMap.Node {
Entry before, after;
Entry(int hash, K key, V value, Node next) {
super(hash, key, value, next);
}
}
...
} 17.HashMap源码七：哈希冲突时插入红黑树
假设现在某个table[i]已经是一颗红黑树了。如果此时在table[i]再次出现哈希冲突，则会在红黑树中插入一个元素，也就是在HashMap的putVal()方法中调用TreeNode的putTreeVal()方法。红黑树是一个平衡的二叉查找树，插入元素时需要变色、旋转。TreeNode.putTreeVal()方法会在保持平衡的前提下，插入元素到红黑树。
public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {
static final int TREEIFY_THRESHOLD = 8;//链表转红黑树的阈值
...
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node[] tab; Node p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0) {
n = (tab = resize()).length;
}
if ((p = tab[i = (n - 1) & hash]) == null) {
//如果通过哈希寻址算法定位到的下标为i的数组元素为空(即tab[i]为空)
//那么就可以直接将一个新创建的Node对象放到数组的tab[i]这个位置；
tab[i] = newNode(hash, key, value, null);
} else {
Node e; K k;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
//通过哈希寻址算法定位到的数组位置已有Node元素
//那么判断是否为相同的key，如果是相同的key则进行value覆盖
e = p;
} else if (p instanceof TreeNode) {
//通过哈希寻址算法定位到的数组位置已有Node元素，而且不是相同的key
//那么通过"p instanceof TreeNode)"，判断数组的tab[i]元素是否是一颗红黑树
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
} else {
...
}
...
}
++modCount;
if (++size > threshold) {
resize();
}
afterNodeInsertion(evict);
return null;
}
...
//Entry for Tree bins.
//Extends LinkedHashMap.Entry (which in turn extends Node) so can be used as extension of either regular or linked node.
static final class TreeNode extends LinkedHashMap.Entry {
TreeNode parent;//red-black tree links
TreeNode left;
TreeNode right;
TreeNode prev;//needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node next) {
super(hash, key, val, next);
}
...
//Tree version of putVal.
final TreeNode putTreeVal(HashMap map, Node[] tab, int h, K k, V v) {
Class kc = null;
boolean searched = false;
TreeNode root = (parent != null) ? root() : this;
for (TreeNode p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h) {
dir = -1;
} else if (ph < h) {
dir = 1;
} else if ((pk = p.key) == k || (k != null && k.equals(pk))) {
return p;
} else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode q, ch;
searched = true;
if (((ch = p.left) != null && (q = ch.find(h, k, kc)) != null) || ((ch = p.right) != null && (q = ch.find(h, k, kc)) != null)) {
return q;
}
}
dir = tieBreakOrder(k, pk);
}
TreeNode xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node xpn = xp.next;
TreeNode x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0) {
xp.left = x;
} else {
xp.right = x;
}
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null) {
((TreeNode)xpn).prev = x;
}
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
...
}
...
} 18.HashMap源码八：JDK 1.7的数组扩容原理
(1)HashMap的扩容会进行两倍扩容 + rehash
(2)HashMap的扩容原理总结
(1)HashMap的扩容会进行两倍扩容 + rehash
由于HashMap底层是基于数组来实现的，所以和ArrayList一样存在扩容的问题。也就是如果数组满了，那么就必须要扩容。
HashMap扩容的原理非常简单：2倍扩容 + rehash。每个key-value对，都会基于key的hash值重新寻址找到新数组的新位置。
原来数组的长度是16，现在新数组的长度是32。原来所有的key的hash对16取模是一个位置，比如index = 5。但是如果对32取模，可能就是index = 11，位置可能变化。
(2)HashMap的扩容原理总结
一.基于数组实现
二.一次扩容2倍
三.rehash的过程
在rehash的过程中，很多key在新数组的位置可能都不一样了，之前存在冲突的key可能在新的数组里分布在不同的位置上了。
上述便是JDK 1.7以前的扩容原理，通过取模实现哈希寻址。在JDK 1.8以后，则通过位与来实现哈希寻址。
19.HashMap源码九：JDK 1.8的数组扩容原理
(1)出现hash冲突的例子
(2)数组扩容的源码
(3)数组扩容后的例子
(4)HashMap的底层原理总结
JDK 1.8为提升rehash性能，不再使用key的hash值对新数组大小取模。而使用位与操作实现哈希寻址，因为直接取模的性能比较低。
(1)出现hash冲突的例子
如下两个hash值会出现哈希冲突，HashMap使用链表 + 红黑树解决。
n - 1 0000 0000 0000 0000 0000 0000 0000 1111
hash值1 1111 1111 1111 1111 0000 1111 0000 0101
&结果 0000 0000 0000 0000 0000 0000 0000 0101 = 5（index = 5的位置）
n - 1 0000 0000 0000 0000 0000 0000 0000 1111
hash值2 1111 1111 1111 1111 0000 1111 0001 0101
&结果 0000 0000 0000 0000 0000 0000 0000 0101 = 5（index = 5的位置）(2)数组扩容的源码
每次执行HashMap的put()方法(也就是执行HashMap的putVal()方法)，将一个新的key-value对放入到HashMap的数组之后，就会对size自增。
接着会判断数组大小size，是否已经达到了扩容阈值threshold大小。如果已经达到扩容阈值，那么就执行HashMap的resize()方法进行扩容。
public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {
static final int TREEIFY_THRESHOLD = 8;//链表转红黑树的阈值
...
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node[] tab; Node p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0) {
n = (tab = resize()).length;
}
if ((p = tab[i = (n - 1) & hash]) == null) {
//如果通过哈希寻址算法定位到的下标为i的数组元素为空(即tab[i]为空)
//那么就可以直接将一个新创建的Node对象放到数组的tab[i]这个位置；
tab[i] = newNode(hash, key, value, null);
} else {
Node e; K k;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
//通过哈希寻址算法定位到的数组位置已有Node元素
//那么判断是否为相同的key，如果是相同的key则进行value覆盖
e = p;
} else if (p instanceof TreeNode) {
//通过哈希寻址算法定位到的数组位置已有Node元素，而且不是相同的key
//那么通过"p instanceof TreeNode)"，判断数组的tab[i]元素是否是一颗红黑树
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
} else {
...
}
...
}
++modCount;
//判断数组大小size，是否已经达到了扩容阈值threshold大小
if (++size > threshold) {
resize();
}
afterNodeInsertion(evict);
return null;
}
final Node[] resize() {
Node[] oldTab = table;//原数组
int oldCap = (oldTab == null) ? 0 : oldTab.length;//原数组大小
int oldThr = threshold;//原扩容阈值
int newCap, newThr = 0;//新数组大小，新扩容阈值
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) {
//newCap = oldCap << 1，就是乘以2，新数组的大小是原数组的2倍
newThr = oldThr << 1; // double threshold
}
} else if (oldThr > 0) {// initial capacity was placed in threshold
newCap = oldThr;
} else {// zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node[] newTab = (Node[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//如果e.next是null的话，这个位置的元素不是链表也不是红黑树
if (e.next == null) {
//那么此时就是用e.hash & newCap(新数组的大小) - 1，进行与运算
//直接定位到新数组的某个位置，然后直接就放在新数组里
newTab[e.hash & (newCap - 1)] = e;
} else if (e instanceof TreeNode) {
//如果这个位置是一个红黑树的话，此时会调用split()方法，去里面遍历这颗红黑树
//然后将里面每个结点都进行重新hash寻址，找到新数组的位置
((TreeNode)e).split(this, newTab, j, oldCap);
} else {//preserve order
//进入这个else分支的话，证明是链表
Node loHead = null, loTail = null;//旧链表
Node hiHead = null, hiTail = null;//新链表
Node next;
//对链表的处理逻辑
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null) {
loHead = e;
} else {
loTail.next = e;
}
loTail = e;
} else {
if (hiTail == null) {
hiHead = e;
} else {
hiTail.next = e;
}
hiTail = e;
}
} while ((e = next) != null);
//要么直接放在新数组的原来的那个index，要么就是原来的index + oldCap
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
} (3)数组扩容后的例子
如果数组的长度扩容之后为32，需要重新对每个hash值进行寻址，也就是用每个hash值跟新数组的length - 1进行与操作。
n-1 0000 0000 0000 0000 0000 0000 0001 1111
hash值1 1111 1111 1111 1111 0000 1111 0000 0101
&结果 0000 0000 0000 0000 0000 0000 0000 0101 = 5（index = 5的位置）
n-1 0000 0000 0000 0000 0000 0000 0001 1111
hash值2 1111 1111 1111 1111 0000 1111 0001 0101
&结果 0000 0000 0000 0000 0000 0000 0001 0101 = 21（index = 21的位置）可见hash2的位置，从原来的5变成了21 = 6 + 原数组大小16。也就是说，HashMap的数组大小每次扩容2倍后，比如从16到32到64，元素要么停留在原index位置，要么移动到原index + 原数组大小位置。以上就是JDK 1.8以后，数组扩容时元素重新寻址的过程。
(4)HashMap的底层原理总结
一.哈希算法
为什么要对key的HashCode进行高低位的异或运算？
因为可以降低数组大小为16时的哈希冲突的概率。(h = key.hashCode()) ^ (h >>> 16);
二.哈希寻址
为什么是hash值和数组.length - 1进行与运算？
因为位与的性能比取模要高：tab[(n - 1) & hash];
三.哈希冲突处理
首先将元素存到单向链表中，当单向链表的元素超8个时，再将单向链表转双向链表再转红黑树。
四.数组扩容机制
每次按原数组大小2倍扩容，并按hash & (n - 1)进行重新寻址(rehash)。重新寻址时，会判断hash & (n - 1)的二进制结果是否多出一个bit的1。如果是，那么重新寻址后的位置就是index + oldCap。如果否，那么重新寻址后的位置还是原来的index。通过这个方式，避免rehash时使用低效的每个hash值对新数组大小进行取模。
20.HashMap源码十：get与remove操作源码
(1)HashMap的get()方法源码
(2)HashMap的remove()方法源码
(1)HashMap的get()方法源码
public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {
...
public V get(Object key) {
Node e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
final Node getNode(int hash, Object key) {
Node[] tab; Node first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))) {
//直接从定位到的数组位置中获取并返回元素
return first;
}
if ((e = first.next) != null) {
if (first instanceof TreeNode) {
//从红黑树中获取元素
return ((TreeNode)first).getTreeNode(hash, key);
}
//从链表中获取元素
do {
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
return e;
}
} while ((e = e.next) != null);
}
}
return null;
}
...
static final class TreeNode extends LinkedHashMap.Entry {
TreeNode parent;//red-black tree links
TreeNode left;
TreeNode right;
TreeNode prev;//needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node next) {
super(hash, key, val, next);
}
...
//Calls find for root node.
final TreeNode getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}
//Returns root of tree containing this node.
final TreeNode root() {
for (TreeNode r = this, p;;) {
if ((p = r.parent) == null) {
return r;
}
r = p;
}
}
//Finds the node starting at root p with the given hash and key.
//The kc argument caches comparableClassFor(key) upon first use comparing keys.
final TreeNode find(int h, Object k, Class kc) {
TreeNode p = this;
do {
int ph, dir; K pk;
TreeNode pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h) {
p = pl;
} else if (ph < h) {
p = pr;
} else if ((pk = p.key) == k || (k != null && k.equals(pk))) {
return p;
} else if (pl == null) {
p = pr;
} else if (pr == null) {
p = pl;
} else if ((kc != null || (kc = comparableClassFor(k)) != null) && (dir = compareComparables(kc, k, pk)) != 0) {
p = (dir < 0) ? pl : pr;
} else if ((q = pr.find(h, k, kc)) != null) {
return q;
} else {
p = pl;
}
} while (p != null);
return null;
}
}
...
} (2)HashMap的remove()方法源码
public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {
...
public V remove(Object key) {
Node e;
return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
final Node removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
Node[] tab; Node p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
Node node = null, e; K k; V v;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
//直接从定位到的数组位置中获取元素
node = p;
} else if ((e = p.next) != null) {
if (p instanceof TreeNode) {
//从红黑树中获取元素
node = ((TreeNode)p).getTreeNode(hash, key);
} else {
//从链表中获取元素
do {
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
if (node instanceof TreeNode) {
//从红黑树中删除元素
((TreeNode)node).removeTreeNode(this, tab, movable);
} else if (node == p) {
//从数组位置上删除元素
tab[index] = node.next;
} else {
//从链表中删除元素
p.next = node.next;
}
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
...
static final class TreeNode extends LinkedHashMap.Entry {
TreeNode parent;//red-black tree links
TreeNode left;
TreeNode right;
TreeNode prev;//needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node next) {
super(hash, key, val, next);
}
...
//Removes the given node, that must be present before this call.
//This is messier than typical red-black deletion code
//because we cannot swap the contents of an interior node with a leaf successor
//that is pinned by "next" pointers that are accessible independently during traversal.
//So instead we swap the tree linkages.
//If the current tree appears to have too few nodes, the bin is converted back to a plain bin.
//(The test triggers somewhere between 2 and 6 nodes, depending on tree structure).
final void removeTreeNode(HashMap map, Node[] tab, boolean movable) {
int n;
if (tab == null || (n = tab.length) == 0) {
return;
}
int index = (n - 1) & hash;
TreeNode first = (TreeNode)tab[index], root = first, rl;
TreeNode succ = (TreeNode)next, pred = prev;
if (pred == null) {
tab[index] = first = succ;
} else {
pred.next = succ;
}
if (succ != null) {
succ.prev = pred;
}
if (first == null) {
return;
}
if (root.parent != null) {
root = root.root();
}
if (root == null || (movable && (root.right == null || (rl = root.left) == null || rl.left == null))) {
tab[index] = first.untreeify(map);//too small
return;
}
TreeNode p = this, pl = left, pr = right, replacement;
if (pl != null && pr != null) {
TreeNode s = pr, sl;
while ((sl = s.left) != null) {//find successor
s = sl;
}
boolean c = s.red; s.red = p.red; p.red = c; // swap colors
TreeNode sr = s.right;
TreeNode pp = p.parent;
if (s == pr) {// p was s's direct parent
p.parent = s;
s.right = p;
} else {
TreeNode sp = s.parent;
if ((p.parent = sp) != null) {
if (s == sp.left) {
sp.left = p;
} else {
sp.right = p;
}
}
if ((s.right = pr) != null) {
pr.parent = s;
}
}
p.left = null;
if ((p.right = sr) != null) {
sr.parent = p;
}
if ((s.left = pl) != null) {
pl.parent = s;
}
if ((s.parent = pp) == null) {
root = s;
} else if (p == pp.left) {
pp.left = s;
} else {
pp.right = s;
}
if (sr != null) {
replacement = sr;
} else {
replacement = p;
}
} else if (pl != null) {
replacement = pl;
} else if (pr != null) {
replacement = pr;
} else {
replacement = p;
}
if (replacement != p) {
TreeNode pp = replacement.parent = p.parent;
if (pp == null) {
root = replacement;
} else if (p == pp.left) {
pp.left = replacement;
} else {
pp.right = replacement;
}
p.left = p.right = p.parent = null;
}
TreeNode r = p.red ? root : balanceDeletion(root, replacement);
if (replacement == p) { // detach
TreeNode pp = p.parent;
p.parent = null;
if (pp != null) {
if (p == pp.left) {
pp.left = null;
} else if (p == pp.right) {
pp.right = null;
}
}
}
if (movable) {
moveRootToFront(tab, r);
}
}
}
} 21.LinkedHashMap有顺序的Map数据结构
(1)HashMap和LinkedHashMap的遍历顺序
(2)LinkedHashMap和TreeMap的区别
(3)HashMap的newNode()方法
(4)LinkedHashMap重写的newNode()方法
(5)LinkedHashMap覆盖key时是否改变顺序
(1)HashMap和LinkedHashMap的遍历顺序
HashMap添加一些key-value对后，如果要遍历这个HashMap，那么遍历的顺序并不是按照插入的key-value的顺序来进行遍历的；
LinkedHashMap是HashMap的一个子类。LinkedHashMap会记录添加key-value的顺序，在遍历LinkedHashMap时会按照添加key-value对的顺序进行遍历。
(2)LinkedHashMap和TreeMap的区别
LinkedHashMap和TreeMap都可以维持key的插入顺序。LinkedHashMap是基于链表来实现的，TreeMap是基于红黑树来实现的。
LinkedHashMap基本上与HashMap是差不多的。区别在插入、覆盖、删除时，会使用一个链表来记录key-value对的顺序。这样遍历LinkedHashMap时就可以按照这个链表的顺序来遍历；
LinkedHashMap重写了HashMap的newNode()方法。LinkedHashMap的newNode()方法会用一个链表来记录key-value对的顺序。
(3)HashMap的newNode()方法
HashMap在putVal()方法会调用newNode方法：
public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {
...
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node[] tab; Node p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0) {
n = (tab = resize()).length;
}
if ((p = tab[i = (n - 1) & hash]) == null) {
tab[i] = newNode(hash, key, value, null);
} else {
...
}
}
Node newNode(int hash, K key, V value, Node next) {
return new Node<>(hash, key, value, next);
}
...
} (4)LinkedHashMap重写的newNode()方法
首先会将结点封装为一个LinkedHashMap.Entry对象，然后调用linkNodeLast()方法将这个结点挂到一个链表里去。
LinkedHashMap有两个指针head和tail，head和tail这两个指针都是LinkedHashMap.Entry类型的。
LinkedHashMap.Entry也有两个指针before和after。通过before和after两个指针，LinkedHashMap便可以将：LinkedHashMap.Entry类型的结点通过尾插法串成一个双向链表。
public class LinkedHashMap extends HashMap implements Map {
//HashMap.Node subclass for normal LinkedHashMap entries.
static class Entry extends HashMap.Node {
Entry before, after;
Entry(int hash, K key, V value, Node next) {
super(hash, key, value, next);
}
}
...
//The head (eldest) of the doubly linked list.
transient LinkedHashMap.Entry head;
//The tail (youngest) of the doubly linked list.
transient LinkedHashMap.Entry tail;
Node newNode(int hash, K key, V value, Node e) {
LinkedHashMap.Entry p = new LinkedHashMap.Entry(hash, key, value, e);
linkNodeLast(p);
return p;
}
//通过尾插法维护一个双向链表
private void linkNodeLast(LinkedHashMap.Entry p) {
LinkedHashMap.Entry last = tail;
tail = p;
if (last == null) {
head = p;
} else {
p.before = last;
last.after = p;
}
}
} (5)LinkedHashMap覆盖key时是否改变顺序
一开始LinkedHashMap这个链表里只有一个结点，比如p。所以LinkedHashMap的tail和head两个指针，都会指向这个p。
LinkedHashMap的构造方法有一个参数accessOrder，默认是false。如果accessOrder是false，那么get一个key或者覆盖这个key，都不会改变它在链表里的顺序；如果accessOrder是true，那么get一个key或者覆盖这个key，就会改变它在链表里的顺序到尾部；
当删除LinkedHashMap的某个元素时，就会将那个元素从链表中删除。当迭代LinkedHashMap的元素时，就会从链表的头部head开始迭代。
public class LinkedHashMap extends HashMap implements Map {
...
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
public V get(Object key) {
Node e;
if ((e = getNode(hash(key), key)) == null) {
return null;
}
if (accessOrder) {
afterNodeAccess(e);
}
return e.value;
}
void afterNodeAccess(Node e) {//move node to last
LinkedHashMap.Entry last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry p = (LinkedHashMap.Entry)e, b = p.before, a = p.after;
p.after = null;
if (b == null) {
head = a;
} else {
b.after = a;
}
if (a != null) {
a.before = b;
} else {
last = b;
}
if (last == null) {
head = p;
} else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
...
} 22.TreeMap可自定义排序规则的红黑树Map
TreeMap是基于红黑树实现的，不是传统意义上的HashMap。TreeMap天然可以按key的自然顺序来排序，即按照key的大小来排序。而且TreeMap也可以自定义比较方法来进行排序，也就是TreeMap可以定制Comparator，自己决定排序的算法和逻辑。TreeMap会基于红黑树来实现按key排序。
public class TreeMap extends AbstractMap implements NavigableMap, Cloneable, java.io.Serializable {
...
static final class Entry implements Map.Entry {
K key;
V value;
Entry left;
Entry right;
Entry parent;
boolean color = BLACK;
}
...
} 23.HashSet + LinkedHashSet + TreeSet简介
(1)HashSet基于HashMap来实现
(2)LinkedHashSet基于LinkedHashMap实现
(3)TreeSet基于TreeMap来实现
(4)Set基于Map也有数组扩容的问题
(1)HashSet基于HashMap来实现
ArrayList、LinkedList都比较简单，没什么太多复杂问题。HashMap和LinkedHashMap是基于HashMap来实现的，TreeMap和Set是直接基于Map来实现的。
HashSet是基于HashMap来实现的。因为HashMap不允许key重复，HashMap的底层是一个数组。如果key重复，那hash寻址会到数组的同一个位置，然后覆盖原值。
HashSet是一个集合，里面的元素是无序的，里面的元素没有重复。而HashMap的key就是无顺序的，插入顺序和迭代遍历的顺序不一样。而且HashMap的key也没有重复，所以HashSet可以直接基于HashMap来实现。
当不断地往HashSet里放入元素，底层就是不断put元素到HashMap里。如果要从HashSet里进行遍历，直接遍历HashMap的key即可。
(2)LinkedHashSet基于LinkedHashMap实现
LinkedHashSet是有顺序的Set，也就是维持了插入Set的顺序，迭代LinkedHashSet的顺序跟插入的顺序是一样的。LinkedHashSet可直接基于LinkedHashMap来实现。
(3)TreeSet基于TreeMap来实现
TreeSet默认是根据插入进去的元素的值来排序的，而且可以定制Comparator，自己决定排序的算法和逻辑，所以TreeSet底层可基于TreeMap来实现。
(4)Set基于Map也有数组扩容的问题
Set底层的Map，只有key是有值的，value都是null值都是空的。HashSet底层是基于HashMap来实现的，所以也有数组扩容的问题，可以在构造HashSet的时候就传入数组的大小。
问题：Set底层的实现原理是什么？
Set是基于Map来实现的。也就是在Map的key里放置值，但里面的value都是一个空对象。
比如，LinkedHashSet.add()方法，会调用LinkedHashMap.put()方法。此时在这个方法里就会记住加入元素的顺序。遍历LinkedHashSet时，直接遍历LinkedHashMap里维护好的链表。
24.迭代器应对多线程并发修改的Fail-Fast机制
(1)Java集合在迭代时的Fail-Fast机制
(2)通过modCount实现Java集合在迭代时的Fail-Fast机制
(1)Java集合在迭代时的Fail-Fast机制
也就是一个线程在迭代遍历集合，另一个线程在修改集合时：迭代的线程会快速报异常：
ConcurrentModificationException。这个异常就是并发修改的异常，这种机制就叫做Fail-Fast机制。
(2)通过modCount实现Java集合在迭代时的Fail-Fast机制
modCount就是用来实现Fail-Fast机制的，各个集合里其实都有这个modCount的概念。只要这个集合被修改了，那么就会对modCount++。modCount就是修改次数之意，只要修改一次集合，那么就会更新modCount。这些修改集合的方法有：add()、remove()、set()等。
Java集合包下的类都是非线程安全的，都设计了针对并发修改集合的处理，也就是用modCount来实现Fail-Fast机制。
比如在迭代一个ArrayList前，已经插入4个元素，此时modCount = 4。获取和初始化一个迭代器时，其expectedModCount会设为modCount，迭代器每次迭代时都会比较expectedModCount和modCount是否相等。如果不相等，抛出并发修改冲突异常
ConcurrentModificationException。
比如HashMap在迭代开始时，会将modCount赋值给mc。迭代完成后，会判断mc是否等于modCount。如果不相等，抛出并发修改冲突异常
ConcurrentModificationException。
public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable {
...
@Override
public void forEach(Consumer action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
...
}
public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {
...
transient int modCount;
@Override
public void forEach(BiConsumer action) {
Node[] tab;
if (action == null) {
throw new NullPointerException();
}
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node e = tab[i]; e != null; e = e.next) {
action.accept(e.key, e.value);
}
}
if (modCount != mc) {
throw new ConcurrentModificationException();
}
}
}
...
}
本文暂时没有评论，来添加一个吧(●'◡'●)