Java八股文-容器

容器对比

集合框架简述

• Collection
  • List：有序，可重复。ArrayList、LinkedList
  • Set：无序，无重复。HashSet、TreeSet
  • Queue（Deque）：队列，有序，可重复。LinkedList、PriorityQueue
• Map：键值对key-value存储，一个键对应一个值。HashMap、TreeMap、HashTable、ConcurrentHashMap

ArrayList与LinkedList的区别

• 线程安全：二者都不保证线程安全，Vector可以实现线程安全。

• 底层数据结构：

  ArrayList对应数组。

  LinkedList对应双向链表，每个结点有前驱后继两个指针。

• 查找操作多使用ArrayList，插入、删除操作多使用LinkedList。

• 内存空间占用：

  ArrayList由于是数组实现，会预留一定容量空间。整体空间占比高。

  LinkedList每一个元素空间占比更高，因为有前驱后继两个指针。

• 实现RandomAccess接口

  由于ArrayList具有快速随机访问的功能，所以它实现了RandomAccess接口，但RandomAccess接口是没有内容定义的，仅仅是一个标识，代表可以快速随机访问，相对的LinkedList没有实现接口，因为其本身就不具有快速随机访问的功能，所以没有这个标识。

  RandomAccess仅仅只是一个标识，并不是说实现这个接口就具有快速随机访问功能。

HashMap与HashTable区别

• 线程安全：

  HashMap非线程安全，HashTable内部方法有synchronized处理是线程安全的，但要保证线程安全推荐使用ConcurrentHashMap。

• 效率：由于线程安全问题，HashMap比HashTable效率高，HashTable基本被淘汰。

• 对 Null key 和 Null value 的支持：

  HashMap键值对可存储空值，HashTable不允许键值对存储空值，会抛出空指针异常。

• 底层数据结构：

  HashMap1.7是数组+链表，1.8数组+链表+红黑树

  HashTable是数组+链表

• 初始容量以及扩容大小：

  • 初始不指定容量
    • HashTable默认初始大小11，每次扩容容量变为原来的2n+1
    • HashMap默认初始大小16，每次扩容变为原来2倍
  • 创建时指定初始容量
    • HashTable直接使用给定的容量大小
    • HashMap会以给定容量为基础，扩充为2的幂的大小，因为HashMap的大小要保证是2的幂，为了提高算法效率使用按位与计算，必须是2的幂

HashMap与HashSet区别

HashSet底层其实是基于HashMap实现。

HashMap存储键值对，键唯一，使用键计算hashcode。

HashSet只存储对象，通过成员对象计算hashcode，但hashcode可能相同，一般使用equals()判断两个对象是否相同。

ConcurrentHashMap与HashTable区别

主要体现在实现线程安全的方式不同。

HashTable使用全表锁，所有数据争夺一把锁，效率及其低下。

ConcurrentHashMap（jdk1.7）使用分段锁，对桶数组进行分段，拆分成Segment数组，一个Segment包含多个HashEntry，也就是多个数组结点，这样每把锁就对应部分数据，减少锁竞争问题，提高并发访问效率。

ConcurrentHashMap（jdk1.8）取消了Segment分段锁，采用CAS 和 synchronized来保证并发安全，数据结构和HashMap1.8一样。而操作对象由原本的Segment变为HashEntry，直接操作数组结点

CAS对应乐观锁，synchronized对应悲观锁，使用乐观锁进一步提高效率，当乐观锁失效时在采用悲观锁。也就是检测到并发冲突再加锁。

ArrayList底层实现

初始化

• 无参初始化：初始化为一个空数组，然后在执行第一个添加操作时进行扩容，容量变为10，扩容我们后面会细说。
• 有参初始化：初始化一个指定大小的数组。
• 参数为Collection的初始化：复制该集合的元素，不常用。

扩容机制（一般扩容1.5倍）

add

public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

可以发现add就是数组赋值并索引递增，但前提是执行ensureCapacityInternal方法。我们再来看看这个方法是干什么的。

ensureCapacityInternal

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

这里我们可以解释空数组的初始扩容为什么是10，ArrayList定义了默认容量10以及size变量，size是默认值0，这里我们初始化无参数组后，首次执行add方法，它会调用 ensureCapacityInternal(size + 1) 其中参数是1，也就是说 ensureCapacityInternal 方法的最小容量参数首次添加时为1。

