Java集合面试题&知识点总结（下篇）

1、Java集合面试题问题

• 问题 41. 介绍一下 Map 集合，以及它有怎样的特性？
• 问题 42. 介绍一下 Java 中 HashMap 的实现原理
• 问题 43. 详细描述一下 HashMap 底层数据结构是怎样的？
• 问题 44. 详细描述一下 HashMap 扩容机制是怎样的？
• 问题 45. 为什么 HashMap 的扩容长度是 2 的幂次方？
• 问题 46. 为什么 HashMap 的加载因子为什么是 0.75？
• 问题 47. HashMap 是线程安全的吗？为什么？主要体现在哪些地方？
• 问题 48. HashMap 并发插入操作的是怎样导致数据结构混乱和形成环形链表的？
• 问题 49. 解决 Hash 冲突的办法有哪些？HashMap 用的哪种？
• 问题 50. 何 HashMap 用红黑树而不使用 AVL 树？
• 问题 51. HashMap 和 HashTable 有什么区别？
• 问题 52. 为什么 HashTable 不允许使用 null 键和 null 值，而 HashMap 可以？
• 问题 53. 介绍一下 Java 中 ConcurrentHashMap 的实现原理
• 问题 54. 详细描述一下 Java 8 之前的 ConcurrentHashMap 底层数据结构是怎样的？
• 问题 55. ConcurrentHashMap 在 Java8 以前的版本是如何保证线程安全的
• 问题 56. Java 8 中 ConcurrentHashMap 底层数据结构做了哪些改变？
• 问题 57. 介绍一下 Java 中 LinkedHashMap 的实现原理
• 问题 58. 介绍一下 Java 中 TreeMap 的实现原理
• 问题 59. 请解释一下 Java 中的 SortedMap
• 问题 60. 请解释一下 Java 中的 NavigableMap

2、Java集合面试题解答

2.1、JavaMap集合相关-特性&方法

• 问题 41. 介绍一下 Map 集合，以及它有怎样的特性？

解答：Map 是 Java 集合框架中的一个接口，它存储键值对（key-value）的数据结构。

以下是 Map 的一些特性：

1. Map 中的每个元素都包含一对键值对（key-value pair）。
2. Map 中的键（Key）是唯一的，但值（Value）可以重复。
3. Map 接口提供了三种集合视图，允许以键集、值集或键-值映射关系集的形式查看某个映射的内容。
4. Map 是线程不安全的，如果多个线程同时修改 Map，需要进行同步处理。

HashMap 和 TreeMap 是 Map 接口的两个主要实现类。HashMap 提供了基于哈希表的实现，它支持 null 键和 null 值，且不保证映射的顺序。TreeMap 提供了基于红黑树（Red-Black tree）的 NavigableMap 实现，它按照键的自然顺序或者自定义的比较器进行排序。

2.2、JavaMap集合相关-HashMap

• 问题 42. 介绍一下 Java 中 HashMap 的实现原理

解答：HashMap 是 Java 集合框架中的一个重要类，它基于哈希表实现，用于存储键值对。

以下是 HashMap 的实现原理：

1. 存储结构：HashMap 主要由数组和链表（或红黑树）组成。数组每个元素存储的是链表或红黑树的头节点，这样的数组被称为哈希桶。
2. 哈希函数：HashMap 通过哈希函数将键（Key）映射到哈希桶的索引位置，然后在对应的链表或红黑树中进行查找或插入。
3. 链表和红黑树：当哈希冲突发生时（即不同的键映射到同一索引位置），HashMap 会在对应的链表中进行查找或插入。当链表长度超过一定阈值（默认为 8）时，链表会转换为红黑树，以提高搜索效率。
4. 扩容：当 HashMap 中的元素数量超过哈希桶容量与加载因子（默认为 0.75）的乘积时，HashMap 会进行扩容操作，即创建一个新的哈希桶，容量是原来的两倍，并将原来哈希桶中的元素重新映射到新的哈希桶中。
5. null 键和 null 值：HashMap 允许使用 null 键和 null 值，null 键总是存储在哈希桶的第一个位置。
6. 无序性：HashMap 不保证元素的顺序，元素的存储顺序和键的哈希值有关。

