Java集合必知必会：热门面试题汇编与核心源码（ArrayList、HashMap）剖析

写在前面

🔥我把后端Java面试题做了一个汇总，有兴趣大家可以看看！这里👉

⭐️在无数次的复习巩固中，我逐渐意识到一个问题：面对同样的面试题目，不同的资料来源往往给出了五花八门的解释，这不仅增加了学习的难度，还容易导致概念上的混淆。特别是当这些信息来自不同博主的文章或是视频教程时，它们之间可能存在的差异性使得原本清晰的概念变得模糊不清。更糟糕的是，许多总结性的面试经验谈要么过于繁复难以记忆，要么就是过于简略，对关键知识点一带而过，常常在提及某项技术时，又引出了更多未经解释的相关术语和实例，例如，在讨论ReentrantLock时，经常会提到这是一个可重入锁，并存在公平与非公平两种实现方式，但对于这两种锁机制背后的原理以及使用场景往往语焉不详。

⭐️正是基于这样的困扰与思考，我决定亲自上阵，撰写一份与众不同的面试指南。这份指南不仅仅是对现有资源的简单汇总，更重要的是，它融入了我的个人理解和解读。我力求回归技术书籍本身，以一种层层递进的方式剖析复杂的技术概念，让那些看似枯燥乏味的知识点变得生动起来，并在我的脑海中构建起一套完整的知识体系。我希望通过这种方式，不仅能帮助自己在未来的技术面试中更加从容不迫，也能为同行们提供一份有价值的参考资料，使大家都能在这个过程中有所收获。

Java集合相关面试题

1 Java常见的集合类

面试官：说一说Java提供的常见集合？（画一下集合结构图）

候选人：

在java中提供了量大类的集合框架，主要分为两类：

第一个是Collection 属于单列集合，第二个是Map 属于双列集合

在Collection中有两个子接口List和Set。在我们平常开发的过程中用的比较多像list接口中的实现类ArrarList和LinkedList。在Set接口中有实现类HashSet和TreeSet。
在map接口中有很多的实现类，平时比较常见的是HashMap、TreeMap，还有一个线程安全的ConcurrentHashMap

在这里插入图片描述

面试官：说说List,Set,Map三者的区别？

候选人：

List (对付顺序的好帮⼿)：存储的元素是有序的、可重复的。
Set (注重独⼀⽆⼆的性质): 存储的元素是⽆序的、不可重复的。
Map (⽤ Key 来搜索的专家): 使⽤键值对（kye-value）存储，类似于数学上的函数y=f(x)，“x”代表 key，"y"代表 value，Key 是⽆序的、不可重复的，value 是⽆序的、可重复的，每个键最多映射到⼀个值。

面试官：常见集合的时间复杂度分析

候选人：以下是各种常见数据结构的基本操作时间复杂度的简要概述：

1. 数组（Array）

访问：O(1)，因为可以直接通过索引访问。
插入/删除：平均 O(n)，因为在中间位置插入或删除元素需要移动后续元素。
搜索：O(n)，除非数组有序且使用二分查找，否则需要遍历整个数组。

2. 单向链表（Singly Linked List）

访问：O(n)，因为需要从头节点开始遍历。
插入/删除：O(1)，如果已知前驱节点的话；否则需要 O(n) 来找到前驱节点。
搜索：O(n)，因为需要遍历链表直到找到目标元素。

3. 双向链表（Doubly Linked List）

访问：O(n)，因为也需要从头节点或尾节点开始遍历。
插入/删除：O(1)，如果已知前驱或后继节点的话；否则需要 O(n) 来找到前驱或后继节点。
搜索：O(n)，因为需要遍历链表直到找到目标元素。

4. 二叉搜索树（Binary Search Tree）

最佳情况（平衡）：
- 访问/搜索：O(log n)，如果树是平衡的。
- 插入/删除：O(log n)，如果树是平衡的。
最坏情况（不平衡）：
- 访问/搜索/插入/删除：O(n)，如果树退化成链式结构。

5. 红黑树（Red-Black Tree）

访问/搜索/插入/删除：O(log n)，因为红黑树是一种自平衡的二叉搜索树，能够保持树的高度较低。

6. 散列表（Hash Table）

