1.5万字长文Java集合与数据结构面试题（注：该篇博客将会持续维护最新维护时间：2024年11月25日）

🧸本篇博客重在讲解Java集合与数据结构面试题，将会实时更新，欢迎大家添加作者文末联系方式交流

📜JAVA面试题专栏：JAVA崭新面试题——2024版_dream_ready的博客-CSDN博客

📜作者首页： dream_ready-CSDN博客

📜有任何问题都可以评论留言，作者将会实时回复

📜未来将会更新数据结构面试题以及Spring和MySQL等等的面试题，将会涵盖JAVA后端所有技术框架，敬请期待！！！

注：本篇博客题目顺序是精心制作的，建议想要阅读完整篇博客的同学按着顺序阅读！

1、Java的集合类有哪些？

2、集合和数组的区别？

ArrayList%E5%92%8CLinkedList%E7%9A%84%E5%8C%BA%E5%88%AB-toc" style="margin-left:0px;">3、ArrayList和LinkedList的区别

ArrayList%E5%92%8CVector%E6%9C%89%E4%BB%80%E4%B9%88%E5%8C%BA%E5%88%AB%EF%BC%9F-toc" style="margin-left:0px;">4、ArrayList和Vector有什么区别？

ArrayList%E6%98%AF%E5%A6%82%E4%BD%95%E6%89%A9%E5%AE%B9%E7%9A%84%3F-toc" style="margin-left:0px;">5、ArrayList是如何扩容的?

ArrayList%E6%98%AF%E7%BA%BF%E7%A8%8B%E5%AE%89%E5%85%A8%E7%9A%84%E4%B9%88-toc" style="margin-left:0px;">6、ArrayList是线程安全的么

ArrayList%20%E5%8F%98%E6%88%90%E7%BA%BF%E7%A8%8B%E5%AE%89%E5%85%A8%E7%9A%84%3F-toc" style="margin-left:0px;">7、如何让 ArrayList 变成线程安全的?

8、Set集合是如何保证元素不可重复的

HashMap%E5%BA%95%E5%B1%82%E6%98%AF%E5%A6%82%E4%BD%95%E5%AE%9E%E7%8E%B0%E7%9A%84%3F-toc" style="margin-left:0px;">9、HashMap底层是如何实现的?

HashMap%E8%A6%81%E4%BD%BF%E7%94%A8%E7%BA%A2%E9%BB%91%E6%A0%91%EF%BC%8C%E4%B8%BA%E4%BB%80%E4%B9%88%E4%B8%8D%E7%BB%A7%E7%BB%AD%E4%BD%BF%E7%94%A8%E9%93%BE%E8%A1%A8%EF%BC%9F-toc" style="margin-left:0px;">10、为什么Jdk8之后(包含Jdk8)，HashMap要使用红黑树，为什么不继续使用链表？

HashMap%E7%9A%84%E9%93%BE%E8%A1%A8%E5%9C%A8%E9%95%BF%E5%BA%A6%E4%B8%BA%E5%87%A0%E6%97%B6%E4%BC%9A%E8%BD%AC%E6%88%90%E7%BA%A2%E9%BB%91%E6%A0%91%EF%BC%9F-toc" style="margin-left:0px;">11、HashMap的链表在长度为几时会转成红黑树？

12、为什么长度为6的时候转回来?

13、什么是哈希冲突？如何解决哈希冲突？

HashMap%E7%9A%84%E6%9F%A5%E8%AF%A2%E6%B5%81%E7%A8%8B%EF%BC%9F(get%E6%93%8D%E4%BD%9C)-toc" style="margin-left:0px;">14、HashMap的查询流程？(get操作)

HashMap%E7%9A%84%E6%96%B0%E5%A2%9E%E6%B5%81%E7%A8%8B%EF%BC%9F(put%E6%93%8D%E4%BD%9C)-toc" style="margin-left:0px;">15、HashMap的新增流程？(put操作)

HashMap%E7%9A%84%E5%88%A0%E9%99%A4%E6%B5%81%E7%A8%8B%EF%BC%9F(remove%E6%93%8D%E4%BD%9C)-toc" style="margin-left:0px;">16、HashMap的删除流程？(remove操作)

HashMap%E5%9C%A8%E4%BB%80%E4%B9%88%E6%83%85%E5%86%B5%E4%B8%8B%E4%BC%9A%E8%A7%A6%E5%8F%91%E6%89%A9%E5%AE%B9%E6%93%8D%E4%BD%9C%EF%BC%9F-toc" style="margin-left:0px;">17、HashMap在什么情况下会触发扩容操作？

HashMap%E6%98%AF%E5%A6%82%E4%BD%95%E6%89%A9%E5%AE%B9%E7%9A%84%3F-toc" style="margin-left:0px;">18、HashMap是如何扩容的?

HashMap%E7%9A%84%E9%BB%98%E8%AE%A4%E5%88%9D%E5%A7%8B%E5%AE%B9%E9%87%8F%E6%98%AF%E5%A4%9A%E5%B0%91%EF%BC%9F-toc" style="margin-left:0px;">19、HashMap的默认初始容量是多少？

HashMap%E7%9A%84%E9%BB%98%E8%AE%A4%E8%B4%9F%E8%BD%BD%E5%9B%A0%E5%AD%90%E8%AE%BE%E7%BD%AE%E6%88%900.75%EF%BC%9F-toc" style="margin-left:0px;">20、为什么HashMap的默认负载因子设置成0.75？

HashMap%E6%98%AF%E7%BA%BF%E7%A8%8B%E5%AE%89%E5%85%A8%E7%9A%84%E4%B9%88%EF%BC%9F-toc" style="margin-left:0px;">21、HashMap是线程安全的么？

HashMap%E4%B8%BA%E4%BB%80%E4%B9%88%E4%BC%9A%E6%AD%BB%E5%BE%AA%E7%8E%AF%EF%BC%9F-toc" style="margin-left:0px;">22、HashMap为什么会死循环？