以上就是 HashMap 的基本实现原理，它通过哈希表实现了高效的查找、插入和删除操作。

• 问题 43. 详细描述一下 HashMap 底层数据结构是怎样的？

解答：HashMap 的底层数据结构主要由数组（也称为哈希桶）和链表（或红黑树）组成。

1. 数组：数组是 HashMap 的主体，也是实现快速查找的关键。数组的每个位置被称为一个桶，每个桶可以存储一个或多个键值对（Entry）。
2. 链表：当通过哈希函数计算出的索引位置已经有数据存在时，新的键值对会被添加到链表的后面，这种情况被称为哈希冲突。
3. 红黑树：当链表中的元素数量超过一定阈值（默认为 8）时，链表会转换为红黑树，以提高搜索效率。红黑树是一种自平衡的二叉查找树，它可以保证任何一个节点到叶子节点的最长路径的长度不超过其他路径的两倍长度。

在 HashMap 中，数组的初始容量为 16，加载因子默认为 0.75，也就是说，当数组中的元素数量超过 12（16*0.75）时，数组会进行扩容，新的数组长度是原数组长度的两倍。

HashMap 通过哈希函数将键（Key）映射到数组的某个位置，如果出现哈希冲突，就将新的键值对添加到链表或红黑树中。这样，即使哈希函数不是很理想，链表长度过长，转换为红黑树后也能保证较高的查找效率。

• 问题 44. 详细描述一下 HashMap 扩容机制是怎样的？

解答：HashMap 的扩容机制是这样的：

1. HashMap 在初始化时，会有一个默认的容量（16）和一个加载因子（0.75）。
2. 当 HashMap 中的元素数量超过容量与加载因子的乘积（默认为 12）时，HashMap 就会进行扩容。
3. 扩容操作包括两个步骤：创建一个新的哈希桶，这个哈希桶的容量是原来的两倍；然后将原来哈希桶中的元素重新映射到新的哈希桶中。
4. 重新映射的过程需要重新计算元素的哈希值，因为哈希值是依赖于哈希桶的容量的。
5. 扩容操作是一个比较耗时的过程，因为它涉及到重新计算哈希值和数据的复制。在 HashMap 中添加大量数据时，如果能预估数据量并设置一个合适的初始容量，可以避免或减少扩容操作，从而提高性能。
6. 在多线程环境下，如果多个线程同时触发扩容操作，可能会导致 HashMap 中的数据结构混乱，这是 HashMap 线程不安全的一个主要原因。

• 问题 45. 为什么 HashMap 的扩容长度是 2 的幂次方？

解答：HashMap 的扩容长度选择 2 的幂次方，主要是为了优化哈希值的计算过程。

在 HashMap 中，元素的存储位置是通过哈希函数计算得到的。如果 HashMap 的容量为 2 的幂次方，那么哈希值的计算可以简化为：index = hashCode & (length-1)，这种位运算的效率要高于除法运算。

此外，选择 2 的幂次方作为扩容长度，还可以保证元素在扩容后重新分布的过程中，能够尽可能均匀地分布在新的哈希表中，从而减少哈希冲突，提高查询效率。

• 问题 46. 为什么 HashMap 的加载因子为什么是 0.75？

解答：HashMap 的加载因子（load factor）是用来衡量 HashMap 何时进行扩容的一个重要参数。加载因子的默认值是 0.75，这个值是在时间复杂度和空间复杂度之间进行权衡的结果。

1. 如果加载因子过高，比如接近或等于 1，那么 HashMap 中的元素会更加密集，哈希冲突的可能性会增加，这会导致查询性能下降。
2. 如果加载因子过低，比如接近或等于 0，那么 HashMap 中的元素会更加稀疏，这会导致空间浪费，因为 HashMap 的大部分位置都没有被利用。

0.75 是一个折中的选择，它在空间效率和时间效率之间达到了一个平衡。在这个加载因子下，哈希冲突的概率和空间利用率都是可以接受的。这个值是经过大量实践验证得出的，可以提供较好的性能。