然后按层次先执行 calculateCapacity方法，当当前数组为空时，它会比较数组的最小容量与默认容量，取较大值返回，不是空数组则返回最小容量。这里空数组会返回默认容量10。

接着执行 ensureExplicitCapacity方法 ，若最小容量大于数组长度则执行 grow方法进行扩容。这里首次无参初始化的空数组，其传入的最小容量参数大于空数组长度0相等，会进行第一次扩容。

其中modCount用于记录修改次数，为多线程服务，这里单线程就不用关心了。

grow

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

这里grow方法先是获取当前数组长度，将原长度>>1即除2，所以数组扩容为原来的1.5倍左右（奇数有损），然后比较扩容后长度与当前传入的最小容量参数，返回较大值。接着就对最大界限进行了限制。最后执行Arrays.copyOf，创建一个新数组，其长度设置为扩容容量，并把现在的元素复制过去。

复制操作

我们在扩容时往往是新建一个数组，把原本数组内容copy过去，会经常使用 Arrays.copyOf 和 System.arraycopy 这两个方法，这里来分析一下。

Arrays.copyOf

public static int[] copyOf(int[] original, int newLength) {
    int[] copy = new int[newLength];
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

其他数组类似，这里选择了整数型数组，copy操作就是创建一个扩容容量的新数组，然后调用 System.arraycopy 进行复制最后返回新的数组。注意最后一个参数取要复制的数组长度，因为是要复制的数组，也就是待扩容的，肯定长度较小，所以取min。

System.arraycopy

// 我们发现 arraycopy 是一个 native 方法,接下来我们解释一下各个参数的具体意义
/**
 * 复制数组
 * @param src 源数组
 * @param srcPos 源数组中的起始位置
 * @param dest 目标数组
 * @param destPos 目标数组中的起始位置
 * @param length 要复制的数组元素的数量
 */
 public static native void arraycopy(Object src,  int  srcPos,
                                     Object dest, int destPos,
                                     int length);

选择源数组的指定索引后的内容，然后从目标数组的指定索引处开始复制过来，长度代表要复制的数量。

ensureCapacity

public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        ? 0
        : DEFAULT_CAPACITY;
    
    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

这个方法是由用户自行调用的，ArrayList中并没有调用过。我们在进行大量add操作时可以先调用该方法，此时传入的是 add的操作次数。也就是说我们执行100000次add，先调用该方法，会在add操作执行前就用执行的总次数调用 ensureExplicitCapacity方法，先对数组进行扩容，我们传入的最小容量就是执行次数，这样就不用在执行add时频繁扩容，减少了时间的消耗。

HashMap底层实现

HashMap为什么长度是2的幂

这个属于HashMap的经典问题了，不得不说似懂非懂的人太多了，许多博客都在瞎讲，这里我就讲讲自己对这个问题的理解。（推荐看guide哥的容器讲解，这个点讲的很对）

% 与 &

相信大家都知道，计算机在处理% 和 &这两个运算符时，&的效率是高于%的，因为&是二进制计算，计算机处理效率更高。

HashMap的算法

我们一般用算法处理散列值的分配问题，好的算法就可以有效降低hash冲突的发生。在HashMap中就是先用哈希值与数组长度取余，再存放到对应数组下标：

HashCode % length

而取余运算是可以转化为按位与的（前提为length是二进制数）：

HashCode & (length - 1)

这么看来只有当数组长度是2的幂时，才能将取余运算转换为按位与，然后我们便可大大提升运算效率，所以HashMap长度要是2的幂，每次扩容*2。

2的幂

由前两个分析来看，如果当数组长度是2的幂时，我们发现lenth-1的值会变成低位全为1的二进制数：

length:	  10000
length-1: 01111

此时我们再用散列值与这个低位全为1的二进制数进行与运算，并与其他情况对比：

01111	01111	01001	01001
10101	10011	10101	10011
-----	-----	-----	-----
00101	00011	00001	00001

可以发现同样的数据，全为1按位与后的值冲突更不易发生。

这也是因为&的特性导致的，&计算的4种情况：00、01、10、11，结果是3个0，1个1，所以为了减少冲突我们尽量让值成为1，所以数组的长度要尽量全为1。

通过上述分析我们也可以理解为什么要让数组长度为2的幂，其length-1后是低位全1的二进制数，不仅加快了运算效率，而且不易产生hash冲突。

HashMap底层与红黑树

其实我一开始看Java并没有看集合类，毕竟学过数据结构，线性表、栈、队列、树、图、散列等底层我还是了解的，但在看面经的过程中，我突然发现了HashMap、红黑树这几个陌生的词汇经常被考察，所以我就去了解了一下。

了解后，我发现红黑树其实就是简易版的AVL树，也就是平衡二叉树，说简易版可能有点过了，红黑树只是没有AVL那么严格，但它也是通过结点的左旋、右旋来达到平衡状态的。二者相比下，AVL是树的高度平衡，查找效率高；而红黑树是高度平衡相差一层，但其插入删除操作的效率更高。

jdk1.7

数组+链表，发生哈希冲突时，将冲突元素存放到对数组的链表，使用头插法插入，但在多线程进行扩容操作时，使用头插法会形成环。

多线程头插法为什么形成环，比方一个数组索引有三个冲突元素123，则依次头插法插入链表，变成321，而扩容后形成的新数组我们要把现在的元素移过去，再次使用头插就变成了123，这是单线程下的扩容。而多线程下扩容时，第一个线程执行完后轮到第二个线程，但因为头插法的影响导致扩容后的链表顺序发生了改变，之后再按原先的顺序操作就会出现环，导致死锁的发生。

总结就是头插法容易逆序+环形链表死循环，放一个视频讲解：

https://www.bilibili.com/video/BV1n541177Ea?from=search&seid=4027342742461950529

jdk1.8

数组+链表+红黑树，发生哈希冲突也会放入链表，使用的尾插法，但当链表长度超过8时，会将其数据结构转换为红黑树以提高效率。当链表长度小于6时，由红黑树转回链表。

为什么当链表长度超过8转换为红黑树，因为当我们的算法足够好，链表达到8个结点的概率是非常低的，冲突能达到8说明当前算法不够好，导致散列不均匀，此时相对于特殊情况，我们需要转化成红黑树提高效率。

为什么红黑树转变成链表的阙值是6，如果阙值设为8，一个删除和添加操作就会频繁的进行链表和红黑树的转换，所以设置退化的阙值为6，阙值不可太临界。

多线程

刚刚说过jdk1.7使用头插会导致在多线程操作时死锁，就算jdk1.8使用了尾插，HashMap还是多用于单线程，在并发情况下建议使用ConcurrentHashMap。

负载因子

众所周知HashMap负载因子是0.75，但这是为什么呢？首先我们要知道负载因子是用来衡量HashMap何时该扩容的，当HashMap中元素超过 数组长度 * 负载因子 就要进行2倍扩容。负载因子相当于一个容量界限。

如果负载因子是1，相对于数组占满时扩容，其时间利用率低空间利用率高，属于时间换空间，而负载因子为0.5时，数组占一半就要扩容，这时扩容会造成空间的浪费，属于空间换时间。所以我们综合并根据算法选择负载因子是0.75，此时时间、空间利用率比较均衡。

红黑树

红黑树可以理解成没有那么严格的平衡二叉树（AVL），它并不是完全平衡的，因此旋转次数也相应减少。但使用红黑树进行增删操作，效率是高于AVL的。

规则

• 结点为红/黑
• 根结点为黑
• 叶子结点是黑色空结点null
• 每个红色结点的两个子结点均为黑色，不存在两个相连的红色结点
• 从任意结点到每个叶子结点的所有路径都包含相同数目的黑色结点

自平衡（旋转 + 变色）

注意插入的结点一定是红色的。

红黑树在执行添加与删除操作时，如果破坏了红黑树的规则，那么红黑树会和AVL一样，通过旋转进行自平衡，并且还要进行变色操作。这里就体现了红黑树与AVL的区别，AVL是明确规定树的深度差不超过1作为平衡条件，而红黑树巧妙的将规则设定为平衡条件，省去了许多繁琐的操作步骤。