容器对比

集合框架简述

  • 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

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

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

ensureCapacityInternal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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

1
2
3
4
5
6
7
8
9
10
11
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

1
2
3
4
5
6
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

1
2
3
4
5
6
7
8
9
10
11
12
// 我们发现 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

1
2
3
4
5
6
7
8
9
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中就是先用哈希值与数组长度取余,再存放到对应数组下标

1
HashCode % length

而取余运算是可以转化为按位与的(前提为length是二进制数):

1
HashCode & (length - 1)

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

2的幂

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

1
2
length:	  10000
length-1: 01111

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

1
2
3
4
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作为平衡条件,而红黑树巧妙的将规则设定为平衡条件,省去了许多繁琐的操作步骤。