• 问题 47. HashMap 是线程安全的吗？为什么？主要体现在哪些地方？

解答：首先可以明确的一点是，HashMap 不是线程安全的。这主要体现在以下几个方面：

1. 并发插入操作：如果多个线程同时对 HashMap 进行插入操作，并且触发了扩容，那么可能会导致 HashMap 的数据结构混乱，甚至可能形成环形链表，导致死循环。
2. 并发删除操作：如果一个线程正在遍历 HashMap，而另一个线程同时删除了一个元素，可能会导致 ConcurrentModificationException 异常。
3. 并发更新操作：如果多个线程同时对同一个键进行更新操作，可能会导致其中一个线程的更新结果被覆盖。

如果需要满足线程安全，可以用 Collections 的 synchronizedMap 方法使 HashMap 具有线程安全的能力，或者使用 ConcurrentHashMap，再或者就这 HsahTable ，不过 HashTable 显然是不如前二者的。

• 问题 48. HashMap 并发插入操作的是怎样导致数据结构混乱和形成环形链表的？

解答：在 HashMap 中，当元素数量超过容量与加载因子的乘积时，会触发扩容操作。扩容操作包括创建一个新的哈希桶，然后将原来哈希桶中的元素重新映射到新的哈希桶中。

在多线程环境下，如果多个线程同时触发了扩容操作，并且同时对同一个桶进行操作，可能会导致数据结构混乱和形成环形链表。

具体来说，当两个线程同时对同一个桶进行扩容操作时，它们可能会获取到相同的节点引用，并试图将这些节点插入到新的哈希桶中。由于线程执行的顺序无法预测，可能会出现一个线程将节点 A 的 next 指针指向节点 B，而另一个线程将节点 B 的 next 指针指向节点 A，从而形成一个环形链表。

当试图访问这个环形链表时，会导致无限循环，最终可能导致程序挂起。

这就是为什么 HashMap 不是线程安全的，如果需要在多线程环境下使用，可以选择 ConcurrentHashMap 或者使用 Collections.synchronizedMap 方法将 HashMap 包装为线程安全的 Map。

• 问题 49. 解决 Hash 冲突的办法有哪些？HashMap 用的哪种？

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

1. 开放定址法：当哈希函数返回的位置已经被占用时，可以寻找下一个空的哈希地址，直到找到为止。常见的开放定址法有线性探测、二次探测和双重哈希。
2. 链地址法：也称为拉链法，它是将哈希到同一位置的所有元素链接在一起，形成一个链表。
3. 再哈希法：当哈希冲突发生时，使用另一个哈希函数进行计算，直到冲突解决为止。
4. 建立公共溢出区：这种方法是将哈希表分为基本表和溢出表两部分，当基本表的某个位置已经被占用，那么发生冲突的元素就被放入溢出表中。

HashMap 使用的是链地址法（拉链法）来解决哈希冲突。当哈希冲突发生时，HashMap 会在对应的链表中进行查找或插入。当链表长度超过一定阈值（默认为8）时，链表会转换为红黑树，以提高搜索效率。

• 问题 50. 何 HashMap 用红黑树而不使用 AVL 树？

解答：HashMap 选择使用红黑树而不是 AVL 树的原因主要有以下几点：

1. 平衡性：AVL 树是高度平衡的，而红黑树是部分平衡的。在进行大量插入和删除操作时，AVL 树需要进行更多的旋转操作来维持平衡，效率较低。而红黑树的平衡性较差，但是旋转操作较少，效率较高。
2. 查找效率：由于 AVL 树更平衡，理论上查找效率会更高。但是在实际应用中，由于 HashMap 的哈希冲突并不会非常严重，所以红黑树的查找效率已经可以满足需求。
3. 空间占用：红黑树的节点只需要存储 1 位的颜色信息，而 AVL 树需要存储节点的高度或者平衡因子，需要更多的空间。
4. 实现复杂度：红黑树的实现相比 AVL 树来说更简单一些。

