精选 8 道 Java 集合最常见面试题，进大厂 99% 都会被问到，限时送！

Hello，今天给各位童鞋们分享 java 常见的面试题，想在面试、工作中脱颖而出？想在最短的时间内快速掌握 Java 的核心基础知识点？那赶紧拿出小本本记下来吧！

1. List，Set，Map 三者的区别？

List：一个有序（元素存入集合的顺序和取出的顺序一致）容器，元素可以重复，可以插入多个 null 元素，元素都有索引。常用的实现类有 ArrayList、LinkedList 和 Vector

Set：一个无序（存入和取出顺序有可能不一致）容器，不可以存储重复元素，只允许存入一个 null 元素，必须保证元素唯一性。Set 接口常用实现类是 HashSet、LinkedHashSet 以及 TreeSet

Map 是一个键值对集合，存储键、值和之间的映射。 Key 无序，唯一；value 不要求有序，允许重复。Map 的常用实现类：HashMap、TreeMap、HashTable、LinkedHashMap、ConcurrentHashMap

2. 集合框架底层的数据结构

List 集合

Arraylist 和 Vector 使用的是 Object 数组， LinkedList 使用双向循环链表

Set 集合

HashSet（无序，唯一）：基于 HashMap 实现的，HashSet 的值作为 key，value 是 Object 类型的常量

LinkedHashSet 继承 HashSet，并且通过 LinkedHashMap 来实现的

TreeSet（有序，唯一）： 红黑树(自平衡的排序二叉树。)

Map 集合

HashMap 由数组+链表+红黑树组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的，当链表长度大于阈值（默认为 8）并且数组长度大于 64 时，将链表转化为红黑树

LinkedHashMap（有序） 继承自 HashMap，底层仍然是数组+链表+红黑树组成。另外，LinkedHashMap 在此基础上，节点之间增加了一条双向链表，使得可以保持键值对的插入顺序

HashTable 无序，数组+链表组成的，数组是 HashTable 的主体，链表则是主要为了解决哈希冲突而存在的

TreeMap 有序，红黑树

3. 集合框架的扩容

ArrayList 和 Vector 默认初始容量为 10，当元素个数超过容量长度时都进行进行扩容，ArrayList 扩容为原来的 1.5 倍，而 Vector 扩容为原来的 2 倍

HashSet 和 HashMap 默认初始容量为 16，加载因子为 0.75：即当元素个数超过容量长度的 0.75 倍时，进行扩容，扩容为原来的 2 倍。HashSet 基于 HashMap 实现的，因此两者相同

HashTable：默认初始容量为 11，加载因子为 0.75，扩容策略是 2 倍+1，如 初始的容量为 11，一次扩容后是容量为 23

4. HashMap 的实现原理以及 JDK1.7 和 JDK1.8 的区别？

实现原理

数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。我们综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构哈希表。并且使用最常用的一种方法—— 拉链法来实现哈希表。

数组存储的元素是一个 Entry 类，这个类有三个数据域，key、value（键值对），next(指向下一个 Entry)。当两个 key 经过计算得到的 index（索引）相同时，即产生哈希冲突时，用链地址法来解决哈希冲突，即通过 next 属性将索引值相同的链接在一起。随着 map 的容量或者链表长度越来越大，在进行进一步的优化，比如使用红黑树。

存储过程

HashMap 个 put()方法：

第一步首先将 k,v 封装成 Node 节点。第二步调用 hashCode()方法得出 hash 值并将 hash 值转换成数组的下标，下标位置上如果没有任何元素（没有碰撞），就把 Node 节点添加到这个位置上。如果说下标对应的位置上有值（hash 碰撞）。碰撞的元素与要插入的元素 key 值相等，直接进行 value 的更新；如果 key 值不相同，于是增长链表或者树节点的增加。插入之后判断是否进行扩容。

HashMap 个 get()方法：

先调用 k 的 hashCode()方法得出哈希值，并转换成数组的下标。第二步：通过数组下标快速定位到某个位置上。如果该位置上什么都没有，则返回 null。如果这个位置上有数据，那么它就会拿着参数 k 和单向链表上(红黑树)的每一个节点的 k 进行 equals，如果所有 equals 方法都返回 false，则 get 方法返回 null。如果其中一个节点的 k 和参数 k 进行 equals 返回 true，那么返回该节点的 value。

