Java集合面试题看这篇就够了

1.说说Java中常用的容器有哪些？

容器主要包括 Collection和 Map两种，Collection 存储着对象的集合，而 Map 存储着键值对(两个对象)的映射表。

如图：

‍面试官追问：说说集合有哪些类及他们各自的区别和特点？

• Set

  TreeSetHashSetLinkedHashSet

• List

  ArrayListVectorLinkedList

• Queue

  LinkedListPriorityQueueArrayQueue

‍面试官追问：说说Map有哪些类及他们各自的区别和特点？

TreeMapHashMapHashTableLinkedHashMap

2.详细说说 Arraylist 和 LinkedList的区别” /> iterator = list.iterator();while (iterator.hasNext()) { System.out.println(iterator.next());}//foreach遍历for (String s : list) { System.out.println(s);}}}

‍面试官追问：那么对于以上三种遍历方式应该如何选取呢？

在Java集合框架中，提供了一个 RandomAccess接口，该接口没有方法，只是一个标记。通常用来标记List的实现是否支持RandomAccess。所以在遍历时，可以先判断是否支持RandomAccess ( list instanceof RandomAccess)，如果支持可用for循环遍历，否则建议用Iterator或 foreach遍历。

8.comparable和comparator的区别？

• comparable接口出自 java.lang包，可以理解为一个内比较器，因为实现了comparable接口的类可以和自己比较，要和其他实现了Comparable接口类比较，可以使用 compareTo(objectobj)方法。compareTo方法的返回值是int，有三种情况：
  1. 返回正整数（比较者大于被比较者）
  2. 返回0（比较者等于被比较者）
  3. 返回负整数（比较者小于被比较者）
• comparator接口出自 java.util包，它有一个 compare(object obj1，object obj2)方法用来排序，返回值同样是int，有三种情况，和compareTo类似。

它们之间的区别：

1. 很多包装类都实现了comparable接口，像Integer、string等。所以直接调用 co1lections.sort()直接可以使用。如果对类里面自带的自然排序不满意，而又不能修改其源代码的情况下，使用 comparator就比较合适。
2. 此外使用 comparator可以避免添加额外的代码与我们的目标类耦合，同时可以定义多种排序规则，这一点是comparable接口没法做到的
3. 从灵活性和扩展性讲 Comparator更优，故在面对自定义排序的需求时，可以优先考虑使用comparator接口。

9.Collection和Collections有什么区别？

• Collection：是最基本的 集合接口，它提供了对集合对象进行基本操作的通用接口方法。一个Collection代表一组Object，即Collection的元素。它的直接继承接口有List，Set 和Queue。
• Collections：是不属于Java的集合框架的，它是 集合类的一个工具类。 此类不能被实例化， 服务于Java的Collection框架。它包含有关集合操作的静态多态方法，实现对各种集合的搜索、排序、线程安全等操作。

10.说一下PriorityQueue？

PriorityQueue是在 JDK1.5 中被引入的, 其与 Queue的区别在于元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队。

它有这些特点：

• PriorityQueue利用了 二叉堆的数据结构来实现的，底层使用 可变长的数组来存储数据。
• PriorityQueue通过堆元素的上浮和下沉，实现了在 O(logn)的时间复杂度内插入元素和删除堆顶元素。
• PriorityQueue是 非线程安全的，且不支持存储 NULL和 non-comparable的对象。
• PriorityQueue默认是小顶堆，但可以接收一个 Comparator作为构造参数，从而来自定义元素优先级的先后。
• 默认容量是 11。当数组比较小（ 小于64）的时候每次 扩容容量翻倍。当数组比较大（ 大于等于64）的时候每次扩容只 增加一半的容量。
• PriorityQueue不是有序的，只有堆顶存储着最小的元素

可以参考PriorityQueue源码：https://blog.csdn.net/qq_45966440/article/details/122273598?spm=1001.2014.3001.5501

11.说一下HashSet的实现原理？

HashSet的实现是依赖于 HashMap的，HashSet 的值都是存储在HashMap中的。在 HashSet 的构造法中会初始化一个HashMap对象，HashSet 不允许值重复。因此，HashSet的值是作为HashMap的key存储在HashMap 中的，当存储的值已经存在时返回false。

‍面试官追问：HashSet有哪些特点？

• 无序性（存储元素无序）
• 唯一性（允许使用 null）本质上，HashSet的值是作为HashMap的key存储在HashMap 中的，因此保证唯一性
• HashSet没有提供 get()方法，同HashMap一样，因为Set内部是 无序的，所以只能通过 迭代的方式获得