HashMap%E4%B8%BA%E4%BB%80%E4%B9%88%E4%BC%9A%E6%95%B0%E6%8D%AE%E8%A6%86%E7%9B%96%3F-toc" style="margin-left:0px;">23、HashMap为什么会数据覆盖?

HashMap%E7%BA%BF%E7%A8%8B%E5%AE%89%E5%85%A8%EF%BC%9F-toc" style="margin-left:0px;">24、如何保证HashMap线程安全？

HashMap%E3%80%81Hashtable%E5%92%8CConcurrentHashMap%E7%9A%84%E5%8C%BA%E5%88%AB%EF%BC%9F-toc" style="margin-left:0px;">25、HashMap、Hashtable和ConcurrentHashMap的区别？

HashMap%20%E5%85%81%E8%AE%B8%E6%8F%92%E5%85%A5%20null%E9%94%AE%20%E5%92%8C%20null%20%E5%80%BC%EF%BC%9F-toc" style="margin-left:0px;">26、为什么 HashMap 允许插入 null键和 null 值？

27、什么是二义性问题？

HashMap%E4%B8%8D%E5%85%81%E8%AE%B8%E6%8F%92%E5%85%A5nuI%E9%94%AE%E5%92%8CnuI%E5%80%BC%3F-toc" style="margin-left:0px;">28、为什么Hashtable和ConcurrentHashMap不允许插入nuI键和nuI值?

29、Hashtable是如何保证线程安全的?

HashMap%E6%98%AF%E5%A6%82%E4%BD%95%E4%BF%9D%E8%AF%81%E7%BA%BF%E7%A8%8B%E5%AE%89%E5%85%A8%E7%9A%84%3F-toc" style="margin-left:0px;">30、ConcurrentHashMap是如何保证线程安全的?

31、HashSet简介

1、Java的集合类有哪些？

在Java中，常用的集合主要分为五个大类，分别是列表(List)、集合(Set)、队列(Queue)、栈(Stack)、字典(Map)。

其中，前四种结构都是单一元素的集合(每个位置放一个元素)，而Map则是以Key-Value键值对的形式使用的

列表(List)：有序集合，可以包含重复元素。常见实现类有 ArrayList、LinkedList、Vector 等。
集合(Set)：无序集合，不允许包含重复元素。常见实现类有 HashSet、TreeSet 等。
队列(Queue):：先进先出的数据结构。常见实现类有 BlockingQueue、PriorityQueue 等.
栈(Stack)：先进后出的数据结构。
字典(Map)：键值对的集合，每个键只能对应一个值。常见实现类有 HashMap、TreeMap、LinkedHashMap 等。

各个集合的特点在上面用加粗字号显示了，依此口述即可

从继承关系上讲，List，Set，Queue都是Collection的子接口，Map属于一个单独的分类

可以了解一下：Collection又继承了Iterable接口，所以我们经常可以看到，集合类使用迭代器进行遍历

口述话：（阅读即可，不要背，太口语化了）

在大部分的实际使用中，最常用的集合接口包括 List、Set、Map 等。

其中，List 接口表示一个有序的集合，可以包含重复的元素，最常用的实现类有ArrayList，可以说在代码中，只要用到集合类，它一定是脑子中最先想到的。当然，既然您都提问我八股文了，那么理论上最常用的也有LinkedList（链表），毕竟增删的话，链表确实比偏数组的ArrayList更快。其次，需要注意的是，栈，stack也是List的子接口，但是队列，Queue不是

Set 接口表示一个不重复的集合，只有当我们对“不重复”三个字有需求时才会用到它，否则还是优先使用list

Map 接口表示一组键值对的映射关系。这个不比list用的少，甚至无处不在。毕竟其他的数据结构都是一个萝卜一个坑，只有他是键值对存储的，他的查找、插入和删除都是非常迅速的，我们也需要用到它键值对的特性。我举一个常见的使用该场景吧，用户的会话管理，这个时候，我们就可以使用Map来存储用户的会话信息，也就是Session，每个用户的会话信息可以通过唯一的会话ID来索引，说白了，就是这样的结构：<key, Value>: <会话ID, Session>

2、集合和数组的区别？

与其说是集合和数组的区别，不如说是ArrayList和数组的区别

在 Java 中，数组属于一种特殊的数据结构。它是一种固定大小的、用于存储相同类型的多个元素的一种容器。数组在内存中是一个连续的存储区域，可以通过索引来访问其中的某个元素。

int[] numbers = {5, 3, 7, 2, 1};

而集合，是一种用于存储和操作一组对象的数据结构。它们通过一组接口和类来实现，提供了丰富的方法和功能使得对数据的处理更加方便和高效。

List<Integer> numbers = new ArrayList<>();

从严格意义上来讲，数组和集合都是用于存储数据的容器，但数组不属于集合。其实在我看来，二者在实际使用上的最大区别就两点

数组无法存储泛型，这就导致数组能存储的数据结构很有限，无法存储我们自己的实体类
数组在初始化时需要指定大小，后续改变存储大小就很困难了，而集合我们不需要考虑这点，它会动态扩展

注：其他list的实现类和数组差别太大了，比较意义不大，咱很多时候，说集合和数组的区别，其实默认就是比较ArrayList和数组的区别

ArrayList%E5%92%8CLinkedList%E7%9A%84%E5%8C%BA%E5%88%AB">3、ArrayList和LinkedList的区别

说白了，更像是数组和链表的区别，ArrayList是一个可以改变大小的数组，LinkedList是一个双向链表

注：为了防止有些同学困惑，我还是在这里说一下吧，严格意义上，ArrayList是集合，数组是类似int[]这样的，你要专门比较二者的话，你肯定不能说ArrayList是数组，但在我们不讨论严格意义上的数组时，我们是经常会把ArrayList说成数组的，这也是所有开发者的习惯了

