双向链表数据结构
• 插入元素的原理
• 获取元素的原理
• 删除元素的原理

1.HashMap
• 20000核心成员变量
• 优化后的降低冲突概率的hash算法
• put操作原理
• JDK1.8红黑树优化
• 基于数组扩容原理
• get()

newNode()
• afterNodeInsertion
• afterNodeAccess

1.HashSet
• 2.LinkedHashSet
• 3.TreeSet

前言

为什么要学习JDK源码？
各种各样的系统或者技术，最底层、最最核心的一块，其实都是集合（在内存里面存放数据）、并发（分布式系统，底层都会开多个线程，并发的处理一些东西，这里会涉及到一些锁，同步，等等）、IO（读写磁盘上的文件里的数据，发起网络IO，通过网络读写数据）、网络（如何在分布式系统中，各个机器建立网络连接，互相发送请求进行通信），本期先给大家分享集合源码。

一、List

List 是有序的 Collection

List中的元素是有序的、可重复的，主要实现方式有动态数组和链表。

java中提供的List的实现主要有ArrayList、LinkedList、CopyOnWriteArrayList，另外还有两个古老的类Vector和Stack。

1.ArrayList

ArrayList实现了List, RandomAccess, Cloneable, java.io.Serializable等接口。
ArrayList实现了List，提供了基础的添加、删除、遍历等操作。
ArrayList实现了RandomAccess，提供了随机访问的能力。
ArrayList实现了Cloneable，可以被克隆。
ArrayList实现了Serializable，可以被序列化。
AbstractCollection：主要实现了toString()、toArray()、contains()
AbstractList：主要实现了equals()、hashCode()

缺点：
①数组长度固定，java里面数组都是定长数组，比如数组大小设置为100，此时你不停的往ArrayList里面塞入这个数据，此时元素数量超过了100以后，此时就会发生一个数组的扩容，就会搞一个更大的数组，把以前的数组拷贝到新的数组里面去，这个数组扩容+元素拷贝的过程，相对来说会慢一些
②中间插入慢，数组来实现，数组你要是往数组的中间加一个元素，要把数组中那个新增元素后面的元素全部往后面挪动一位，所以说，如果你是往ArrayList中间插入一个元素，性能比较差，会导致他后面的大量的元素挪动一个位置

优点：
①支持随机访问，通过索引访问元素极快，时间复杂度为O(1)

核心参数：

/*** 默认容量*/private static final int DEFAULT_CAPACITY = 10;/*** 空数组，如果传入的容量为0时使用*/private static final Object[] EMPTY_ELEMENTDATA = {};/*** 空数组，传传入容量时使用，添加第一个元素的时候会重新初始为默认容量大小*/private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};/*** 存储元素的数组*/transient Object[] elementData; // non-private to simplify nested class access/*** 集合中元素的个数*/private int size;

（1）DEFAULT_CAPACITY 默认容量为10，也就是通过new ArrayList()创建时的默认容量。
（2）EMPTY_ELEMENTDATA 空的数组，这种是通过new ArrayList(0)创建时用的是这个空数组。
（3）DEFAULTCAPACITY_EMPTY_ELEMENTDATA 也是空数组，这种是通过new ArrayList()创建时用的是这个空数组，与EMPTY_ELEMENTDATA的区别是在添加第一个元素时使用这个空数组的会初始化为DEFAULT_CAPACITY（10）个元素。
（4）elementData 真正存放元素的地方，使用transient是为了不序列化这个字段。 至于没有使用private修饰，后面注释是写的“为了简化嵌套类的访问”，但是楼主实测加了private嵌套类一样可以访问。 private表示是类私有的属性，只要是在这个类内部都可以访问，嵌套类或者内部类也是在类的内部，所以也可以访问类的私有成员。
（5）size 真正存储元素的个数，而不是elementData数组的长度。

核心方法：

构造器

（1）不传初始容量，初始化为DEFAULTCAPACITY_EMPTY_ELEMENTDATA空数组，会在添加第一个元素的时候扩容为默认的大小，即10。