综上，HashMap 选择红黑树作为其底层数据结构是一个权衡效率、空间和实现复杂度的结果。

2.3、JavaMap集合相关-HashTable

• 问题 51. HashMap 和 HashTable 有什么区别？

解答：HashMap 和 HashTable 都是 Java 集合框架中的类，都实现了 Map 接口，用于存储键值对，但是它们之间存在一些重要的区别：

1. 线程安全性：HashTable 是线程安全的，它的大部分方法都使用了 synchronized 关键字进行同步，可以在多线程环境下使用。而 HashMap 是非线程安全的，如果需要在多线程环境下使用，可以使用 Collections.synchronizedMap 方法将 HashMap 包装为线程安全的 Map，或者使用 ConcurrentHashMap。
2. 允许 null 键和 null 值：HashMap 允许使用 null 键和 null 值，而 HashTable 不允许。
3. 性能：由于 HashTable 使用了 synchronized 进行同步，所以在单线程环境下，HashMap 的性能会优于 HashTable。
4. 继承的父类：HashMap 继承自 AbstractMap 类，而 HashTable 继承自 Dictionary 类。
5. 初始容量和加载因子：HashMap 的默认初始容量是 16，加载因子是 0.75。HashTable 的默认初始容量是 11，加载因子是 0.75。

• 问题 52. 为什么 HashTable 不允许使用 null 键和 null 值，而 HashMap 可以？

解答：HashTable 和 HashMap 对 null 键和 null 值的处理不同，主要是因为它们的设计和实现方式不同。

在 HashTable 中，键和值都是通过 equals() 和 hashCode() 方法来进行比较和哈希值计算的。如果键或值为 null，那么在调用这些方法时就会抛出 NullPointerException。因此，为了避免这种异常，HashTable 在设计时就规定了不允许 null 键和 null 值。

而在 HashMap 中，对 null 键和 null 值做了特殊处理。对于 null 键，HashMap 会将其存储在哈希表的一个特定位置，而不是通过计算哈希值来确定位置。对于 null 值，HashMap 允许其存在，因为它并不依赖于值的 hashCode 方法。

这样的设计使得 HashMap 可以灵活地处理 null 键和 null 值，而不会导致 NullPointerException。

2.4、JavaMap集合相关-ConcurrentHashMap

• 问题 53. 介绍一下 Java 中 ConcurrentHashMap 的实现原理

解答：ConcurrentHashMap 是 Java 中的一个线程安全的哈希表实现，它通过分段锁技术来实现高效的并发更新。

1. 分段锁：在 ConcurrentHashMap 中，整个哈希表被分为多个段（Segment），每个段都有自己的锁。当需要更新哈希表时，只需要锁定相关的段，而不是整个哈希表。这样，不同段的更新操作可以并发进行，提高了并发性能。
2. 哈希函数：ConcurrentHashMap 使用了一个特殊的哈希函数，可以将相同的键哈希到同一个段中。这样，如果多个线程更新的是不同段的数据，那么这些更新操作就可以完全并发进行。
3. 扩容：当某个段的元素数量超过阈值时，该段会进行扩容。扩容操作只锁定当前段，不会影响其他段的读写操作。
4. 非阻塞算法：在 ConcurrentHashMap 的实现中，读操作完全不需要加锁，因为它使用了一种叫做“安全发布”的技术来保证并发读的安全性。此外，ConcurrentHashMap 还使用了一种叫做"CAS（Compare and Swap）"的非阻塞算法来实现计数器和其他功能。

以上就是 ConcurrentHashMap 的基本实现原理。通过这些技术，ConcurrentHashMap 在保证线程安全的同时，实现了高效的并发性能。

• 问题 54. 详细描述一下 Java 8 之前的 ConcurrentHashMap 底层数据结构是怎样的？

解答：ConcurrentHashMap 的底层数据结构主要由两部分组成：Segment 数组和 HashEntry 数组。