12.HashMap的实现原理/底层数据结构？

• JDK1.7：数组 + 链表
• JDK1.8：数组 + （链表 | 红黑树）

HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n – 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。

JDK1.8的hash方法：

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

JDK1.7的hash方法：

static int hash(int h) { h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);}

从源码可以看出JDK 1.8 的 hash 方法 相比于 JDK 1.7 hash 方法更加简化，但是原理不变。JDK 1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动了 4 次。

13.HashMap 的长度为什么是 2 的幂次方？

1. 计算索引时效率更高： hash % tab.length，而计算机中直接求余运算效率不如位移运算。所以源码中做了优化，使用 hash & (tab.length- 1)来寻找桶位。而实际上 hash % length等于 hash & ( length - 1)的 前提是 length 必须为 2 的 n 次幂
2. 扩容时重新计算索引效率更高： hash & oldCap == 0的元素留在原来位置 ，否则 新位置 = 旧位置 + oldCap
3. 当根据 key 的 hash 值寻址计算确定桶位下标 index 时，如果HashMap 的数组长度 tab.length 是 2 的 n 次幂数，那么就 可以保证新插入数组中的数据均匀分布，每个桶位都有可能分配到数据，而如果数组长度不是 2 的 n 次幂数，那么就可能导致一些桶位上永远不会被插入到数据，反而有些桶位频繁发生 hash 冲突，导致数组空间浪费，冲hash 突概率增加。

14.说说HashMap的put方法执行流程？

1. 计算key的hash值
2. 如果桶（数组）数量为0，则初始化桶
3. 如果key所在的桶没有元素，则直接插入
4. 如果key所在的桶中的第一个元素的key与待插入的key相同，说明找到了元素，转后续流程（9）处理
5. 如果第一个元素是树节点，则调用树节点的putTreeVal()寻找元素或插入树节点
6. 如果不是以上三种情况，则遍历桶对应的链表查找key是否存在于链表中
7. 如果找到了对应key的元素，则转后续流程（9）处理
8. 如果没找到对应key的元素，则在链表最后插入一个新节点并判断是否需要树化
9. 如果找到了对应key的元素，则判断是否需要替换旧值，并直接返回旧值
10. 如果插入了元素，则数量加1并判断是否需要扩容

详细的HashMap方法执行过程可以参考： 【JDK源码】HashMap源码分析（附常见面试题）

15.说说HashMap的get方法执行流程？

1. 计算key的hash值
2. 找到key所在的桶及其第一个元素
3. 如果第一个元素的key等于待查找的key，直接返回
4. 如果第一个元素是树节点就按树的方式来查找
5. 否则就按链表方式查找
6. 如果都没有，返回null

16.说说HashMap的resize方法执行过程？

1. 如果使用是默认构造方法，则第一次插入元素时初始化为默认值，容量为 16，扩容门槛为12
2. 如果使用的是非默认构造方法，则第一次插入元素时初始化容量等于扩容门槛，扩容门槛在构造方法里等于传入容量向上最近的2的n次方
3. 如果旧容量大于0，则新容量等于旧容量的2倍，但不超过最大容量2的30次方，新扩容门槛为旧扩容门槛的2倍
4. 创建一个新容量的桶
5. 搬移元素，原链表分化成两个链表，低位链表存储在原来桶的位置，高位链表搬移到原来桶的位置加旧容量的位置

关于这部分建议详细看看源码： 【JDK源码】HashMap源码分析（附常见面试题）

17.HashMap什么时候会树化？

必须满足两个条件：

>8>=64

当链表长度超过树化阈值 8 时，先尝试扩容来减少链表长度，如果数组容量已经 >=64，才会进行树化。

‍面试官追问：那什么时候树化退化？

<= 6

18.HashMap底层为什么选择红黑树而不用其他树，比如二叉查找树？

二叉查找树在特殊情况下也会变成一条线性结构，和原先的长链表存在一样的深度遍历问题，查找性能慢，如图：

使用红黑树主要是为了提升查找数据的速度，红黑树是平衡二叉树的一种，插入新数据（新数据初始是红色结点插入）后会 通过左旋，右旋，变色等操作来保持平衡，解决单链表查询深度的问题。

‍面试官追问：那为什么要将链表中转红黑树的阈值设为8？