区别

JDK1.7 是数组+链表，无冲突时，存放数组；冲突时，存放链表；采用头插法。

JDK1.8 是数组 + 链表 + 红黑树，无冲突时，存放数组；有冲突存放链表或者红黑树，当链表长度大于阈值（默认为 8）并且数组长度大于 64 时，将链表转化为红黑树；树元素小于等于 6 时，树结构还原成链表形式。

5. HashMap 是怎么解决哈希冲突的？

使用链地址法（链表）来链接拥有相同 hash 值的数据；

使用 2 次扰动函数（hash 函数）来降低哈希冲突的概率，使得数据分布更平均；

引入红黑树进一步降低遍历的时间复杂度，使得遍历更快；

扰动函数的解释：

如果只使用 hashCode 取余，那么相当于参与运算的只有 hashCode 的低位，高位是没有起到任何作用的，所以我们的思路就是让 hashCode 的高位（与自己右移 16 位进行异或）也参与运算，来获取 hash 值，进一步降低 hash 碰撞的概率，使得数据分布更平均，我们把这样的操作称为扰动。

6. 为什么默认长度和扩容后的长度都必须是 2 的幂

获取数组索引的计算方式为 key 的 hash 值与数组长度减一按位与，当长度为 2 的幂时减一的值的二进制位数一定全为 1，这样数组下标 index 的值完全取决于 key 的 hash 值的后几位，只要 key 的 hash 值分布均匀，HashMap 中 Node 也就尽可能是均匀的，所以当长度为 2 的幂时不同的 hash 值发生碰撞的概率比较小。

7. HashMap 的数据的迁移机制

由于数组的容量是以 2 的幂次方扩容的，新的位置要么在原位置，要么在原长度+原位置的位置。因为数组长度变为原来的 2 倍，表现为 key 的 hash 值在二进制上就是多了一个高位参与数组下标确定。此时，一个元素通过 hash 转换坐标的方法计算后，恰好出现一个现象：最高位是 0 则坐标不变，最高位是 1 则坐标变为“原长度+原坐标”。 因此，我们在扩充 HashMap 的时候，不需要像 JDK1.7 的实现那样重新计算 hash，只需要看看原来的 hash 值新增的那个 bit 是 1 还是 0 就好。

例如：HashMap 扩容之前为 16，那么 length-1 的二进制为 01111，同理扩容后的数组长度为 32，length-1 二进制表示为 011111。我们可以看出扩容后只有一位差异，也就是多出了最左位的 1，这样在通过 h&(length-1)的时候，只要 h 对应的最左边的那一个差异位为 0，那么就是在原先位置；差异位为 1，就在原长度+原位置

8. ConcurrentHashMap 底层具体实现

在 JDK1.7 中，ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。Segment 继承了 ReentrantLock，是一种可重入锁。HashEntry 则用于存储键值对数据。一个 ConcurrentHashMap 里包含一个 Segment 数组，一个 Segment 里包含一个 HashEntry 数组 ，每个 HashEntry 是一个链表结构的元素，因此 JDK1.7 的 ConcurrentHashMap 是一种数组+链表结构。当对 HashEntry 数组的数据进行修改时，必须首先获得与它对应的 Segment 锁，这样只要保证每个 Segment 是线程安全的，也就实现了全局的线程安全

在 JDK1.8 中采用 Node + CAS + Synchronized 来保证并发安全进行实现，synchronized 只锁定当前链表或红黑二叉树的首节点。如果相应位置的 Node 还没有初始化，则调用 CAS 插入相应的数据；如果相应位置的 Node 不为空，如果该节点的 first.hash!=-1，则对该节点加 synchronized 锁，更新节点或插入新节点； 如果该节点的 first.hash=-1，则扩容。读操作无锁，Node 节点的 val 和 next 使用 volatile 修饰，数组也用 volatile 修饰。

好啦，今天的文章就到这里，希望能帮助到屏幕前的你们！