1.为什么要对 JDK 源码剖析
简单的框架源码有：Spring Cloud，ByteTcc 分布式事务，Redisson 以及 Curator 等框架源码。
较难的框架源码有：ZooKeeper，Dubbo、Netty、RocketMQ、Sharding-JDBC 等框架源码。
看这些源码的时候，都有一些基础性的代码逻辑，比如：内存里的各种数据结构(List、Map、Set)、并发、网络请求、磁盘 IO 等。
其实对于各种各样的框架系统的底层，最核心的部分，基本都是：
一.集合(在内存里面存放数据)
二.并发(系统底层都会开多个线程进行并发处理，会涉及锁、同步等)
三.IO(读写磁盘上的文件数据、或者发起网络 IO 通过网络读写数据)
四.网络(在分布式系统中给各个机器建立网络连接，互相发送请求通信)
2.ArrayList 源码一：基本原理以及优缺点
(1)数组长度固定需要扩容和拷贝
由于 Java 里的数组都是定长数组，数组的长度是固定的。比如数组大小设置为 100，此时不停的往 ArrayList 里面塞入数据，当元素数量超过了 100 以后，此时就会发生数组的扩容，就会申请更大的数组，把旧数组元素拷贝到新数组里去。
这个数组扩容 + 元素拷贝的过程，相对来说会慢一些。所以使用 ArrayList 时要注意，不要频繁往 ArraList 里面去塞数据，而导致频繁的数组扩容影响性能。
(2)添加元素导致大量移动元素
由于基于数组来实现，当往数组中添加元素，会导致移动元素。
(3)基于数组非常适合随机读
由于基于数组来实现，所以非常适合随机读。可以随机的去读数组中的某个元素，这个随机读的性能是比较高的，可以直接通过内存地址来定位某个元素。
(4)总结
如果不会频繁插入元素，导致频繁的移动元素位置、List 扩容，而主要用于遍历集合或通过索引随机读取元素，那么可以用 ArrayList。
如果会频繁插入元素到 List 中，那么尽量还是不要用 ArrayList，因为很可能会造成大量的元素移动 + 数组扩容 + 元素拷贝。
3.ArrayList 源码二：核心方法的原理
(1)构造方法的源码
如果不传参直接初始化一个 ArrayList 对象，则会执行默认的构造方法。默认的构造方法会将内部的数组设成一个默认的空数组。
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; transient Object[] elementData; ... //Constructs an empty list with an initial capacity of ten. public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } ...}
复制代码
ArrayList 有一个默认的初始化数组大小的数值是 10，可认为默认的数组初始化大小就只有 10 个元素，但这是往 ArrayList 添加元素时才触发的。
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { //Default initial capacity. private static final int DEFAULT_CAPACITY = 10; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; transient Object[] elementData; ... public boolean add(E e) { ensureCapacityInternal(size + 1);//Increments modCount!! elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } private void ensureExplicitCapacity(int minCapacity) { modCount++; //overflow-conscious code if (minCapacity - elementData.length > 0) { grow(minCapacity); } } private void grow(int minCapacity) { //overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) { newCapacity = minCapacity; } if (newCapacity - MAX_ARRAY_SIZE > 0) { newCapacity = hugeCapacity(minCapacity); } //minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } ...}
复制代码
使用 ArrayList 的场景，应该不会有频繁的插入、移除元素的操作，基本可以知道它里面有多少元素，所以应该不会使用默认的构造方法。
一般给 ArrayList 构造时，会初始化一个合适的数组大小，避免数组太小插入塞入数据时导致频繁扩容。
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; transient Object[] elementData; ... public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity); } } ...}
复制代码
(2)add()方法的源码
每次往 ArrayList 添加元素时，都会判断一下当前数组元素是否满了。如果满了，此时就会对数组进行扩容。然后将旧数组中的元素拷贝到新数组中，确保数组能承受更多元素。
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { //Default initial capacity. private static final int DEFAULT_CAPACITY = 10; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; transient Object[] elementData; ... public boolean add(E e) { ensureCapacityInternal(size + 1);//Increments modCount!! elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } private void ensureExplicitCapacity(int minCapacity) { modCount++; //overflow-conscious code if (minCapacity - elementData.length > 0) { grow(minCapacity); } } private void grow(int minCapacity) { //overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) { newCapacity = minCapacity; } if (newCapacity - MAX_ARRAY_SIZE > 0) { newCapacity = hugeCapacity(minCapacity); } //minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } ...}
复制代码
(3)set()方法的源码
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { transient Object[] elementData; ... public E set(int index, E element) { rangeCheck(index);//检查是否数组越界 E oldValue = elementData(index); elementData[index] = element; return oldValue; } private void rangeCheck(int index) { if (index >= size) { throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } } ...}
复制代码
(4)add(index, element)方法的源码
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { transient Object[] elementData; ... //往随机位置index插入元素 public void add(int index, E element) { rangeCheckForAdd(index);//检查是否数组越界 ensureCapacityInternal(size + 1); //System.arraycopy()方法会将elementData数组的index位置后的数据进行拷贝 System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; } private void rangeCheck(int index) { if (index >= size) { throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } } ...}
复制代码
(5)get()方法的源码
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { transient Object[] elementData; ... public E get(int index) { rangeCheck(index);//检查是否数组越界 return elementData[index]; } private void rangeCheck(int index) { if (index >= size) { throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } } ...}
复制代码
get()方法最简单，基于数组直接定位到元素，这是 ArrayList 性能最好的一个操作。
(6)remove()方法的源码
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { transient Object[] elementData; ... public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) { System.arraycopy(elementData, index + 1, elementData, index, numMoved); } elementData[--size] = null; return oldValue; } ...}
复制代码
(7)源码分析的总结
一.remove()和 add(index, element)
都会导致数组的拷贝(System.arraycopy())，因此性能都不是太高。所以基于 ArrayList 来进行随机位置的插入和删除，性能不会太高。
二.add()和 add(index, element)
都可能会导致数组需要扩容(ensureCapacityInternal())。由于数组长度是固定的，默认初始大小是 10。如果往数组里添加数据，可能会导致数组不停扩容，影响性能。
三.set()和 get()
可以基于数组实现随机位置的直接定位，性能很高。
4.ArrayList 源码三：数组扩容以及元素拷贝
(1)每次添加元素都判断是否扩容
ArrayList 里最关键的就是：如果数组满了，如何进行扩容，每当往 ArrayList 添加元素都会调用 ensureCapacityInternal()方法。
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { transient Object[] elementData; ... public boolean add(E e) { ensureCapacityInternal(size + 1);//Increments modCount!! elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private void ensureExplicitCapacity(int minCapacity) { modCount++; if (minCapacity - elementData.length > 0) { grow(minCapacity); } } ...}
复制代码
(2)数组扩容一半时会进行数组拷贝
假设 ArrayList 使用的是默认数组大小，也就是 10。现已经往数组添加了 10 个元素，数组的 size = 10，capacity = 10。此时再调用 add()方法插入一个元素，也就是需要插入第 11 个元素，那么肯定是插入不进去的。此时执行的是 ensureCapacityInternal(11)。
elementData 已经填充了 10 个元素，minCapacity = 11。elementData.length 是默认的值，也就是 10。现在要放第 11 个元素，所以就会调用 grow()方法对数组进行扩容。
根据"int newCapacity = oldCapacity + (oldCapacity >> 1);"以及"elementData = Arrays.copyOf(elementData, newCapacity);"可知：老的大小 + 老的大小 >> 1(相当于扩容一半)，得出新数组大小。然后调用 Arrays.copyOf()进行数组拷贝。
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { transient Object[] elementData; ... private void grow(int minCapacity) { //overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) { newCapacity = minCapacity; } if (newCapacity - MAX_ARRAY_SIZE > 0) { newCapacity = hugeCapacity(minCapacity); } //minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } ...}
复制代码
5.LinkedList 源码一：优缺点和使用场景
(1)LinkedList 的优缺点
LinkedList，底层是基于链表来实现的。LinkedList 的优点就是非常适合频繁插入各种元素。LinkedList 的缺点就是不太适合获取某个随机位置的元素。
比如 LinkedList.get(10)这种操作，性能就较低。因为需要遍历链表，直到找到 index = 10 的这个元素为止。
而 ArrayList.get(10)，则不需要遍历，直接根据内存的地址，根据指定的 index，直接定位到那个元素，不需要遍历数组。
ArrayList 和 LinkedList 区别就是数组和链表的区别。
(2)LinkedList 的使用场景
一.ArrayList 的使用场景
一般会使用 ArrayList 来代表一个集合。只要别频繁插入大量元素即可，遍历或者随机查都可以。
二.LinkedList 的使用场景
适合频繁在 list 中插入和删除元素，LinkedList 可以当队列来使用。如果要在内存中实现一个内存队列，那么可以使用 LinkedList。
6.LinkedList 源码二：双向链表数据结构
(1)LinkedList 的双向链表数据结构
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { transient int size = 0; transient Node<E> first; transient Node<E> last; protected transient int modCount = 0; ... private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } } ...}
复制代码
(2)ArrayList 和 LinkedList 的区别
一般的回答：ArrayList 是数组实现的，LinkedList 是链表实现的。
深入的回答：结合 ArrayList 的源码，介绍 add、remove、get、set 方法的实现原理。介绍 ArrayList 数组扩容、元素移动的原理、以及优缺点是什么。LinkedList 则是基于双向链表实现的，可以介绍一下它的数据结构。介绍 LinkedList 一些常见操作的原理、node 是怎么变化的、以及优缺点，以及在哪个项目哪个业务场景下用过 ArrayList 和 LinkedList。
(3)LinkedList 的主要操作
在双向链表头部添加一个元素 / 获取一个元素 / 删除一个元素；
在双向链表尾部添加一个元素 / 获取一个元素 / 删除一个元素；
在双向链表中插入一个元素 / 获取一个元素 / 删除一个元素；
7.LinkedList 源码三：插入元素的原理
(1)add()方法在尾部插入元素(尾插法)
add()方法会向双向链表尾部添加元素，add(2, e)会在 index = 2 的位置插入一个元素，都使用了尾插法。
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { transient int size = 0; transient Node<E> first; transient Node<E> last; protected transient int modCount = 0; ... public boolean add(E e) { linkLast(e); return true; } public void add(int index, E element) { checkPositionIndex(index); if (index == size) { linkLast(element); } else { linkBefore(element, node(index)); } } void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) { first = newNode; } else { l.next = newNode; } size++; modCount++; } void linkBefore(E e, Node<E> succ) { //assert succ != null; final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) { first = newNode; } else { pred.next = newNode; } size++; modCount++; } ...}
复制代码
(2)addFirst()方法在头部插入元素(头插法)
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { transient int size = 0; transient Node<E> first; transient Node<E> last; protected transient int modCount = 0; ... public void addFirst(E e) { linkFirst(e); } private void linkFirst(E e) { final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) { last = newNode; } else { f.prev = newNode; } size++; modCount++; } ...}
复制代码
(3)add(index, e)方法在中间插入元素
add(index, e)方法在调用 linkBefore()方法时会调用 node()方法，这个 node()方法就是用来返回位置为 index 的那个结点的。node()方法会根据 index 判断是在队列的前半部分还是后半部分，然后决定从头进行遍历还是从尾进行遍历。获取到位置为 index 的结点后，便可以通过 linkBefore()方法插入元素。
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { transient int size = 0; transient Node<E> first; transient Node<E> last; protected transient int modCount = 0; ... public void add(int index, E element) { checkPositionIndex(index); if (index == size) { linkLast(element); } else { linkBefore(element, node(index)); } } Node<E> node(int index) { //assert isElementIndex(index); if (index < (size >> 1)) { //如果index < size / 2，说明要找的结点是在队列的前半部分，从队头遍历 Node<E> x = first; for (int i = 0; i < index; i++) { x = x.next; } return x; } else { //如果index >= size / 2，说明要找的结点是在队列的后半部分，从队尾开始遍历 Node<E> x = last; for (int i = size - 1; i > index; i--) { x = x.prev; } return x; } } void linkBefore(E e, Node<E> succ) { //assert succ != null; final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) { first = newNode; } else { pred.next = newNode; } size++; modCount++; } ...}
复制代码
(4)LinkedList 的主要方法
一.add()方法
在双向链表的尾部插入一个元素。
二.add(index, element)方法
在双向链表的中间插入一个元素。
三.addFirst()方法
在双向链表的头部插入一个元素。
四.addLast()方法
和 add()方法一样也是在双向链表尾部插入一个元素。
五.offer()方法
在双向链表的尾部插入一个元素。
六.poll()方法
从双向链表头部获取一个元素并删除元素。
七.peek()方法
获取双向链表头部的元素，但是头部的元素不删除，所以 LinkedList 也可以作为一个队列来使用。
8.LinkedList 源码四：获取元素的原理
(1)getFirst()方法和 peek()方法
getFirst()方法获取头部的元素，直接返回 first 指针指向的那个 Node 元素。如果对空的 LinkedList 调用 getFirst()方法，会抛出异常。
peek()方法也获取头部的元素，直接返回 first 指针指向的那个 Node 元素。如果对空的 LinkedList 调用 peek()方法，会返回 null。
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { transient Node<E> first; ... public E getFirst() { final Node<E> f = first; if (f == null) { throw new NoSuchElementException(); } return f.item; } public E peek() { final Node<E> f = first; return (f == null) ? null : f.item; } ...}
复制代码
(2)getLast()方法
getLast()方法会获取双向链表尾部的元素。
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { transient Node<E> last; ... public E getLast() { final Node<E> l = last; if (l == null) { throw new NoSuchElementException(); } return l.item; } ...}
复制代码
(3)get(int index)方法
get(int index)方法会随机获取双向链表在 index 位置上的元素。
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { transient int size = 0; transient Node<E> first; transient Node<E> last; ... public E get(int index) { checkElementIndex(index); return node(index).item; } Node<E> node(int index) { //assert isElementIndex(index); if (index < (size >> 1)) { //如果index < size / 2，说明要找的结点是在队列的前半部分，从队头遍历 Node<E> x = first; for (int i = 0; i < index; i++) { x = x.next; } return x; } else { //如果index >= size / 2，说明要找的结点是在队列的后半部分，从队尾开始遍历 Node<E> x = last; for (int i = size - 1; i > index; i--) { x = x.prev; } return x; } } ...}
复制代码
(4)总结
对于 ArrayList 而言，如果要获取某个随机位置的元素，则其 get(int index)方法会直接通过数组的 index 定位到该元素，性能超高。
对 LinkedList 而言，如果要获取某个随机位置的元素，则其 get(int index)方法需调用 node(index)这个方法，进行链表的遍历。也就是会比较 index 和 size >> 1(链表元素一半)的大小，如果在前半部分就从头开始遍历，如果在后半部分就从尾开始遍历。
9.LinkedList 源码五：删除元素的原理
(1)removeLast()方法
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { transient int size = 0; transient Node<E> first; transient Node<E> last; ... public E removeLast() { final Node<E> l = last; if (l == null) { throw new NoSuchElementException(); } return unlinkLast(l); } private E unlinkLast(Node<E> l) { //assert l == last && l != null; final E element = l.item; final Node<E> prev = l.prev; l.item = null; l.prev = null;//help GC last = prev; if (prev == null) { first = null; } else { prev.next = null; } size--; modCount++; return element; } ...}
复制代码
(2)removeFirst()方法和 poll()方法
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { transient int size = 0; transient Node<E> first; transient Node<E> last; ... public E removeFirst() { final Node<E> f = first; if (f == null) { throw new NoSuchElementException(); } return unlinkFirst(f); } public E poll() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); } private E unlinkFirst(Node<E> f) { //assert f == first && f != null; final E element = f.item; final Node<E> next = f.next; f.item = null; f.next = null;//help GC first = next; if (next == null) { last = null; } else { next.prev = null; } size--; modCount++; return element; } ...}
复制代码
(3)remove(int index)方法
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { transient int size = 0; transient Node<E> first; transient Node<E> last; ... public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } E unlink(Node<E> x) { //assert x != null; final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev;
if (prev == null) { first = next; } else { prev.next = next; x.prev = null; }
if (next == null) { last = prev; } else { next.prev = prev; x.next = null; }
x.item = null; size--; modCount++; return element; } Node<E> node(int index) { //assert isElementIndex(index); if (index < (size >> 1)) { //如果index < size / 2，说明要找的结点是在队列的前半部分，从队头遍历 Node<E> x = first; for (int i = 0; i < index; i++) { x = x.next; } return x; } else { //如果index >= size / 2，说明要找的结点是在队列的后半部分，从队尾开始遍历 Node<E> x = last; for (int i = size - 1; i > index; i--) { x = x.prev; } return x; } } ...}
复制代码
(4)总结
如果往 LinkedList 里插入大量数据(队头、队尾、队列中间)，由于基于链表实现，不会出现大量的元素移动，也不会出现数组扩容。但在中间插入元素的性能没有在队头和队尾插入元素的性能好，因为需要遍历到指定的位置，然后才能完成元素的插入。
所以基于链表的 LinkedList 很适合做队列，缺点是随机位置获取一个元素会导致遍历。如果元素很多，遍历的性能可能比较差。
10.Vector 和 Stack：栈的数据结构和源码
(1)栈的数据结构
栈是由 Vector 和 Stack 这两个类来实现的。Stack 代表了栈这种数据结构，它是继承自 Vector 的。
Vector 是一种类似 ArrayList 的数据结构(基于数组实现)，是有序的集合。
Stack 是一种基于数组来实现的栈数据结构。栈是先进后出，队列是先进先出。栈的使用一般通过 push()和 pop()，将元素压入栈底和从栈顶弹出元素；
(2)栈的 push()方法
栈的 push()方法会将元素压入栈底。Stack.push()方法和 ArrayList.add()方法的的实现源码几乎是一样的：就是放在数组按顺序排列的位置上。
public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { protected Object[] elementData; protected int elementCount; protected int capacityIncrement; protected transient int modCount = 0; ... public Vector() { this(10); } public Vector(int initialCapacity) { this(initialCapacity, 0); } public Vector(int initialCapacity, int capacityIncrement) { super(); if (initialCapacity < 0) { throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity); } this.elementData = new Object[initialCapacity]; this.capacityIncrement = capacityIncrement; } ...}
public class Stack<E> extends Vector<E> { public E push(E item) { addElement(item); return item; } public synchronized void addElement(E obj) { modCount++; ensureCapacityHelper(elementCount + 1); elementData[elementCount++] = obj; } private void ensureCapacityHelper(int minCapacity) { //overflow-conscious code if (minCapacity - elementData.length > 0) { grow(minCapacity); } } private void grow(int minCapacity) { //overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity); if (newCapacity - minCapacity < 0) { newCapacity = minCapacity; } if (newCapacity - MAX_ARRAY_SIZE > 0) { newCapacity = hugeCapacity(minCapacity); } elementData = Arrays.copyOf(elementData, newCapacity); } ...}
复制代码
ArrayList 默认每次扩容成原来的 1.5 倍，Vector 默认每次扩容成原来的 2 倍。Vector 将元素压入栈底时，elementData[elementCount++] = element。看这些源码可学习如何使用 System.arraycopy()、Arrays.copyOf()方法。
(3)栈的 pop()方法和 peek()方法
Stack.pop()方法和 Stack.peek()方法会从栈顶弹出一个元素。也就是最后一个压入栈的元素，会通过 Stack.pop()方法从栈顶弹出。首先使用 elementData[size - 1]获取最后一个元素，返回给用户。然后通过 removeElementAt(size - 1)方法删除最后一个元素。
public class Stack<E> extends Vector<E> { ... public synchronized E pop() { E obj; int len = size(); obj = peek(); removeElementAt(len - 1); return obj; }
public synchronized E peek() { int len = size(); if (len == 0) { throw new EmptyStackException(); } return elementAt(len - 1); }
public synchronized void removeElementAt(int index) { modCount++; if (index >= elementCount) { throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount); } else if (index < 0) { throw new ArrayIndexOutOfBoundsException(index); } int j = elementCount - index - 1; if (j > 0) { System.arraycopy(elementData, index + 1, elementData, index, j); } elementCount--; elementData[elementCount] = null; /* to let gc do its work */ } ...}
复制代码
11.HashMap 源码一：数组 + 链表 + 红黑树
(1)关于 HashMap 的问题
HashMap 应该是整个 JDK 集合包源码剖析的重点，关于 HashMap 底层原理或者源码的问题如下。
一.基础问法
哈希冲突的时候怎么解决：用链表来处理。
二.初级问法
HashMap 的原理：对 key 进行哈希运算，找到对应的位置进行存放。
三.中级问法
HashMap 的扩容是怎么处理的，扩容的原理。
四.资深问法
JDK 1.8 以后 HashMap 底层做了哪些优化，HashMap 底层的源码。迭代集合时，Fail-Fast 机制和 ConcurrentModificationException。
(2)HashMap 的基本数据结构和原理
一.HashMap 设置元素和获取元素的流程
如果要对一个 HashMap 执行 map.put(1, "张三")，map.put(2, "李四")。首先对一个 key 进行 hashCode()运算，获取该 key 的哈希值。然后常规的做法是用这个哈希值对数组的长度进行取模。接着根据取模的结果，将 key-value 对放在数组中的某个元素上。
如果要对一个 HashMap 执行 map.get(1)，同理会先根据 key 获取哈希值。然后根据哈希值对数组长度取模，这样就知道 key 对应的 value 在哪里。
二.HashMap 设置元素时出现哈希冲突的处理
如果某两个 key 对应的 Hash 值一样，该怎么处理？
在 JDK 1.8 以前，使用的是数组 + 链表来进行处理。如果出现大量哈希冲突，那么遍历长链表寻找 key-value 对时的复杂度是 O(n)。
在 JDK 1.8 以后，使用的是数组 + 链表 + 红黑树来进行处理。如果链表长度超过 8，会自动将链表转换为红黑树，那么查找 key-value 对时的复杂度是 O(logn)。
下图要搜索 map.get(38)，如果是链表的话，必须要遍历 5 个结点。如果是红黑树的话，只要找 3 个结点，就可以找到那个 38 的值。
(3)红黑树的特点
一.红黑树是二叉查找树，左小右大，根据这个规则可以快速查找某个值。
二.普通的二叉查找树，有可能出现瘸腿的情况。也就是只有一条腿，出现不平衡了，导致查询的性能变成了 O(n)，退化成线性查询了。
三.红黑树，有红色和黑色两种结点。有一些条件限制来尽量保证树是平衡的，不会出现瘸腿的情况。
四.如果插入结点的时候破坏了红黑树的规则和平衡，那么会自动重新平衡。变色(红 <-> 黑)、旋转、左旋转、右旋转。
JDK 1.8+，在链表长度为 8 以后，链表 -> 红黑树。链表的遍历性能，时间复杂度是 O(n)，红黑树是 O(logn)。所以如果出现大量哈希冲突后，红黑树的性能比链表高得多。
JDK 1.8+，HashMap 的数据结构是：
数组 + 链表 + 红黑树。
12.HashMap 源码二：核心成员变量的作用分析
(1)HashMap 的数组默认大小 16
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { //The default initial capacity - MUST be a power of two. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 ...}
复制代码
HashMap 的数组的默认初始大小是 16；
ArrayList 的数组的默认初始大小是 10；
(2)HashMap 的默认负载因子 0.75
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { //The load factor used when none specified in constructor. static final float DEFAULT_LOAD_FACTOR = 0.75f; ...}
复制代码
默认的负载因子为 0.75。如果数组里的元素个数达到了数组大小(16) * 负载因子(0.75)，也就是数组元素达到 12 个时就会进行数组扩容。
(3)HashMap 的结点内部类 Node
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { ... //Basic hash bin node, used for most entries. //(See below for TreeNode subclass, and in LinkedHashMap for its Entry subclass.) static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; ... }}
复制代码
Node 是 HashMap 的内部类，它代表了一个 key-value 对。一个 Node 结点里包含了：key 的哈希值、key、value、一个 next 指针。这个 next 指针会指向下一个 Node，也就是单向链表中的下一个结点。通过这个 next 指针就可以形成一个链表，来解决哈希冲突。
(4)HashMap 的 Node 数组 table
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { //The table, initialized on first use, and resized as necessary. //When allocated, length is always a power of two. //(We also tolerate length zero in some operations to allow bootstrapping mechanics that are currently not needed.) transient Node<K,V>[] table; ...}
复制代码
Node[]，这个数组就是 HashMap 里的核心数据结构的数组。数组的元素是 Node 类型的，天然就可以挂成一个单向链表，因为 Node 里面会有一个 next 指针。
(5)HashMap 中的 key-value 对数量
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { //The number of key-value mappings contained in this map. transient int size; ...}
复制代码
这个 size 就是当前 HashMap 中有多少个 key-value 对。如果该数量达到了指定大小 * 负载因子，那么就会进行数组扩容。
(6)HashMap 的扩容阈值
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { //The next size value at which to resize (capacity * load factor). int threshold; final int capacity() { return (table != null) ? table.length : (threshold > 0) ? threshold : DEFAULT_INITIAL_CAPACITY; } ...}
复制代码
扩容阈值 threshold = 数组容量 * 负载因子。如果 size 达到 threshold，那么 HashMap 就会进行数组扩容。
扩容原理涉及：负载因子、默认值、threshold、扩容、rehash 的算法。
(7)HashMap 的负载因子
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { //The load factor for the hash table. final float loadFactor; ...}
复制代码
这就是负载因子，默认值是 0.75f，也可以自己指定，一般不会修改。HashMap 数组的初始容量，一般会手动指定。和使用 ArrayList 一样，需要预估会放多少 key-value 对，避免频繁扩容。
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { //The load factor used when none specified in constructor. static final float DEFAULT_LOAD_FACTOR = 0.75f;
//The load factor for the hash table. final float loadFactor; //Constructs an empty HashMap with the default initial capacity (16) and the default load factor (0.75). public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } //Constructs an empty HashMap with the specified initial capacity and the default load factor (0.75). //@param initialCapacity the initial capacity. public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) { throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); } if (initialCapacity > MAXIMUM_CAPACITY) { initialCapacity = MAXIMUM_CAPACITY; } if (loadFactor <= 0 || Float.isNaN(loadFactor)) { throw new IllegalArgumentException("Illegal load factor: " + loadFactor); } this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); } //Returns a power of two size for the given target capacity. static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; } ...}
复制代码
(8)HashMap 的构造方法
构造方法只是对 HashMap 的负载因子和扩容阈值进行赋值，具体的数组初始化则是在执行 put()方法时才开始进行处理的。
13.HashMap 源码三：降低哈希冲突概率的算法
(1)HashMap 的 put()方法会先对 key 进行哈希
通过 key 的哈希值获取到对应数组中的 index 位置。
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { //Associates the specified value with the specified key in this map. //If the map previously contained a mapping for the key, the old value is replaced. public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } ...}
复制代码
(2)Hash 算法的工作原理
HashMap 里的 Hash 算法是经过优化的、高性能的。HashMap 的 hash()方法会对 key 执行具体的 Hash 算法来获取一个 Hash 值。
首先通过 key.hashCode()获取 key 的 HashCode，然后通过 h >>> 16 对 HashCode 进行右移 16 位，也就是把 32 位的二进制数字的所有 bit 往右侧移动 16 位，最后将右移 16 位的结果和 HashCode 进行异或运算。
假设h = 1111 1111 1111 1111 1111 1010 0111 1100那么h >>> 16 = 0000 0000 0000 0000 1111 1111 1111 1111接着h ^ (h >>> 16)，异或也就是：1111 1111 1111 1111 1111 1010 0111 11000000 0000 0000 0000 1111 1111 1111 11111111 1111 1111 1111 1111 0101 1000 0011
复制代码
实际上就是将 32 位的 key.hashCode()的高 16 位和低 16 位进行异或运算，这样可以降低哈希冲突的概率。
(3)如何降低哈希冲突的概率
为什么要将 32 位的 key.hashCode()的高 16 位和低 16 位进行异或运算？
因为首先 HashMap 的数组的默认初始大小是 16，然后在 get()方法会用这个异或运算的结果值定位数组的 index 时，默认情况下就会将数组大小 16 和异或运算的结果值进行位与运算。当然随着数组扩容，之后可能用 32 和异或运算的结果值进行位与运算。
当使用数组大小 16 和异或运算的结果值进行位与运算时：由于 HashCode 是 32 位，所以运算结果最多只能利用 HashCode 低 16 位。因此为了尽量利用到 HashCode 的 32 位，降低哈希冲突的概率，才对 HashCode 进行高低 16 位的异或处理。否则如果直接使用 HashCode 的低 16 位进行位与运算，则冲突更多。
而当使用扩容后的数组大小 32 和异或运算的结果值进行位与运算时，即使不对 HashCode 进行高低 16 位异或，也能利用到 32 位的 HashCode。
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { public V get(Object key) { Node<K,V> 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<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) { 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<K,V>)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; } ...}
复制代码
(4)总结
在 HashMap 的 hash()方法里，把 HashCode 的高低 16 位进行异或运算，可保证异或运算结果同时保留 HashCode 的高 16 位和低 16 位的特征。
于是在 get()方法中通过位运算定位数组 index 时，即使只有低 16 位参与运算，HashCode 的高低 16 位特征也参与到运算中。相比于直接使用 HashCode 的低 16 位去定位数组 index，能减少哈希冲突。
14.HashMap 源码四：put 操作及哈希寻址算法
(1)HashMap.put()方法的源码
首先会通过 HashMap.hash()方法的哈希算法根据 key 获取其哈希值，然后调用 HashMap.putVal()方法把对应的键和值设置到 HashMap 数组。
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, 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<K,V>[] tab; 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); } else { Node<K,V> 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<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); 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<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> 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<K,V>[] resize() { //第一次执行HashMap的put()方法时，table为null Node<K,V>[] 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<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; ... return newTab; } ...}
复制代码
(3)通过位与运算的哈希寻址算法设置数组值
接着执行"hash & (n - 1)"代码，其中 n 是 16，所以变成"15 & hash"：
1111 1111 1111 1111 0000 0101 1000 00110000 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<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; 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); } ... } Node<K,V> newNode(int hash, K key, V value, Node<K,V> 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<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> 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<K,V> extends AbstractMap<K,V> implements Map<K,V>, 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<K,V>[] tab; 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) { //如果通过哈希寻址算法定位到的下标为i的数组元素为空(即tab[i]为空) //那么就可以直接将一个新创建的Node对象放到数组的tab[i]这个位置； tab[i] = newNode(hash, key, value, null); } else { Node<K,V> 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<K,V>)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)红黑树的查找复杂度比链表的低
如果出现大量的哈希冲突后，某位置挂的一个链表可能会特别的长。如果链表长度太长，那么就会导致有一些 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<K,V> extends AbstractMap<K,V> implements Map<K,V>, 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<K,V>[] tab, int hash) { int n, index; Node<K,V> e; if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) { resize(); } else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; //通过do while循环将Node类型的单向链表转换为TreeNode类型的双向链表 do { TreeNode<K,V> 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<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> 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<K,V> extends AbstractMap<K,V> implements Map<K,V>, 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<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent;//red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev;//needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node<K,V> next) { super(hash, key, val, next); } //Forms tree of the nodes linked from this node. final void treeify(Node<K,V>[] tab) { TreeNode<K,V> root = null; for (TreeNode<K,V> x = this, next; x != null; x = next) { next = (TreeNode<K,V>)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<K,V> 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<K,V> 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<K,V> extends HashMap<K,V> implements Map<K,V> { ... static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } } ...}
复制代码
17.HashMap 源码七：哈希冲突时插入红黑树
假设现在某个 table[i]已经是一颗红黑树了。如果此时在 table[i]再次出现哈希冲突，则会在红黑树中插入一个元素，也就是在 HashMap 的 putVal()方法中调用 TreeNode 的 putTreeVal()方法。红黑树是一个平衡的二叉查找树，插入元素时需要变色、旋转。TreeNode.putTreeVal()方法会在保持平衡的前提下，插入元素到红黑树。
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, 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<K,V>[] tab; 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) { //如果通过哈希寻址算法定位到的下标为i的数组元素为空(即tab[i]为空) //那么就可以直接将一个新创建的Node对象放到数组的tab[i]这个位置； tab[i] = newNode(hash, key, value, null); } else { Node<K,V> 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<K,V>)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<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent;//red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev;//needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node<K,V> next) { super(hash, key, val, next); } ... //Tree version of putVal. final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v) { Class<?> kc = null; boolean searched = false; TreeNode<K,V> root = (parent != null) ? root() : this; for (TreeNode<K,V> 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<K,V> 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<K,V> xp = p; if ((p = (dir <= 0) ? p.left : p.right) == null) { Node<K,V> xpn = xp.next; TreeNode<K,V> 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<K,V>)xpn).prev = x; } moveRootToFront(tab, balanceInsertion(root, x)); return null; } } } ... } ...}
复制代码
18.HashMap 源码八：JDK 1.7 的数组扩容原理
(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 的数组扩容原理
JDK 1.8 为提升 rehash 性能，不再使用 key 的 hash 值对新数组大小取模。而使用位与操作实现哈希寻址，因为直接取模的性能比较低。
(1)出现 hash 冲突的例子
如下两个 hash 值会出现哈希冲突，HashMap 使用链表 + 红黑树解决。
n - 1 0000 0000 0000 0000 0000 0000 0000 1111hash值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 1111hash值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<K,V> extends AbstractMap<K,V> implements Map<K,V>, 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<K,V>[] tab; 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) { //如果通过哈希寻址算法定位到的下标为i的数组元素为空(即tab[i]为空) //那么就可以直接将一个新创建的Node对象放到数组的tab[i]这个位置； tab[i] = newNode(hash, key, value, null); } else { Node<K,V> 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<K,V>)p).putTreeVal(this, tab, hash, key, value); } else { ... } ... } ++modCount; //判断数组大小size，是否已经达到了扩容阈值threshold大小 if (++size > threshold) { resize(); } afterNodeInsertion(evict); return null; } 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; } 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<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; //如果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<K,V>)e).split(this, newTab, j, oldCap); } else {//preserve order //进入这个else分支的话，证明是链表 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); //要么直接放在新数组的原来的那个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 1111hash值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 1111hash值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()方法源码
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { ... public V get(Object key) { Node<K,V> 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<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) { 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<K,V>)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<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent;//red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev;//needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node<K,V> next) { super(hash, key, val, next); } ... //Calls find for root node. final TreeNode<K,V> getTreeNode(int h, Object k) { return ((parent != null) ? root() : this).find(h, k, null); } //Returns root of tree containing this node. final TreeNode<K,V> root() { for (TreeNode<K,V> 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<K,V> find(int h, Object k, Class<?> kc) { TreeNode<K,V> p = this; do { int ph, dir; K pk; TreeNode<K,V> 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<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { ... public V remove(Object key) { Node<K,V> 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<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { Node<K,V>[] tab; Node<K,V> p; int n, index; if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { Node<K,V> 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<K,V>)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<K,V>)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<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent;//red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev;//needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node<K,V> 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<K,V> map, Node<K,V>[] tab, boolean movable) { int n; if (tab == null || (n = tab.length) == 0) { return; } int index = (n - 1) & hash; TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl; TreeNode<K,V> succ = (TreeNode<K,V>)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<K,V> p = this, pl = left, pr = right, replacement; if (pl != null && pr != null) { TreeNode<K,V> 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<K,V> sr = s.right; TreeNode<K,V> pp = p.parent; if (s == pr) {// p was s's direct parent p.parent = s; s.right = p; } else { TreeNode<K,V> 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<K,V> 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<K,V> r = p.red ? root : balanceDeletion(root, replacement); if (replacement == p) { // detach TreeNode<K,V> 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 的遍历顺序
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<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { ... final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; 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); } else { ... } } Node<K,V> newNode(int hash, K key, V value, Node<K,V> 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<K,V> extends HashMap<K,V> implements Map<K,V> { //HashMap.Node subclass for normal LinkedHashMap entries. static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } } ... //The head (eldest) of the doubly linked list. transient LinkedHashMap.Entry<K,V> head;
//The tail (youngest) of the doubly linked list. transient LinkedHashMap.Entry<K,V> tail; Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) { LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e); linkNodeLast(p); return p; }
//通过尾插法维护一个双向链表 private void linkNodeLast(LinkedHashMap.Entry<K,V> p) { LinkedHashMap.Entry<K,V> 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<K,V> extends HashMap<K,V> implements Map<K,V> { ... public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; }
public V get(Object key) { Node<K,V> e; if ((e = getNode(hash(key), key)) == null) { return null; } if (accessOrder) { afterNodeAccess(e); } return e.value; }
void afterNodeAccess(Node<K,V> e) {//move node to last LinkedHashMap.Entry<K,V> last; if (accessOrder && (last = tail) != e) { LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)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<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable { ... static final class Entry<K,V> implements Map.Entry<K,V> { K key; V value; Entry<K,V> left; Entry<K,V> right; Entry<K,V> parent; boolean color = BLACK; } ...}
复制代码
23.HashSet + LinkedHashSet + TreeSet 简介
(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 机制
也就是一个线程在迭代遍历集合，另一个线程在修改集合时：迭代的线程会快速报异常：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<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { ... @Override public void forEach(Consumer<? super E> 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<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { ... transient int modCount; @Override public void forEach(BiConsumer<? super K, ? super V> action) { Node<K,V>[] 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<K,V> e = tab[i]; e != null; e = e.next) { action.accept(e.key, e.value); } } if (modCount != mc) { throw new ConcurrentModificationException(); } } } ...}
复制代码
文章转载自：东阳马生架构
原文链接：https://www.cnblogs.com/mjunz/p/18712313
体验地址：http://www.jnpfsoft.com/?from=001YH
评论