为了镇楼，先搬一段英文来解释一下 fail-fast。
In systems design, a fail-fast system is one which immediately reports at its interface any condition that is likely to indicate a failure. Fail-fast systems are usually designed to stop normal operation rather than attempt to continue a possibly flawed process. Such designs often check the system's state at several points in an operation, so any failures can be detected early. The responsibility of a fail-fast module is detecting errors, then letting the next-highest level of the system handle them.
这段话的大致意思就是，fail-fast 是一种通用的系统设计思想，一旦检测到可能会发生错误，就立马抛出异常，程序将不再往下执行。
public void test(Wanger wanger) { if (wanger == null) { throw new RuntimeException("wanger 不能为空"); } System.out.println(wanger.toString()); }
一旦检测到 wanger 为 null，就立马抛出异常，让调用者来决定这种情况下该怎么处理，下一步 wanger.toString() 就不会执行了——避免更严重的错误出现。
很多时候，我们会把 fail-fast 归类为 Java 集合框架的一种错误检测机制，但其实 fail-fast 并不是 Java 集合框架特有的机制。
之所以我们把 fail-fast 放在集合框架篇里介绍，是因为问题比较容易再现。
List<String> list = new ArrayList<>(); list.add("爱码有方"); list.add("爱码有方"); list.add("一个文章真特么有趣的程序员"); for (String str : list) { if ("爱码有方".equals(str)) { list.remove(str); } } System.out.println(list);
这段代码看起来没有任何问题，但运行起来就报错了。
根据错误的堆栈信息，我们可以定位到 ArrayList 的第 901 行代码。
final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); }
也就是说，remove 的时候触发执行了 checkForComodification 方法，该方法对 modCount 和 expectedModCount 进行了比较，发现两者不等，就抛出了 ConcurrentModificationException 异常。
为什么会执行 checkForComodification 方法呢？
是因为 for-each 本质上是个语法糖，底层是通过迭代器 Iterator 配合 while 循环实现的，来看一下反编译后的字节码。
List<String> list = new ArrayList(); list.add("爱码有方"); list.add("爱码五方"); list.add("一个文章真特么有趣的程序员"); Iterator var2 = list.iterator(); while(var2.hasNext()) { String str = (String)var2.next(); if ("爱码有方".equals(str)) { list.remove(str); } } System.out.println(list);
来看一下 ArrayList 的 iterator 方法吧：
public Iterator<E> iterator() { return new Itr(); }
内部类 Itr 实现了 Iterator 接口。
private class Itr implements Iterator<E> { int cursor; // index of next element to return int lastRet = -1; // index of last element returned; -1 if no such int expectedModCount = modCount; Itr() {} public boolean hasNext() { return cursor != size; } @SuppressWarnings("unchecked") public E next() { checkForComodification(); int i = cursor; Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i + 1; return (E) elementData[lastRet = i]; } }
也就是说 new Itr() 的时候 expectedModCount 被赋值为 modCount，而 modCount 是 List 的一个成员变量，表示集合被修改的次数。由于 list 此前执行了 3 次 add 方法。
- add 方法调用 ensureCapacityInternal 方法
- ensureCapacityInternal 方法调用 ensureExplicitCapacity 方法
- ensureExplicitCapacity 方法中会执行
modCount++
所以 modCount 的值在经过三次 add 后为 3，于是 new Itr() 后 expectedModCount 的值也为 3。
执行第一次循环时，发现“爱码有方”等于 str，于是执行 list.remove(str)。
- remove 方法调用 fastRemove 方法
- fastRemove 方法中会执行
modCount++
private void fastRemove(int index) { modCount++; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work }
modCount 的值变成了 4。
执行第二次循环时，会执行 Itr 的 next 方法（String str = (String) var3.next();），next 方法就会调用 checkForComodification 方法，此时 expectedModCount 为 3，modCount 为 4，就只好抛出 ConcurrentModificationException 异常了。
那其实在阿里巴巴的 Java 开发手册里也提到了，不要在 for-each 循环里进行元素的 remove/add 操作。remove 元素请使用 Iterator 方式。
那原因其实就是我们上面分析的这些，出于 fail-fast 保护机制。
那该如何正确地删除元素呢？
1）remove 后 break
List<String> list = new ArrayList<>(); list.add("爱码有方"); list.add("爱码无方"); list.add("一个文章真特么有趣的程序员"); for (String str : list) { if ("爱码有方".equals(str)) { list.remove(str); break; } }
break 后循环就不再遍历了，意味着 Iterator 的 next 方法不再执行了，也就意味着 checkForComodification 方法不再执行了，所以异常也就不会抛出了。
但是呢，当 List 中有重复元素要删除的时候，break 就不合适了。
2）for 循环
List<String> list = new ArrayList<>(); list.add("爱码有方"); list.add("爱码无方"); list.add("一个文章真特么有趣的程序员"); for (int i = 0, n = list.size(); i < n; i++) { String str = list.get(i); if ("爱码有方".equals(str)) { list.remove(str); } }
for 循环虽然可以避开 fail-fast 保护机制，也就说 remove 元素后不再抛出异常；但是呢，这段程序在原则上是有问题的。为什么呢？
第一次循环的时候，i 为 0，list.size() 为 3，当执行完 remove 方法后，i 为 1，list.size() 却变成了 2，因为 list 的大小在 remove 后发生了变化，也就意味着“爱码无方”这个元素被跳过了。能明白吗？
remove 之前 list.get(1) 为“爱码无方”；但 remove 之后 list.get(1) 变成了“一个文章真特么有趣的程序员”，而 list.get(0) 变成了“爱码无方”。
3）使用 Iterator
List<String> list = new ArrayList<>(); list.add("爱码有方"); list.add("爱码无方"); list.add("一个文章真特么有趣的程序员"); Iterator<String> itr = list.iterator(); while (itr.hasNext()) { String str = itr.next(); if ("爱码有方".equals(str)) { itr.remove(); } }
为什么使用 Iterator 的 remove 方法就可以避开 fail-fast 保护机制呢？看一下 remove 的源码就明白了。
public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } }
删除完会执行 expectedModCount = modCount，保证了 expectedModCount 与 modCount 的同步。
简单地总结一下，fail-fast 是一种保护机制，可以通过 for-each 循环删除集合的元素的方式验证这种保护机制。
那也就是说，for-each 本质上是一种语法糖，遍历集合时很方面，但并不适合拿来操作集合中的元素（增删）。
Java中的Iterator和Iterable区别
在 Java 中，我们对 List 进行遍历的时候，主要有这么三种方式。
第一种：for 循环。
for (int i = 0; i < list.size(); i++) { System.out.print(list.get(i) + "，"); }
第二种：迭代器。
Iterator it = list.iterator(); while (it.hasNext()) { System.out.print(it.next() + "，"); }
第三种：for-each。
for (String str : list) { System.out.print(str + "，"); }
第一种我们略过，第二种用的是 Iterator，第三种看起来是 for-each，其实背后也是 Iterator，看一下反编译后的代码就明白了。
Iterator var3 = list.iterator(); while(var3.hasNext()) { String str = (String)var3.next(); System.out.print(str + "，"); }
for-each 只不过是个语法糖，让我们在遍历 List 的时候代码更简洁明了。
Iterator 是个接口，JDK 1.2 的时候就有了，用来改进 Enumeration：
- 允许删除元素（增加了 remove 方法）
- 优化了方法名（Enumeration 中是 hasMoreElements 和 nextElement，不简洁）
来看一下 Iterator 的源码：
public interface Iterator<E> { // 判断集合中是否存在下一个对象 boolean hasNext(); // 返回集合中的下一个对象，并将访问指针移动一位 E next(); // 删除集合中调用next()方法返回的对象 default void remove() { throw new UnsupportedOperationException("remove"); } }
JDK 1.8 时，Iterable 接口中新增了 forEach 方法
default void forEach(Consumer<? super T> action) { Objects.requireNonNull(action); for (T t : this) { action.accept(t); } }
它对 Iterable 的每个元素执行给定操作，具体指定的操作需要自己写Consumer接口通过accept方法回调出来。
List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3)); list.forEach(integer -> System.out.println(integer));
写得更浅显易懂点，就是：
List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3)); list.forEach(new Consumer<Integer>() { @Override public void accept(Integer integer) { System.out.println(integer); } });
如果我们仔细观察ArrayList 或者 LinkedList 的“户口本”就会发现，并没有直接找到 Iterator 的影子。
反而找到了 Iterable！
public interface Iterable<T> { Iterator<T> iterator(); }
也就是说，List 的关系图谱中并没有直接使用 Iterator，而是使用 Iterable 做了过渡。
回头再来看一下第二种遍历 List 的方式。
Iterator it = list.iterator(); while (it.hasNext()) { }
发现刚好呼应上了。拿 ArrayList 来说吧，它重写了 Iterable 接口的 iterator 方法：
public Iterator<E> iterator() { return new Itr(); }
返回的对象 Itr 是个内部类，实现了 Iterator 接口，并且按照自己的方式重写了 hasNext、next、remove 等方法。
private class Itr implements Iterator<E> { public boolean hasNext() { return cursor != size; } @SuppressWarnings("unchecked") public E next() { Object[] elementData = ArrayList.this.elementData; cursor = i + 1; return (E) elementData[lastRet = i]; } public void remove() { try { ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } }
那可能有些小伙伴会问：为什么不直接将 Iterator 中的核心方法 hasNext、next 放到 Iterable 接口中呢？直接像下面这样使用不是更方便？
Iterable it = list.iterator(); while (it.hasNext()) { }
从英文单词的后缀语法上来看，（Iterable）able 表示这个 List 是支持迭代的，而 （Iterator）tor 表示这个 List 是如何迭代的。
支持迭代与具体怎么迭代显然不能混在一起，否则就乱的一笔。还是各司其职的好。
想一下，如果把 Iterator 和 Iterable 合并，for-each 这种遍历 List 的方式是不是就不好办了？
原则上，只要一个 List 实现了 Iterable 接口，那么它就可以使用 for-each 这种方式来遍历，那具体该怎么遍历，还是要看它自己是怎么实现 Iterator 接口的。
Map 就没办法直接使用 for-each，因为 Map 没有实现 Iterable 接口，只有通过 map.entrySet()、map.keySet()、map.values() 这种返回一个 Collection 的方式才能 使用 for-each。
如果我们仔细研究 LinkedList 的源码就会发现，LinkedList 并没有直接重写 Iterable 接口的 iterator 方法，而是由它的父类 AbstractSequentialList 来完成。
public Iterator<E> iterator() { return listIterator(); }
LinkedList 重写了 listIterator 方法：
public ListIterator<E> listIterator(int index) { checkPositionIndex(index); return new ListItr(index); }
这里我们发现了一个新的迭代器 ListIterator，它继承了 Iterator 接口，在遍历List 时可以从任意下标开始遍历，而且支持双向遍历。
public interface ListIterator<E> extends Iterator<E> { boolean hasNext(); E next(); boolean hasPrevious(); E previous(); }
我们知道，集合（Collection）不仅有 List，还有 Map 和 Set，那 Iterator 不仅支持 List，还支持 Set，但 ListIterator 就只支持 List。
那可能有些小伙伴会问：为什么不直接让 List 实现 Iterator 接口，而是要用内部类来实现呢？
这是因为有些 List 可能会有多种遍历方式，比如说 LinkedList，除了支持正序的遍历方式，还支持逆序的遍历方式——DescendingIterator：
private class DescendingIterator implements Iterator<E> { private final ListItr itr = new ListItr(size()); public boolean hasNext() { return itr.hasPrevious(); } public E next() { return itr.previous(); } public void remove() { itr.remove(); } }
可以看得到，DescendingIterator 刚好利用了 ListIterator 向前遍历的方式。可以通过以下的方式来使用：
Iterator it = list.descendingIterator(); while (it.hasNext()) { }
好了，关于Iterator与Iterable我们就先聊这么多，总结两点：
- 学会深入思考，一点点抽丝剥茧，多想想为什么这样实现，很多问题没有自己想象中的那么复杂。
- 遇到疑惑不放弃，这是提升自己最好的机会，遇到某个疑难的点，解决的过程中会挖掘出很多相关的东西。
重新认识HashMap
来看一下 hash 方法的源码（JDK 8 中的 HashMap）：
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
这段代码究竟是用来干嘛的呢？
我们都知道，key.hashCode() 是用来获取键位的哈希值的，理论上，哈希值是一个 int 类型，范围从-2147483648 到 2147483648。前后加起来大概 40 亿的映射空间，只要哈希值映射得比较均匀松散，一般是不会出现哈希碰撞的。
但问题是一个 40 亿长度的数组，内存是放不下的。HashMap 扩容之前的数组初始大小只有 16，所以这个哈希值是不能直接拿来用的，用之前要和数组的长度做取模运算，用得到的余数来访问数组下标才行。
取模运算有两处。
取模运算（“Modulo Operation”）和取余运算（“Remainder Operation ”）两个概念有重叠的部分但又不完全一致。主要的区别在于对负整数进行除法运算时操作不同。取模主要是用于计算机术语中，取余则更多是数学概念。
一处是往 HashMap 中 put 的时候（putVal 方法中）：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { HashMap.Node<K,V>[] tab; HashMap.Node<K,V> 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); }
一处是从 HashMap 中 get 的时候（getNode 方法中）：
final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {} }
其中的 (n - 1) & hash 正是取模运算，就是把哈希值和（数组长度-1）做了一个“与”运算。
可能大家在疑惑：取模运算难道不该用 % 吗？为什么要用 & 呢？
这是因为 & 运算比 % 更加高效，并且当 b 为 2 的 n 次方时，存在下面这样一个公式。
a % b = a & (b-1)
用 2^n 替换下 b 就是：
a % 2^n = a & (2^n-1)
我们来验证一下，假如 a = 14，b = 8，也就是 2^3，n=3。
14%8，14 的二进制为 1110，8 的二进制 1000，8-1 = 7 的二进制为 0111，1110&0111=0110，也就是 0*2^0+1*2^1+1*2^2+0*2^3=0+2+4+0=6，14%8 刚好也等于 6。
这也正好解释了为什么 HashMap 的数组长度要取 2 的整次方。
因为（数组长度-1）正好相当于一个“低位掩码”——这个掩码的低位最好全是 1，这样 & 操作才有意义，否则结果就肯定是 0，那么 & 操作就没有意义了。
a&b 操作的结果是：a、b 中对应位同时为 1，则对应结果位为 1，否则为 0
2 的整次幂刚好是偶数，偶数-1 是奇数，奇数的二进制最后一位是 1，保证了 hash &(length-1) 的最后一位可能为 0，也可能为 1（这取决于 h 的值），即 & 运算后的结果可能为偶数，也可能为奇数，这样便可以保证哈希值的均匀性。
& 操作的结果就是将哈希值的高位全部归零，只保留低位值，用来做数组下标访问。
假设某哈希值为 10100101 11000100 00100101，用它来做取模运算，我们来看一下结果。HashMap 的初始长度为 16（内部是数组），16-1=15，二进制是 00000000 00000000 00001111（高位用 0 来补齐）：
10100101 11000100 00100101 & 00000000 00000000 00001111 ---------------------------------- 00000000 00000000 00000101
因为 15 的高位全部是 0，所以 & 运算后的高位结果肯定是 0，只剩下 4 个低位 0101，也就是十进制的 5，也就是将哈希值为 10100101 11000100 00100101 的键放在数组的第 5 位。
明白了取模运算后，我们再来看 put 方法的源码：
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }
以及 get 方法的源码：
public V get(Object key) { HashMap.Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; }
它们在调用 putVal 和 getNode 之前，都会先调用 hash 方法：
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
那为什么取模运算之前要调用 hash 方法呢？
看下面这个图。
某哈希值为 11111111 11111111 11110000 1110 1010，将它右移 16 位（h >>> 16），刚好是 00000000 00000000 11111111 11111111，再进行异或操作（h ^ (h >>> 16)），结果是 11111111 11111111 00001111 00010101
异或（
^）运算是基于二进制的位运算，采用符号 XOR 或者^来表示，运算规则是：如果是同值取 0、异值取 1
由于混合了原来哈希值的高位和低位，所以低位的随机性加大了（掺杂了部分高位的特征，高位的信息也得到了保留）。
结果再与数组长度-1（00000000 00000000 00000000 00001111）做取模运算，得到的下标就是 00000000 00000000 00000000 00000101，也就是 5。
还记得之前我们假设的某哈希值 10100101 11000100 00100101 吗？在没有调用 hash 方法之前，与 15 做取模运算后的结果也是 5，我们不妨来看看调用 hash 之后的取模运算结果是多少。
某哈希值 00000000 10100101 11000100 00100101（补齐 32 位），将它右移 16 位（h >>> 16），刚好是 00000000 00000000 00000000 10100101，再进行异或操作（h ^ (h >>> 16)），结果是 00000000 10100101 00111011 10000000
结果再与数组长度-1（00000000 00000000 00000000 00001111）做取模运算，得到的下标就是 00000000 00000000 00000000 00000000，也就是 0。
综上所述，hash 方法是用来做哈希值优化的，把哈希值右移 16 位，也就正好是自己长度的一半，之后与原哈希值做异或运算，这样就混合了原哈希值中的高位和低位，增大了随机性。
说白了，hash 方法就是为了增加随机性，让数据元素更加均衡的分布，减少碰撞。
二、扩容机制
大家都知道，数组一旦初始化后大小就无法改变了，所以就有了 ArrayListopen in new window这种“动态数组”，可以自动扩容。
HashMap 的底层用的也是数组。向 HashMap 里不停地添加元素，当数组无法装载更多元素时，就需要对数组进行扩容，以便装入更多的元素。
当然了，数组是无法自动扩容的，所以如果要扩容的话，就需要新建一个大的数组，然后把小数组的元素复制过去。
HashMap 的扩容是通过 resize 方法来实现的，JDK 8 中融入了红黑树，比较复杂，为了便于理解，就还使用 JDK 7 的源码，搞清楚了 JDK 7 的，我们后面再详细说明 JDK 8 和 JDK 7 之间的区别。
resize 方法的源码：
// newCapacity为新的容量 void resize(int newCapacity) { // 小数组，临时过度下 Entry[] oldTable = table; // 扩容前的容量 int oldCapacity = oldTable.length; // MAXIMUM_CAPACITY 为最大容量，2 的 30 次方 = 1<<30 if (oldCapacity == MAXIMUM_CAPACITY) { // 容量调整为 Integer 的最大值 0x7fffffff（十六进制）=2 的 31 次方-1 threshold = Integer.MAX_VALUE; return; } // 初始化一个新的数组（大容量） Entry[] newTable = new Entry[newCapacity]; // 把小数组的元素转移到大数组中 transfer(newTable, initHashSeedAsNeeded(newCapacity)); // 引用新的大数组 table = newTable; // 重新计算阈值 threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }
代码注释里出现了左移（<<），这里简单介绍一下：
a=39 b = a << 2
十进制 39 用 8 位的二进制来表示，就是 00100111，左移两位后是 10011100（低位用 0 补上），再转成十进制数就是 156。
移位运算通常可以用来代替乘法运算和除法运算。例如，将 0010011（39）左移两位就是 10011100（156），刚好变成了原来的 4 倍。
实际上呢，二进制数左移后会变成原来的 2 倍、4 倍、8 倍。
transfer 方法用来转移，将小数组的元素拷贝到新的数组中。
void transfer(Entry[] newTable, boolean rehash) { // 新的容量 int newCapacity = newTable.length; // 遍历小数组 for (Entry<K,V> e : table) { while(null != e) { // 拉链法，相同 key 上的不同值 Entry<K,V> next = e.next; // 是否需要重新计算 hash if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } // 根据大数组的容量，和键的 hash 计算元素在数组中的下标 int i = indexFor(e.hash, newCapacity); // 同一位置上的新元素被放在链表的头部 e.next = newTable[i]; // 放在新的数组上 newTable[i] = e; // 链表上的下一个元素 e = next; } } }
e.next = newTable[i]，也就是使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置；这样先放在一个索引上的元素终会被放到链表的尾部（如果发生了hash冲突的话），这一点和 JDK 8 有区别。
在旧数组中同一个链表上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上（仔细看下面的内容，会解释清楚这一点）。
假设 hash 算法（之前的章节有讲到open in new window，点击链接再温故一下）就是简单的用键的哈希值（一个 int 值）和数组大小取模（也就是 hashCode % table.length）。
继续假设：
- 数组 table 的长度为 2
- 键的哈希值为 3、7、5
取模运算后，哈希冲突都到 table[1] 上了，因为余数为 1。那么扩容前的样子如下图所示。
小数组的容量为 2， key 3、7、5 都在 table[1] 的链表上。
假设负载因子 loadFactor 为 1，也就是当元素的实际大小大于 table 的实际大小时进行扩容。
扩容后的大数组的容量为 4。
- key 3 取模（3%4）后是 3，放在 table[3] 上。
- key 7 取模（7%4）后是 3，放在 table[3] 上的链表头部。
- key 5 取模（5%4）后是 1，放在 table[1] 上。
按照我们的预期，扩容后的 7 仍然应该在 3 这条链表的后面，但实际上呢？ 7 跑到 3 这条链表的头部了。针对 JDK 7 中的这个情况，JDK 8 做了哪些优化呢？
看下面这张图。
n 为 table 的长度，默认值为 16。
- n-1 也就是二进制的 0000 1111（1X2^0+1X2^1+1X2^2+1X2^3=1+2+4+8=15）；
- key1 哈希值的最后 8 位为 0000 0101
- key2 哈希值的最后 8 位为 0001 0101（和 key1 不同）
- 做与运算后发生了哈希冲突，索引都在（0000 0101）上。
扩容后为 32。
- n-1 也就是二进制的 0001 1111（1X2^0+1X2^1+1X2^2+1X2^3+1X2^4=1+2+4+8+16=31），扩容前是 0000 1111。
- key1 哈希值的低位为 0000 0101
- key2 哈希值的低位为 0001 0101（和 key1 不同）
- key1 做与运算后，索引为 0000 0101。
- key2 做与运算后，索引为 0001 0101。
新的索引就会发生这样的变化：
- 原来的索引是 5（0 0101）
- 原来的容量是 16
- 扩容后的容量是 32
- 扩容后的索引是 21（1 0101），也就是 5+16，也就是原来的索引+原来的容量
也就是说，JDK 8 不需要像 JDK 7 那样重新计算 hash，只需要看原来的hash值新增的那个bit是1还是0就好了，是0的话就表示索引没变，是1的话，索引就变成了“原索引+原来的容量”。
JDK 8 的这个设计非常巧妙，既省去了重新计算hash的时间，同时，由于新增的1 bit是0还是1是随机的，因此扩容的过程，可以均匀地把之前的节点分散到新的位置上。
woc，只能说 HashMap 的作者 Doug Lea、Josh Bloch、Arthur van Hoff、Neal Gafter 真的强——的一笔。
JDK 8 扩容的源代码：
final Node<K,V>[] resize() { Node<K,V>[] 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; } // 没超过最大值，就扩充为原来的2倍 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 { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 计算新的resize上限 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<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab != null) { // 小数组复制到大数组 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order // 链表优化重 hash 的代码块 Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> 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); // 原来的索引 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } // 索引+原来的容量 if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }
三、加载因子为什么是0.75
JDK 8 中的 HashMap 是用数组+链表+红黑树实现的，我们要想往 HashMap 中放数据或者取数据，就需要确定数据在数组中的下标。
先把数据的键进行一次 hash：
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
再做一次取模运算确定下标：
i = (n - 1) & hash
哈希表这样的数据结构容易产生两个问题：
- 数组的容量过小，经过哈希计算后的下标，容易出现冲突；
- 数组的容量过大，导致空间利用率不高。
加载因子是用来表示 HashMap 中数据的填满程度：
加载因子 = 填入哈希表中的数据个数 / 哈希表的长度
这就意味着：
- 加载因子越小，填满的数据就越少，哈希冲突的几率就减少了，但浪费了空间，而且还会提高扩容的触发几率；
- 加载因子越大，填满的数据就越多，空间利用率就高，但哈希冲突的几率就变大了。
好难！！！！
这就必须在“哈希冲突”与“空间利用率”两者之间有所取舍，尽量保持平衡，谁也不碍着谁。
我们知道，HashMap 是通过拉链法来解决哈希冲突的。
为了减少哈希冲突发生的概率，当 HashMap 的数组长度达到一个临界值的时候，就会触发扩容，扩容后会将之前小数组中的元素转移到大数组中，这是一个相当耗时的操作。
这个临界值由什么来确定呢？
临界值 = 初始容量 * 加载因子
一开始，HashMap 的容量是 16：
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
加载因子是 0.75：
static final float DEFAULT_LOAD_FACTOR = 0.75f;
也就是说，当 16*0.75=12 时，会触发扩容机制。
为什么加载因子会选择 0.75 呢？为什么不是0.8、0.6呢？
这跟统计学里的一个很重要的原理——泊松分布有关。
是时候上维基百科了：
泊松分布，是一种统计与概率学里常见到的离散概率分布，由法国数学家西莫恩·德尼·泊松在1838年时提出。它会对随机事件的发生次数进行建模，适用于涉及计算在给定的时间段、距离、面积等范围内发生随机事件的次数的应用情形。
阮一峰老师曾在一篇博文中详细的介绍了泊松分布和指数分布，大家可以去看一下。
链接：https://www.ruanyifeng.com/blog/2015/06/poisson-distribution.html
具体是用这么一个公式来表示的。
等号的左边，P 表示概率，N表示某种函数关系，t 表示时间，n 表示数量。
在 HashMap 的 doc 文档里，曾有这么一段描述：
Because TreeNodes are about twice the size of regular nodes, we use them only when bins contain enough nodes to warrant use (see TREEIFY_THRESHOLD). And when they become too small (due to removal or resizing) they are converted back to plain bins. In usages with well-distributed user hashCodes, tree bins are rarely used. Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution (http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance, the expected occurrences of list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The first values are: 0: 0.60653066 1: 0.30326533 2: 0.07581633 3: 0.01263606 4: 0.00157952 5: 0.00015795 6: 0.00001316 7: 0.00000094 8: 0.00000006 more: less than 1 in ten million
大致的意思就是：
因为 TreeNode（红黑树）的大小约为链表节点的两倍，所以我们只有在一个拉链已经拉了足够节点的时候才会转为tree（参考TREEIFY_THRESHOLD）。并且，当这个hash桶的节点因为移除或者扩容后resize数量变小的时候，我们会将树再转为拉链。如果一个用户的数据的hashcode值分布得很均匀的话，就会很少使用到红黑树。
理想情况下，我们使用随机的hashcode值，加载因子为0.75情况，尽管由于粒度调整会产生较大的方差，节点的分布频率仍然会服从参数为0.5的泊松分布。链表的长度为 8 发生的概率仅有 0.00000006。
虽然这段话的本意更多的是表示 jdk 8中为什么拉链长度超过8的时候进行了红黑树转换，但提到了 0.75 这个加载因子——但这并不是为什么加载因子是 0.75 的答案。
为了搞清楚到底为什么，我看到了这篇文章：
里面提到了一个概念：二项分布（二哥概率论没学好，只能简单说一说）。
在做一件事情的时候，其结果的概率只有2种情况，和抛硬币一样，不是正面就是反面。
为此，我们做了 N 次实验，那么在每次试验中只有两种可能的结果，并且每次实验是独立的，不同实验之间互不影响，每次实验成功的概率都是一样的。
以此理论为基础，我们来做这样的实验：我们往哈希表中扔数据，如果发生哈希冲突就为失败，否则为成功。
我们可以设想，实验的hash值是随机的，并且经过hash运算的键都会映射到hash表的地址空间上，那么这个结果也是随机的。所以，每次put的时候就相当于我们在扔一个16面（我们先假设默认长度为16）的骰子，扔骰子实验那肯定是相互独立的。碰撞发生即扔了n次有出现重复数字。
然后，我们的目的是啥呢？
就是掷了k次骰子，没有一次是相同的概率，需要尽可能的大些，一般意义上我们肯定要大于0.5（这个数是个理想数，但是我是能接受的）。
于是，n次事件里面，碰撞为0的概率，由上面公式得：
这个概率值需要大于0.5，我们认为这样的hashmap可以提供很低的碰撞率。所以：
这时候，我们对于该公式其实最想求的时候长度s的时候，n为多少次就应该进行扩容了？而负载因子则是n/s的值。所以推导如下：
所以可以得到
其中
这就是一个求 ∞⋅0函数极限问题，这里我们先令s = m+1（m \to \infty）则转化为
我们再令 x = \frac{1}{m} （x \to 0） 则有，
所以，
考虑到 HashMap的容量有一个要求：它必须是2的n 次幂（这个之前的文章open in new window讲过了，点击链接回去可以再温故一下）。当加载因子选择了0.75就可以保证它与容量的乘积为整数。
16*0.75=12 32*0.75=24
除了 0.75，0.5~1 之间还有 0.625（5/8）、0.875（7/8）可选，从中位数的角度，挑 0.75 比较完美。另外，维基百科上说，拉链法（解决哈希冲突的一种）的加载因子最好限制在 0.7-0.8以下，超过0.8，查表时的CPU缓存不命中（cache missing）会按照指数曲线上升。
综上，0.75 是个比较完美的选择。
四、线程不安全
三方面原因：多线程下扩容会死循环、多线程下 put 会导致元素丢失、put 和 get 并发时会导致 get 到 null，我们来一一分析。
01、多线程下扩容会死循环
众所周知，HashMap 是通过拉链法来解决哈希冲突的，也就是当哈希冲突时，会将相同哈希值的键值对通过链表的形式存放起来。
JDK 7 时，采用的是头部插入的方式来存放链表的，也就是下一个冲突的键值对会放在上一个键值对的前面（同一位置上的新元素被放在链表的头部）。扩容的时候就有可能导致出现环形链表，造成死循环。
resize 方法的源码：
// newCapacity为新的容量 void resize(int newCapacity) { // 小数组，临时过度下 Entry[] oldTable = table; // 扩容前的容量 int oldCapacity = oldTable.length; // MAXIMUM_CAPACITY 为最大容量，2 的 30 次方 = 1<<30 if (oldCapacity == MAXIMUM_CAPACITY) { // 容量调整为 Integer 的最大值 0x7fffffff（十六进制）=2 的 31 次方-1 threshold = Integer.MAX_VALUE; return; } // 初始化一个新的数组（大容量） Entry[] newTable = new Entry[newCapacity]; // 把小数组的元素转移到大数组中 transfer(newTable, initHashSeedAsNeeded(newCapacity)); // 引用新的大数组 table = newTable; // 重新计算阈值 threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }
transfer 方法用来转移，将小数组的元素拷贝到新的数组中。
void transfer(Entry[] newTable, boolean rehash) { // 新的容量 int newCapacity = newTable.length; // 遍历小数组 for (Entry<K,V> e : table) { while(null != e) { // 拉链法，相同 key 上的不同值 Entry<K,V> next = e.next; // 是否需要重新计算 hash if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } // 根据大数组的容量，和键的 hash 计算元素在数组中的下标 int i = indexFor(e.hash, newCapacity); // 同一位置上的新元素被放在链表的头部 e.next = newTable[i]; // 放在新的数组上 newTable[i] = e; // 链表上的下一个元素 e = next; } } }
注意 e.next = newTable[i] 和 newTable[i] = e 这两行代码，就会将同一位置上的新元素被放在链表的头部。
扩容前的样子假如是下面这样子。
那么正常扩容后就是下面这样子。
假设现在有两个线程同时进行扩容，线程 A 在执行到 newTable[i] = e; 被挂起，此时线程 A 中：e=3、next=7、e.next=null
线程 B 开始执行，并且完成了数据转移。
此时，7 的 next 为 3，3 的 next 为 null。
随后线程A获得CPU时间片继续执行 newTable[i] = e，将3放入新数组对应的位置，执行完此轮循环后线程A的情况如下：
执行下一轮循环，此时 e=7，原本线程 A 中 7 的 next 为 5，但由于 table 是线程 A 和线程 B 共享的，而线程 B 顺利执行完后，7 的 next 变成了 3，那么此时线程 A 中，7 的 next 也为 3 了。
采用头部插入的方式，变成了下面这样子：
好像也没什么问题，此时 next = 3，e = 3。
进行下一轮循环，但此时，由于线程 B 将 3 的 next 变为了 null，所以此轮循环应该是最后一轮了。
接下来当执行完 e.next=newTable[i] 即 3.next=7 后，3 和 7 之间就相互链接了，执行完 newTable[i]=e 后，3 被头插法重新插入到链表中，执行结果如下图所示：
套娃开始，元素 5 也就成了弃婴，惨~~~
不过，JDK 8 时已经修复了这个问题，扩容时会保持链表原来的顺序。
02、多线程下 put 会导致元素丢失
正常情况下，当发生哈希冲突时，HashMap 是这样的：
但多线程同时执行 put 操作时，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。
put 的源码：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 步骤①：tab为空则创建 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 步骤②：计算index，并对null做处理 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; // 步骤③：节点key存在，直接覆盖value if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 步骤④：判断该链为红黑树 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)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); //链表长度大于8转换为红黑树进行处理 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // key已经存在直接覆盖value 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) tab[i] = newNode(hash, key, value, null);
两个线程都执行了 if 语句，假设线程 A 先执行了 tab[i] = newNode(hash, key, value, null)，那 table 是这样的：
接着，线程 B 执行了 tab[i] = newNode(hash, key, value, null)，那 table 是这样的：
3 被干掉了。
03、put 和 get 并发时会导致 get 到 null
线程 A 执行put时，因为元素个数超出阈值而出现扩容，线程B 此时执行get，有可能导致这个问题。
注意来看 resize 源码：
final Node<K,V>[] resize() { Node<K,V>[] 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; } // 没超过最大值，就扩充为原来的2倍 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 { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 计算新的resize上限 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<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; }
线程 A 执行完 table = newTab 之后，线程 B 中的 table 此时也发生了变化，此时去 get 的时候当然会 get 到 null 了，因为元素还没有转移。
