前言

我之前整理过Java常见集合的超详细八股笔记:https://www.nowcoder.com/discuss/641559745995755520?sourceSSR=search，但是说实话因为这份这份八股资料过于详细，内容过于充实，给背记带来了很大的挑战，所以我准备再出一系列帖子，内容就是我根据自己的面试经历和网上的面经，去筛选八股里面哪些是最常被问到的问题把它们整理出来，这样也能省去大家自己整理和筛选的时间，大家可以在面试前一两个小时快速把这一系列最常问八股的帖子拿出来看看，临时抱佛脚的效果应该很好。后面这系列帖子我会放入专栏https://www.nowcoder.com/creation/manager/columnDetail/0ybvLm，欢迎大家订阅。最后我想说，速成虽好，但是还是建议有时间就去看看我详细的八股笔记帖子。

想要学习Java冲实习或冲春招的，我能助你一臂之力，我之前整理了高质量可速成的魔改外卖项目话术和7000字轮子项目话术，还有超全超精品八股大全专栏，怎么写简历，怎么包装实习经历，怎么0基础速成冲春招和实习等等等等精品帖子，大家可以去看看我的精品文章汇总帖子：https://www.nowcoder.com/discuss/721704696242536448?sourceSSR=users

我的八股大全专栏（15w人学习，超千人订阅，牛客最受欢迎最高质量java八股专栏，多一句没有，少一句不行）：https://www.nowcoder.com/creation/manager/columnDetail/j8ZZk0

1.集合基础知识

1.Java集合有哪几种？

Java集合类主要由两个接口Collection和Map派生出来的，

一个是 Collection接口，主要用于存放单一元素；另一个是 Map 接口，主要用于存放键值对。对于Collection 接口，下面又有三个主要的子接口：List、Set 和 Queue(念q)。

2.集合的具体实现类

List

• ArrayList：Object[] 数组。
• Vector：Object[] 数组。
• LinkedList：双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环)。

Map

• HashMap：JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。
• LinkedHashMap：LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
• Hashtable：数组+链表组成的，数组是 Hashtable 的主体，链表则是主要为了解决哈希冲突而存在的。
• TreeMap：红黑树（自平衡的排序二叉树）。

Set

• HashSet(无序，唯一): 基于 HashMap 实现的，底层采用 HashMap 来保存元素。
• LinkedHashSet: LinkedHashSet 是 HashSet 的子类，并且其内部是通过 LinkedHashMap 来实现的。
• TreeSet(有序，唯一): 红黑树(自平衡的排序二叉树)。

Queue

• PriorityQueue: Object[] 数组来实现小顶堆。
• DelayQueue:PriorityQueue。
• ArrayDeque: 可扩容动态双向数组。

3.说说 List, Set, Queue, Map 四者的区别？

Java中的集合类主要由Collection和Map这两个接口派生而出，其中Collection接口又派生出三个子接口，分别是Set、List、Queue。所有的Java集合类，都是Set、List、Queue、Map这四个接口的实现类，这四个接口将集合分成了四大类，其中

• Set代表无序的，元素不可重复的集合；
• List代表有序的，元素可以重复的集合；
• Queue代表先进先出（FIFO）的队列；
• Map代表具有映射关系（key-value）的集合。

2.List

1.List有哪些类？

2.Arraylist 与 LinkedList的区别

• ArrayList的实现是基于数组，LinkedList的实现是基于双向链表；
• 对于随机访问ArrayList要优于LinkedList，ArrayList可以根据下标以O(1)时间复杂度对元素进行随 机访问，而LinkedList的每一个元素都依靠地址指针和它后一个元素连接在一起，查找某个元素的 时间复杂度是O(N)；
• 对于插入和删除操作，LinkedList要优于ArrayList，因为当元素被添加到LinkedList任意位置的时 候，不需要像ArrayList那样重新计算大小或者是更新索引；
• LinkedList比ArrayList更占内存，因为LinkedList的节点除了存储数据，还存储了两个引用，一个 指向前一个元素，一个指向后一个元素

3.ArrayList扩容原理（常问）

ArrayList有三种构造方法，无参构造方法将创建一个空的ArrayList，其内部使用一个默认容量为10的空数组初始化。如果通过指定初始容量来构造ArrayList，那么会创建一个具有该初始容量的数组。第三种构造方法允许传入一个集合，并将其所有元素添加到ArrayList中。

• 无参构造方法扩容过程如下

ArrayList的底层是动态数组，默认第一次插入元素时创建大小为10的数组。当调用add方法添加一个元素时，首先会确保当前ArrayList维护的数组具有存储新元素的能力。如果数组的容量不足以存储新元素，那么就会通过grow方法进行扩容。扩容的方式是将数组的容量扩大到原来的1.5倍，然后将原数组的数据复制到新的数组中。最后，将新元素添加到数组的末尾

4. 面试题-ArrayList list=new ArrayList(10)中的list扩容几次

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

3.Map相关面试题

1.Map有哪些类？

2.HashMap的底层实现(jdk1.7和jdk1.8有区别)（常问）

• jdk1.7