之所以以 8为树化门槛，是因为经过大量测试，8 这个值是最合适的。理想情况下，使用随机的哈希码，节点分布在 hash 桶中的频率 遵循泊松分布，按照泊松分布的公式计算，长度超过 8 的链表出现概率是 0.00000006。树化阈值选择 8 就是为了让树化几率足够小

‍面试官继续追问：那为什么不一开始直接使用红黑树？

• 当链表数据量少的时候，遍历线性链表比遍历红黑树消耗的资源少 (因为少量数据，红黑树本身自选、变色保持平衡也是需要消耗资源的)，所以前期使用线性表。
• 然后TreeNode 占用空间也比普通 Node 的大，如非必要，尽量还是使用链表

19.HashMap扩容（加载）因子为何默认是 0.75f？

1. 在空间占用与查询时间之间取得较好的权衡
2. 大于这个值，空间节省了，但链表就会比较长影响性能
3. 小于这个值，冲突减少了，但扩容就会更频繁，空间占用也更多

20.HashMap怎么计算 key 的 hash 值的？

我们先看源码：

static final int hash(Object key) {int h;//key==null直接返回0//1、否则调用key的hashCode()方法计算出key的哈希值然后赋值给h,//2、h >>> 16。后与h无符号右移16位后的二进制进行按位异或得到最后的hash值,//3、这样做是为了使计算出的hash更分散，让高16位可以参与（低16位具有高16位的特征）return (key == null) " />
 
由上图，可以知道如果只使用 key.hashCode()方法计算得到的 hash 值，那么当 hash 值高位变化较大，而低位变化较小时，通过寻址算法 hash & (tab.length - 1) 得到的桶位下标 index 就更容易出现 hash 冲突了！
 
21.HashMap是怎么解决哈希冲突的？
 
哈希冲突：hashMap在存储元素时会先计算key的hash值来确定存储位置，因为key的hash值计算最后有个对数组长度取余的操作，所以即使不同的key也可能计算出相同的hash值，这样就引起了hash冲突。hashMap的底层结构中的链表/红黑树就是用来解决这个问题的。
 
HashMap中的哈希冲突解决方式可以主要从三方面考虑（以JDK1.8为背景)
 
拉链法
 HasMap中的数据结构为数组+链表/红黑树，当不同的key计算出的hash值相同时，就用链表的形式将Node结点（冲突的key及key对应的value)挂在数组后面。
hash函数
 key的hash值经过两次扰动， key的hashcode值与key的hashcode值的右移16位进行异或，然后对数组的长度取余（实际为了提高性能用的是位运算，但目的和取余一样)，这样做可以让hashcode取值出的高位也参与运算，进一步降低hash冲突的概率，使得数据分布更平均。
红黑树
 在拉链法中，如果hash冲突特别严重，则会导致数组上挂的链表长度过长，性能变差，因此在链表长度大于8时，将链表转化为红黑树，可以提高遍历链表的速度。
 
22.HashMap多线程操作导致死循环问题知道吗" />hashmap扩容时死循环问题
 
23.说说LinkedHashMap 的实现原理？
 