public ArrayList() {// 如果没有传入初始容量，则使用空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA// 使用这个数组是在添加第一个元素的时候会扩容到默认大小10this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}

（2）ArrayList(int initialCapacity)构造方法，传入初始容量，如果大于0就初始化elementData为对应大小，如果等于0就使用EMPTY_ELEMENTDATA空数组，如果小于0抛出异常

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);}}

DEFAULTCAPACITY_EMPTY_ELEMENTDATA 也是空数组，这种是通过new ArrayList()创建时用的是这个空数组，与EMPTY_ELEMENTDATA的区别是在添加第一个元素时使用这个空数组的会初始化为DEFAULT_CAPACITY（10）个元素。

（3）ArrayList(Collection c)构造方法

传入集合并初始化elementData，这里会使用拷贝把传入集合的元素拷贝到elementData数组中，如果元素个数为0，则初始化为EMPTY_ELEMENTDATA空数组。

public ArrayList(Collection<? extends E> c) {elementData = c.toArray();if ((size = elementData.length) != 0) {// c.toArray might (incorrectly) not return Object[] (see 6260652)if (elementData.getClass() != Object[].class)elementData = Arrays.copyOf(elementData, size, Object[].class);} else {// replace with empty array.this.elementData = EMPTY_ELEMENTDATA;}}

根据业务预测初始化的数组的大小，避免数组太小，往里面塞入数据的时候，导致数据不断的扩容，不断的搞新的数组

add()

（1）默认添加

添加元素到size+1位置，平均时间复杂度为O(1)。

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++;// 判断是否需要扩容：size + 1 - 当前数组长度 > 0时扩容if (minCapacity - elementData.length > 0)grow(minCapacity);}

补充：当前数组长度10，添加第11个元素时才扩容

private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;// 新容量是老容量的1.5倍（oldCapacity + (oldCapacity >> 1)）// 老的大小 + 老的大小 >> 1（相当于除以2）int newCapacity = oldCapacity + (oldCapacity >> 1);// 如果加了这么多容量发现比需要的容量还小，则以需要的容量为准if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// 创建新容量的数组并把老数组拷贝到新数组elementData = Arrays.copyOf(elementData, newCapacity);}

补充：空参构造器，第一次初始化时，就需要以需要的容量为准，因为0+(0>>1)=0

（2）添加到指定位置

public void add(int index, E element) {rangeCheckForAdd(index);ensureCapacityInternal(size + 1);  // Increments modCount!!// 把插入索引位置后的元素都往后挪一位System.arraycopy(elementData, index, elementData, index + 1,size - index);// 在插入索引位置放置插入的元素elementData[index] = element;size++;}

addAll()

public boolean addAll(Collection<? extends E> c) {Object[] a = c.toArray();int numNew = a.length;ensureCapacityInternal(size + numNew);  // Increments modCountSystem.arraycopy(a, 0, elementData, size, numNew);size += numNew;return numNew != 0;}

①将集合C转化为数组a
②获取数组a长度
③判断是否需要扩容

get()

获取指定索引位置的元素，时间复杂度为O(1)。

public E get(int index) {rangeCheck(index);return elementData(index);}private void rangeCheck(int index) {if (index >= size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}E elementData(int index) {return (E) elementData[index];}

remove()

（1）通过索引删除
删除指定索引位置的元素，时间复杂度为O(n)。

public E remove(int index) {rangeCheck(index);modCount++;E oldValue = elementData(index);int numMoved = size - index - 1;// 如果index不是最后一位，则将index之后的元素往前挪一位if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);// 将最后一个元素删除，帮助GCelementData[--size] = null; // clear to let GC do its workreturn oldValue;}private void rangeCheck(int index) {if (index < 0 || index >= this.size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}

（2）通过元素删除

删除指定元素值的元素，时间复杂度为O(n)。

public boolean remove(Object o) {if (o == null) {for (int index = 0; index < size; index++)if (elementData[index] == null) {fastRemove(index);return true;}} else {for (int index = 0; index < size; index++)if (o.equals(elementData[index])) {fastRemove(index);return true;}}return false;}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}

①找到第一个等于指定元素值的元素；
②快速删除；

fastRemove(int index)相对于remove(int index)少了检查索引越界的操作，可见jdk将性能优化到极致。

6.迭代器

private class Itr implements Iterator<E> {...}private class ListItr extends Itr implements ListIterator<E> {...}

ListItr继承了Itr和ListIterator，ListIterator有插入和修改删除方法，同时还具有向前遍历的方法，所以ListIterator就具备了增删改查的功能，比Itr的功能更加齐全

快速失败机制

假设存在两个线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就会抛出 ConcurrentModificationException 异常，从而产生fail-fast。

检查modCount标识符

final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();}

无论是add()、remove()，还是clear()，只要涉及到修改集合中的元素个数时，都会改变modCount的值（都是modCount+1）。

ArrayList的Iterator实现类中调用next()时，会“调用checkForComodification()比较‘expectedModCount’和‘modCount’的大小”；但是，CopyOnWriteArrayList的Iterator实现类中，没有所谓的checkForComodification()，更不会抛出ConcurrentModificationException异常！

ArrayList如何把元素序列化？

elementData设置成了transient，那ArrayList是怎么把元素序列化的呢？

一般地，只要实现了Serializable接口即可自动序列化，writeObject()和readObject()是为了自己控制序列化的方式，这两个方法必须声明为private，在java.io.ObjectStreamClass#getPrivateMethod()方法中通过反射获取到writeObject()这个方法。（用户自定义的 writeObject 和 readObject 方法可以允许用户控制序列化的过程）

Serializable：一个对象序列化的接口，一个类只有实现了Serializable接口，它的对象才是可序列化的。
Serializeble的作用仅仅是一个标识这个类是可序列化的

什么情况下需要序列化？（应用场景）
①将内存对象保存到磁盘中或数据库中（持久化）。
②最常见的用法，web客服端连接服务器的时候，假如连接的客服端比较多，这时服务端压力比较大（内存不足），为了解决这些问题，把一些Session序列化，存入硬盘用的时候拿出来。
③在跨平台环境下，通过网络传输对象的时候需要序列化，例如WebService SOAP

transient：表示方法和属性等成员变量是透明的，不参与序列化。
static：静态变量不能序列化

什么是序列化和反序列化？
序列化机制：将内存Java 对象通过字节输出流写入硬盘（大部分是乱码，因为是二进制）。
反序列化机制：通过字节输入流从硬盘中文件中把对象读到内存中。（字节序列转换成Java对象）
为什么要有序列号？

如果没有给序列号，会根据属性和方法算出序列号，若属性和方法改变会报错，因为序列号不同，若加了序列号，可以添删属性，改变toString都不会报错
elementData定义为transient的优势，自己根据size序列化真实的元素，而不是根据数组的长度序列化元素，减少了空间占用。

总结：
（1）ArrayList内部使用数组存储元素，当数组长度不够时进行扩容，每次加一半的空间，ArrayList不会进行缩容；
（2）ArrayList支持随机访问，通过索引访问元素极快，时间复杂度为O(1)；
（3）ArrayList添加元素到尾部极快，平均时间复杂度为O(1)；
（4）ArrayList添加元素到中间比较慢，因为要搬移元素，平均时间复杂度为O(n)；
（5）ArrayList从尾部删除元素极快，时间复杂度为O(1)；
（6）ArrayList从中间删除元素比较慢，因为要搬移元素，平均时间复杂度为O(n)；

2.LinkedList

LinkedList是一个以双向链表实现的List，它除了作为List使用，还可以作为队列或者栈来使用

ArrayList+Deque

因为ArrayList代表了List的典型实现，LInkedList代表了Deque的典型实现，同时LinkedList也实现了List，通过这两个类一首一尾正好可以把整个集合贯穿起来。

优点：
①插入性能高，不管是从末尾插入还是中间插入

缺点：
随机读性能差，例如LinkedList.get(10)，这种操作，性能就很低，因为他需要遍历这个链表，从头开始遍历这个链表，直到找到index = 10的这个元素为止

使用场景

（1）ArrayList：一般场景，都是用ArrayList来代表一个集合，只要别频繁的往里面插入和灌入大量的元素就可以了，遍历，或者随机查，都可以

（2）LinkedList：适合，频繁的在list中插入和删除某个元素，然后尤其是LinkedList他其实是可以当做队列来用的，这个东西的话呢，我们后面看源码的时候，可以来看一下，先进先出，在list尾部怼进去一个元素，从头部拿出来一个元素。如果要在内存里实现一个基本的队列的话，可以用LinkedList

我们之前在电商系统开发的时候，在第一个版本中，用到了内存队列，用的就是LinkedList，他里面基于链表实现，天然就可以做队列的数据结构，先进先出，链表来实现，特别适合频繁的在里面插入元素什么的，也不会导致数组扩容

其实在工作中使用的时候，都是用的是java并发包下面的一些线程安全的集合，这个东西等到讲java并发包的时候，我们可以再来看一下

LinkedList作为队列使用
offer()，就是在队列尾部入队，将一个元素插入队列尾部
poll()，从队列头部出队
peek()，获取队列头部的元素，但是头部的元素不出队
offerFirst()
offerLast()

双向链表数据结构

item是元素
prev、next是指针

插入元素的原理

（1）尾部插入

add()，默认就是在队列的尾部插入一个元素，在那个双向链表的尾部插入一个元素
addLast()，跟add()方法是一样的，也是在尾部插入一个元素

public boolean add(E e) {linkLast(e);return true;}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;elsel.next = newNode;size++;modCount++;}

（2）队列中间插入

add(index, element)，是在队列的中间插入一个元素

public void add(int index, E element) {checkPositionIndex(index);if (index == size)linkLast(element);elselinkBefore(element, node(index));}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;elsepred.next = newNode;size++;modCount++;}Node<E> node(int index) {// assert isElementIndex(index);if (index < (size >> 1)) {Node<E> x = first;for (int i = 0; i < index; i++)x = x.next;return x;} else {Node<E> x = last;for (int i = size - 1; i > index; i--)x = x.prev;return x;}}

（3）头部插入

addFirst()，在队列的头部插入一个元素

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;elsef.prev = newNode;size++;modCount++;}

获取元素的原理

（1）获取头部元素

getFirst() 获取头部的元素，他其实就是直接返回first指针指向的那个Node他里面的数据，他们都是返回头部的元素。getFirst()如果是对空list调用，会抛异常；peek()对空list调用，会返回null

（2）获取尾部元素

getLast()：获取尾部的元素，他其实就是直接返回last指针指向的那个Node他里面的数据

public E getLast() {final Node<E> l = last;if (l == null)throw new NoSuchElementException();return l.item;}

（3）获取中间的元素

public E get(int index) {checkElementIndex(index);return node(index).item;}Node<E> node(int index) {// assert isElementIndex(index);if (index < (size >> 1)) {Node<E> x = first;for (int i = 0; i < index; i++)x = x.next;return x;} else {Node<E> x = last;for (int i = size - 1; i > index; i--)x = x.prev;return x;}}

LinkedList而言，get(int index)这个方法，是他的弱项，也是他的缺点，如果他要获取某个随机位置的元素，需要使用node(index)这个方法，是要进行链表的遍历，会判断一下index和size >> 1进行比较，如果在前半部分，就会从头部开始遍历；如果在后半部分，就会从尾部开始遍历

删除元素的原理

（1）删除尾部

（2）删除头部

（3）删除中间的元素

3.Vector&Stack

栈由Vector和Stack两个来实现，Stack代表了一个栈这种数据结构，他是继承自Vector来实现的，Vector是一种类似于ArrayList（基于数组来实现的）数据结构，有序的集合，Stack是一种基于数组来实现的栈数据结构

栈，先进后出，跟队列的先进先出是不一样

队列：一般是队尾巴进去开始排队，从队头开始出来，排队的过程，先进先出
栈：进去的时候直接压入栈底，出来的时候是从栈的最上面一个元素开始先出来，先进后出

ArrayList每次扩容是1.5倍，capacity + (capacity >> 1) = 1.5
Vector每次扩容默认是2倍，默认情况下是直接扩容两倍，2倍

二、Map

1.HashMap

核心成员变量

// 数组默认的初始大小,16static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16// 负载因子，如果你在数组里的元素的个数达到了数组大小 * 负载因子，就会进行数组的扩容static final float DEFAULT_LOAD_FACTOR = 0.75f;// 这个数组就是所谓的map里的核心数据结构的数组，数组的元素就可以看到是Node类型的，天然就可以挂成一个链表，单向链表，Node里面只有一个next指针transient Node<K,V>[] table;// 这个size代表的是就是当前hashmap中有多少个key-value对，如果这个数量达到了指定大小 * 负载因子，那么就会进行数组的扩容transient int size;

static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Node<K,V> next;}

这是一个很关键的内部类，他其实是代表了一个key-value对，里面包含了key的hash值，key，value，还有就是可以有一个next的指针，指向下一个Node，也就是指向单向链表中的下一个节点

通过这个next指针，就可以形成一个链表

优化后的降低冲突概率的hash算法

基础补充：
左移运算符（<<）
定义：将一个运算对象的各二进制位全部左移若干位（左边的二进制位丢弃，右边补0）。
设 a=1010 1110，a = a<< 2 将a的二进制位左移2位、右补0，即得a=1011 1000。
若左移时舍弃的高位不包含1，则每左移一位，相当于该数乘以2。

右移运算符（>>）
定义：将一个数的各二进制位全部右移若干位，正数左补0，负数左补1，右边丢弃。
例如：a=a>>2 将a的二进制位右移2位，左补0 或者 左补1得看被移数是正还是负。
操作数每右移一位，相当于该数除以2。

异或：两个位相同为0，相异为1

map.put(key, value) -> 对key进行hash算法，通过hash获取到对应的数组中的index位置

static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

第一步：计算出key的哈希值

第二步：把hash值右移16位
假设原hashcode值是：1111 1111 1111 1111 1111 1010 0111 1100
h >>> 16，这个是位运算的操作，这个东西是把32位的二进制的数字，所有的bit往右侧右移了16位

第三步：用原hash值与右移16位的哈希值做异或操作

提前在hash()函数里面，就会把高16位和低16位进行一下异或运算，就可以保证说，在hash值的低16位里面，可以同时保留他的高16位和低16位的特征

相当于是在后面定位到数组index的位运算的时候，哪怕只有低16位参与了运算，其实运算的时候，他的hash值的高16位和低16位的特征都参与到了运算定位到那个数组的index

这么做有什么好处呢？为什么要保证同时将高16位和低16位的特征同时纳入运算，考虑到数组index的定位中去呢？因为这样子可以保证降低hash冲突的概率，如果说直接用hash值的低16位去运算定位数组index的话，可能会导致一定的hash冲突

为什么要做这么一个操作呢？hash算法里，为什么是hash值跟hash >>> 16位的结果，异或运算的结果呢？他这么做的话，这里牵扯到很多数学的概念，暂时先记住结论就行

目标是什么呢？通过这样的方式算出来的hash值，可以降低hash冲突的概率

结论1：后面在用这个hash值定位到数组的index的时候，也有一个位运算，但是的话呢，一般那个后面的位运算，一般都是用低16位在进行运算，所以说如果你不把hash值的高16位和低16位进行运算的话，那么就会导致你后面在通过hash值找到数组index的时候，只有hash值的低16位参与了运算
结论2：这样可以把他原来的高16位变成低16位，他其实只取16位，相当于把高16位和低16位做了一个异或运算，在hash值的低16位里面，可以同时保留他的高16位和低16位的特征
结论3：数组index定位时，只取hash前16位

继续关注put方法，才能完全看懂hash算法的优化

put操作原理

基础补充
与操作：两个位都为1时，结果才为1

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;// 1.假设，hashmap是空的，通过resize扩容，数组大小就是默认的16，负载因子就是默认的12if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 2.这是一个寻址算法，用&操作寻址，性能会比用取模高// 2.1 n是数组的长度，用数组长度和hash做与运算// 2.2在数组长度比较小的时候，高16基本上就废掉了// 3.这个数组里的元素是空的// 3.1这个分支，他的意思是说tab[i]，i就是hash定位到的数组index，tab[i]如果为空，也就是hash定位到的这个位置是空的，之前没有任何人在这里，此时直接是放一个Node在数组的这个位置即可if ((p = tab[i = (n - 1) & hash]) == null)// 3.2定位到数组了，那就把元素插入到链表或者红黑树里tab[i] = newNode(hash, key, value, null);else {// 4.hash定位到的数组位置，是已经有了Node了Node<K,V> e; K k;// 5.相同的key（会覆盖旧的value）if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;// 6.红黑树else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {// 7.链表for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);// 8.如果链表的长度大于等于8的话，链表的总长度达到8的话，那么此时就需要将这个链表转换为一个红黑树的数据结构// 当你遍历到第8个节点，此时binCount是7，同时你挂上了第9个节点，然后就会发现binCount >= 7，达到了临界值，也就是说，当你的链表节点的数量超过8的时候，此时就会将链表转换为红黑树if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}// 相同的key（会覆盖旧的value）if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}// 9.相同的key，覆盖旧的valueif (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;}

注意：每次扩容，数组的大小就是2的n次方，只要保证数组的大小是2的n次方，就可以保证说，(n – 1) & hash，可以保证就是hash % 数组.length取模的一样的效果，也就是说通过(n – 1) & hash，就可以将任意一个hash值定位到数组的某个index里去

JDK1.8红黑树优化

如果说出现大量的hash冲突之后，假设某给位置挂的一个链表特别的长，就很恶心了，如果链表长度太长的话，会导致有一些get()操作的时间复杂度就是O(n)，正常来说，table[i]数组索引直接定位的方式的话，O(1)

但是如果链表，大量的key冲突，会导致get()操作，性能急剧下降，导致很多的问题

所以说JDK 1.8以后人家优化了这块东西，会判断，如果链表的长度达到8的时候，那么就会将链表转换为红黑树，如果用红黑树的话，get()操作，即使对一个很大的红黑树进行二叉查找，那么时间复杂度会变成O(logn)，性能会比链表的O(n)得到大幅度的提升

基于数组扩容原理

hashmap底层是基于数组来实现的核心的数据结构，如果是用数组的话，就天然会有一个问题，就跟ArrayList一样，就是数组如果满了，就必须要扩容，hashmap所以也是有扩容的问题存在的

2倍扩容 + rehash，2倍扩容之后，每个key-value对，都会基于key的hash值取模数组长度重新寻址找到新数组的新的位置

hashmap扩容的原理，数组一次扩容2倍，rehash过程，基于key的hash值重新在新的数组里找到新的位置，很多key在新数组的位置都不一样了，如果是之前冲突的这个key可能就会在新的数组里分布在不同的位置上了

这个原理大体上是JDK 1.7以前的原理，现在的话呢，JDK 1.8以后，都是数组大小是2的n次方扩容，用的是与操作符来实现hash寻址的算法，来进行扩容的时候，rehash

JDK 1.8以后，为了提升rehash这个过程的性能，不是说简单的用key的hash值对新数组.length取模，取模给大家讲过，性能较低，所以JDK 1.8以后hash寻址这块，用的与操作

此时，上面两个hash值会出现hash碰撞的问题，使用链表，或者是红黑树来解决

如果数组的长度扩容之后 = 32，重新对每个hash值进行寻址，也就是用每个hash值跟新数组的length – 1进行与操作

hash2的位置，从原来的5变成了21，规律是什么？

也就是说，JDK 1.8，扩容一定是2的倍数，从16到32到64到128

就可以保证说，每次扩容之后，你的每个hash值要么是停留在原来的那个index的地方，要么是变成了原来的index（5） + oldCap（16） = 21

所以说，这个就是JDK 1.8以后，数组扩容的时候，元素重新寻址的一个过程和原理

如果面试官问你，hashmap的底层原理
（1）hash算法：为什么要高位和低位做异或运算？
（2）hash寻址：为什么是hash值和数组.length – 1进行与运算？
（3）hash冲突的机制：链表，超过8个以后，红黑树
（4）扩容机制：数组2倍扩容，重新寻址（rehash），hash & n – 1，判断二进制结果中是否多出一个bit的1，如果没多，那么就是原来的index，如果多了出来，那么就是index + oldCap，通过这个方式，就避免了rehash的时候，用每个hash对新数组.length取模，取模性能不高，位运算的性能比较高

通过这个方式的话，可以有效的将原来冲突在一个位置的多个key，给分散到新数组的不同的位置去

get()

public V get(Object key) {Node<K,V> e;// 1.计算key的hash值return (e = getNode(hash(key), key)) == null ? null : e.value;}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 &&// 1.先确定数组下标(first = tab[(n - 1) & hash]) != null) {// 2.如果第一个节点的hash和当前值的hash相等，且值也相等，直接返回if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;if ((e = first.next) != null) {// 3.如果是红黑树，走红黑树获取节点方法if (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);// 4.如果是链表，遍历链表比较do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null;}

2.LinkedHashMap

LinkedHashMap内部维护了一个双向链表，能保证元素按插入的顺序访问，也能以访问顺序访问，可以用来实现LRU缓存策略。

HashMap，比如你放了一堆key-value对进去，后面的话呢如果你要遍历这个HashMap的话，遍历的顺序，并不是按照你插入的key-value的顺序来的。

LinkedHashMap，他会记录你插入key-value的顺序， 如果你在遍历的时候，他是按照插入key-value对的顺序给你遍历出来的

核心属性

/*** 双向链表头结点*/transient LinkedHashMap.Entry<K,V> head;/*** 双向链表尾结点*/transient LinkedHashMap.Entry<K,V> tail;/*** 是否按访问顺序排序*/final boolean accessOrder;

（1）head双向链表的头节点，旧数据存在头节点。
（2）tail双向链表的尾节点，新数据存在尾节点。
（3）accessOrder是否需要按访问顺序排序，如果为false则按插入顺序存储元素，如果是true则按访问顺序存储元素。

在调用LinkedHashMap的put()方法的时候，其实调用的是父类HashMap的put()方法

newNode()

LinkedHashMap重写了HashMap的newNode()方法

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;// 一开始这个链表里就一个节点，所以tail和head两个指针，都会指向这个pif (last == null)head = p;else {p.before = last;last.after = p;}}

LinkedHashMap内部维护了一个双向链表，head（双向链表头结点）、tail（双向链表尾结点）

补充：
HashMap的newNode创建的是HashMap的内部类Node，Node实现了Map.Entry
LinkedHashMap的newNode创建的是LinkedHashMap的内部类Entry，Entry继承了HashMap.Node

afterNodeInsertion

调用完put()方法，插入一个key-value对之后，其实就会调用afterNodeInsertion(evict);，LinkedHashMap重写了afterNodeInsertion(evict)方法

void afterNodeInsertion(boolean evict) { // possibly remove eldestLinkedHashMap.Entry<K,V> first;if (evict && (first = head) != null && removeEldestEntry(first)) {K key = first.key;removeNode(hash(key), key, null, false, true);}}

evict：驱逐的意思
（1）如果evict为true，且头节点不为空，且确定移除最老的元素，那么就调用HashMap.removeNode()把头节点移除（这里的头节点是双向链表的头节点，而不是某个桶中的第一个元素）；
（2）HashMap.removeNode()从HashMap中把这个节点移除之后，会调用afterNodeRemoval()方法；
（3）afterNodeRemoval()方法在LinkedHashMap中也有实现，用来在移除元素后修改双向链表;
（4）默认removeEldestEntry()方法返回false，也就是不删除元素。

afterNodeAccess

但是如果accessOrder是true的话，那么如果你get一个key，或者是覆盖这个key的值，就会导致个key-value对顺序会在链表里改变，他会被挪动到链表的尾部去，如果你把accessOrder指定为true，你每次修改一个key的值，或者是get访问一下这个key，都会导致这个key挪动到链表的尾部去

补充：可以通过构造器指定accessOrder，默认false

总结
（1）LinkedHashMap继承自HashMap，具有HashMap的所有特性；
（2）LinkedHashMap内部维护了一个双向链表存储所有的元素；
（3）如果accessOrder为false，则可以按插入元素的顺序遍历元素；
（4）如果accessOrder为true，则可以按访问元素的顺序遍历元素；
（5）LinkedHashMap的实现非常精妙，很多方法都是在HashMap中留的钩子（Hook），直接实现这些Hook就可以实现对应的功能了，并不需要再重写put()等方法；
（6）默认的LinkedHashMap并不会移除旧元素，如果需要移除旧元素，则需要重写removeEldestEntry()方法设定移除策略；
（7）LinkedHashMap可以用来实现LRU缓存淘汰策略；

3.TreeMap

TreeMap使用红黑树存储元素，按key的自然顺序来排序。

TreeMap实现了Map、SortedMap、NavigableMap、Cloneable、Serializable等接口。

public V put(K key, V value) {Entry<K,V> t = root;if (t == null) {compare(key, key); // type (and possibly null) checkroot = new Entry<>(key, value, null);size = 1;modCount++;return null;}int cmp;Entry<K,V> parent;// split comparator and comparable pathsComparator<? super K> cpr = comparator;if (cpr != null) {do {parent = t;cmp = cpr.compare(key, t.key);if (cmp < 0)t = t.left;else if (cmp > 0)t = t.right;elsereturn t.setValue(value);} while (t != null);}else {if (key == null)throw new NullPointerException();@SuppressWarnings("unchecked")Comparable<? super K> k = (Comparable<? super K>) key;do {parent = t;cmp = k.compareTo(t.key);if (cmp < 0)t = t.left;else if (cmp > 0)t = t.right;elsereturn t.setValue(value);} while (t != null);}Entry<K,V> e = new Entry<>(key, value, parent);if (cmp < 0)parent.left = e;elseparent.right = e;fixAfterInsertion(e);size++;modCount++;return null;}

TreeMap底层的Entry实现了Map.Entry，里面包含left（左节点）、right（右节点）、parent（父节点）、color（颜色）

三、Set

1.HashSet

比如说HashSet就是基于HashMap来实现的

HashSet，他其实就是说一个集合，里面的元素是无序的，他里面的元素不能重复的，HashMap的key是无顺序的，你插入进去的顺序，跟你迭代遍历的顺序是不一样的，而且HashMap的key是没有重复的，HashSet可以直接基于HashMap来实现

2.LinkedHashSet

LinkedHashSet，他是有顺序的set，也就是维持了插入set的这个顺序，你迭代LinkedHashSet的顺序跟你插入的顺序是一样的，底层直接就可以基于LinkedHashMap来实现

3.TreeSet

TreeSet，默认是根据你插入进去的元素的值来排序的，而且可以定制Comparator，自己决定排序的算法和逻辑，他底层可以基于TreeMap来实现

Set底层的Map，只有key是有值的，value都是null值，都是空的