JDK7中的HashMap，是基于数组+链表来实现的，它的底层维护一个Entry数组。它会根据计算的hashCode将对应的KV键值对存储到该数组中，一旦发生hashCode冲突，那么就会将该KV键值对放到对应的已有元素的后面， 此时便形成了一个链表式的存储结构。

JDK7中HashMap的实现方案有一个明显的缺点，即当Hash冲突严重时，在桶上形成的链表会变得越来越长，这样在查询时的效率就会越来越低，其时间复杂度为O(N)。

• jak1.8

JDK8中的HashMap，是基于数组+链表+红黑树来实现的，它的底层维护一个Node数组。当链表长度大于阈值（默认为 8）外加数组长度大于64时时，将链表转化为红黑树，以减少搜索时间。这么做主要是在查询 的时间复杂度上进行优化，链表为O(N)，而红黑树一直是O(logN)，可以大大的提高查找性能。

1.线性探测法和链地址法

线性探测法是开放地址法的一种，用于处理哈希表中的冲突问题。

线性探测法的核心在于解决哈希冲突时不采用链表，而是通过探测散列表中的下一个位置来寻找空位。具体来说，如果一个关键字通过散列函数计算的地址已经被占用，它会尝试下一个地址，即当前地址加一（也可以考虑为负数或固定步长，视情况而定），直到找到一个空位为止。这种方法在实际操作中简单且易于实现，但当哈希表较为拥挤时，可能会导致很多空闲位置之间出现很多“堆积”，增加了平均查找时间。

链地址法则是将具有相同哈希值的所有元素链接在同一个链表中。

链地址法也被称为拉链法，它采用了不同的策略来解决哈希冲突。在这个方法中，每个哈希到同一个值的元素都会被插入到对应哈希值下的链表中。这意味着如果多个元素的哈希值相同，它们会被放在同一个链表里，以此来区分这些具有相同哈希值的元素。链地址法的优点是可以减少在插入和查找过程中的平均比较次数，因为每次比较的都是同义词节点。然而，这种方法需要额外的空间来存储指针信息。

2.红黑树

1.红黑树的介绍

（1）概述

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

（2）红黑树的特质

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

性质2：根节点是黑色

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

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

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

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

（3）红黑树的复杂度

• 查找： 红黑树也是一棵BST（二叉搜索树）树，查找操作的时间复杂度为：O(log n)
• 添加： 添加先要从根节点开始找到元素添加的位置，时间复杂度O(log n)添加完成后涉及到复杂度为O(1)的旋转调整操作故整体复杂度为：O(log n)
• 删除： 首先从根节点开始找到被删除元素的位置，时间复杂度O(log n)删除完成后涉及到复杂度为O(1)的旋转调整操作故整体复杂度为：O(log n)

2.为什么选红黑树，和二叉搜索树、AVL树（平衡二叉树）有什么区别？

• 二叉搜索树：在二叉搜索树中，左子节点的值小于根节点的值，右子节点的值大于根节点的值。这使得二叉搜索树在查找操作上具有优势。然而**，二叉搜索树可能退化为线性结构，即链**表，当数据插入顺序有序或接近有序时，其查找效率会大大降低，时间复杂度可能达到O(n)。
• AVL树:是一种高度平衡的二叉搜索树，它要求每个节点的左右子树的高度差不超过1。这种严格的平衡条件使得AVL树在查找操作上具有很高的效率，时间复杂度为O(log n)。然而，为了维护这种严格的平衡，AVL树在插入和删除操作时需要进行频繁的旋转调整，这增加了维护成本。因此，AVL树适合用于查找操作频繁但插入和删除操作较少的场景。
• 红黑树：**红黑树是一种近似平衡的二叉搜索树，它通过一系列性质（如节点颜色、黑高）来维护树的平衡。与AVL树相比，红黑树的平衡条件相对宽松，因此在插入和删除操作时的维护成本较低。**虽然红黑树的查找效率略低于AVL树，但其综合性能较好，适用于各种操作（插入、删除和查找）都较频繁的场景。此外，红黑树的高度近似为2log n，在实际应用中表现出良好的性能。

3.在解决 hash 冲突的时候，为什么选择先用链表，再转红黑树?

**因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡，而单链表不需要,所以元素的插入操作非常高效。所以，当元素个数小于8个的时候，采用链表结构可以保证查询性能。**而当元素个数大于8个的时候并且数组容量大于等于64，会采用红黑树结构。因为红黑树搜索时间复杂度是 O(logn)，而链表是 O(n)，在n比较大的时候，使用红黑树可以加快查询速度。

4.为什么链表改为红黑树的阈值是 8?

理想情况下使用随机的哈希码，容器中节点分布在 hash 桶中的频率遵循泊松分布，按照泊松分布的计算公式计算出了桶中元素个数和概率的对照表，可以看到链表中元素个数为 8 时的概率已经非常小，再多的就更少了，所以原作者在选择链表元素个数时选择了 8，是根据概率统计而选择的。

