世上无难事，只要肯攀登——毛泽东

ArrayList源码解析及设计思路

提纲挈领地说，主要从ArrayList整体架构出发，考虑到新增、扩容、删除、迭代等内容。

ArrayList其实就是围绕底层数组，各个API都是对数组的操作进行封装，使用者使用的时候对底层无需感知，只要关注如何使用即可。

ArrayList是线程不安全的，多线程情况下更推荐使用线程安全的类：Collections#synchronizedList。

如果我们不指定位置直接添加元素时(add(E element))，元素会默认会添加在最后，不会触发底层数组的复制，不考虑底层数组自动扩容的话，时间复杂度为O(1) ，在指定位置添加元素(add(int index, E element))，需要复制底层数组，根据最坏打算，时间复杂度是O(n)。

ArrayList整体架构

ArrayList底层就是一个数组，如图：

和数组一样，index下标从0开始，然后上图数组的名字是elementData。

除了上面这两个概念，源码中还有下面三个基础概念：

DEFAULT_CAPACITY 表示数组的初始大小，默认是 10，这个数字要记住；
size 表示当前数组的大小，类型 int，因为没有使用 volatile 修饰，所以是非线程安全的；
modCount 统计当前数组被修改的版本次数，每当这个结构发生结构变动的时候，会 +1。

然后，在ArrayList的类注释中有下面比较重要的四点：

ArrayList允许put null值，而且会自动扩容;
size()、isEmpty()、get()、set()、add()等方法的时间复杂度都是O(1);
ArrayList不是线程安全的，多线程情况下更推荐使用线程安全的类：Collections#synchronizedList;
增强 for 循环，或者使用迭代器迭代过程中，如果数组大小被改变，会快速失败，抛出异常。

源码解析(未完成)

源码解析主要集中在ArrayList的初始化、新增与扩容、删除元素、迭代器等方面

初始化

初始化有三种方法：无参数直接初始化、指定大小初始化、指定初始数据初始化

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//无参数直接初始化，数组大小为空
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//指定初始数据初始化
public ArrayList(Collection<? extends E> c) {
    //elementData 是保存数组的容器，默认为 null
    elementData = c.toArray();
    //如果给定的集合（c）数据有值
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        //如果集合元素类型不是 Object 类型，我们会转成 Object
        if (elementData.getClass() != Object[].class) {
            elementData = Arrays.copyOf(elementData, size, Object[].class);
        }
    } else {
        // 给定集合（c）无值，则默认空数组
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

需要补充：

ArrayList无参构造器初始化的时候，默认大小是空数组，并不是大家常说的 10，10 是在第一次 add 的时候扩容的数组值。
指定初始数据初始化时，我们发现一个这样子的注释 see 6260652，这是 Java 的一个 bug，意思是当给定集合内的元素不是 Object 类型时，我们会转化成 Object 的类型。这个BUG在JDK9中被解决。

新增和扩容实现

新增就是往数组中添加元素，主要分成两步：

判断是否需要扩容，如果需要执行扩容操作；
直接赋值。

两步的源码如下：

public boolean add(E e) {
  //确保数组大小是否足够，不够执行扩容，size 为当前数组的大小
  ensureCapacityInternal(size + 1);  // Increments modCount!!
  //直接赋值，线程不安全的
  elementData[size++] = e;
  return true;
}

扩容(ensureCapacityInternal)的源码：

private void ensureCapacityInternal(int minCapacity) {
  //如果初始化数组大小时，有给定初始值，以给定的大小为准，不走 if 逻辑
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  //确保容积足够
  ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
  //记录数组被修改
  modCount++;
  // 如果我们期望的最小容量大于目前数组的长度，那么就扩容
  if (minCapacity - elementData.length > 0)
    grow(minCapacity);
}
//扩容，并把现有数据拷贝到新的数组里面去
private void grow(int minCapacity) {
  int oldCapacity = elementData.length;
  // oldCapacity >> 1 是把 oldCapacity 除以 2 的意思
  int newCapacity = oldCapacity + (oldCapacity >> 1);

  // 如果扩容后的值 < 我们的期望值，扩容后的值就等于我们的期望值
  if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;

  // 如果扩容后的值 > jvm 所能分配的数组的最大值，那么就用 Integer 的最大值
  if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);
 
  // 通过复制进行扩容
  elementData = Arrays.copyOf(elementData, newCapacity);
}

除了注释内容，需要额外注意四点：

扩容的规则并不是翻倍，是原来容量大小 + 容量大小的一半，直白来说，扩容后的大小是原来容量的 1.5 倍；
ArrayList 中的数组的最大值是 Integer.MAX_VALUE，超过这个值，JVM 就不会给数组分配内存空间了。
新增时，并没有对值进行严格的校验，所以 ArrayList 是允许 null 值的。
源码在扩容的时候，有数组大小溢出意识，就是说扩容后数组的大小下界不能小于 0，上界不能大于 Integer 的最大值，这种意识我们可以学习。

扩容完成之后，赋值是非常简单的，直接往数组上添加元素即可：elementData [size++] = e。也正是通过这种简单赋值，没有任何锁控制，所以这里的操作是线程不安全的。

时间复杂度

对ArrayList的新增或者删除操作本质都是对数组元素的操作，只需要根据数组索引，直接新增和删除数据，所以时间复杂度是O(1)

线程安全

需要强调的是，只有当 ArrayList 作为共享变量时，才会有线程安全问题，当 ArrayList 是方法内的局部变量时，是没有线程安全的问题的。

ArrayList 有线程安全问题的本质，是因为 ArrayList 自身的 elementData、size、modConut 在进行各种操作时，都没有加锁，而且这些变量的类型并非是可见（volatile）的，所以如果多个线程对这些变量进行操作时，可能会有值被覆盖的情况。

类注释中推荐我们使用 Collections#synchronizedList 来保证线程安全，SynchronizedList 是通过在每个方法上面加上锁来实现，虽然实现了线程安全，但是性能大大降低，具体实现源码：

public boolean add(E e) {
    synchronized (mutex) {// synchronized 是一种轻量锁，mutex 表示一个当前 SynchronizedList
        return c.add(e);
    }
}

LinkedList源码解析及设计思路

LinkedList可以用于先入先出，也可以用于先入后出，因为它本质是一个链表，而且是双向链表。

LinkedList整体架构

LinkedList本质是双向链表，整体结构如下图：

源码解析(未完)

新增元素

追加节点时，我们可以选择追加到链表头部，还是追加到链表尾部，add 方法默认是从尾部开始追加，addFirst 方法是从头部开始追加。

从尾部追加(add)

