Skip to content

Java集合面试题.md

Latest commit

 

History

History
114 lines (76 loc) · 6.8 KB

Java集合面试题.md

File metadata and controls

114 lines (76 loc) · 6.8 KB
Raw

集合面试题

ArrayList、LinkedList和Vector的区别和实现原理

数据结构实现

ArrayList和Vector都是基于可改变大小的数据实现的，而LinkedList是基于双链表实现的。

增删改查效率对比

ArrayList和Vector都是基于可改变大小的数据实现的，因此，从指定的位置检索对象时，或在集合的末尾插入对象、删除一个对象的时间都是O(1)，但是如果在其他位置增加或者删除对象，花费的时间是O(n)；

而LinkedList是基于双链表实现的，因此，在插入、删除集合中的任何位置上的对象，所花费的时间都是O(1)，但基于链表的数据结构在查找元素时的效率是更低的，花费的时间为O(n)。

因此，从以上分析我们可以知道，查找特定的对象或者在集合末端增加或者删除对象，ArrayList和Vector的效率是ok的，如果在指定的位置删除或者插入，LinkedList的效率则更高。

线程安全

ArrayList、LinkedList不具有线程安全性，在多线程的问题下是不能使用的，如果想要在多线程的环境下使用怎么办呢？我们可以采用Collections的静态方法synchronizedList包装一下，就可以保证线程安全了，但是在实际情况下，并不会使用这种方式，而是会采用更高级的集合进行线程安全的操作。

Vector是线程安全的，其保证线程安全的机制是采用synchronized关键字，我们都知道，这个关键字的效率是不高的，在后续的很多版本中，线程安全的机制都不会采用这种方式，因此，Vector的效率是比ArrayList、LinkedList更低效的。

扩容机制

ArrayList和Vector都是基于数据这种数据结构实现的，因此，在集合的容量满了时，是需要进行扩容操作的。

在扩容时，ArrayList扩容后的容量是原先的1.5倍，扩容后，再将原先的数组中的数据拷贝到新建的数组中。

Vector默认情况下，扩容后的容量是原先的2倍，除此之外，Vector还有一种可以设置容量增量的机制，在Vector中有capacityIncrement变量用于控制扩容时的增量，具体的规则是：当capacityIncrement大于0时，扩容时增加的大小就是capacityIncrement的大小，如果capacityIncrement小于等于0时，则将容量增加为之前的2倍。

HashMap原理分析

在分析HashMap的原理之前，先说明一下，大家应该都知道HashMap在JDK1.7和1.8的实现上是有较大的区别的，而面试官也是非常喜欢考察这一个点，因此，这里也是采用这两个JDK版本对比来进行分析，这样也可以印象更加深刻一些。

数据结构

在数据结构的实现上，大家应该都知道，JDK1.7是数组+单链表的形式，而1.8采用的是数组+单链表+红黑树，具体的表现如下：

版本 数据结构 数组+链表的实现形式 红黑树实现形式
JDK1.8 数组+单链表+红黑树 Node TreeNode
JDK1.7 数组+单链表 Entry -

为了更好的让大家理解后续的讲解，这里先讲解一下HashMap中实现的一些重要参数。

  • 容量（capacity）： HashMap中数组的长度

    • 容量范围：必须是 2 的幂
    • 初始容量 = 哈希表创建时的容量
      • 默认容量 = 16 = 1<<4 = 00001中的1向左移4位 = 10000 = 十进制的 2^4 = 16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
      • 最大容量 = 2的30次方 static final int MAXIMUM_CAPACITY = 1 << 30;

  • 加载因子(Load factor)：HashMap在其容量自动增加时，会设置加载因子，当达到设置的值时，就会触发自动扩容。

    • 加载因子越大、填满的元素越多，也就是说，空间利用率高、但冲突的机会加大、查找效率变低
    • 加载因子越小、填满的元素越少，也就是说，空间利用率小、冲突的机会减小、查找效率高 // 实际加载因子 final float loadFactor; // 默认加载因子 = 0.75 static final float DEFAULT_LOAD_FACTOR = 0.75f;

  • 扩容阈值（threshold）：当哈希表的大小 ≥ 扩容阈值时，就会扩容哈希表（即扩充HashMap的容量）。

    • 扩容 = 对哈希表进行resize操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数
    • 扩容阈值 = 容量 x 加载因子

获取数据（get）

HashMap的获取数据的过程大致如下：

  • 首先，根据key判断是否为空值；
  • 如果为空，则到hashmap数组的第1个位置，寻找对应key为null的键；
  • 如果不为空，则根据key计算hash值；
  • 根据得到的hash值采用hash & (length - 1)的计算方式得到key在数组中的位置；
  • 结束。

以上就是大致的数据获取流程，接下来，我们再对JDK1.7和1.8获取数据的细节做一个对比。

版本 hash值的计算方式
JDK1.8 1、hash = (key == null) ? 0 : hash(key);
2、扰动处理 = 2次扰动 = 1次位运算+1次异或运算
JDK1.7 1、hash = (key == null) ? 0 : hash(key);
2、扰动处理 = 9次扰动 = 4次位运算+5次异或运算

保存数据（put）

HashMap的保存数据的过程大致如下：

  • 判读HashMap是否初始化，如果没有则进行初始化；
  • 判断key是否为null，如果为null，则将key-value的数据存储在数组的第1个位置，这里与获取数据时对应的；否则，进行后续操作；
  • 根据key计算数据存放的位置；
  • 根据位置判断key是否存在，如果存在，则用新值替换旧值；如果不存在，则直接设置；

这里也对保存数据的过程进行一个更加细致的对比。

版本 hash值的计算方式 存放数据方式 插入数据方式
JDK1.8 1. hash = (key == null) ? 0 : hash(key);
2. 扰动处理 = 2次扰动 = 1次位运算+1次异或运算		 数组+单链表+红黑树
- 无冲突，直接保存数据
- 冲突时，当链表长度小于8时，存放到单链表，当长度大于8时，存到到红黑树		 尾插法
JDK1.7 1、hash = (key == null) ? 0 : hash(key);
2、扰动处理 = 9次扰动 = 4次位运算+5次异或运算		 数组+单链表
- 无冲突，直接保存数据
- 冲突时，存放到单链表		 头插法

扩容机制

HashMap的扩容的过程大致如下：

  • 当发现容量不足时，开始扩容机制；
  • 首先，保存旧数组，再根据旧容量的2倍新建数组；
  • 遍历旧数组的每个元素，采用头插法的方式，将每个元素保存到新数组；
  • 将新数组引用到hashmap的table属性上；
  • 重新设置扩容阀值，完成扩容操作。

最后，也对扩容的过程进行一个更加细致的对比。

版本 扩容后的位置计算方式 数据转移方式
JDK1.8 扩容后的位置 = 原位置 or 原位置+旧容量 尾插法
JDK1.7 扩容后的位置 = hashCode() -> 扰动处理 -> h & (length - 1) 头插法