5.红黑树会退化为O(n）的查找时间复杂度吗

红黑树理论上不会退化为O(n)的查找时间复杂度。红黑树是一种自平衡二叉查找树，它通过对树中的节点进行着色和旋转维护了特定的性质，从而确保了其查找、插入和删除操作的时间复杂度在最坏情况下仍为O(log n)。

以下是确保红黑树效率的关键要素：

1. 着色规则：红黑树中的每一个节点要么是红色，要么是黑色。其中，红色的节点不能相邻，这意味着没有两个红色节点可以成为对方的父子关系。
2. 树的平衡：通过旋转操作来保持树的平衡。如果添加或删除节点后破坏了红黑树的性质，可以通过左旋或右旋来调整节点的位置，重新满足红黑树的性质。
3. 黑高度相等：从根节点到任何叶子节点的路径上，黑色节点的数量都相等，这个性质保证了最长路径不会超过最短路径的两倍长度。
4. 节点插入策略：新插入的节点总是作为红色节点，并遵循一定的规则来保证插入后仍是一棵有效的红黑树，必要时会通过旋转和重新着色来维护树的结构。
5. 修复机制：当执行删除操作时，可能会有一些红黑树性质被破坏，但算法提供了修复机制来重新调整树的结构，以恢复其有效性。

然而，尽管红黑树设计得旨在防止性能退化，但在极端情况下（例如，频繁的序列性插入和删除导致多次调整后仍出现不平衡），如果没有适当的旋转和重平衡，极端不平衡的二叉查找树可能会接近链表的性能。这种情况在实际中很少见，因为红黑树的操作本身就是为了防止这种极端情况的发生。

总的来说，红黑树是设计用来在各种操作下维持对数级性能的，即使在最坏的情况下也保证了O(log n)的时间复杂度，不会出现 O(n) 的查找时间复杂度。

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

key的Hash 值是int型(32位)，范围值-很大，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。

如果数组大小是2的n次方的化，我们也可以用hash值位与运算&(数组大小-1），这样和取模效果一样，而且二进制的位运算比取模效率高得多。

3.HashMap的扩容机制（常问）

• 在添加元素或初始化的时候需要调用resize方法进行扩容，第一次添加数据初始化数组长度为16，以后每次每次扩容都是达到了扩容阈值（当前数组长度 * 0.75）
• 每次扩容的时候，都是扩容之前容量的2倍；
• 扩容之后，会新创建一个数组，需要把老数组中的数据挪动到新的数组中
• 没有hash冲突节点，则直接使用 e.hash & (newCap - 1) (值等于e.hash%newCap)计算新数组的索引位置
• 如果是红黑树，走红黑树的添加
• 如果是链表，则需要遍历链表，可能需要拆分链表，判断(e.hash & oldCap)是否为0，若为0该元素的位置停留在原始位置，否则移动到原始位置+增加的数组大小这个位置上

1.为什么容量是以2的次方扩充的？

是为了提高性能使用足够大的数组，二是为了能使用位运算代替取模预算(据说提升了5~8倍)。

2.为什么要判断e.hash & oldCap==0

举例:原数组容量为16，存有3个元素，他们hash值分别为5，21，37，他们都存在下标为5的链表里，扩容后数组容量为32，他们对应的新数组下标分别为5，21，5，可用发现，hash值为5和37的都满足e.hash & oldCap==0,因此他们下标不变；而hash为21的不满足e.hash & oldCap==0,此时他的下标变为原下标+oldCap。这样可以省去重新计算hash值的时间

3.100个数据放入hashmap要扩容到多少

256；应为扩容到128时128*0.75<100,所以要再扩容一次

4. JDK 1.7 和 JDK 1.8 的 ConcurrentHashMap 实现有什么不同？

线程安全实现方式：JDK 1.7 采用 Segment 分段锁来保证安全， Segment 是继承自 ReentrantLock。JDK1.8 放弃了 Segment 分段锁的设计，采用 CAS + synchronized 保证线程安全，锁粒度更细，synchronized 只锁定当前链表或红黑二叉树的首节点。

Hash 碰撞解决方法 : JDK 1.7 采用拉链法，JDK1.8 采用拉链法结合红黑树（链表长度超过一定阈值时，将链表转换为红黑树）。

5.Queue

1.Queue 与 Deque 的区别

Queue 是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循 先进先出（FIFO） 规则。

Queue 扩展了 Collection 的接口，根据 因为容量问题而导致操作失败后处理方式的不同 可以分为两类方法: 一种在操作失败后会抛出异常，另一种则会返回特殊值

Deque 是双端队列，在队列的两端均可以插入或删除元素。

Deque 扩展了 Queue 的接口, 增加了在队首和队尾进行插入和删除的方法，同样根据失败后处理方式的不同分为两类：

2.ArrayDeque 与 LinkedList 的区别

ArrayDeque 和 LinkedList 都实现了 Deque 接口，两者都具有队列的功能，但两者有什么区别呢？

• ArrayDeque 是基于可变长的数组和双指针来实现，而 LinkedList 则通过链表来实现。
• ArrayDeque 不支持存储 NULL 数据，但 LinkedList 支持。
• ArrayDeque 是在 JDK1.6 才被引入的，而LinkedList 早在 JDK1.2 时就已经存在。
• ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。

从性能的角度上，选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外，ArrayDeque 也可以用于实现栈