1. Segment 数组：ConcurrentHashMap 将整个哈希表分为多个段（Segment），每个 Segment 是一个独立的子哈希表，拥有自己的锁。这样，多线程环境下对不同 Segment 的操作可以并发进行，提高了并发性能。Segment 数组的大小默认为16，也就是说默认情况下 ConcurrentHashMap 会被分为16个 Segment。
2. HashEntry 数组：每个 Segment 内部包含一个 HashEntry 数组，也就是哈希桶。每个 HashEntry 包含一个键、一个值和一个指向下一个 HashEntry 的引用，形成了链表结构。当发生哈希冲突时，新的元素会被添加到链表的头部。

在 ConcurrentHashMap 中，通过哈希函数计算出元素的哈希值，然后根据哈希值确定元素在 Segment 数组中的位置，再根据哈希值确定元素在 HashEntry 数组中的位置。这样，就可以快速定位到元素的存储位置。

这就是 ConcurrentHashMap 的底层数据结构。通过这种结构，ConcurrentHashMap 实现了高效的并发操作和良好的扩展性。

• 问题 55. ConcurrentHashMap 在 Java8 以前的版本是如何保证线程安全的

解答：在 Java 8 之前的版本中，ConcurrentHashMap 主要通过"分段锁"（Segment）机制来保证线程安全。

ConcurrentHashMap 的整个哈希表被分为多个段（Segment），每个段都有自己的锁。每个 Segment 实质上就是一个小的哈希表，它包含一个 HashEntry 数组和一个计数器，用于记录该段中的元素数量。

当需要对 ConcurrentHashMap 进行修改操作（如 put、remove 等）时，只需要锁定相关的 Segment，而不是整个哈希表。这样，不同 Segment 的更新操作可以并发进行，提高了并发性能。

如果多个线程同时对同一个 Segment 进行修改操作，那么这些线程会进行竞争，只有获得该 Segment 锁的线程才能进行修改操作，其他线程会被阻塞等待。

对于读操作（如 get），ConcurrentHashMap 则完全无锁，因为各个 Segment 是相互独立的，不会影响到其他 Segment。

这就是 ConcurrentHashMap 在 Java 8 之前的版本中保证线程安全的主要机制。通过这种方式，ConcurrentHashMap 在保证线程安全的同时，实现了高效的并发操作。

• 问题 56. Java 8 中 ConcurrentHashMap 底层数据结构做了哪些改变？

解答：在 Java 8 中，ConcurrentHashMap 的底层数据结构做了以下主要改变：

1. 取消了 Segment 数组：在 Java 7 及其之前的版本中，ConcurrentHashMap 使用一个 Segment 数组来分段存储数据，每个 Segment 有自己的锁，可以实现部分并发。但在 Java 8 中，取消了 Segment 数组，整个 ConcurrentHashMap 只有一个 Node 数组。
2. 引入了红黑树：在 Node 数组中，每个元素仍然是一个链表，但当链表的长度超过一定阈值（默认为 8）时，链表会被转换为红黑树。这是因为红黑树的查找效率比链表更高，当元素数量较多时，使用红黑树可以提高性能。当红黑树的节点数量减少到一定程度（默认为 6）时，红黑树会被转换回链表。
3. 并发控制：Java 8 的 ConcurrentHashMap 不再使用 Segment 数组来实现并发控制，而是引入了一种新的并发控制机制。在进行更新操作时，ConcurrentHashMap 会尝试使用 CAS 操作来实现无锁更新。如果 CAS 操作失败，那么 ConcurrentHashMap 会使用内置的锁进行同步。

这些改变使得 ConcurrentHashMap 在保证线程安全的同时，实现了更高的并发性能和更好的扩展性。

• 问题 57. 介绍一下 Java 中 LinkedHashMap 的实现原理

解答：LinkedHashMap 是 HashMap 的一个子类，它保留了 HashMap 的所有特性，同时还增加了一些新的特性。