HashMapaccessOrder
24.说说HashMap 和 HashSet 区别？
HashSet底层就是基于 HashMap实现的。两者主要区别：
HashMap
HashSet
实现了 Map接口
实现了 set接口
存储键值对
存储对象
key 唯一，value不唯一
存储对象唯一
HashMap使用键(Key )计算Hashcode
HashSet 使用成员对象来计算 hashcode 值，对于两个对象来说 hashcode 可能相同，所以equals()方法用来判断对象的相等性
速度相对较快
速度相对较慢
25.说下HashMap 和 Hashtable 的区别？
线程是否安全： HashMap是非线程安全的， Hashtable是线程安全的,因为 Hashtable 内部的方法基本都经过 synchronized修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap吧！）
**效率：**因为Hashtable加了 synchronized锁。所以HashMap 要比 Hashtable 效率高一点。另外，Hashtable 基本被淘汰，不要在代码中使用它
对 Null key 和 Null value 的支持： HashMap可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个； Hashtable不允许有 null 键和 null 值，否则会抛出 NullPointerException。
初始容量大小和每次扩充容量大小的不同 ：
① 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2倍。
② 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap会将其扩充为 2 的幂次方大小。也就是说 HashMap总是使用 2 的幂作为哈希表的大小。
底层数据结构：JDK1.8 以后的 HashMap在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。
26.说一下HashMap 和 TreeMap 区别？
TreeMap和 HashMap都继承自 AbstractMap，但是需要注意的是 TreeMap它还实现了 NavigableMap接口和 SortedMap接口。
实现 NavigableMap接口让 TreeMap有了对集合内元素的搜索的能力。
实现 SortedMap接口让 TreeMap有了对集合中的元素根据键排序的能力。默认是按 key 的升序排序，不过我们也可以指定排序的比较器。
示例代码如下：
/** * @author xppll * @date 2022/1/1 21:35 */public class Person { private Integer age;public Person(Integer age) { this.age = age;}public Integer getAge() { return age;}public static void main(String[] args) { TreeMap treeMap = new TreeMap((o1, o2) -> { return Integer.compare(o1.getAge() - o2.getAge(), 0);});treeMap.put(new Person(2), "person1");treeMap.put(new Person(42), "person2");treeMap.put(new Person(22), "person3");treeMap.put(new Person(10), "person4");treeMap.forEach((key, value) -> System.out.println(value));}}//输出：person1person4person3person2
可以看出， TreeMap中的元素已经是按照 Person的 age 字段的升序来排列了。
综上，相比于 HashMap来说 TreeMap主要多了对集合中的元素根据键排序的能力以及对集合内元素的搜索的能力
27.为什么HashMap中String、Integer这样的包装类适合作为Key?
这些包装类都是 final修饰，是不可变性的，保证了key的不可更改性，不会出现放入和获取时哈希值不同的情况。
它们内部已经重写过 hashcode()， equal()等方法。
‍面试官追问：如果使用Object作为HashMap的Key，应该怎么办呢？
重写 hashcode()方法， 因为需要计算hash值确定存储位置
重写 equals()方法， 因为需要保证key的唯一性
‍面试官继续追问：能否使用任何类作为Map 的key？
可以，但要注意以下两点:
如果类重写了 equals()方法，也应该重写 hashcode()方法。
最好定义key类是不可变的，这样key对应的 hashcode()值可以被缓存起来，性能更好，这也是为什么string特别适合作为HashMap 的key 。
28.说一下Queue 与 Deque 的区别？
Queue是 单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循 先进先出（FIFO）规则。Queue 扩展了 Collection的接口，根据 因为容量问题而导致操作失败后处理方式的不同可以分为两类方法: 一种在操作失败后会抛出异常，另一种则会返回特殊值。
Queue 接口
抛出异常
返回特殊值
插入队尾
add(E e)
offer(E e)
删除队首
remove()
poll()
查询队首元素
element()
peek()
Deque是 双端队列，在队列的两端均可以插入或删除元素。Deque 扩展了 Queue的接口, 增加了在队首和队尾进行插入和删除的方法，同样根据失败后处理方式的不同分为两类：
Deque 接口
抛出异常
返回特殊值
插入队首
addFirst(E e)
offerFirst(E e)
插入队尾
addLast(E e)
offerLast(E e)
删除队首
removeFirst()
pollFirst()
删除队尾
removeLast()
pollLast()
查询队首元素
getFirst()
peekFirst()
查询队尾元素
getLast()
peekLast()
除此之外。 Deque还提供有 push()和 pop()等其他方法，可用于模拟栈。
29.说说ArrayDeque 与 LinkedList 的区别？
ArrayDeque和 LinkedList都实现了 Deque接口，两者都具有队列的功能，也都可以实现栈。连着区别：
ArrayDeque 是基于 可变长的数组和双指针来实现，而 LinkedList 则通过 链表来实现。
ArrayDeque 不支持存储 NULL数据，但 LinkedList 支持。
ArrayDeque 是在 JDK1.6才被引入的，而LinkedList 早在 JDK1.2时就已经存在。
ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。
从性能的角度上，选用 ArrayDeque来实现队列要比 LinkedList更好。
ArrayDeque 源码可以参考： 【JDK源码】ArrayDeque源码分析
LinkedList 源码可以参考： 【JDK源码】LinkedList源码分析
30.说一下 HashSet、LinkedHashSet 和 TreeSet 三者的异同？
HashSet、 LinkedHashSet和 TreeSet都是 Set接口的实现类， 都能保证元素唯一，并且都不是线程安全的。他们的不同点：
HashSet、LinkedHashSet 和 TreeSet 的主要区别在于底层数据结构不同：
HashSet的底层数据结构是 哈希表（基于 HashMap实现）
LinkedHashSet的底层数据结构是 链表和哈希表，元素的插入和取出顺序满足 FIFO
TreeSet底层数据结构是 红黑树，元素是有序的，排序的方式有自然排序和定制排序
底层数据结构不同又导致这三者的应用场景不同：
HashSetLinkedHashSetTreeSet