JUC并发—1.Java集合包底层源码剖析一
大纲
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机制
1.为什么要对JDK源码剖析
简单的框架源码有：Spring Cloud，ByteTcc分布式事务，Redisson以及Curator等框架源码。
较难的框架源码有：ZooKeeper，Dubbo、Netty、RocketMQ、Sharding-JDBC等框架源码。
看这些源码的时候，都有一些基础性的代码逻辑，比如：内存里的各种数据结构(List、Map、Set)、并发、网络请求、磁盘IO等。
其实对于各种各样的框架系统的底层，最核心的部分，基本都是：
一.集合(在内存里面存放数据)
二.并发(系统底层都会开多个线程进行并发处理，会涉及锁、同步等)
三.IO(读写磁盘上的文件数据、或者发起网络IO通过网络读写数据)
四.网络(在分布式系统中给各个机器建立网络连接，互相发送请求通信)
2.ArrayList源码一：基本原理以及优缺点
(1)数组长度固定需要扩容和拷贝
(2)添加元素导致大量移动元素
(3)基于数组非常适合随机读
(4)总结
(1)数组长度固定需要扩容和拷贝
由于Java里的数组都是定长数组，数组的长度是固定的。比如数组大小设置为100，此时不停的往ArrayList里面塞入数据，当元素数量超过了100以后，此时就会发生数组的扩容，就会申请更大的数组，把旧数组元素拷贝到新数组里去。
这个数组扩容 + 元素拷贝的过程，相对来说会慢一些。所以使用ArrayList时要注意，不要频繁往ArraList里面去塞数据，而导致频繁的数组扩容影响性能。
(2)添加元素导致大量移动元素
由于基于数组来实现，当往数组中添加元素，会导致移动元素。
(3)基于数组非常适合随机读
由于基于数组来实现，所以非常适合随机读。可以随机的去读数组中的某个元素，这个随机读的性能是比较高的，可以直接通过内存地址来定位某个元素。
(4)总结
如果不会频繁插入元素，导致频繁的移动元素位置、List扩容，而主要用于遍历集合或通过索引随机读取元素，那么可以用ArrayList。
如果会频繁插入元素到List中，那么尽量还是不要用ArrayList，因为很可能会造成大量的元素移动 + 数组扩容 + 元素拷贝。
3.ArrayList源码二：核心方法的原理
(1)构造方法的源码
(2)add()方法的源码
(3)set()方法的源码
(4)add(index, element)方法的源码
(5)get()方法的源码
(6)remove()方法的源码
(7)源码分析的总结
(1)构造方法的源码
如果不传参直接初始化一个ArrayList对象，则会执行默认的构造方法。默认的构造方法会将内部的数组设成一个默认的空数组。
public class ArrayList extends AbstractList implements List, 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 extends AbstractList implements List, 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 extends AbstractList implements List, 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 extends AbstractList implements List, 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 extends AbstractList implements List, 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 extends AbstractList implements List, 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 extends AbstractList implements List, 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 extends AbstractList implements List, 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)每次添加元素都判断是否扩容
(2)数组扩容一半时会进行数组拷贝
(1)每次添加元素都判断是否扩容
ArrayList里最关键的就是：如果数组满了，如何进行扩容，每当往ArrayList添加元素都会调用ensureCapacityInternal()方法。
public class ArrayList extends AbstractList implements List, 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 extends AbstractList implements List, 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的优缺点
(2)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的双向链表数据结构
(2)ArrayList和LinkedList的区别
(3)LinkedList的主要操作
(1)LinkedList的双向链表数据结构
public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable {
transient int size = 0;
transient Node first;
transient Node last;
protected transient int modCount = 0;
...
private static class Node {
E item;
Node next;
Node prev;
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
...
} LinkedList的数据结构如下：
(2)ArrayList和LinkedList的区别
一般的回答：ArrayList是数组实现的，LinkedList是链表实现的。
深入的回答：结合ArrayList的源码，介绍add、remove、get、set方法的实现原理。介绍ArrayList数组扩容、元素移动的原理、以及优缺点是什么。LinkedList则是基于双向链表实现的，可以介绍一下它的数据结构。介绍LinkedList一些常见操作的原理、node是怎么变化的、以及优缺点，以及在哪个项目哪个业务场景下用过ArrayList和LinkedList。
(3)LinkedList的主要操作
在双向链表头部添加一个元素 / 获取一个元素 / 删除一个元素；
在双向链表尾部添加一个元素 / 获取一个元素 / 删除一个元素；
在双向链表中插入一个元素 / 获取一个元素 / 删除一个元素；
7.LinkedList源码三：插入元素的原理
(1)add()方法在尾部插入元素(尾插法)
(2)addFirst()方法在头部插入元素(头插法)
(3)add(index, e)方法在中间插入元素
(4)LinkedList的主要方法
(1)add()方法在尾部插入元素(尾插法)
add()方法会向双向链表尾部添加元素，add(2, e)会在index = 2的位置插入一个元素，都使用了尾插法。
public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable {
transient int size = 0;
transient Node first;
transient Node 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 l = last;
final Node newNode = new Node<>(l, e, null);
last = newNode;
if (l == null) {
first = newNode;
} else {
l.next = newNode;
}
size++;
modCount++;
}
void linkBefore(E e, Node succ) {
//assert succ != null;
final Node pred = succ.prev;
final Node 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 extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable {
transient int size = 0;
transient Node first;
transient Node last;
protected transient int modCount = 0;
...
public void addFirst(E e) {
linkFirst(e);
}
private void linkFirst(E e) {
final Node f = first;
final Node 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 extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable {
transient int size = 0;
transient Node first;
transient Node 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 node(int index) {
//assert isElementIndex(index);
if (index < size>> 1)) {
//如果index < size / 2，说明要找的结点是在队列的前半部分，从队头遍历
Node x = first;
for (int i = 0; i < index i x='x.next;' return x else index>= size / 2，说明要找的结点是在队列的后半部分，从队尾开始遍历
Node x = last;
for (int i = size - 1; i > index; i--) {
x = x.prev;
}
return x;
}
}
void linkBefore(E e, Node succ) {
//assert succ != null;
final Node pred = succ.prev;
final Node 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()方法
(2)getLast()方法
(3)get(int index)方法
(4)总结
(1)getFirst()方法和peek()方法
getFirst()方法获取头部的元素，直接返回first指针指向的那个Node元素。如果对空的LinkedList调用getFirst()方法，会抛出异常。
peek()方法也获取头部的元素，直接返回first指针指向的那个Node元素。如果对空的LinkedList调用peek()方法，会返回null。
public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable {
transient Node first;
...
public E getFirst() {
final Node f = first;
if (f == null) {
throw new NoSuchElementException();
}
return f.item;
}
public E peek() {
final Node f = first;
return (f == null) ? null : f.item;
}
...
} (2)getLast()方法
getLast()方法会获取双向链表尾部的元素。
public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable {
transient Node last;
...
public E getLast() {
final Node l = last;
if (l == null) {
throw new NoSuchElementException();
}
return l.item;
}
...
} (3)get(int index)方法
get(int index)方法会随机获取双向链表在index位置上的元素。
public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable {
transient int size = 0;
transient Node first;
transient Node last;
...
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node node(int index) {
//assert isElementIndex(index);
if (index < size>> 1)) {
//如果index < size / 2，说明要找的结点是在队列的前半部分，从队头遍历
Node x = first;
for (int i = 0; i < index i x='x.next;' return x else index>= size / 2，说明要找的结点是在队列的后半部分，从队尾开始遍历
Node 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()方法
(2)removeFirst()方法和poll()方法
(3)remove(int index)方法
(4)总结
(1)removeLast()方法
public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable {
transient int size = 0;
transient Node first;
transient Node last;
...
public E removeLast() {
final Node l = last;
if (l == null) {
throw new NoSuchElementException();
}
return unlinkLast(l);
}
private E unlinkLast(Node l) {
//assert l == last && l != null;
final E element = l.item;
final Node 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 extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable {
transient int size = 0;
transient Node first;
transient Node last;
...
public E removeFirst() {
final Node f = first;
if (f == null) {
throw new NoSuchElementException();
}
return unlinkFirst(f);
}
public E poll() {
final Node f = first;
return (f == null) ? null : unlinkFirst(f);
}
private E unlinkFirst(Node f) {
//assert f == first && f != null;
final E element = f.item;
final Node 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 extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable {
transient int size = 0;
transient Node first;
transient Node last;
...
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
E unlink(Node x) {
//assert x != null;
final E element = x.item;
final Node next = x.next;
final Node 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 node(int index) {
//assert isElementIndex(index);
if (index < size>> 1)) {
//如果index < size / 2，说明要找的结点是在队列的前半部分，从队头遍历
Node x = first;
for (int i = 0; i < index i x='x.next;' return x else index>= size / 2，说明要找的结点是在队列的后半部分，从队尾开始遍历
Node x = last;
for (int i = size - 1; i > index; i--) {
x = x.prev;
}
return x;
}
}
...
} (4)总结
如果往LinkedList里插入大量数据(队头、队尾、队列中间)，由于基于链表实现，不会出现大量的元素移动，也不会出现数组扩容。但在中间插入元素的性能没有在队头和队尾插入元素的性能好，因为需要遍历到指定的位置，然后才能完成元素的插入。
所以基于链表的LinkedList很适合做队列，缺点是随机位置获取一个元素会导致遍历。如果元素很多，遍历的性能可能比较差。
10.Vector和Stack：栈的数据结构和源码
(1)栈的数据结构
(2)栈的push()方法
(3)栈的pop()方法和peek()方法
(1)栈的数据结构
栈是由Vector和Stack这两个类来实现的。Stack代表了栈这种数据结构，它是继承自Vector的。
Vector是一种类似ArrayList的数据结构(基于数组实现)，是有序的集合。
Stack是一种基于数组来实现的栈数据结构。栈是先进后出，队列是先进先出。栈的使用一般通过push()和pop()，将元素压入栈底和从栈顶弹出元素；
(2)栈的push()方法
栈的push()方法会将元素压入栈底。Stack.push()方法和ArrayList.add()方法的的实现源码几乎是一样的：就是放在数组按顺序排列的位置上。
public class Vector extends AbstractList implements List, 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 extends Vector {
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 extends Vector {
...
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 arrayindexoutofboundsexceptionindex 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的问题
(2)HashMap的基本数据结构和原理
(3)红黑树的特点
(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
(2)HashMap的默认负载因子0.75
(3)HashMap的结点内部类Node
(4)HashMap的Node数组table
(5)HashMap中的key-value对数量
(6)HashMap的扩容阈值
(7)HashMap的负载因子
(8)HashMap的构造方法
(1)HashMap的数组默认大小16
public class HashMap extends AbstractMap implements Map, 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 extends AbstractMap implements Map, 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 extends AbstractMap implements Map, 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 implements Map.Entry {
final int hash;
final K key;
V value;
Node next;
...
}
} Node是HashMap的内部类，它代表了一个key-value对。一个Node结点里包含了：key的哈希值、key、value、一个next指针。这个next指针会指向下一个Node，也就是单向链表中的下一个结点。通过这个next指针就可以形成一个链表，来解决哈希冲突。
(4)HashMap的Node数组table
public class HashMap extends AbstractMap implements Map, 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[] table;
...
} Node[]，这个数组就是HashMap里的核心数据结构的数组。数组的元素是Node类型的，天然就可以挂成一个单向链表，因为Node里面会有一个next指针。
(5)HashMap中的key-value对数量
public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {
//The number of key-value mappings contained in this map.
transient int size;
...
} 这个size就是当前HashMap中有多少个key-value对。如果该数量达到了指定大小 * 负载因子，那么就会进行数组扩容。
(6)HashMap的扩容阈值
public class HashMap extends AbstractMap implements Map, 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 extends AbstractMap implements Map, Cloneable, Serializable {
//The load factor for the hash table.
final float loadFactor;
...
} 这就是负载因子，默认值是0.75f，也可以自己指定，一般不会修改。HashMap数组的初始容量，一般会手动指定。和使用ArrayList一样，需要预估会放多少key-value对，避免频繁扩容。
public class HashMap extends AbstractMap implements Map, 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 illegalargumentexceptionillegal initial capacity: initialcapacity if initialcapacity> MAXIMUM_CAPACITY) {
initialCapacity = MAXIMUM_CAPACITY;
}
if (loadFactor <= 0 float.isnanloadfactor throw new illegalargumentexceptionillegal load factor: loadfactor this.loadfactor='loadFactor;' this.threshold='tableSizeFor(initialCapacity);' returns a power of two size for the given target capacity. static final int tablesizeforint cap int n='cap' - 1 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进行哈希
(2)Hash算法的工作原理
(3)如何降低哈希冲突的概率
(4)总结
(1)HashMap的put()方法会先对key进行哈希
通过key的哈希值获取到对应数组中的index位置。
public class HashMap extends AbstractMap implements Map, 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 1100
0000 0000 0000 0000 1111 1111 1111 1111
1111 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 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;
}
...
} (4)总结
在HashMap的hash()方法里，把HashCode的高低16位进行异或运算，可保证异或运算结果同时保留HashCode的高16位和低16位的特征。
于是在get()方法中通过位运算定位数组index时，即使只有低16位参与运算，HashCode的高低16位特征也参与到运算中。相比于直接使用HashCode的低16位去定位数组index，能减少哈希冲突。