1. 双向链表：LinkedHashMap 在内部维护了一个双向链表，用于记录元素的插入顺序或者访问顺序。每次插入新元素，或者访问已有元素（如果构造函数的 accessOrder 参数为 true）时，都会将元素移动到双向链表的尾部。这样，当我们遍历 LinkedHashMap 时，就可以按照元素的插入顺序或者访问顺序进行遍历。
2. 继承自 HashMap：LinkedHashMap 继承自 HashMap，因此它也使用哈希表作为主要的数据结构，拥有 HashMap 的所有特性，如快速的查找、插入和删除操作。
3. 重写了部分方法：LinkedHashMap 重写了 HashMap 的部分方法，如 newNode、afterNodeAccess 等，以实现双向链表的维护。
4. 支持 LRU 算法：如果 LinkedHashMap 的构造函数的 accessOrder 参数为 true，那么就可以实现最近最少使用（LRU）算法。当 LinkedHashMap 的大小超过最大容量时，可以通过重写 removeEldestEntry 方法，自动删除最不常访问的元素。

以上就是 LinkedHashMap 的实现原理。通过这种方式，LinkedHashMap 在保证快速查找的同时，还能按照一定的顺序遍历元素，非常适合用于实现缓存等需要保持顺序的场景。

2.5、JavaMap集合相关-TreeMap

• 问题18. 介绍一下 Java 中 TreeMap 的实现原理

解答：TreeMap 是 Java 中的一个基于红黑树实现的 Map 接口，它能够按照键（Key）的自然顺序或者自定义顺序进行排序。

1. 红黑树：TreeMap 的底层数据结构是红黑树，红黑树是一种自平衡的二叉查找树。在红黑树中，每个节点都包含了一个键值对，节点之间的排序关系由键决定。
2. 排序：TreeMap 中的元素可以按照键的自然顺序进行排序，也可以在构造 TreeMap 时传入一个 Comparator 对象，按照自定义的顺序进行排序。
3. 操作：TreeMap 提供了一系列的操作方法，如 put、get、remove 等。这些方法的实现都是基于红黑树的相关操作，因此 TreeMap 的大部分操作的时间复杂度都是 O(log n)。
4. 非线程安全：TreeMap 是非线程安全的，如果需要在多线程环境下使用，可以使用 Collections.synchronizedSortedMap 方法来获取一个线程安全的 SortedMap。

以上就是 TreeMap 的实现原理。通过这种方式，TreeMap 在保证操作效率的同时，还能按照一定的顺序遍历元素，非常适合用于需要排序的场景。

2.6、JavaMap集合相关-SortedMap

• 问题 59. 请解释一下 Java 中的 SortedMap

解答：SortedMap 是 Java 集合框架中的一个接口，它是 Map 接口的子接口，用于创建可以自动排序的映射。

SortedMap 中的键可以按照自然顺序或者自定义的比较器（Comparator）进行排序。SortedMap 接口中定义了一些额外的方法，如 firstKey()、lastKey()、headMap()、tailMap() 等，用于获取映射中的第一个键、最后一个键、给定键之前的所有键值对、给定键之后的所有键值对等。

TreeMap 是 SortedMap 接口的一个实现类，它是基于红黑树实现的。TreeMap 保证了所有的键值对按照键的顺序进行排序，无论是插入时的顺序如何。

以上就是 SortedMap 的基本概念。它是用于创建可以自动排序的映射，提供了丰富的方法来操作排序后的键值对。

2.7、JavaMap集合相关-NavigableMap

• 问题 60. 请解释一下 Java 中的 NavigableMap

解答：NavigableSet 是 Java 集合框架中的一个接口，它是 SortedSet 接口的子接口，用于创建可以进行导航（如获取给定元素的上一个元素、下一个元素等）的集合。

NavigableSet 接口中定义了一些额外的方法，如 lower()、higher()、floor()、ceiling()、pollFirst()、pollLast() 等，用于获取给定元素的上一个元素、下一个元素、小于等于给定元素的最大元素、大于等于给定元素的最小元素、移除并返回第一个元素、移除并返回最后一个元素等。

TreeSet 是 NavigableSet 接口的一个实现类，它是基于红黑树实现的。TreeSet 保证了所有的元素按照元素的顺序进行排序，无论是插入时的顺序如何。

以上就是 NavigableSet 的基本概念。它是用于创建可以进行导航的集合，提供了丰富的方法来操作排序后的元素。