ArrayList和LinkedList都是数据的集合，区别如下：

1、底层数据结构实现不同：

ArrayList底层使用数组实现，是一块连续的内存区域，通过一个可调整大小的数组来存储元素
LinkedList 底层使用双向链表实现，可以由不连续的内存区域实现，它通过链表节点来连接元素，每个元素都会存储上一个元素和下一个元素的地址

2、插入和删除的效率不同：

ArrayList 对于插入和删除操作的性能相对较低，因为需要进行元素的移动和数组的重新分配，尤其是在ArrayList 列表最前面插入和删除时，效率最慢。
LinkedList 对于插入和删除操作会比 ArrayList 更好，因为它只需要修改相邻节点的指针即可。

3、随机访问效率不同：

ArrayList 对于随机访问(根据索引获取元素)具有更好的性能，因为可以通过索引直接计算元素在数组中的位置，时间复杂度为 O(1)
LinkedList 对于随机访问的性能较差，需要通过链表节点一个个遍历找到对应的索引位置，时间复杂度为O(n)

4、内存要求和占用空间大小不同：

ArrayList 在内存中需要连续的存储空间，因此在存储大量数据时，需要有大块的连续内存空间，所以对内存要求较高(不能有太多的内存碎片)。
LinkedList 不要求有连续的内存空间，它的链表是逻辑的先后顺序，每个元素用额外的空间来存储指向前和后的节点指针，所以，LinkedList 相对而言会占用更多的内存空间。

因此，在多查的场景下考虑使用 ArrayList，而在插入和删除比较多的场景下考虑使用 LinkedList

ArrayList%E5%92%8CVector%E6%9C%89%E4%BB%80%E4%B9%88%E5%8C%BA%E5%88%AB%EF%BC%9F">4、ArrayList和Vector有什么区别？

ArrayList 和 Vector 都是 List 的子类，都实现了 List 接口，如下图所示：

首先，需要明白的是，尽管从上图看，Stack继承Vector，但是Vector已经不是接口了，是一个具体的类

二者的区别主要有以下几点：

线程安全不同：Vector 是线程安全的，而 ArrayList 是非线程安全的。在 Vector中，每个方法都使用了synchronized 关键字进行同步，以确保线程安全。
扩容策略不同：Vector 和 ArrayList 都是可以动态扩容的。但是，当动态的长度不同，Vector 会自动增长当前的容量一倍，也就是扩容 100%，而 ArrayList 只会增长当前容量的 50%。
性能不同：ArrayList 由于不具备线程安全的机制，所以在单线程环境下通常有更好的性能。而 Vector 由于是线程安全的，使用 synchronized 修饰，所以会带来额外的加锁和释放锁的性能开销，因此在单线程环境下Vector 性能不如 ArrayList。

ArrayList%E6%98%AF%E5%A6%82%E4%BD%95%E6%89%A9%E5%AE%B9%E7%9A%84%3F">5、ArrayList是如何扩容的?

首先，我们要明白ArrayList是基于数组的，我们都知道，申请数组的时候，只能申请一个定长的数组，那么List是如何通过数组扩容的呢?

ArrayList都是在新增元素时发现容量不足而触发扩容操作的

ArrayList的扩容分为以下几步：

检查新增元素后是否会超过数组的容量，如果超过，则进行下一步扩容
设置新的容量为老容量的1.5倍，容量最多不超过2^31-1
之后，申请一个容量为1.5倍的数组，并将元素复制到新数组中，扩容完成。
最后将原本要添加的那个新元素添加到数组中

ArrayList%E6%98%AF%E7%BA%BF%E7%A8%8B%E5%AE%89%E5%85%A8%E7%9A%84%E4%B9%88">6、ArrayList是线程安全的么

不是！

多线程环境下，如果多个线程同时对同一个 ArrayList 进行添加、删除或修改操作，可能会导致数据不一致或发生异常。这是因为，ArrayList 在内部实现时，并没有添加任何线程同步的机制，所以如果有多个线程同时对ArrayList 进行修改时，就会导致线程不安全的问题发生。

例如，添加操作和修改操作同时执行，那么它们的执行情况可能是这样的：

首先，先执行添加操作，而添加时发现 ArrayList 需要进行扩容，所以此时就先执行了扩容操作。
扩容操作执行一半之后，当前线程 CPU 时间片用完了，停止执行。
修改线程开始执行，于是将 ArrayList 已经扩容的这部分旧数据进行修改，修改线程执行完成。（问题已经出现了，因为修改的是原数组，也就是老数组）
扩容操作继续执行，将后半一半数组进行扩容。
将原对象的引用更换到新数组上。

此时就会发现，修改线程的修改操作失效了，因为修改线程，修改的是老数组，而添加操作在扩容时，已经将旧数据复制到新数组了，所以此时的修改操作就丢失了，这就是线程安全问题。

ArrayList%20%E5%8F%98%E6%88%90%E7%BA%BF%E7%A8%8B%E5%AE%89%E5%85%A8%E7%9A%84%3F">7、如何让 ArrayList 变成线程安全的?

想要让 ArrayList 变成线程安全的，也就是想要在多线程下使用 ArrayList 的方案有以下两类

加锁：在多线程下，对 ArrayList 进行非查询操作时，先加锁，可以使用 synchronized 或 Lock，让线程排队执行，这样对于 ArrayList 的操作就变成单线程了，这样 ArrayList 就是线程安全的了。
更换同类型线程安全的容器：在多线程下可以将 ArrayList 更换为线程安全的 CopyOnWriteArrayList或Vector，这样也不会有线程安全问题了。

这里简单说一下，CopyOnWriteArrayList和Vector分别靠什么实现线程安全的（防止被面试官提问）