// 从尾部开始追加节点
void linkLast(E e) {
    // 把尾节点数据暂存
    final Node<E> l = last;
    // 新建新的节点，初始化入参含义：
    // l 是新节点的前一个节点，当前值是尾节点值
    // e 表示当前新增节点，当前新增节点后一个节点是 null
    final Node<E> newNode = new Node<>(l, e, null);
    // 新建节点追加到尾部
    last = newNode;
    //如果链表为空（l 是尾节点，尾节点为空，链表即空），头部和尾部是同一个节点，都是新建的节点
    if (l == null)
        first = newNode;![图片描述](//img1.sycdn.imooc.com/5d5fc69600013e4803600240.gif)
    //否则把前尾节点的下一个节点，指向当前尾节点。
    else
        l.next = newNode;
    //大小和版本更改
    size++;
    modCount++;
}

从源码上来看，尾部追加节点比较简单，只需要简单地把指向位置修改下即可

从头部追加(addFirst)

// 从头部追加
private void linkFirst(E e) {
    // 头节点赋值给临时变量
    final Node<E> f = first;
    // 新建节点，前一个节点指向null，e 是新建节点，f 是新建节点的下一个节点，目前值是头节点的值
    final Node<E> newNode = new Node<>(null, e, f);
    // 新建节点成为头节点
    first = newNode;
    // 头节点为空，就是链表为空，头尾节点是一个节点
    if (f == null)
        last = newNode;
    //上一个头节点的前一个节点指向当前节点
    else
        f.prev = newNode;
    size++;
    modCount++;
}

头部追加节点和尾部追加节点非常类似，只是前者是移动头节点的 prev 指向，后者是移动尾节点的 next 指向。

节点删除

节点删除的方式和追加类似，我们可以选择从头部删除，也可以选择从尾部删除，删除操作会把节点的值，前后指向节点都置为 null，帮助 GC 进行回收。

从头部删除：

//从头删除节点 f 是链表头节点
private E unlinkFirst(Node<E> f) {
    // 拿出头节点的值，作为方法的返回值
    final E element = f.item;
    // 拿出头节点的下一个节点
    final Node<E> next = f.next;
    //帮助 GC 回收头节点
    f.item = null;
    f.next = null;
    // 头节点的下一个节点成为头节点
    first = next;
    //如果 next 为空，表明链表为空
    if (next == null)
        last = null;
    //链表不为空，头节点的前一个节点指向 null
    else
        next.prev = null;
    //修改链表大小和版本
    size--;
    modCount++;
    return element;
}

从尾部删除差不多，不重复贴了。

链表结构的节点新增、删除都非常简单，仅仅把前后节点的指向修改下就好了，所以 LinkedList 新增和删除速度很快。

访问元素(节点)

这是LinkedList的缺陷了，需要循环挨个查找才行。但是LinkedList其实也是用了二分法来加快查找的。

// 根据链表索引位置查询节点
Node<E> node(int index) {
    // 如果 index 处于队列的前半部分，从头开始找，size >> 1 是 size 除以 2 的意思。
    if (index < (size >> 1)) {
        Node<E> x = first;
        // 直到 for 循环到 index 的前一个 node 停止
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {// 如果 index 处于队列的后半部分，从尾开始找
        Node<E> x = last;
        // 直到 for 循环到 index 的后一个 node 停止
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

LinkedList 并没有采用从头循环到尾的做法，而是采取了简单二分法，首先看看 index 是在链表的前半部分，还是后半部分。如果是前半部分，就从头开始寻找，反之亦然。通过这种方式，使循环的次数至少降低了一半，提高了查找的性能，这种思想值得我们借鉴。

LinkedList和其他结构对比

首先，LinkedList实现了Queue接口，也就是实例化Queue的时候，需要这么写：Queue<E> queue = new LinkedList<>()，在新增、删除、查询等方面增加了很多新的方法，这些方法在平时特别容易混淆，在链表为空的情况下，返回值也不太一样

List接口常见问题

1.说说对ArrayList的理解？

建议先回答总体架构，再从某个细节出发作为突破口，比如这样：

ArrayList 底层数据结构是个数组，其 API 都做了一层对数组底层访问的封装，比如说 add 方法的过程是……（这里可以引用我们在 ArrayList 源码解析中 add 的过程）。

谈谈对LinkedList的理解？——一样的套路。

2.扩容类问题

2.1 ArrayList 无参数构造器构造，现在 add 一个值进去，此时数组的大小是多少，下一次扩容前最大可用大小是多少？

答：此处数组的大小是 1，下一次扩容前最大可用大小是 10，因为 ArrayList 第一次扩容时，是有默认值的，默认值是 10，在第一次 add 一个值进去时，数组的可用大小被扩容到 10 了。

2.2 如果我连续往 list 里面新增值，增加到第 11 个的时候，数组的大小是多少？

扩容一次，从10扩容1.5倍，到15

2.3 数组初始化，被加入一个值后，如果我使用 addAll 方法，一下子加入 15 个值，那么最终数组的大小是多少？

扩容一次不够，根据ArrayList源码的扩容原则，当期望值(这里是16)大于一次扩容之后的量，那么我们这次扩容的值为期望值，即扩容之后容量为16

2.4 现在我有一个很大的数组需要拷贝，原数组大小是 5k，请问如何快速拷贝？

答：因为原数组比较大，不能频繁扩容，否则有大量拷贝的工作，造成拷贝的性能低下，所以回答说新建数组时，指定新数组的大小为 5k 即可。

2.5 为什么说扩容会消耗性能？

答：扩容底层使用的是 System.arraycopy 方法，会把原数组的数据全部拷贝到新数组上，所以性能消耗比较严重。

2.6 源码扩容过程有什么值得借鉴的地方？

主要两点：

扩容的思想。每次扩容1.5倍，也是比较合理的设置，前期慢慢增加，后期增加速度更快
扩容过程中，有数组大小溢出的意识，比如要求扩容后的数组大小，不能小于 0，不能大于 Integer 的最大值。

3.对比问题

3.1 ArrayList和LinkedList有何不同？

最大的不同是两者底层的数据结构不同，ArrayList 底层是数组，LinkedList 底层是双向链表，两者的数据结构不同也导致了操作的 API 实现有所差异，拿新增实现来说，ArrayList 会先计算并决定是否扩容，然后把新增的数据直接赋值到数组上，而 LinkedList 仅仅只需要改变插入节点和其前后节点的指向位置关系即可。

3.2 ArrayList 和 LinkedList 应用场景有何不同

答：ArrayList 更适合于快速的查找匹配，不适合频繁新增删除，像工作中经常会对元素进行匹配查询的场景比较合适，LinkedList 更适合于经常新增和删除，对查询反而很少的场景。

3.3 ArrayList 和 LinkedList 两者有没有最大容量

答：ArrayList 有最大容量的，为 Integer 的最大值，大于这个值 JVM 是不会为数组分配内存空间的，LinkedList 底层是双向链表，理论上可以无限大。但源码中，LinkedList 实际大小用的是 int 类型，这也说明了 LinkedList 不能超过 Integer 的最大值，不然会溢出。

3.4 ArrayList 和 LinkedList 是如何对 null 值进行处理的

答：ArrayList 允许 null 值新增，也允许 null 值删除。删除 null 值时，是从头开始，找到第一值是 null 的元素删除；LinkedList 新增删除时对 null 值没有特殊校验，是允许新增和删除的。

3.5 ArrayList 和 LinedList 是线程安全的么，为什么？

答：当两者作为非共享变量时，比如说仅仅是在方法里面的局部变量时，是没有线程安全问题的，只有当两者是共享变量时，才会有线程安全问题。主要的问题点在于多线程环境下，所有线程任何时刻都可对数组和链表进行操作，这会导致值被覆盖，甚至混乱的情况。

如果有线程安全问题，在迭代的过程中，会频繁报 ConcurrentModificationException 的错误，意思是在我当前循环的过程中，数组或链表的结构被其它线程修改了。

3.6 如何解决线程安全问题？

Java 源码中推荐使用 Collections#synchronizedList 进行解决，Collections#synchronizedList 的返回值是 List 的每个方法都加了 synchronized 锁，保证了在同一时刻，数组和链表只会被一个线程所修改，或者采用CopyOnWriteArrayList 并发 List 来解决。

4.其他

4.1 描述下双向链表的新增和删除

如果条件允许，可以画图说明，参考前面LinkedList的图。

如果远程电话面试，可以这样描述：双向链表中双向的意思是说前后节点之间互相有引用，链表的节点我们称为 Node。Node 有三个属性组成：其前一个节点，本身节点的值，其下一个节点，假设 A、B 节点相邻，A 节点的下一个节点就是 B，B 节点的上一个节点就是 A，两者互相引用，在链表的头部节点，我们称为头节点。头节点的前一个节点是 null，尾部称为尾节点，尾节点的后一个节点是 null，如果链表数据为空的话，头尾节点是同一个节点，本身是 null，指向前后节点的值也是 null。

4.2 描述下双向链表的新增和删除

答：如果是面对面沟通，最好可以直接画图，如果是电话面试，可以这么描述：

新增：我们可以选择从链表头新增，也可以选择从链表尾新增，如果是从链表尾新增的话，直接把当前节点追加到尾节点之后，本身节点自动变为尾节点。

删除：把删除节点的后一个节点的 prev 指向其前一个节点，把删除节点的前一个节点的 next 指向其后一个节点，最后把删除的节点置为 null 即可。

Hashmap源码解析与架构(未完)

首先HashMap的源码很长，面试题也很多，最好能弄清楚底层。

1.整体架构

HashMap 底层的数据结构主要是：数组 + 链表 + 红黑树。其中当链表的长度大于等于 8 时，链表会转化成红黑树，当红黑树的大小小于等于 6 时，红黑树会转化成链表。

图中左边竖着的是 HashMap 的数组结构，数组的元素可能是单个 Node，也可能是个链表，也可能是个红黑树，比如数组下标索引为 2 的位置就是一个链表，下标索引为 9 的位置对应的就是红黑树

1.1类注释中的信息

从下面这些信息可以大体把握HashMap的重点。

允许 null 值，不同于 HashTable ，是线程不安全的；
load factor（影响因子）默认值是 0.75，是均衡了时间和空间损耗算出来的值，较高的值会减少空间开销（扩容减少，数组大小增长速度变慢），但增加了查找成本（hash 冲突增加，链表长度变长），不扩容的条件：数组容量 > 需要的数组大小 /load factor；
如果有很多数据需要储存到 HashMap 中，建议 HashMap 的容量一开始就设置成足够的大小，这样可以防止在其过程中不断的扩容，影响性能；
HashMap 是非线程安全的，我们可以自己在外部加锁，或者通过 Collections#synchronizedMap 来实现线程安全，Collections#synchronizedMap 的实现是在每个方法上加上了 synchronized 锁；
在迭代过程中，如果 HashMap 的结构被修改，会快速失败。

1.2 常见的属性

//初始容量为 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

//负载因子默认值
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//桶上的链表长度大于等于8时，链表转化成红黑树
static final int TREEIFY_THRESHOLD = 8;

//桶上的红黑树大小小于等于6时，红黑树转化成链表
static final int UNTREEIFY_THRESHOLD = 6;

//当数组容量大于 64 时，链表才会转化成红黑树
static final int MIN_TREEIFY_CAPACITY = 64;

//记录迭代过程中 HashMap 结构是否发生变化，如果有变化，迭代时会 fail-fast
transient int modCount;

//HashMap 的实际大小，可能不准(因为当你拿到这个值的时候，可能又发生了变化)
transient int size;

//存放数据的数组
transient Node<K,V>[] table;

// 扩容的门槛，有两种情况
// 如果初始化时，给定数组大小的话，通过 tableSizeFor 方法计算，数组大小永远接近于 2 的幂次方，比如你给定初始化大小 19，实际上初始化大小为 32，为 2 的 5 次方。
// 如果是通过 resize 方法进行扩容，大小 = 数组容量 * 0.75
int threshold;

//链表的节点
static class Node<K,V> implements Map.Entry<K,V> {

//红黑树的节点
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {

2.新增节点

新增 key，value 大概的步骤如下：

空数组有无初始化，没有的话初始化；
如果通过 key 的 hash 能够直接找到值，跳转到 6，否则到 3；
如果 hash 冲突，两种解决方案：链表 or 红黑树；
如果是链表，递归循环，把新元素追加到队尾；
如果是红黑树，调用红黑树新增的方法；
通过 2、4、5 将新元素追加成功，再根据 onlyIfAbsent 判断是否需要覆盖；
判断是否需要扩容，需要扩容进行扩容，结束。

2.1链表的新增

链表的新增比较简单，就是把当前节点追加到链表的尾部，和 LinkedList 的追加实现一样的。

当链表长度大于等于 8 时，此时的链表就会转化成红黑树，转化的方法是：treeifyBin，此方法有一个判断，当链表长度大于等于 8，并且整个数组大小大于 64 时，才会转成红黑树，当数组大小小于 64 时，只会触发扩容，不会转化成红黑树。

可能面试的时候，有人问你为什么是 8，这个答案在源码中注释有说，中文翻译过来大概的意思是：

链表查询的时间复杂度是 O (n)，红黑树的查询复杂度是 O (log (n))。在链表数据不多的时候，使用链表进行遍历也比较快，只有当链表数据比较多的时候，才会转化成红黑树，但红黑树需要的占用空间是链表的 2 倍，考虑到转化时间和空间损耗，所以我们需要定义出转化的边界值。

在考虑设计 8 这个值的时候，我们参考了泊松分布概率函数，由泊松分布中得出结论，链表各个长度的命中概率为：

* 0:    0.60653066
* 1:    0.30326533
* 2:    0.07581633
* 3:    0.01263606
* 4:    0.00157952
* 5:    0.00015795
* 6:    0.00001316
* 7:    0.00000094
* 8:    0.00000006

意思是，当链表的长度是 8 的时候，出现的概率是 0.00000006，不到千万分之一，所以说正常情况下，链表的长度不可能到达 8 ，而一旦到达 8 时，肯定是 hash 算法出了问题，所以在这种情况下，为了让 HashMap 仍然有较高的查询性能，所以让链表转化成红黑树，我们正常写代码，使用 HashMap 时，几乎不会碰到链表转化成红黑树的情况，毕竟概念只有千万分之一。

2.2红黑树新增节点过程

首先判断新增的节点在红黑树上是不是已经存在，判断手段有如下两种：

1.1. 如果节点没有实现 Comparable 接口，使用 equals 进行判断；

1.2. 如果节点自己实现了 Comparable 接口，使用 compareTo 进行判断。
新增的节点如果已经在红黑树上，直接返回；不在的话，判断新增节点是在当前节点的左边还是右边，左边值小，右边值大；
自旋递归 1 和 2 步，直到当前节点的左边或者右边的节点为空时，停止自旋，当前节点即为我们新增节点的父节点；
把新增节点放到当前节点的左边或右边为空的地方，并于当前节点建立父子节点关系；
进行着色和旋转，结束。

红黑树的新增，要求大家对红黑树的数据结构有一定的了解。面试的时候，一般只会问到新增节点到红黑树上大概是什么样的一个过程，着色和旋转的细节不会问，因为很难说清楚，但我们要清楚着色指的是给红黑树的节点着上红色或黑色，旋转是为了让红黑树更加平衡，提高查询的效率，总的来说都是为了满足红黑树的 5 个原则：

节点是红色或黑色
根是黑色
所有叶子都是黑色
从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点
从每个叶子到根的所有路径上不能有两个连续的红色节点

3.查找

HashMap 的查找主要分为以下三步：

根据 hash 算法定位数组的索引位置，equals 判断当前节点是否是我们需要寻找的 key，是的话直接返回，不是的话往下。
判断当前节点有无 next 节点，有的话判断是链表类型，还是红黑树类型。
分别走链表和红黑树不同类型的查找方法。

Treemap和LinkedHashMap源码解析与架构(未完)

首先可以明确分析源码的目的：TreeMap 是如何根据 key 进行排序的和 LinkedHashMap 是如何用两种策略进行访问的。

1. Treemap解析

1.1 Treemap排序方式解析

了解 TreeMap 之前，我们来看下日常工作中排序的两种方式，作为我们学习的基础储备，两种方式的代码如下：

public class TreeMapDemo {

  @Data
  // DTO 为我们排序的对象
  class DTO implements Comparable<DTO> {
    private Integer id;
    public DTO(Integer id) {
      this.id = id;
    }

    @Override
    public int compareTo(DTO o) {
      //默认从小到大排序
      return id - o.getId();
    }
  }

  @Test
  public void testTwoComparable() {
    // 第一种排序，从小到大排序，实现 Comparable 的 compareTo 方法进行排序
    List<DTO> list = new ArrayList<>();
    for (int i = 5; i > 0; i--) {
      list.add(new DTO(i));
    }
    Collections.sort(list);
    log.info(JSON.toJSONString(list));

    // 第二种排序，从大到小排序，利用外部排序器 Comparator 进行排序
    Comparator comparator = (Comparator<DTO>) (o1, o2) -> o2.getId() - o1.getId();
    List<DTO> list2 = new ArrayList<>();
    for (int i = 5; i > 0; i--) {
      list2.add(new DTO(i));
    }
    Collections.sort(list,comparator);
    log.info(JSON.toJSONString(list2));
  }
}

第一种排序输出的结果从小到大，结果是：[{“id”:1},{“id”:2},{“id”:3},{“id”:4},{“id”:5}]；

第二种输出的结果恰好相反，结果是：[{“id”:5},{“id”:4},{“id”:3},{“id”:2},{“id”:1}]。

以上两种就是分别通过 Comparable 和 Comparator 两者进行排序的方式，而 TreeMap 利用的也是此原理，从而实现了对 key 的排序，我们一起来看下。

1.2 TreeMap整体架构

TreeMap 底层的数据结构就是红黑树，和 HashMap 的红黑树结构一样。

不同的是，TreeMap 利用了红黑树左节点小，右节点大的性质，根据 key 进行排序，使每个元素能够插入到红黑树大小适当的位置，维护了 key 的大小关系，适用于 key 需要排序的场景。

因为底层使用的是平衡红黑树的结构，所以 containsKey、get、put、remove 等方法的时间复杂度都是 log(n)。

1.3 TreeMap常见属性

//比较器，如果外部有传进来 Comparator 比较器，首先用外部的
//如果外部比较器为空，则使用 key 自己实现的 Comparable#compareTo 方法
//比较手段和上面日常工作中的比较 demo 是一致的
private final Comparator<? super K> comparator;

//红黑树的根节点
private transient Entry<K,V> root;

//红黑树的已有元素大小
private transient int size = 0;

//树结构变化的版本号，用于迭代过程中的快速失败场景
private transient int modCount = 0;

//红黑树的节点
static final class Entry<K,V> implements Map.Entry<K,V> {}

1.4新增节点过程

看下 TreeMap 新增节点的步骤：

判断红黑树的节点是否为空，为空的话，新增的节点直接作为根节点
根据红黑树左小右大的特性，进行判断，找到应该新增节点的父节点
在父节点的左边或右边插入新增节点
着色旋转，达到平衡，结束。

1	(这里省略掉了这四步的代码)

从源码中，我们可以看到：

新增节点时，就是利用了红黑树左小右大的特性，从根节点不断往下查找，直到找到节点是 null 为止，节点为 null 说明到达了叶子结点；
查找过程中，发现 key 值已经存在，直接覆盖；
TreeMap 是禁止 key 是 null 值的。

1.5 TreeMap小结

TreeMap 相对来说比较简单，红黑树和 HashMap 比较类似，比较关键的是通过 compare 来比较 key 的大小，然后利用红黑树左小右大的特性，为每个 key 找到自己的位置，从而维护了 key 的大小排序顺序。

2. LinkedHashMap整体结构解析(未完)

LinkedHashMap最主要的就是维护了插入的顺序。其本身继承了HashMap,再此基础上，还提供了两大特性：

按照插入顺序进行访问；
实现了访问最少最先删除功能，其目的是把很久都没有访问的 key 自动删除。

2.1 LinkedHashMap按照插入顺序访问

2.1.1 LinkedHashMap的链表结构

LinkedHashMap 的数据结构很像是把 LinkedList 的每个元素换成了 HashMap 的 Node，像是两者的结合体，也正是因为增加了这些结构，从而能把 Map 的元素都串联起来，形成一个链表，而链表就可以保证顺序了，就可以维护元素插入进来的顺序。

2.1.2 LinkedHashMap如何按照顺序新增

LinkedHashMap 初始化时，默认 accessOrder 为 false，就是会按照插入顺序提供访问，插入方法使用的是父类 HashMap 的 put 方法，不过覆写了 put 方法执行中调用的 newNode/newTreeNode 和 afterNodeAccess 方法。

newNode/newTreeNode 方法，控制新增节点追加到链表的尾部，这样每次新节点都追加到尾部，即可保证插入顺序了。

(略去源码)

LinkedHashMap 通过新增头节点、尾节点，给每个节点增加 before、after 属性，每次新增时，都把节点追加到尾节点等手段，在新增的时候，就已经维护了按照插入顺序的链表结构了。

换句话说，LinkedHashMap底层其实是双向链表+哈希Map的组合。

2.1.3 LinkedHashMap如何按照顺序访问

LinkedHashMap 只提供了单向访问，即按照插入的顺序从头到尾进行访问，不能像 LinkedList 那样可以从头和从尾两个方向双向访问。

我们主要通过迭代器进行访问，迭代器初始化的时候，默认从头节点开始访问，在迭代的过程中，不断访问当前节点的 after 节点即可。

Map 对 key、value 和 entity（节点）都提供出了迭代的方法，假设我们需要迭代 entity，就可使用 LinkedHashMap.entrySet().iterator() 这种写法直接返回 LinkedHashIterator ，LinkedHashIterator 是迭代器，我们调用迭代器的 nextNode 方法就可以得到下一个节点。

(源码略)

在新增节点时，我们就已经维护了元素之间的插入顺序了，所以迭代访问时非常简单，只需要不断的访问当前节点的下一个节点即可。

2.2 访问最少删除策略(LRU cahce)

非常经典的LRU（Least recently used,最近最少使用）了，大概的意思就是经常访问的元素会被追加到队尾，这样不经常访问的数据自然就靠近队头，然后每次删除都会把最尾部，也就是最不常用的元素，删除掉。(注意源码这里想表示的是删除队头的元素，所以常用的元素其实是会被追加到队尾的，这和我们自己实现的LRU cache是相反的，但是原理是相同的。我们自己写的LRU可以命名为moveToHead,但是我们写的就是head了，不是队尾)

删除策略的方法：removeEldestEntry

比如我们设定节点个数大于3个开始删除：

1
2
3

protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
  return size() > 3;
}

再次强调，LinkedHashMap的源码中经常使用的元素会被移动到队尾。

把元素移动到队尾的方法：afterNodeAccess。其实不仅仅是 get 方法，执行 getOrDefault、compute、computeIfAbsent、computeIfPresent、merge 方法时，也会这么做，通过不断的把经常访问的节点移动到队尾，那么靠近队头的节点，自然就是很少被访问的元素了。

2.2.1具体删除策略

我们在执行 put 方法时，发现队头元素被删除了，LinkedHashMap 本身是没有 put 方法实现的，调用的是 HashMap 的 put 方法，但 LinkedHashMap 实现了 put 方法中的调用 afterNodeInsertion 方法，这个方式实现了删除。

2.3 LinkedHashMap小结

LinkedHashMap 提供了两个很有意思的功能：按照插入顺序访问和删除最少访问元素策略(LRU cache)，简单地通过链表的结构就实现了，设计得非常巧妙。

Map接口常问问题

1. Map整体数据结构问题

1.1 HashMap的底层数据结构

答：HashMap 底层是数组 + 链表 + 红黑树的数据结构，数组的主要作用是方便快速查找，时间复杂度是 O(1)，默认大小是 16，数组的下标索引是通过 key 的 hashcode 计算出来的，数组元素叫做 Node，当多个 key 的 hashcode 一致，但 key 值不同时，单个 Node 就会转化成链表，链表的查询复杂度是 O(n)，当链表的长度大于等于 8 并且数组的大小超过 64 时，链表就会转化成红黑树，红黑树的查询复杂度是 O(log(n))，简单来说，最坏的查询次数相当于红黑树的最大深度。

具体来说，数组中的每个元素都是一个哈希桶，每个哈希桶里面包含四个字段：hash、key、value、next。其中next表示链表的下一个节点。

JDK 1.8 之所以添加红黑树是因为一旦链表过长，会严重影响 HashMap 的性能，而红黑树具有快速增删改查的特点，这样就可以有效的解决链表过长时操作比较慢的问题。

数据结构总结：jdk1.6 1.7 采用数组+链表，把key 进行取模获取下标，到对应的链表进行put/get操作 jdk1.8 采用数组+链表+红黑树（当链表超过8 而且总长度大于64时，转红黑树【1.符合二叉树结果 2.不是黑色就红色 3.叶子节点都是黑色或者nil 4.左右子树高度差小于 1 】）

1.2 HashMap、TreeMap、LinkedHashMap 三者有啥相同点，有啥不同点？

答：相同点：

三者在特定的情况下，都会使用红黑树；
底层的 hash 算法相同；
在迭代的过程中，如果 Map 的数据结构被改动，都会报 ConcurrentModificationException 的错误。

不同点：

Map 数据结构以数组为主，查询非常快，TreeMap 数据结构以红黑树为主，利用了红黑树左小右大的特点，可以实现 key 的排序，LinkedHashMap 在 HashMap 的基础上增加了链表的结构，实现了插入顺序访问和最少访问删除两种策略;
由于三种 Map 底层数据结构的差别，导致了三者的使用场景的不同，TreeMap 适合需要根据 key 进行排序的场景，LinkedHashMap 适合按照插入顺序访问，或需要删除最少访问元素的场景，剩余场景我们使用 HashMap 即可，我们工作中大部分场景基本都在使用 HashMap；
由于三种 map 的底层数据结构的不同，导致上层包装的 api 略有差别。

1.3 说一下 HashMap 的对hash 算法和寻址算法的优化

对hash算法的优化：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
key 在数组中的位置公式：tab[(n - 1) & hash]

这段代码是HashMap的hash算法。

这其实是一个数学问题，源码中就是通过以上代码来计算 hash 值的，首先计算出 key 的 hashcode，因为 key 是 Object，所以会根据 key 的不同类型进行 hashcode 的计算，接着计算 h ^ (h >>> 16) ，这么做的好处是使大多数场景下，算出来的 hash 值比较分散，因为此时hash计算之后的结果的低16位融合了高16位的特征，可以让每个计算出来的hash的值的低16位更大概率不同。

举个例子，如果一个key经过hashCode()计算后值为：1111 1111 1111 1111 1111 1010 0111 1100(没有经过优化的hash值)，那么右移16位之后会得到：0000 0000 0000 0000 1111 1111 1111 1111，然后将两者异或运算，得到：1111 1111 1111 1111 0000 0101 1000 0011 (经过优化和二进制位运算的新的hash值)（int值，32位）

这些计算我能看懂，但是为啥这么做？目的是让key的高16位和低16位做异或运算，其本身高16位在结果中还是不变的。这个过程就是对hash算法的优化，从而减少冲突。

对寻址算法的优化：

一般来说，hash 值算出来之后，要计算当前 key 在数组中的索引下标位置时，可以采用取模的方式，就是索引下标位置 = hash 值 % 数组大小，这样做的好处，就是可以保证计算出来的索引下标值可以均匀的分布在数组的各个索引位置上，但取模操作对于处理器的计算是比较慢的，我们可以考虑将取模运算转换成效果相同的与运算，数学上有个公式，当 b 是 2 的幂次方时，a % b = a &（b-1），所以此处索引位置的计算公式我们可以更换为： (n-1) & hash。

所以原本是取模的运算，在这里变成了和(长度-1)的与运算，这个是对寻址算法的优化，但是这个与运算和取模运算等价的前提是数组长度为2的倍数，所以哈希表元素数量要是2的倍数。

对hash和寻址算法的优化的总结：

hash算法的优化：对每个hash值，在他的低16位中，让高低16位进行了异或，让他的低16位同时保持了高低16位的特征，尽量避免一些hash值后续出现冲突，大家可能会进入数组的同一个位置
寻址算法的优化：用与运算替代取模，提升性能

此问题可以延伸出三个小问题：

为什么不用 key % 数组大小，而是需要用 key 的 hash 值 % 数组大小。

答：如果 key 是数字，直接用 key % 数组大小是完全没有问题的，但我们的 key 还有可能是字符串，是复杂对象，这时候用字符串或复杂对象 % 数组大小是不行的，所以需要先计算出 key 的 hash 值。

计算 hash 值时，为什么需要右移 16 位？

答：hash 算法是 h ^ (h >>> 16)，为了使计算出的 hash 值更分散，所以选择先将 h 无符号右移 16 位，然后再于 h 异或时，就能达到 h 的高 16 位和低 16 位都能参与计算，减少了碰撞的可能性。

为什么把取模操作换成了 & 操作？

答：key.hashCode() 算出来的 hash 值还不是数组的索引下标，为了随机的计算出索引的下表位置，我们还会用 hash 值和数组大小进行取模，这样子计算出来的索引下标比较均匀分布。

取模操作处理器计算比较慢，处理器对 & 操作就比较擅长，换成了 & 操作，是有数学上证明的支撑，为了提高了处理器处理的速度。

为什么提倡数组大小是 2 的幂次方？

答：因为只有大小是 2 的幂次方时，才能使 hash 值 % n(数组大小) == (n-1) & hash 公式成立。

1.4 为解决 hash 冲突，大概有哪些办法。

答：1：好的 hash 算法，细问的话复述一下上题的 hash 算法;

2：自动扩容，当数组大小快满的时候，采取自动扩容，可以减少 hash 冲突;

3：hash 冲突发生时，采用链表来解决;

4：hash 冲突严重时，链表会自动转化成红黑树，提高遍历速度。

其他不熟悉的方法不要说了。

2. HashMap源码细节类问题

2.1 HashMap 是如何扩容的？

答：扩容的时机：

put 时，发现数组为空，进行初始化扩容，默认扩容大小为 16;
put 成功后，发现现有数组大小大于扩容的门阀值时，进行扩容，扩容为老数组大小的 2 倍;

扩容的门阀是 threshold，每次扩容时 threshold 都会被重新计算，门阀值等于数组的大小 * 影响因子（0.75）。

新数组初始化之后，需要将老数组的值拷贝到新数组上，链表和红黑树都有自己拷贝的方法。

延伸问题：为什么数组容量会是2的倍数，以及扩容为什么是扩成两倍？

答：可以减少碰撞几率，2的倍数 -1 得到值所有位都是1，和计算值相与后能保证结果单一，如果位上的0越多，碰撞概率越大。举个例子，比如容量是2的4次方减1就是 1111。那么计算值1110过来和他相与，结果是1110，另一个计算值1111和他相与结果仍是1111 各自结果不一样不会碰撞如果容量不是2的4次方比如15 减1就是1110. 那么计算值1110过来和他相与，结果是1110，另一个计算值1111和他相与结果是1110 跟前一个一样发生碰撞了。

2.2 HashMap 是如何解决哈希冲突的？

答：hash 冲突指的是 key 值的 hashcode 计算相同，但 key 值不同的情况。

如果桶中元素原本只有一个或已经是链表了，新增元素直接追加到链表尾部；

如果桶中元素已经是链表，并且链表个数大于等于 8 时，此时有两种情况：

如果此时数组大小小于 64，数组再次扩容，链表不会转化成红黑树;
如果数组大小大于 64 时，链表就会转化成红黑树。

这里不仅仅判断链表个数大于等于 8，还判断了数组大小，数组容量小于 64 没有立即转化的原因，猜测主要是因为红黑树占用的空间比链表大很多，转化也比较耗时，所以数组容量小的情况下冲突严重，我们可以先尝试扩容，看看能否通过扩容来解决冲突的问题。

在 JDK 1.7 时 HashMap 是由数组和链表组成的，而 JDK 1.8 则新增了红黑树结构，当链表的长度大于 8 并且容量大于 64 时会转换为红黑树存储，以提升元素的操作性能。结合源码来具体说：当链表长度到8需要转化红黑树是还有一个判断table的length大于MIN_TREEIFY_CAPACITY，也就是64才会转化红黑树

2.3 为什么链表个数大于等于 8 时，链表要转化成红黑树了？

答：当链表个数太多了，遍历可能比较耗时(O(N))，转化成红黑树，可以使遍历的时间复杂度降低，但转化成红黑树，有空间和转化耗时的成本(O(logN))，我们通过泊松分布公式计算，正常情况下，链表个数出现 8 的概念不到千万分之一(源码中有写)，所以说正常情况下，链表都不会转化成红黑树，这样设计的目的，是为了防止非正常情况下，比如 hash 算法出了问题时，导致链表个数轻易大于等于 8 时，仍然能够快速遍历。

延伸问题：红黑树什么时候转变成链表。

答：当节点的个数小于等于 6 时，红黑树会自动转化成链表，主要还是考虑红黑树的空间成本问题，当节点个数小于等于 6 时，遍历链表也很快，所以红黑树会重新变成链表。

2.4 HashMap 在 put 时，如果数组中已经有了这个 key，我不想把 value 覆盖怎么办？取值时，如果得到的 value 是空时，想返回默认值怎么办？

答：如果数组有了 key，但不想覆盖 value ，可以选择 putIfAbsent 方法，这个方法有个内置变量 onlyIfAbsent，内置是 true ，就不会覆盖，我们平时使用的 put 方法，内置 onlyIfAbsent 为 false，是允许覆盖的。

取值时，如果为空，想返回默认值，可以使用 getOrDefault 方法，方法第一参数为 key，第二个参数为你想返回的默认值，如 map.getOrDefault(“2”,“0”)，当 map 中没有 key 为 2 的值时，会默认返回 0，而不是空。

2.5 通过以下代码进行删除，是否可行？

HashMap<String,String > map = Maps.newHashMap();
map.put("1","1");
map.put("2","2");
map.forEach((s, s2) -> map.remove("1"));

答：不行，会报错误 ConcurrentModificationException

2.6 描述一下 HashMap get(查询)、put(新增)、resize(数据扩容) 的过程

get(查询)

通过源码分析：如果没有哈希冲突，可以直接查询到。如果有哈希冲突，需要判断key的值是否相等，才能确认此元素是不是我们想要的元素。

add(新增)

直接来看流程图：

注意，如果根据key计算的哈希值冲突了，会比较复杂。首先如果之前key已经存在了，会直接覆盖value

resize(扩容)(重点)

当原本数组存不下的时候，需要考虑扩容。比如原先16位的数组，经过扩容之后会变成32位，那么原先的元素在的位置就会变化了。

举个例子，如果用16位存储，我们现在有两个数，经过hash之后结果是一样的，都是5，会冲突。

第一个数：

n - 1      0000 0000 0000 0000 0000 0000 0000 1111

hash1     1111 1111 1111 1111 0000 1111 0000 0101

&结果    0000 0000 0000 0000 0000 0000 0000 0101    = 5（index = 5的位置）

第二个数：

n - 1      0000 0000 0000 0000 0000 0000 0000 1111

hash2     1111 1111 1111 1111 0000 1111 0001 0101

&结果    0000 0000 0000 0000 0000 0000 0000 0101 = 5（index = 5的位置）

会发现，这两个数hash之后结果都是5，也就是说在数组长度为16的时候，他们两个hash值的位置是一样的，用链表来处理，出现一个hash冲突的问题。

所以我们可以进行扩容，扩容到32位去保存。扩容之后：

第一个数：

n-1        0000 0000 0000 0000 0000 0000 0001 1111

hash1     1111 1111 1111 1111 0000 1111 0000 0101

&结果    0000 0000 0000 0000 0000 0000 0000 0101 = 5（index = 5的位置）

第二个数：

n-1        0000 0000 0000 0000 0000 0000 0001 1111

hash2     1111 1111 1111 1111 0000 1111 0001 0101

&结果    0000 0000 0000 0000 0000 0000 0001 0101 = 21（index = 21的位置）

由此一来，计算之后index就不冲突了，扩容的数组得到了利用。

判断二进制结果中是否多出一个bit的1，如果没多，那么就是原来的index，如果多了出来，那么就是index + oldCap(对于这个例子，就是5+16，新位置是21)，通过这个方式，就避免了rehash的时候，用每个hash对新数组.length取模，取模性能不高，位运算的性能比较高。

也就是说，如果扩容之后高位发生了变化，那么新的位置是原数组下标+原数组长度

上面只是一个大概的印象，下面结合源码进行详细分析：

从源码可以看出，JDK 1.8 在扩容时并没有像 JDK 1.7 那样，重新计算每个元素的哈希值，而是通过高位运算（e.hash & oldCap）来确定元素是否需要移动，比如 key1 的信息如下：

key1.hash = 10 (0000 1010)
oldCap = 16 (0001 0000)

使用 e.hash & oldCap 得到的结果，高一位为 0，当结果为 0 时表示元素在扩容时位置不会发生任何变化.

再举个例子，key2:

key2.hash = 10 0001 0001
oldCap = 16 0001 0000

这时候得到的结果，高一位为 1，当结果为 1 时，表示元素在扩容时位置发生了变化，新的下标位置等于原下标位置 + 原数组长度，如下图所示：

其中红色的虚线图代表了扩容时元素移动的位置。

2.7 什么是加载因子？加载因子为什么是0.75？

加载因子也叫扩容因子或负载因子，用来判断什么时候进行扩容的，假如加载因子是0.5，HashMap的初始化容量是16，那么当HashMap中有16*0.5=8个元素时，HashMap就会进行扩容。

那加载因子为什么是 0.75 而不是 0.5 或者 1.0 呢？

这其实是出于容量和性能之间平衡的结果：

当加载因子设置比较大的时候，扩容的门槛就被提高了，扩容发生的频率比较低，占用的空间会比较小，但此时发生Hash冲突的几率就会提升，因此需要更复杂的数据结构来存储元素，这样对元素的操作时间就会增加，运行效率也会因此降低；而当加载因子值比较小的时候，扩容的门槛会比较低，因此会占用更多的空间，此时元素的存储就比较稀疏，发生哈希冲突的可能性就比较小，因此操作性能会比较高。
为了提升扩容效果，HashMap的容量(capacity)有一个固定的要求，那就是一定要是2的幂。所以，如果负载因子是3/4的话，那么和capacity的乘积结果就可以是一个整数。

所以综合了以上情况就取了一个 0.5 到 1.0 的平均数 0.75 作为加载因子。

2.8 HashMap死循环分析

以JDK1.7为例，假设HashMap默认大小为2，原本HashMap中有一个元素key(5)，我们再使用两个线程：t1添加元素key(3)，t2添加元素key(7)，当元素key(3) 和 key(7) 都添加到 HashMap 中之后，线程 t1 在执行到 Entry<K,V> next = e.next; 时，交出了 CPU 的使用权，源码如下：

那么此时线程t1中的e指向了key(3)，而next指向了key(7)；之后线程t2重新rehash之后链表的顺序被反转，链表的位置变成了key(5)→key(7)→key(3)，其中 “→” 用来表示下一个元素。

当t1重新获得执行权之后，先执行newTalbe[i]=e把key(3)的next设置为key(7)，而下次循环时查询到key(7)的next元素为key(3)，于是就形成了 key(3) 和 key(7) 的循环引用，因此就导致了死循环的发生，如下图所示：

当然发生死循环的原因是 JDK 1.7 链表插入方式为首部倒序插入，这个问题在 JDK 1.8 得到了改善，变成了尾部正序插入。

有人曾经把这个问题反馈给了Sun公司，但Sun公司认为这不是一个问题，因为HashMap本身就是非线程安全的，如果要在多线程下，建议使用ConcurrentHashMap替代，但这个问题在面试中被问到的几率依然很大，所以在这里需要特别说明一下。

3.其他Map面试题

3.1 DTO 作为 Map 的 key 时，有无需要注意的点？

答：DTO 就是一个数据载体，可以看做拥有很多属性的 Java 类，我们可以对这些属性进行 get、set 操作。

看是什么类型的 Map，如果是 HashMap 的话，一定需要覆写 equals 和 hashCode 方法，因为在 get 和 put 的时候，需要通过 equals 方法进行相等的判断；如果是 TreeMap 的话，DTO 需要实现 Comparable 接口，因为 TreeMap 会使用 Comparable 接口进行判断 key 的大小；如果是 LinkedHashMap 的话，和 HashMap 一样的。

3.2 为什么推荐 TreeMap 的元素最好都实现 Comparable 接口？但 key 是 String 的时候，我们却没有额外的工作呢？

答：因为 TreeMap 的底层就是通过排序来比较两个 key 的大小的，所以推荐 key 实现 Comparable 接口，是为了往你希望的排序顺序上发展，而 String 本身已经实现了 Comparable 接口，所以使用 String 时，我们不需要额外的工作，不仅仅是 String ，其他包装类型也都实现了 Comparable 接口，如 Long、Double、Short 等等。

集合在JDK7和JDK8有什么区别

1.通用区别

所有集合都新增了forEach方法

List、Set、Map 在 Java 8 版本中都增加了 forEach 的方法，方法的入参是 Consumer，Consumer 是一个函数式接口，可以简单理解成允许一个入参，但没有返回值的函数式接口

2 List区别

ArrayList 无参初始化时，Java 7 是直接初始化 10 的大小，Java 8 去掉了这个逻辑，初始化时是空数组，在第一次 add 时才开始按照 10 进行扩容。

需要注意，List在其他方面，Java7和Java8没有改动。

3 Map区别

3.1 HashMap

和 ArrayList 一样，Java 8 中 HashMap 在无参构造器中，丢弃了 Java 7 中直接把数组初始化 16 的做法，而是采用在第一次新增的时候，才开始扩容数组大小；
hash 算法计算公式不同，Java 8 的 hash 算法更加简单，代码更加简洁；
Java 8 的 HashMap 增加了红黑树的数据结构，这个是 Java 7 中没有的，Java 7 只有数组 + 链表的结构，Java 8 中提出了数组 + 链表 + 红黑树的结构，一般 key 是 Java 的 API 时，比如说 String 这些 hashcode 实现很好的 API，很少出现链表转化成红黑树的情况，因为 String 这些 API 的 hash 算法够好了，只有当 key 是我们自定义的类，而且我们覆写的 hashcode 算法非常糟糕时，才会真正使用到红黑树，提高我们的检索速度。

也是因为 Java 8 新增了红黑树，所以几乎所有操作数组的方法的实现，都发生了变动，比如说 put、remove 等操作，可以说 Java 8 的 HashMap 几乎重写了一遍，所以 Java 7 的很多问题都被 Java 8 解决了，比如扩容时极小概率死锁，丢失数据等等。

新增了一些好用的方法，比如 getOrDefault
新增了putIfAbsent(K key, V value) 方法，意思是，如果 map 中存在 key 了，那么 value 就不会覆盖，如果不存在 key ，新增成功。
新增了compute 方法，意思是允许我们把 key 和 value 的值进行计算后，再 put 到 map 中，为防止 key 值不存在造成未知错误，map 还提供了 computeIfPresent 方法，表示只有在 key 存在的时候

上述 Java 8 新增的几种方法非常好用，在实际工作中，可以大大减少我们的代码量

3.2 LinkedHashMap

由于 Java 8 的底层数据有变动，导致 HashMap 操作数据的方法几乎重写，也使 LinkedHashMap 的实现名称上有所差异。

4 其他区别

Arrays 提供了很多 parallel 开头的方法。

Java 8 的 Arrays 提供了一些 parallel 开头的方法，这些方法支持并行的计算，在数据量大的时候，会充分利用 CPU ，提高计算效率，比如说 parallelSort 方法，方法底层有判断，只有数据量大于 8192 时，才会真正走并行的实现，在实际的实验中，并行计算的确能够快速的提高计算速度。

5.面试题

Java 8 在 List、Map 接口上新增了很多方法，为什么 Java 7 中这些接口的实现者不需要强制实现这些方法呢？
答：主要是因为这些新增的方法被 default 关键字修饰了，default 一旦修饰接口上的方法，我们需要在接口的方法中写默认实现，并且子类无需强制实现这些方法，所以 Java 7 接口的实现者无需感知。
Java 8 中有新增很多实用的方法，你在平时工作中有使用过么？

答：有的，比如说 getOrDefault、putIfAbsent、computeIfPresent 方法等等，具体使用细节参考上文。

说说 computeIfPresent 方法的使用姿势？

答：computeIfPresent 是可以对 key 和 value 进行计算后，把计算的结果重新赋值给 key，并且如果 key 不存在时，不会报空指针，会返回 null 值。

Java 8 集合新增了 forEach 方法，和普通的 for 循环有啥不同？

答：新增的 forEach 方法的入参是函数式的接口，比如说 Consumer 和 BiConsumer，这样子做的好处就是封装了 for 循环的代码，让使用者只需关注实现每次循环的业务逻辑，简化了重复的 for 循环代码，使代码更加简洁，普通的 for 循环，每次都需要写重复的 for 循环代码，forEach 把这种重复的计算逻辑吃掉了，使用起来更加方便。

HashMap 8 和 7 有啥区别？

答：HashMap 8 和 7 的差别太大了，新增了红黑树，修改了底层数据逻辑，修改了 hash 算法，几乎所有底层数组变动的方法都重写了一遍，可以说 Java 8 的 HashMap 几乎重新了一遍。

6.小结

总体来说，List 方面是小改动，HashMap 几乎重写了一套，所有的集合都新增了函数式的方法，比如说 forEach，也新增了很多好用的函数，比如说 getOrDefault，这些函数可以大大减少我们的代码量，让我们把关注点聚焦在业务逻辑的实现上，这其实是一种思想，把繁琐重复的计算逻辑抽取出来，从计算逻辑中扩展出业务逻辑的口子，让使用者只专心关注业务逻辑的实现即可。

ConcurrentHashMap 源码解析和设计思路(未完)

当我们碰到线程不安全场景下，需要使用 Map 的时候，我们第一个想到的 API 估计就是 ConcurrentHashMap，ConcurrentHashMap 内部封装了锁和各种数据结构来保证访问 Map 是线程安全的。

Q：说明一下，为什么要解决HashMap的多线程问题？

A：HashMap不是线程安全的，而如果每次多线程使用HashMap的时候都加上synchronized关键字，性能很低也很不合理，因为底层数组里有很多的元素，除非是对同一个元素执行put操作，否则不需要多线程加上阻塞来强制同步进行。

总体概览

在JDK 1.7以及之前的版本里，是对数组的每个部分都进行分段，即：[数组1] , [数组2]，[数组3] -> 每个数组都对应一个锁，分段加锁。但是，如果不同线程访问的数组的位置不同那么其实没必要耗费资源加锁。比如，多个线程过来，线程1要put的位置是数组1[5]，线程2要put的位置是数组2[21]，那么其实这两个线程之间不冲突，没必要针对不同的数组加锁。

所以，JDK 1.8以及之后，做了一些优化和改进，对锁粒度进行了细化。

现在我们只有一个数组，即[一个大的数组]，数组里每个元素进行put操作，都是有一个不同的锁，刚开始进行put的时候，如果两个线程都是在数组[5]这个位置进行put，这个时候，对数组[5]这个位置进行put的时候，采取的是CAS的策略。

同一个时间，只有一个线程能成功执行这个CAS，就是说他刚开始先获取数组[5]这个位置的值，如果是null，那么之后执行CAS，线程1，比较一下，如果还是null，则put进去我的这条数据，此时，其他的线程执行CAS的时候都会失败。

使用了分段加锁，通过对数组每个元素执行CAS的策略，如果是很多线程对数组里不同的元素执行put，大家是没有关系的，如果其他线程失败了，其他线程此时会发现数组[5]这位置，已经给刚才有线程放值进去了。

此时就需要在这个位置基于链表+红黑树来进行处理，synchronized(数组[5])，加锁，基于链表或者是红黑树在这个位置插进去自己的数据。

所以，在JDK1.8之后实现了：如果你是对数组里同一个位置的元素进行操作，才会加锁串行化处理；如果是对数组不同位置的元素操作，此时大家可以并发执行的。ConcurrentHashMap就是在这上面进行了优化。

总体概览小结：

jdk1.8之前ConcurrentHashMap实现线程安全使用的是分段锁技术，即将一个大数组分成几个小数组，当并发put时，处于同一个小数组的put操作会串行；不同小数组间的put操作不受影响。

jdk1.8及之后，ConcurrentHashMap优化了锁的细粒度，并发操作时，对数组中每一个位置元素进行CAS。当并发put时，对同一位置进行put操作，如果put失败，说明在这之前有线程对这个位置进行了put成功操作，则对这个位置上的链表或者红黑树使用synchronized加锁；对不同位置put操作是不受影响的。

1. 类注释

我们从类注释上大概可以得到如下信息：

所有的操作都是线程安全的，我们在使用时，无需再加锁；
多个线程同时进行 put、remove 等操作时并不会阻塞，可以同时进行，和 HashTable 不同，HashTable 在操作时，会锁住整个 Map；
迭代过程中，即使 Map 结构被修改，也不会抛 ConcurrentModificationException 异常；
除了数组 + 链表 + 红黑树的基本结构外，新增了转移节点，是为了保证扩容时的线程安全的节点；
提供了很多 Stream 流式方法，比如说：forEach、search、reduce 等等。

2.结构

虽然 ConcurrentHashMap 的底层数据结构，和方法的实现细节和 HashMap 大体一致，但两者在类结构上却没有任何关联

如下图：

有的同学可能会问，为什么不继承 HashMap 呢？继承的确是个好办法，但尴尬的是，ConcurrentHashMap 都是在方法中间进行一些加锁操作，也就是说加锁把方法切割了，继承就很难解决这个问题。

ConcurrentHashMap 和 HashMap 两者的相同之处：

数组、链表结构几乎相同，所以底层对数据结构的操作思路是相同的（只是思路相同，底层实现不同）；
都实现了 Map 接口，继承了 AbstractMap 抽象类，所以大多数的方法也都是相同的，HashMap 有的方法，ConcurrentHashMap 几乎都有，所以当我们需要从 HashMap 切换到 ConcurrentHashMap 时，无需关心两者之间的兼容问题。

不同之处：

红黑树结构略有不同，HashMap 的红黑树中的节点叫做 TreeNode，TreeNode 不仅仅有属性，还维护着红黑树的结构，比如说查找，新增等等；ConcurrentHashMap 中红黑树被拆分成两块，TreeNode 仅仅维护的属性和查找功能，新增了 TreeBin，来维护红黑树结构，并负责根节点的加锁和解锁；
新增 ForwardingNode （转移）节点，扩容的时候会使用到，通过使用该节点，来保证扩容时的线程安全。

3.Put操作

ConcurrentHashMap 在 put 方法上的整体思路和 HashMap 相同，但在线程安全方面写了很多保障的代码，我们先来看下大体思路：

如果数组为空，初始化，初始化完成之后，走 2；
计算当前槽点有没有值，没有值的话，cas 创建，失败继续自旋（for 死循环），直到成功，槽点有值的话，走 3；
如果槽点是转移节点(正在扩容)，就会一直自旋等待扩容完成之后再新增，不是转移节点走 4；
槽点有值的，先锁定当前槽点，保证其余线程不能操作，如果是链表，新增值到链表的尾部，如果是红黑树，使用红黑树新增的方法新增；
新增完成之后 check 需不需要扩容，需要的话去扩容。

3.1数组初始化时的线程安全

数组初始化时，首先通过自旋来保证一定可以初始化成功，然后通过 CAS 设置 SIZECTL 变量的值，来保证同一时刻只能有一个线程对数组进行初始化，CAS 成功之后，还会再次判断当前数组是否已经初始化完成，如果已经初始化完成，就不会再次初始化，通过自旋 + CAS + 双重 check 等手段保证了数组初始化时的线程安全。

3.2新增槽点值时的线程安全

此时为了保证线程安全，做了四处优化：

通过自旋死循环保证一定可以新增成功。

在新增之前，通过 for (Node[] tab = table;;) 这样的死循环来保证新增一定可以成功，一旦新增成功，就可以退出当前死循环，新增失败的话，会重复新增的步骤，直到新增成功为止。

当前槽点为空时，通过 CAS 新增。

Java 这里的写法非常严谨，没有在判断槽点为空的情况下直接赋值，因为在判断槽点为空和赋值的瞬间，很有可能槽点已经被其他线程赋值了，所以我们采用 CAS 算法，能够保证槽点为空的情况下赋值成功，如果恰好槽点已经被其他线程赋值，当前 CAS 操作失败，会再次执行 for 自旋，再走槽点有值的 put 流程，这里就是自旋 + CAS 的结合。

当前槽点有值，锁住当前槽点。

put 时，如果当前槽点有值，就是 key 的 hash 冲突的情况，此时槽点上可能是链表或红黑树，我们通过锁住槽点，来保证同一时刻只会有一个线程能对槽点进行修改。

1
2
3

V oldVal = null;
// 锁定当前槽点，其余线程不能操作，保证了安全
synchronized(f){}

红黑树旋转时，锁住红黑树的根节点，保证同一时刻，当前红黑树只能被一个线程旋转，如下图代码：

通过以上 4 点，保证了在各种情况下的新增（不考虑扩容的情况下），都是线程安全的，通过自旋 + CAS + 锁三大姿势，实现的很巧妙。

3.3 扩容时的线程安全

ConcurrentHashMap 的扩容时机和 HashMap 相同，都是在 put 方法的最后一步检查是否需要扩容，如果需要则进行扩容，但两者扩容的过程完全不同，ConcurrentHashMap 扩容的方法叫做 transfer，从 put 方法的 addCount 方法进去，就能找到 transfer 方法，transfer 方法的主要思路是：

首先需要把老数组的值全部拷贝到扩容之后的新数组上，先从数组的队尾开始拷贝；
拷贝数组的槽点时，先把原数组槽点锁住，保证原数组槽点不能操作，成功拷贝到新数组时，把原数组槽点赋值为转移节点；
这时如果有新数据正好需要 put 到此槽点时，发现槽点为转移节点，就会一直等待，所以在扩容完成之前，该槽点对应的数据是不会发生变化的；
从数组的尾部拷贝到头部，每拷贝成功一次，就把原数组中的节点设置成转移节点；
直到所有数组数据都拷贝到新数组时，直接把新数组整个赋值给数组容器，拷贝完成

扩容中的关键点，就是如何保证是线程安全的，小结有如下几点：

拷贝槽点时，会把原数组的槽点锁住；
拷贝成功之后，会把原数组的槽点设置成转移节点，这样如果有数据需要 put 到该节点时，发现该槽点是转移节点，会一直等待，直到扩容成功之后，才能继续 put，可以参考 put 方法中的 helpTransfer 方法；
从尾到头进行拷贝，拷贝成功就把原数组的槽点设置成转移节点。
等扩容拷贝都完成之后，直接把新数组的值赋值给数组容器，之前等待 put 的数据才能继续 put。

扩容方法还是很有意思的，通过在原数组上设置转移节点，put 时碰到转移节点时会等待扩容成功之后才能 put 的策略，来保证了整个扩容过程中肯定是线程安全的，因为数组的槽点一旦被设置成转移节点，在没有扩容完成之前，是无法进行操作的。

4.get

ConcurrentHashMap 读的话，就比较简单，先获取数组的下标，然后通过判断数组下标的 key 是否和我们的 key 相等，相等的话直接返回，如果下标的槽点是链表或红黑树的话，分别调用相应的查找数据的方法，整体思路和 HashMap 很像。

5.ConcurrentHashMap线程安全的具体实现方式/底层实现

如下图：

JDK1.7之前：

具体实现：

首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。

ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。

Segment 实现了 ReentrantLock,所以 Segment 是一种可重入锁，扮演锁的角色。HashEntry 用于存储键值对数据。

1
2
3

static class Segment<K,V> extends ReentrantLock implements Serializable {

}

一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和HashMap类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个 HashEntry数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment的锁。

JDK1.8的ConcurrentHashMap:

ConcurrentHashMap取消了Segment分段锁，采用CAS和synchronized来保证并发安全。数据结构跟HashMap1.8 的结构类似，数组+链表/红黑二叉树。

synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产生并发，效率又提升N倍。