理想情况（均匀分布）：
- 访问/搜索/插入/删除：平均 O(1)，理想情况下，哈希函数将键均匀分布在哈希表中，减少了冲突。
最坏情况（严重冲突）：
- 访问/搜索/插入/删除：O(n)，如果哈希函数导致大量冲突，性能退化。

2 List

面试官：ArrayList底层是如何实现的？(jdk1.8源码解析)

候选人：

类定义与成员变量

public class ArrayList<E>extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, Serializable {// 内部使用的数组，用于存储元素transient Object[] elementData; // non-private to simplify nested class access// 列表的实际大小private int size;// 初识容量为10private static final int DEFAULT_CAPACITY = 10;// 默认的空数组，用于初始化空的 ArrayListprivate static final Object[] EMPTY_ELEMENTDATA = {};// 空闲数组，用于优化 ArrayList 的行为private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
}

构造函数

// 默认构造函数，初始化为空数组
public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}// 指定初始容量的构造函数
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);}}
// 从 Collection 初始化 ArrayList
public ArrayList(Collection<? extends E> c) {Object[] a = c.toArray();if ((size = a.length) != 0) {if (c.getClass() == ArrayList.class) {elementData = a;} else {elementData = Arrays.copyOf(a, size, Object[].class);}} else {// replace with empty array.elementData = EMPTY_ELEMENTDATA;}}

添加元素

public boolean add(E e) {// 第一步：确保数组已使用长度（size）加1之后足够存下下一个数据ensureCapacityInternal(size + 1);  // Increments modCount!!// 第三步：确保新增的数据有地方存储之后，则将新元素添加到位于size的位置上elementData[size++] = e;// 第四步：返回添加成功布尔值return true;
}private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}private void ensureExplicitCapacity(int minCapacity) {modCount++;// 第二步：计算数组的容量，如果当前数组已使用长度+1后的大于当前的数组长度，则调用grow方法扩容（原来的1.5倍）if (minCapacity - elementData.length > 0)grow(minCapacity);
}private void grow(int minCapacity) {// overflow-conscious codeint 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);
}

获取元素

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

面试官：ArrayList list=new ArrayList(10)中的list扩容几次

候选人：

在ArrayList的源码中提供了一个带参数的构造方法，这个参数就是指定的集合初始长度，所以给了一个10的参数，就是指定了集合的初始长度是10，这里面并没有扩容。

面试官：说⼀说 ArrayList 的扩容机制吧？

候选人： 在添加元素时会检查当前数组的容量是否足够存放新的元素。如果不足够，则会触发扩容操作。扩容机制主要包括以下几个步骤：

检测容量不足：
- 当尝试添加新元素时，ArrayList 会先检查当前的容量是否足以容纳新的元素。
触发扩容：
- 如果当前容量不足，则会调用 ensureCapacityInternal 方法来确保有足够的空间。
计算新容量：
- 通常情况下，新容量为当前容量的 1.5 倍。
执行扩容：
- 使用 Arrays.copyOf 方法来创建一个新的数组，并将旧数组的内容拷贝到新数组中。

源码分析：

public boolean add(E e) {// 确保有足够的容量来存放新的元素ensureCapacityInternal(size + 1);  // Increments modCount!!// 将新元素放置在当前 size 的位置，并将 size 增加 1elementData[size++] = e;// 返回添加成功的标志return true;
}private void ensureCapacityInternal(int minCapacity) {// 如果所需的最小容量大于当前数组的长度，则调用 grow 方法if (minCapacity - elementData.length > 0)grow(minCapacity);
}private void grow(int minCapacity) {// 获取当前数组的长度int oldCapacity = elementData.length;// 计算新的容量，默认情况下是旧容量的 1.5 倍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开始，寻址公式可以简化为：

arr[i] = baseAddress + i * dataTypeSize
地址=基地址+(索引×元素大小)

如果数组的索引从1开始，寻址公式中就会增加一次减法操作，对CPU来说就多了一条指令，性能不高。

如果索引从1开始，则寻址公式变为：

arr[i] = baseAddress + (i - 1) * dataTypeSize
地址=基地址+((索引−1)×元素大小)

面试官：如何实现数组和List之间的转换

候选人：

数组转list，可以使用jdk自动的一个工具类Arrars，里面有一个asList方法可以转换为数组

List 转数组，可以直接调用list中的toArray方法，需要给一个参数，指定数组的类型，需要指定数组的长度。

面试官：用Arrays.asList转List后，如果修改了数组内容，list受影响吗？List用toArray转数组后，如果修改了List内容，数组受影响吗

候选人：

Arrays.asList 转换list之后，如果修改了数组的内容，list会受影响，因为它的底层使用的Arrays类中的一个内部类ArrayList来构造的集合，在这个集合的构造器中，把我们传入的这个集合进行了包装而已，最终指向的都是同一个内存地址。

list用了 toArray 转数组后，如果修改了list内容，数组不会影响，当调用了toArray以后，在底层是它是进行了数组的拷贝，跟原来的元素就没啥关系了，所以即使list修改了以后，数组也不受影响。

面试官：ArrayList 和 LinkedList 的区别是什么？

候选人：

是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
底层数据结构： Arraylist 底层使⽤的是 Object 数组； LinkedList 底层使⽤的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环。注意双向链表和双向循环链表的区别）
插⼊和删除是否受元素位置的影响： ① ArrayList 采⽤数组存储，所以插⼊和删除元素的时间复杂度受元素位置的影响。 ⽐如：执⾏ add(E e) ⽅法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置插⼊和删除元素的话时间复杂度就为 O(n)。②LinkedList 采⽤链表存储，所以对于 add(E e) ⽅法的插⼊，删除元素时间复杂度不受元素位置的影响，近似O(1)，如果是要在指定位置插⼊和删除元素的话（ (add(int index, Eelement) ）时间复杂度近似为o(n)。
是否⽀持快速随机访问： LinkedList 不⽀持⾼效的随机元素访问，⽽ ArrayList ⽀持。（数组天然⽀持随机访问，时间复杂度为 O(1)，所以称为快速随机访问。链表需要遍历到特定位置才能访问特定位置的元素，时间复杂度为 O(n)，所以不⽀持快速随机访问。）
内存空间占⽤： ArrayList 底层是数组，内存连续，节省内存；LinkedList 是双向链表需要存储数据和两个指针，更占用内存。

补充：双向链表和双向循环链表

双向链表： 包含两个指针，⼀个 prev 指向前⼀个节点，⼀个 next 指向后⼀个节点。

双向循环链表： 最后⼀个节点的 next 指向 head，⽽ head 的 prev 指向最后⼀个节点，构成⼀个环。

补充：RandomAccess接⼝
public interface RandomAccess {
}
查看源码我们发现实际上 RandomAccess 接⼝中什么都没有定义。所以，在我看来RandomAccess 接⼝不过是⼀个标识罢了。标识什么？标识实现这个接⼝的类具有随机访问功能。ArrayList 实现了 RandomAccess 接⼝，就表明了他具有快速随机访问功能。 RandomAccess 接⼝只是标识，并不是说 ArrayList实现 RandomAccess 接⼝才具有快速随机访问功能的！

面试官： ArrayList 与 Vector 区别？

候选人：

ArrayList 是 List 的主要实现类，底层使⽤ Object[ ] 存储，适⽤于频繁的查找⼯作，线程不安全；
Vector 是 List 的古⽼实现类，底层使⽤ Object[ ] 存储，线程安全的。

面试官：刚才你说了ArrayList 和 LinkedList 不是线程安全的，你们在项目中是如何解决这个的线程安全问题的？

候选人：

主要有两种解决方案：

第一：我们使用这个集合，优先在方法内使用，定义为局部变量，且不能逃离方法的作用范围。这样的话，就不会出现线程安全问题。

第二：如果非要在成员变量中使用的话，可以使用线程安全的集合来替代

ArrayList可以通过Collections 的 synchronizedList 方法将 ArrayList 转换成线程安全的容器后再使用。
LinkedList 换成ConcurrentLinkedQueue来使用

3 HashMap

前提知识：红黑树和二叉搜索树（Binary Search Tree,BST）

（1）二叉搜索树

二叉搜索树(Binary Search Tree,BST)又名二叉查找树，有序二叉树或者排序二叉树，是二叉树中比较常用的一种类型。

二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

在这里插入图片描述

（2）红黑树

红黑树（Red Black Tree）：也是一种自平衡的二叉搜索树(BST)，之前叫做平衡二叉B树（Symmetric Binary B-Tree）。

在这里插入图片描述

（2）红黑树的特质

性质1：节点要么是红色,要么是黑色

性质2：根节点是黑色

性质3：叶子节点都是黑色的空节点

性质4：红黑树中红色节点的子节点都是黑色

性质5：从任一节点到叶子节点的所有路径都包含相同数目的黑色节点

在添加或删除节点的时候，如果不符合这些性质会发生旋转，以达到所有的性质，保证红黑树的平衡

面试官：说一下HashMap的实现原理？

候选人：

1，底层使用hash表数据结构，即数组 + 链表 / 红黑树。

2，添加数据时，计算key的值确定元素在数组中的下标。

key相同则替换
不同则存入链表或红黑树中

3，获取数据通过key的hash计算数组下标获取元素。

面试官：HashMap的jdk1.7和jdk1.8有什么区别

候选人：

JDK1.8之前采用的拉链法，数组+链表
JDK1.8之后采用数组+链表+红黑树，链表长度大于8且数组长度大于64则会从链表转化为红黑树

补充：什么是拉链法？

所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建⼀个链表数组，数组中每⼀格就是⼀个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

jdk1.8 中将链表改造红黑树还有一个非常重要的原因，可以防止DDos攻击

DDos 攻击：分布式拒绝服务攻击(英文意思是Distributed Denial of Service，简称DDoS）

指处于不同位置的多个攻击者同时向一个或数个目标发动攻击，或者一个攻击者控制了位于不同位置的多台机器并利用这些机器对受害者同时实施攻击。由于攻击的发出点是分布在不同地方的，这类攻击称为分布式拒绝服务攻击，其中的攻击者可以有多个

面试官：说下HashMap的put方法的具体流程

候选人：https://blog.csdn.net/weixin_74199893/article/details/138028976

在这里插入图片描述

首先判断键值对数组table是否为空，如果为空则执行resize()进行扩容（初始化长度为16的数组）
如果不为空则根据key计算hash值，得到数组的索引
判断该索引位置是否为空，如果为空直接插入即可，否则进行后续操作
判断当前索引位置上的key是否与要插入元素的key相同（是否存在），存在相同的话直接覆盖value就可以了
不相同的话判断该位置是否为红黑树，如果是红黑树，则直接在树中插入键值对即可
如果不是的话就要遍历链表，判断该位置的key是否存在，如果存在相同的直接覆盖value即可
如果不相同的话就使用尾插法，并判断链表长度是否大于8，大于8的话把链表转换为红黑树，走红黑树插入的逻辑
最后一步，就是在以上所有涉及到插入的操作中，判断实际存在的键值对数量size（也就是++size）是否超出了最大容量threshold，如果超过，就进行扩容。

添加元素的时候至少考虑三种情况：

数组位置为null
数组位置不为null，键重复，元素覆盖
数组位置不为null，键不重复，挂在下面形成链表或者红黑树

源码分析：

public V put(K key, V value) {//参数一：键//参数二：值//返回值：被覆盖元素的值，如果没有覆盖，返回nullreturn putVal(hash(key), key, value, false, true);
}//利用键计算出对应的哈希值，再把哈希值进行一些额外的处理
//简单理解：返回值就是返回键的哈希值
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {//定义一个局部变量，用来记录哈希表中数组的地址值。Node<K, V>[] tab;//临时的第三方变量，用来记录键值对对象的地址值Node<K, V> p;//表示当前数组的长度int n;//表示索引int i;//把哈希表中数组的地址值，赋值给局部变量tabtab = table;//判断数组是否未初始化if (tab == null || (n = tab.length) == 0) {//1.如果当前是第一次添加数据，底层会创建一个默认长度为16，加载因子为0.75的数组//2.如果不是第一次添加数据，会看数组中的元素是否达到了扩容的条件//如果没有达到扩容条件，底层不会做任何操作//如果达到了扩容条件，底层会把数组扩容为原先的两倍，并把数据全部转移到新的哈希表中tab = resize();//表示把当前数组的长度赋值给nn = tab.length;}//拿着数组的长度跟键的哈希值进行计算，计算出当前键值对对象，在数组中应存入的位置i = (n - 1) & hash;   //index//获取数组中对应元素的数据p = tab[i];//判断该下标位置是否有数据if (p == null) {//如果没有，直接将数据放在该下标位置tab[i] = newNode(hash, key, value, null);} else {Node<K, V> e;K k;//等号的左边：数组中键值对的哈希值//等号的右边：当前要添加键值对的哈希值//如果键不一样，此时返回false//如果键一样，返回trueboolean b1 = p.hash == hash;//判断该位置数据的key和新来的数据是否一样if (b1 && ((k = p.key) == key || (key != null && key.equals(k)))) {//如果一样，证明为修改操作，该节点的数据赋值给e,后边会用到e = p;} else if (p instanceof TreeNode) {//判断数组中获取出来的键值对是不是红黑树中的节点//如果是，则调用方法putTreeVal，把当前的节点按照红黑树的规则添加到树当中。e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);} else {//如果从数组中获取出来的键值对不是红黑树中的节点//表示此时下面挂的是链表for (int binCount = 0; ; ++binCount) {//判断next节点，如果为空的话，证明遍历到链表尾部了if ((e = p.next) == null) {//把新值放入链表尾部p.next = newNode(hash, key, value, null);//判断当前链表长度是否超过8，如果超过8，就会调用方法treeifyBin//treeifyBin方法的底层还会继续判断:判断数组的长度是否大于等于64//如果同时满足这两个条件，就会把这个链表转成红黑树if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st//如果是，进行转换红黑树操作treeifyBin(tab, hash);break;}//判断链表当中有数据相同的值，如果一样，证明为覆盖操作if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;//把下一个节点赋值为当前节点p = e;}}//判断e是否为空（e值为修改操作存放原数据的变量）if (e != null) {//不为空的话证明是修改操作，取出旧值V oldValue = e.value;//一定会执行  onlyIfAbsent传进来的是falseif (!onlyIfAbsent || oldValue == null) {//将新值赋值当前节点e.value = value;}afterNodeAccess(e);//返回老值return oldValue;}}//计数器，计算当前节点的修改次数++modCount;//threshold：记录的就是数组的长度 * 0.75，哈希表的扩容时机  16 * 0.75 = 12if (++size > threshold)//进行扩容操作resize();//空方法afterNodeInsertion(evict);//表示当前没有覆盖任何元素，返回nullreturn null;
}

面试官：讲一讲HashMap的扩容机制

候选人：https://blog.csdn.net/weixin_74199893/article/details/138028976

请添加图片描述

在添加元素或初始化的时候需要调用resize方法进行扩容，第一次添加数据初始化数组长度为16，以后每次扩容都是达到了扩容阈值（数组长度 * 0.75）

扩容阈值 = 数组容量 * 加载因子

每次扩容的时候，都是扩容之前容量的2倍；
扩容之后，会新创建一个数组，需要把老数组中的数据挪动到新的数组中
没有hash冲突的节点，则直接使用 e.hash & (newCap - 1) 计算新数组的索引位置
有冲突节点的话，如果是红黑树，就走红黑树的添加
如果是链表，则需要遍历链表，可能需要拆分链表，判断(e.hash & oldCap)是否为0，该元素的位置要么停留在原始位置，要么移动到原始位置+增加的数组大小这个位置上

源码分析：

//扩容、初始化数组
final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;//如果当前数组为null的时候，把oldCap老数组容量设置为0int oldCap = (oldTab == null) ? 0 : oldTab.length;//老的扩容阈值int oldThr = threshold;int newCap, newThr = 0;//判断数组容量是否大于0，大于0说明数组已经初始化if (oldCap > 0) {//判断当前数组长度是否大于最大数组长度if (oldCap >= MAXIMUM_CAPACITY) {//如果是，将扩容阈值直接设置为int类型的最大数值并直接返回threshold = Integer.MAX_VALUE;return oldTab;}//如果在最大长度范围内，则需要扩容  OldCap << 1等价于oldCap*2//运算过后判断是不是最大值并且oldCap需要大于16else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold  等价于oldThr*2}//如果oldCap<0，但是已经初始化了，像把元素删除完之后的情况，那么它的临界值肯定还存在，       			如果是首次初始化，它的临界值则为0else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;//数组未初始化的情况，将阈值和扩容因子都设置为默认值else {               // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}//初始化容量小于16的时候，扩容阈值是没有赋值的if (newThr == 0) {//创建阈值float ft = (float)newCap * loadFactor;//判断新容量和新阈值是否大于最大容量newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}//计算出来的阈值赋值threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})//根据上边计算得出的容量 创建新的数组       Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//赋值table = newTab;//扩容操作，判断不为空证明不是初始化数组if (oldTab != null) {//遍历数组for (int j = 0; j < oldCap; ++j) {Node<K,V> e;//判断当前下标为j的数组如果不为空的话赋值个e，进行下一步操作if ((e = oldTab[j]) != null) {//将数组位置置空oldTab[j] = null;//判断是否有下个节点if (e.next == null)//如果没有，就重新计算在新数组中的下标并放进去newTab[e.hash & (newCap - 1)] = e;//有下个节点的情况，并且判断是否已经树化else if (e instanceof TreeNode)//进行红黑树的操作((TreeNode<K,V>)e).split(this, newTab, j, oldCap);//有下个节点的情况，并且没有树化（链表形式）else {//比如老数组容量是16，那下标就为0-15//扩容操作*2，容量就变为32，下标为0-31//低位：0-15，高位16-31//定义了四个变量//        低位头          低位尾Node<K,V> loHead = null, loTail = null;//        高位头		   高位尾Node<K,V> hiHead = null, hiTail = null;//下个节点Node<K,V> next;//循环遍历do {//取出next节点next = e.next;//通过 与操作 计算得出结果为0if ((e.hash & oldCap) == 0) {//如果低位尾为null，证明当前数组位置为空，没有任何数据if (loTail == null)//将e值放入低位头loHead = e;//低位尾不为null，证明已经有数据了else//将数据放入next节点loTail.next = e;//记录低位尾数据loTail = e;}//通过 与操作 计算得出结果不为0else {//如果高位尾为null，证明当前数组位置为空，没有任何数据if (hiTail == null)//将e值放入高位头hiHead = e;//高位尾不为null，证明已经有数据了else//将数据放入next节点hiTail.next = e;//记录高位尾数据hiTail = e;}} //如果e不为空，证明没有到链表尾部，继续执行循环while ((e = next) != null);//低位尾如果记录的有数据，是链表if (loTail != null) {//将下一个元素置空loTail.next = null;//将低位头放入新数组的原下标位置newTab[j] = loHead;}//高位尾如果记录的有数据，是链表if (hiTail != null) {//将下一个元素置空hiTail.next = null;//将高位头放入新数组的(原下标+原数组容量)位置newTab[j + oldCap] = hiHead;}}}}}//返回新的数组对象return newTab;}

面试官：了解hashMap的寻址算法吗？为何HashMap的数组长度一定是2的次幂？

候选人：JDK 1.8 的 hash ⽅法

 static final int hash(Object key) {int h;// key.hashCode()：返回散列值也就是hashcode// ^ ：按位异或// >>>:⽆符号右移，忽略符号位，空位都以0补⻬return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

二次哈希：首先计算出key的hashCode值，然后通过这个hash值右移16位后的二进制进行按位异或运算得到最后的hash值。

在putValue的方法中，计算数组下标的时候使用hash值与数组长度取模得到存储数据下标的位置，hashmap为了性能更好，并没有直接采用取模的方式，而是使用了数组长度-1 得到一个值，用这个值按位与运算hash值，最终得到数组的位置。（也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次⽅），并且采⽤⼆进制位操作 &，相对于 % 能够提⾼运算效率，这就解释了HashMap 的⻓度为什么是2的幂次⽅。

面试官：知道hashmap在1.7情况下的多线程死循环问题吗？

候选人：

Java 1.7 中的死循环问题

在Java 1.7中，HashMap采用的是“头插法”进行扩容。这意味着在扩容时，旧数组中的元素会根据新的索引位置被插入到新数组对应的链表头部。当两个或更多的线程几乎同时进行扩容操作时，可能会导致如下情形：

线程一读取并开始扩容：假设线程一开始读取HashMap并准备进行扩容。此时，它读取到了某个链表，该链表包含节点A和节点B（顺序为A -> B）。
线程二介入并完成扩容：在线程一还没有完成扩容之前，线程二也开始了扩容操作。线程二按照头插法将节点A和节点B重新插入新数组中的对应位置，但是顺序变成了B -> A（因为A先插入，然后B插入到A的前面）。
线程一继续执行：当线程一恢复执行时，它尝试将节点A插入新数组中的对应位置。按照头插法，它会将A插入到链表的头部。然而，此时节点B已经在链表的头部，并且B的next已经指向了A。因此，当线程一将A插入时，A的next又指向了B，这就形成了一个循环链表（A -> B -> A）。

解决方法：Java 1.8 的尾插法

Java 1.8中的HashMap采用了“尾插法”，而不是头插法来进行扩容。这意味着在扩容时，元素会插入到链表的末尾，而不是头部。这样做的好处在于，即使多个线程几乎同时进行扩容，也不会改变链表原有的顺序，从而避免了循环链表的产生。

面试官：好的，hashmap是线程安全的吗？

候选人：不是线程安全的

面试官：那我们想要使用线程安全的map该怎么做呢？

候选人：我们可以采用ConcurrentHashMap进行使用，它是一个线程安全的HashMap

面试官：那你能聊一下ConcurrentHashMap的原理吗？

《Java并发编程的艺术》 6.1.1 为什么要使用 ConcurrentHashMap?

在并发编程中使用 HashMap 可能导致程序死循环。而使用线程安全的 HashTable 效率又非常低下，基于以上两个原因，便有了ConcurrentHashMap 的登场机会。

（1）线程不安全的HashMap

在多线程环境下，使用 HashMap 进行 put 操作会引起死循环，导致 CPU 利用率接近100%，所以在并发情况下不能使用 HashMap。HashMap 在并发执行 put 操作时会引起死循环，是因为多线程会导致 HashMap 的 Entry 链表形成环形数据结构，一旦形成环形数据结构，Entry的next节点永远不为空，就会产生死循环获取 Entry。

（2）效率低下的HashTable（一锁就锁全表）

HashTable 容器使用synchronized来保证线程安全，但在线程竞争激烈的情况下HashTable 的效率非常低下。因为当一个线程访问HashTable 的同步方法，其他线程也访问HashTable 的同步方法时，会进入阻塞或轮询状态。如线程1使用 put 进行元素添加，线程2 不但不能使用 put 方法添加元素，也不能使用 get 方法来获取元素，所以竞争越激烈效率越低。

（3）ConcurrentHashMap 的锁分段技术可有效提升并发访问率

HashTable 容器在竞争激烈的并发环境下表现出效率低下的原因是所有访问 HashTable的线程都必须竞争同一把锁，假如容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效提高并发访问效率，这就是ConcurrentHashMap 所使用的锁分段技术。

候选人：ConcurrentHashMap 是一种线程安全的高效Map集合，jdk1.7和1.8也做了很多调整。

JDK1.7的底层采用是分段的数组+链表实现
JDK1.8 采用的数据结构跟HashMap1.8的结构一样，数组+链表/红黑二叉树。

在jdk1.7中ConcurrentHashMap 是由Segment 数组结构和HashEntry数组结构组成。Segment 是一种可重入锁(ReentrantLock)，扮演锁的⻆⾊。HashEntry 则用于存储键值对数据。一个 ConcurrentHashMap 里包含一个Segment数组。Segment 的结构和 HashMap 类似，是一种数组和链表结构。一个Segment 里包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个 HashEntry 数组，当对 HashEntry 数组的数据进行修改时，必须首先获得与它对应的Segment锁。

在这里插入图片描述

在jdk1.8中ConcurrentHashMap 取消了 Segment 分段锁，采⽤ CAS 和 synchronized 来保证并发安全。数据结构跟 HashMap的结构类似，数组+链表/红⿊树。Java 8 在链表⻓度超过⼀定阈值8时将链表（寻址时间复杂度为O(N)）转换为红⿊树（寻址时间复杂度为 O(log(N))）。synchronized 只锁定当前链表或红⿊树的⾸节点，这样只要 hash 不冲突，就不会产⽣并发，效率⼜提升 N 倍。

在这里插入图片描述

面试官：HashSet与HashMap的区别？

候选人：HashSet 底层就是基于 HashMap 实现的。

在这里插入图片描述

面试官：HashTable与HashMap的区别

候选人：

区别	HashTable	HashMap
数据结构	数组+链表	数组+链表+红黑树
是否可以为null	Key和value都不能为null	可以为null
hash算法	key的hashCode()	二次hash
扩容方式	当前容量翻倍 +1	当前容量翻倍
线程安全	同步(synchronized)的，线程安全	非线程安全