CopyOnWriteArrayList是使用 “写时复制” 的机制来实现线程安全的。具体来说，每当有写操作（如add、remove）发生时，CopyOnWriteArrayList 会创建一个新的数组副本，并在新的数组上进行操作，而读操作则始终在旧的数组上进行。这样，读操作不会受到写操作的影响，从而实现了高并发读取，也保证了安全性。
Vector 就非常粗暴了，所有方法都是同步的，每个方法都使用了synchronized关键字。这意味着每次调用这些方法时，都会锁定整个 Vector 对象，从而确保在同一时间只有一个线程可以执行这些方法。

8、Set集合是如何保证元素不可重复的

在 Java编程中，Set是一种用于存储不重复元素的集合。Set接口的实现类，如HashSet、TreeSet和LinkedHashSet，都保证了集合中的元素是唯一的

HashSet基于哈希表实现，底层是HashMap，HashSet通过哈希函数和 equals方法来保证元素不重复

在往HashSet中添加对象的时候，首先会通过该对象的hashCode方法计算该对象的hash值。
将计算出来的hash值去hash表中查询，如果hash表中不存在该值，则对象添加成功。
如果hash表中有该hash值，那么还会将要添加的对象和集合中的对象进行进一步的比较，使用对象的equals方法比较两个对象是否相等。如果相等，则认为元素已存在，不插入新元素；否则，插入新元素。

TreeSet 是 Set 接口的一种实现类，基于红黑树实现。TreeSet 通过比较器或元素的自然顺序来保证元素不重复。

TreeSet默认是用自然排序来保证元素不重复的，依靠 compareTo 方法比较元素是否存在，但我们也可以自定义比较逻辑，用比较器的方式来写下我们所需的比较逻辑

自然顺序（TreeSet默认的比较方式）

如果元素实现了 Comparable 接口，TreeSet 使用元素的自然顺序进行比较。元素必须重写 compareTo 方法，TreeSet 在插入元素时，调用 compareTo 方法比较元素。如果 compareTo 方法返回 0，则认为元素相等，不插入新元素。

比较器（自定义比较逻辑）

TreeSet 可以使用自定义的比较器来比较元素。比较器必须实现 Comparator 接口，并重写 compare 方法。TreeSet 在插入元素时，调用比较器的 compare 方法比较元素。如果 compare 方法返回 0，则认为元素相等，不插入新元素。

比较器代码举例：(方便大家理解)

Comparator<String> comparator = new Comparator<String>() {@Overridepublic int compare(String s1, String s2) {return s1.length() - s2.length(); // 按字符串长度比较}
};

LinkedHashSet 是 Set 接口的一种实现类，基于哈希表和双向链表实现。LinkedHashSet 通过哈希函数和 equals 方法来保证元素不重复，同时保持元素的插入顺序。

HashMap%E5%BA%95%E5%B1%82%E6%98%AF%E5%A6%82%E4%BD%95%E5%AE%9E%E7%8E%B0%E7%9A%84%3F">9、HashMap底层是如何实现的?

不同的 JDK 版本，HashMap 的底层实现是不一样的，总体来说：在 JDK 1.8 之前(不包含 JDK 1.8)HashMap 使用的是数组 + 链表实现的，而 JDK 1.8 之后(包含 JDK 1.8)使用的是数组 + 链表或红黑树实现的。

不要被图像迷惑，数组对应的元素并不是key，HashMap数组的每个元素是一个链表或者红黑树，链表或红黑树的每个节点会存储一对键值对

HashMap 在 JDK 1.8 以前(不包含 JDK 1.8)的版本中的实现如下图所示：

HashMap 在 JDK 1.8+中(包含 JDK 1.8)的实现如下图所示：

需要注意的是，当数组节点处的元素数量小于8时，该数组节点后跟的是链表，当大于等于8时，该数组节点后跟的是红黑树

HashMap%E8%A6%81%E4%BD%BF%E7%94%A8%E7%BA%A2%E9%BB%91%E6%A0%91%EF%BC%8C%E4%B8%BA%E4%BB%80%E4%B9%88%E4%B8%8D%E7%BB%A7%E7%BB%AD%E4%BD%BF%E7%94%A8%E9%93%BE%E8%A1%A8%EF%BC%9F">10、为什么Jdk8之后(包含Jdk8)，HashMap要使用红黑树，为什么不继续使用链表？

为什么不继续使用链表？

主要就是链表查询效率接近O(N)，使用红黑树的主要原因就是为了提高查询效率( O(log n) )

我们知道，HashMap解决hash冲突是通过拉链法完成的，在JK8之前，如果产生冲突，就会把新增的元素增加到当前桶所在的链表中。

这样就会产生一个问题，当某个bucket冲突过多的时候，其指向的链表就会变得很长，这样如果put或者get该bucket上的元素时，复杂度就无限接近于O(N)，这样显然是不可以接受的。

所以在JDK1.7的时候，在元素put之前做hash的时候，就会充分利用扰动函数，将不同KEY的hash尽可能的分散开。不过这样做起来效果还不是太好，所以当链表过长的时候，我们就要对其数据结构进行修改

为什么是红黑树？

首先，我们知道，元素过多时，链表是绝对不适合的，也是必须要替换的，这个时候我们的重心就变成了找到一种数据结构代替链表

在诸多博客以及先贤中，他们统一提到了三种数据结构可以考虑，分别是二叉搜索树、二叉平衡树(AVL树)、红黑树

HashMap 中之所以使用红黑树，是因为红黑树最合适做 HashMap 多节点的数据存储和查询。因为使用二叉搜索树在某些情况下会退化为链表，所以它的查询效率可能会存在问题；而使用 AVL 树，在添加或删除时，效率又不如红黑树，所以选择使用红黑树是 HashMap 最合适的选择

二叉查找树：

所谓的二又查找树，一定是left<root<right，这样我们遍历的时间复杂度就会由链表的O(N)变为二叉査找树的O(loqN)，二叉查找树如下所示：

但是，二叉搜索树有个致命的缺点，它在极端情况下会退化为链表结构，当子节点都比父节点大或者小的时候，二叉查找树又会退化成链表，查询复杂度会重新变为O(N)，如下所示：

所以，它并不是最适合的存储结构

二叉平衡树(AVL树)：

在二又搜索树的基础上，增加了平衡性的要求，保持左右子树的高度差不超过 1，通过旋转操作来保持树的平衡。

他会在每次插入操作时来检查每个节点的左子树和右子树的高度差至多等于1，如果>1，就需要进行左旋或者右旋操作，使其查询复杂度一直维持在O(logN)。

但是这样就万无一失了吗？其实并不然，我们不仅要保证查询的时间复杂度，还需要保证插入的时间复杂度足够低，因为平衡二叉树要求高度差最多为1，非常严格，导致每次插入都需要左旋或者右旋，极大的消耗了插入的时间。

对于那些插入和删除比较频繁的场景，AVL树显然是不合适的。为了保证查询和插入的时间复杂度维持在一个均衡的水平上，所以就引入了红黑树。

红黑树：

红黑树也是一种具有平衡性质的二又搜索树。通过约束节点的颜色(红色或黑色)和些平衡性质来保持树的平衡。

红黑树不会像AVL树一样追求绝对的平衡，它的插入最多两次旋转，删除最多三次旋转，在频繁的插入和删除场景中，红黑树的时间复杂度，是优于AVL树的。

HashMap%E7%9A%84%E9%93%BE%E8%A1%A8%E5%9C%A8%E9%95%BF%E5%BA%A6%E4%B8%BA%E5%87%A0%E6%97%B6%E4%BC%9A%E8%BD%AC%E6%88%90%E7%BA%A2%E9%BB%91%E6%A0%91%EF%BC%9F">11、HashMap的链表在长度为几时会转成红黑树？

当节点处的链表长度达到8时，会转成红黑树

为什么不在冲突的时候立刻转？

从空间维度来讲，因为红黑树的空间是普通链表节点空间的2倍，立刻转为红黑树后，太浪费空间

从时间维度上讲，红黑树虽然查询比链表快，但是插入比链表慢多了，每次插入都要旋转和变色，如果小于8就转为红黑树，时间和空间的综合平衡上就没有链表好

为什么长度为8的时候转？

源码中说，TreeNode占用的内存是Node的两倍，只有在node数量达到8时才会使用它，而当 node 数量变小时(删除或者扩容)，又会变回普通的 Node 。最后再结合其他资料总结一下，8这个数是经过数学推理的，不是瞎写的。

12、为什么长度为6的时候转回来?

当红黑树节点数小于6时，又会把红黑树转换回链表，这个设计的主要原因是出于对于性能和空间的考虑。毕竟我们说过红黑树的插入效率是低的

为什么不在低于8的时候立马就转回来？

8的时候转成红黑树，那么如果小于8立刻转回去，那么就可能会导致频繁转换，所以要选一个小于8的值，但是又不能是7。当红黑树节点数小于6时，它所带来的优势其实就是已经没有那么大了，就不足以抵消由于红黑树维护节点所带来的额外开销，此时转换回链表能够节省空间和时间，

总结，6 这个数值是通过大量实验得到的经验值，在绝大多数情况下取得比较好的效果

13、什么是哈希冲突？如何解决哈希冲突？

哈希冲突是指不同的输入数据在进行哈希函数计算后，得到相同的哈希值的情况。

此时如果强行的进行数据存储就会发生数据覆盖的问题

由于哈希函数是将输入映射到一个有限的哈希表中，而输入的数据量可能是无限的，所以在特定的哈希函数和哈希表大小的限制下，哈希冲突是难以避免的。

解决哈希冲突的常见方法有以下几种:

链地址法：将哈希表中的每个桶都设置为一个链表，当发生哈希冲突时，将新的元素插入到链表的末尾。这种方法的优点是简单易懂，适用于元素数量较多的情况。缺点是当链表过长时，查询效率会降低。
再哈希法：当发生哈希冲突时，使用另一个哈希函数计算出一个新的哈希值，然后将元素插入到对应的桶中。这种方法的优点是简单易懂，适用于元素数量较少的情况。缺点是需要额外的哈希函数，且当哈希函数不够随机时，容易产生聚集现象。
开放地址法：当发生哈希冲突时，就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，之后再将数据进行存储。

在 Java 的 HashMap 中，是通过链地址法来解决哈希冲突的。

HashMap%E7%9A%84%E6%9F%A5%E8%AF%A2%E6%B5%81%E7%A8%8B%EF%BC%9F(get%E6%93%8D%E4%BD%9C)">14、HashMap的查询流程？(get操作)

首先，根据哈希函数计算Key的哈希值，并通过哈希值计算出在数组中的索引位置
如果该位置上的元素为空，说明没有找到对应的键值对，直接返回nul。
如果该位置上的元素不为空，遍历该位置上的元素，如果找到了与当前键相等的键值对，那么返回该键值对的值，否则返回null。

HashMap%E7%9A%84%E6%96%B0%E5%A2%9E%E6%B5%81%E7%A8%8B%EF%BC%9F(put%E6%93%8D%E4%BD%9C)">15、HashMap的新增流程？(put操作)

首先，根据哈希函数计算Key的哈希值，并通过哈希值计算出在数组中的索引位置
如果该位置上的元素为空，那么直接将键值对存储在该位置上
如果该位置上的元素不为空，那么遍历该位置上的元素，如果找到了与当前键相等的键值对，那么将该键值对的值更新为当前值，并返回旧值
如果该位置上的元素不为空，但没有与当前键相等的键值对，那么将键值对插入到链表或红黑树中(如果该位置上的元素数是超过了一个阈值，就会将链表转化为红黑树来提高效率)。
如果插入成功，返回旧值，如果插入失败，返回nul。
插入成功后，如果需要扩容，那么就进行一次扩容操作

HashMap%E7%9A%84%E5%88%A0%E9%99%A4%E6%B5%81%E7%A8%8B%EF%BC%9F(remove%E6%93%8D%E4%BD%9C)">16、HashMap的删除流程？(remove操作)

首先，根据哈希函数计算Key的哈希值，并通过哈希值计算出在数组中的索引位置
如果该位置上的元素为空，说明没有找到对应的键值对，直接返回nul
如果该位置上的元素不为空，检查是否与当前键相等，如果相等，那么将该键值对删除，并返回该键值对的值
如果该位置上的元素不为空，但也与当前键不相等，那么就需要在链表或红黑树中继续査找，遍历链表或者红黑树，查找与当前键相等的键值对，找到则将该键值对删除，并返回该键值对的值，否则返回null

HashMap%E5%9C%A8%E4%BB%80%E4%B9%88%E6%83%85%E5%86%B5%E4%B8%8B%E4%BC%9A%E8%A7%A6%E5%8F%91%E6%89%A9%E5%AE%B9%E6%93%8D%E4%BD%9C%EF%BC%9F">17、HashMap在什么情况下会触发扩容操作？

HashMap为什么要进行扩容

众所周知，HashMap是由数组+链表+红黑树组成的，那么理论上初始化后，有再多的数据也能存储的下，那为什么需要扩容呢？这不多此一举么？

扩容操作的主要目的是减少哈希冲突，提高查找效率。假设现在散列表中的元素已经很多了，但是现在散列表的链化已经比较严重了，哪怕是树化了，时间复杂度也是O(log n)，也没有O(1)好，所以需要扩容来降低Hash冲突的概率，以此来提高性能。

当 Hashmap 中的元素数量增长到一定程度时，会自动进行扩容操作。

当 HashMap 中的元素数量(即 size)超过当前容量与负载因子的乘积时，会触发扩容操作。

拿第一次扩容举例，默认情况下，HashMap的初始容量是 16，负载因子是 0.75。因此，当HashMap 中的元素数量超过 12(16*0.75)时，会触发扩容。

HashMap%E6%98%AF%E5%A6%82%E4%BD%95%E6%89%A9%E5%AE%B9%E7%9A%84%3F">18、HashMap是如何扩容的?

当 HashMap 中的元素数量(即 size)超过当前容量与负载因子的乘积时，会触发扩容操作。

创建一个新的数组，其容量是当前数组容量的两倍。
如果该桶中只有一个节点或者为空，即没有形成链表或红黑树，则直接将该节点重新计算哈希值，并放置到新数组的相应位置。
如果某个桶中形成了链表，则需要将链表中的每个节点重新计算哈希值，并重新链接到新数组的相应位置。(链表中的每个节点存储一对键值对)
如果桶中的链表已经形成红黑树，但是链表中的元素个数小于6，则将红黑树转成链表，然后按着链表的步骤走
如果红黑树节点数量仍然大于等于 6，则保持红黑树结构，并将树中的每个节点重新计算哈希值，重新插入到新数组的相应位置。

由于新数组的容量发生了变化，所有已存在的键值对都需要重新计算哈希值，并找到其在新数组中的位置。重新计算哈希值的目的是确保元素在新的数组中分布更加均匀，减少哈希冲突。

HashMap%E7%9A%84%E9%BB%98%E8%AE%A4%E5%88%9D%E5%A7%8B%E5%AE%B9%E9%87%8F%E6%98%AF%E5%A4%9A%E5%B0%91%EF%BC%9F">19、HashMap的默认初始容量是多少？

HashMap的默认初始容量默认是16

这意味着当你创建一个HashMap对象时，如果没有显式指定初始容量，它内部使用的数组大小默认为16。

注：HashMap的默认负载因子是0.75，而负载因子和初始容量都是可以在初始化时指定的

HashMap<String, String> map = new HashMap<>(初始容量, 负载因子);

HashMap%E7%9A%84%E9%BB%98%E8%AE%A4%E8%B4%9F%E8%BD%BD%E5%9B%A0%E5%AD%90%E8%AE%BE%E7%BD%AE%E6%88%900.75%EF%BC%9F">20、为什么HashMap的默认负载因子设置成0.75？

总结：官方给的答案是，负载因子为 0.75 是一种经验性的权衡，这个值被认为是在时间和空间效率之间找到的一个良好平衡。 （也有非官方的大佬从数学的角度推测了这个问题的答案，它通过数学公式得到合理的负载因子是在0.7左右的）

负载因子也叫扩容因子，它是一个用于控制 HashMap 何时进行扩容的参数。当 HashMap 中存储的键值对数量，超过了 HashMap 总容量乘以扩容因子时，HashMap 就会进行扩容操作。

例如 HashMap 的总容量为 16，扩容因子为 0.75，那么当 HashMap 中存储的键值对大于 12(16*0.75)时HashMap 就会进行扩容。

注：负载因子的值是0到1之间(大于 0，小于 1)。

当负载因子比较大的时候，那么扩容就会比较晚，空间利用率就会比较高，但发生哈希冲突的概率就会增大那么插入的时间就会变长
当负载因子比较小的时候，那么扩容会比较早，发生哈希冲突的概率会变小，插入的时间会变快，但空间利用率就会很低。

因此选择 0.75 是空间和时间效率的一种平衡。

HashMap%E6%98%AF%E7%BA%BF%E7%A8%8B%E5%AE%89%E5%85%A8%E7%9A%84%E4%B9%88%EF%BC%9F">21、HashMap是线程安全的么？

HashMap 是线程不安全的，原因主要体现在以下两个方面:

1、HashMap 在 JDK 1.7 之前(包含 JDK 1.7)它线程不安全的原因体现在两个方面:

HashMap 可能会造成环形链表，导致程序执行死循环。
多线程下并发执行，可能会导致数据覆盖。

2、HashMap 在 JDK 1.8 之后(包含 JDK 1.8)不再有死循环问题，但依旧存在数据覆盖问题。
所以，HashMap 是线程不安全的。

HashMap%E4%B8%BA%E4%BB%80%E4%B9%88%E4%BC%9A%E6%AD%BB%E5%BE%AA%E7%8E%AF%EF%BC%9F">22、HashMap为什么会死循环？

JDK 1.7 之前(包含 JDK 1.7)，HashMap有可能会出现死循环，原因是并发情况下 HashMap 扩容导致出现了环形链表。进一步的原因如下

HashMap在扩容的时候，会将元素插入链表头部，即头插法。如下图，原来是A->B->C，扩容后会变成"C->B->A"

如下图所示：

之所以选择使用头插法，是因为JDK的开发者认为，后插入的数据被使用到的概率更高，更容易成为热点数据，而通过头插法把它们放在队列头部，就可以使查询效率更高。

死循环执行步骤1：

死循环是因为并发 HashMap 扩容导致的，并发扩容的第一步，线程 T1 和线程 T2 要对 HashMap 进行扩容操作

此时 T1 和 T2 指向的是链表的头结点元素 A，而 T1 和 T2 的下一个节点，也就是 T1.next 和 T2.next 指向的是B 节点，如下图所示：

死循环执行步骤2：

死循环的第二步操作是，线程 T2 时间片用完进入休眠状态，而线程 T1 开始执行扩容操作，一直到线程 T1 扩容完成后，线程 T2 才被唤醒，扩容之后的场景如下图所示：

从上图可知线程 T1 执行之后，因为是头插法，所以 HashMap 的顺序已经发生了改变，但线程 T2 对于发生的一切是不可知的，所以它的指向元素依然没变，如上图展示的那样，T2 指向的是 A 元素，T2.next 指向的节点是 B元素。

死循环执行步骤3：

当线程 T1 执行完，而线程 T2 恢复执行时，死循环就建立了，如下图所示：

因为 T1 执行完扩容之后 B 节点的下一个节点是 A，而 T2 线程指向的首节点是 A，第二个节点是 B，这个顺序刚好和 T1 扩完容完之后的节点顺序是相反的。T1 执行完之后的顺序是 B 到 A，而 T2 的顺序是 A 到 B，这样 A节点和 B 节点就形成死循环了，这就是 HashMap 死循环导致的原因。

HashMap%E4%B8%BA%E4%BB%80%E4%B9%88%E4%BC%9A%E6%95%B0%E6%8D%AE%E8%A6%86%E7%9B%96%3F">23、HashMap为什么会数据覆盖?

数据覆盖问题发生在并发添加元素的场景下，它不止出现在 JDK 1.7 版本中，其他版本中也存在此问题，数据覆盖立生的流程如下：

线程 T1 进行添加时，判断某个位置可以插入元素，但还没有真正的进行插入操作，自己时间片就用完了
线程 T2 也执行添加操作，并且 T2 产生的哈希值和 T1 相同，也就是 T2 即将要存储的位置和 T1 相同，因为此位置尚未插入值(T1 线程执行了一半)，于是 T2 就把自己的值存入到当前位置了。
T1 恢复执行之后，因为非空判断已经执行完了，它感知不到此位置已经有值了，于是就把自己的值也插入到了此位置，那么 T2 的值就被覆盖了。

其实，这种数据覆盖的情况不仅发生在HashMap中，它是在并发场景下极其常见的情况，比如很典型的，两个请求A和B先后来到我们后端，都是对同一条数据进行修改，结果后到来的请求B先执行完了，这时候就出现了脏数据，其实不死扣的话，也算数据覆盖的一种情况。

HashMap%E7%BA%BF%E7%A8%8B%E5%AE%89%E5%85%A8%EF%BC%9F">24、如何保证HashMap线程安全？

保证 HashMap 线程安全的主要手段有以下两种：

使用线程安全的容器作为替代： 例如 ConcurrentHashMap 或 Hashtable(不推荐使用，效率低)
加锁： 使用 synchronized 或 Lock 加锁将并发操作 HashMap，让对于 HashMap 的非查询操作，从多线程同时执行，变成多线程排队执行(某一个时刻只有一个线程在执行)

注：绝大部分的问题，只要问到你如何保证线程安全，基本加锁永远是其中一种解决办法，无非就是怎样加锁，何时加锁，锁的粒度等问题

HashMap%E3%80%81Hashtable%E5%92%8CConcurrentHashMap%E7%9A%84%E5%8C%BA%E5%88%AB%EF%BC%9F">25、HashMap、Hashtable和ConcurrentHashMap的区别？

HashMap、Hashtable和ConcurrentHashMap都是Map接口的实现类，都是用于存储Key-Value键值对的数据结构

HashMap 适用于单线程环境或不需要线程安全的场景。
Hashtable 虽然是线程安全的，但由于其同步机制较粗，性能较差，通常不推荐使用。
ConcurrentHashMap 是线程安全的，并且在高并发环境下提供了更好的性能，是现代多线程应用中的首选。

特性/集合类	HashMap	Hashtable	ConcurrentHashMap
线程安全	否	是，基于方法锁	是，基于方法锁
继承关系	AbstractMap	Dictionary	AbstractMap、ConcurrentMap
允许null值	K-V都允许	K-V都不允许	K-V都不允许
默认初始容量	16	11	16
默认加载因子	0.75	0.75	0.75
扩容后容量	原来的两倍	原来的两倍+1	原来的两倍
是否支持fail-fast	支持	支持	fail-safe

注：当一个集合的迭代器在迭代过程中检测到集合的结构发生了改变（例如，添加或删除了元素），迭代器会立即抛出 ConcurrentModificationException 异常，而不是继续迭代。这种行为被称为“fail-fast”。

注：Hashtable “同步机制较粗”是指在实现线程安全时使用的同步机制粒度较大，通常是整个对象级别的同步。这意味着在多线程环境中，当一个线程正在访问 Hashtable 的某个方法时，其他线程必须等待，直到该方法执行完毕才能继续访问。这种同步机制会导致较高的锁竞争，从而影响并发性能。

注：ConcurrentHashMap 通过使用更细粒度的锁定机制来解决这个问题。它将整个数据结构分成多个段，每个段都有自己的锁。这样，多个线程可以同时访问不同的段，从而减少锁竞争，提高并发性能。

HashMap%20%E5%85%81%E8%AE%B8%E6%8F%92%E5%85%A5%20null%E9%94%AE%20%E5%92%8C%20null%20%E5%80%BC%EF%BC%9F">26、为什么 HashMap 允许插入 null键和 null 值？

因为 HashMap 设计是在单线程下使用的，而单线程可以证明真伪，它在进行查询判断的时候，不用担心有其他线程对这个值同时做修改，所以它不存在二义性问题，所以 HashMap 允许 key 和 value 都为 null。

说白了，HashMap设计的时候，就是为单线程设计的，它没考虑那么多，什么都按着单线程来的，单线程下，我能分得清这个null是本来就是空，还是后来被修改为了空(具体怎么分清不是我们需要考虑的，是java底层需要考虑的)

27、什么是二义性问题？

所谓的二义性问题是指含义不清或不明确。

如果我们假设 Hashtable 和 ConcurrentHashMap允许插入 nul，那么此时它就会有二义性问题，这个 null 值就有两层含义：

这个 key 不存在，所以返回 null
这个 key 存在，并且值本身就为 null，所以返回的就是 null

而在多线程下，你没有办法证明真伪，因为你在判断证明的时候，其他线程可能同时做了修改，所以不能被证明的二义性问题需要从源头上杜绝，所以多线程下的 Hashtable 和 ConcurrentHashMap是不允许 key 和 value 插入 null 值的。

HashMap%E4%B8%8D%E5%85%81%E8%AE%B8%E6%8F%92%E5%85%A5nuI%E9%94%AE%E5%92%8CnuI%E5%80%BC%3F">28、为什么Hashtable和ConcurrentHashMap不允许插入nuI键和nuI值?

浅层次讲，JDK源码不支持 Hashtable 和 ConcurrentHashMap 插入的 Key 和 Value值为null

插入 value 值为 null 就会抛出空指针异常。
插入 key 值为 null 的话，因为 null 没有 hashCode 所以它也会报空指针异常

深层次的原因就是，设计的 Hashtable 和ConcurrentHashMap 是在多线程下使用的，而如果 key 或 value 允许为 null 的话，那么程序就会存在二义性问题。

注：既然说了插入key值为null时报错是因为null没有hashCode，不知道将其往哪里插入，那为什么HashMap支持Key值为null呢？

因为 HashMap 处理 null 键的方式是特殊的。对于 null 键，HashMap 直接使用固定的索引位置，而不是调用 hashCode 方法。具体来说，HashMap 会在内部检查键是否为 null，如果是 null，则直接将其放在第一个桶中。

29、Hashtable是如何保证线程安全的?

非常简单粗暴！Hashtable 保证线程安全主要是通过给关键方法，例如 put 添加方法、remove 删除方法，添加 synchronized 加锁来保证线程安全的。

HashMap%E6%98%AF%E5%A6%82%E4%BD%95%E4%BF%9D%E8%AF%81%E7%BA%BF%E7%A8%8B%E5%AE%89%E5%85%A8%E7%9A%84%3F">30、ConcurrentHashMap是如何保证线程安全的?

ConcurrentHashMap 在不同 JDK 版本中，保证线程安全的手段是不同的，它主要分为以下两种情况：

JDK 1.7 之前(包含 JDK 1.7)，ConcurrentHashMap 主要是通过分段锁来保证线程安全的
而在 JDK 1.8 之后(包含 JDK 1.8)，使用了粒度更小锁，通过在数组的头节点加锁来保证线程安全的，并且加锁的手段也进行了优化，它使用的是 CAS + volatile 或 synchronized 来保证线程安全的

在JDK1.7中，ConcurrentHashMap使用了分段锁技术，即将哈希表分成多个段，每个段拥有一个独立的锁。这样可以在多个线程同时访问哈希表时，只需要锁住需要操作的那个段，而不是整个哈希表，从而提高了并发性能

虽然JDK 1.7的这种方式可以减少锁竞争，但是在高并发场景下，仍然会出现锁竞争，从而导致性能下降

在JDK 1.8中，ConcurrentHashMap的实现方式进行了改进，使用节点锁的思想，即采用“CAS+Synchronized”的机制来保证线程安全。在JDK1.8中，ConcurrentHashMap在添加元素时，如果某个段为空，那么使用CAS操作来添加新节点；如果段不为空，使用Synchronized锁住当前段（锁住当前数组头节点），再次尝试put。这样可以避免分段锁机制下的锁粒度太大，以及在高并发场景下，由于线程数量过多导致的锁竞争问题，提高了并发性能。

31、HashSet简介

前言：看下面这个关系图，需要注意，HashSet本质是set，是Collection的子类，不是Map的子类，存储的也是一个一个的值，不是Key-Value结构的数据，真要说像，用法上反而和ArrayList差不多，只是不能存储重复元素

不要和HashMap弄混！！！

Hashset 是 Java 集合框架中的一种数据结构，它实现了 set 接口。

Hashset 的主要特点包括：

无序性：Hashset 不保证元素的顺序，也就是说，当你遍历一个 Hashset 时，元素的顺序可能与插入顺序不同
唯一性：Hashset 中的元素是唯一的，不允许重复。当你尝试添加一个已经存在的元素时， Hashset 会忽略这个操作
基于哈希表实现：Hashset 底层使用哈希表(实际上是 HashMap)来存储元素。这意味着 Hashset 提供了常数时间复杂度 O(1)的平均性能用于基本的操作(添加、删除和查找)，前提是哈希函数能够均匀分布元素

HashSet<String> set = new HashSet<>();

一定要注意，存储的不是键值对类型哦

🧸前路漫漫，愿星光与您相伴！