Java 面试题 - 集合篇

Java 集合体系

Collection 接口

它是集合框架的根接口，定义了一组集合框架通用的共性功能，用于操作集合中的元素，如添加、删除、遍历等。常见的实现类有List、Set和Queue。

List 接口

它是有序的集合，可以包含重复的元素。常见的实现类有 ArrayList、LinkedList 和 Vector。

ArrayList

基于数组实现，非线程安全的，它允许有重复元素和 null 值，适用于需要快速随机访问元素的情况，但在插入和删除元素时效率较低。

LinkedList

基于链表实现，它允许有重复元素和 null 值，适用于需要在列表中频繁地进行插入、删除操作的情况。由于它是基于链表实现的，所以在随机访问元素时效率较低。

Vector

基于数组实现，类似于 ArrayList，但与 ArrayList 不同的是，Vector 是线程安全的，所有对其的操作都是同步的。由于需要同步，因此效率不如 ArrayList。

实现类	基础数据结构	线程安全	允许重复元素和null值	适用场景
ArrayList	数组	否	是	快速随机访问元素
LinkedList	链表	否	是	频繁的插入、删除操作
Vector	数组	是	是	需要线程安全的情况

Set 接口

它是不允许包含重复元素的集合。常见的实现类有HashSet、LinkedHashSet 和 TreeSet。

HashSet

基于哈希表实现，它不保证集合中元素的顺序，允许使用 null 元素，不允许集合中有重复的值，使用该方式时需要重写 equals()和 hashCode()方法。

LinkedHashSet

继承与 HashSet，同时又基于 LinkedHashMap 来进行实现，底层使用的是 LinkedHashMp，LinkedHashSet 同样不允许有重复元素，但允许有一个 null 元素。

TreeSet

基于红黑树的 Set 实现类，它可以确保集合元素处于有序状态。TreeSet 会对集合中的元素进行排序。TreeSet 不允许使用 null 元素，并提供了 log(n) 时间复杂度的添加、删除和包含操作。

实现类	基础数据结构	是否有序	是否允许重复元素和null值	时间复杂度
HashSet	哈希表	否	否	O(1)
LinkedHashSet	哈希表+链表	是	否(允许有一个null)	O(1)
TreeSet	红黑树	是	否	O(log n)

Queue 接口

它是一种特殊的集合，用于存储待处理的元素，并按照一定规则进行访问。常见的实现类有 LinkedList 和 PriorityQueue。

LinkedList

使用双向链表实现的Queue接口，可用作队列（先进先出）或双向队列（可以在队列两端进行插入和删除操作）。

PriorityQueue

优先级队列的实现类，根据元素的自然排序或者指定的比较器对元素进行排序，取出时将先取出最小（或最大）的元素。

实现类	数据结构	队列类型	排序方式
LinkedList	双向链表	队列/双向队列	无
PriorityQueue	数组/堆	优先级队列	自然排序或指定比较器排序

Map 接口

它是一种键值对的集合，它的键不能重复值可以重复。常见的实现类有 HashMap、TreeMap 和 LinkedHashMap。

HashMap

是基于哈希表的 Map 接口实现类，提供了快速的查找、插入和删除操作。不保证元素的顺序，它允许使用null作为键和值，并且是非同步的。

TreeMap

是基于红黑树的 Map 接口实现类，会对键进行排序，默认是按照键的自然顺序排列，可以确保键值对处于有序状态，不允许使用 null 作为键，但允许值为 null。

LinkedHashMap

是 HashMap 的一个子类，它通过双向链表维护键值对的插入顺序，因此可以保证遍历时的顺序和插入的顺序一致。LinkedHashMap 同样不保证键值对的自然顺序。

ConcurrentHashMap

HashMap的线程安全版本，采用分段锁来实现线程安全，使得多线程可以并发地读取和修改Map。性能比较HashMap低，但适合多线程并发的场景。

• 线程安全：ConcurrentHashMap 使用了一种称为分段锁（Segment）的机制来实现线程安全。内部将整个数据结构分成多个段（Segment），每个段维护自己的一部分数据，不同的线程可以同时访问不同的段，从而实现并发读写操作而不需要对整个数据结构加锁。
• 高并发性能：由于使用了分段锁的机制，ConcurrentHashMap 在多线程并发读写的场景下能够提供较高的性能。不同线程可以同时访问不同的段，从而减少了锁的竞争，提高了并发读写的效率。
• 无序性：与 HashMap 类似，ConcurrentHashMap 也不保证键值对的顺序。如果需要有序的遍历，可以考虑使用 ConcurrentHashMap 的一种变种 ConcurrentHashMap.KeySetView 或者使用其他有序的数据结构。
• 支持高效的并发更新：ConcurrentHashMap 提供了一些并发更新的方法，如 putIfAbsent()、remove() 和 replace() 等。这些方法可以在多线程环境下安全地进行更新操作，而不需要额外加锁。

需要注意的是，虽然 ConcurrentHashMap 是线程安全的，但并不意味着所有操作都是原子的。例如，复合操作（如 get() 和 put() 的组合）仍然需要额外的同步措施来确保原子性。

总之，ConcurrentHashMap 是一种线程安全的哈希表实现，通过分段锁机制实现高效的并发读写操作，在多线程环境下能够提供较高的性能。

HashTable

Hashtable 是遗留类，很多映射的常用功能与 HashMap 类似，不同的是它承自 Dictionary 类，并且是线程安全的，任一时间只有一个线程能写Hashtable，并发性不如 ConcurrentHashMap，因为 ConcurrentHashMap引入了分段锁。

Hashtable 不建议在新代码中使用，不需要线程安全的场合可以用 HashMap 替换，需要线程安全的场合可以用 ConcurrentHashMap 替换。

实现类	基础数据结构	是否允许null键和值	是否有序	线程安全	时间复杂度
HashMap	哈希表	是	否	非同步	O(1)
TreeMap	红黑树	否（值允许null）	是	非同步	O(log n)
LinkedHashMap	哈希表+链表	是	是	非同步	O(1)
ConcurrentHashMap	哈希表+分段锁	是	否	是	O(1)
Hashtable	哈希表	不推荐使用	否	是	O(1)

注：哈希表的时间复杂度 O(1) 是指在理想情况下，具体时间复杂度可能因哈希冲突等因素而有所不同。

Iterator 接口

它是一个用于遍历集合中元素的接口 ，主要包含hashNext()，next()，remove()三种方法。如果实现 Iterator 接口，那么在遍历集合中元素的时候，只能往后遍历，被遍历后的元素不会在遍历到，通常无序集合实现的都是这个接口，比如 HashSet，HashMap。

HashSet 的实现原理

HashSet是基于哈希表实现的Set接口的一个实现类。它使用了HashMap来存储元素，HashSet中的元素被存储为HashMap的key，而HashMap中的value则使用一个固定的常量PRESENT来表示，这样实际上整个HashSet中的元素都存储在了HashMap的key中。

HashSet的实现原理大致可以分为以下几个步骤：

1. 当我们向HashSet中添加一个元素时，HashSet会调用该元素的hashCode()方法来获取其哈希码。
2. HashSet会根据元素的哈希码，使用哈希函数来计算出该元素在HashMap中的存储位置。
3. 如果在计算出的位置上已经存在了其他元素，那么会通过equals()方法来比较这两个元素是否相等。如果不相等，就会发生哈希冲突，这时会使用开放寻址法或者链地址法等处理方式来解决冲突。
4. 如果该位置上没有元素，或者哈希冲突后成功插入新元素，那么HashSet就会将该元素作为HashMap的key存储，并将固定的PRESENT作为value存储。

这样一来，HashSet通过使用哈希表来存储元素，能够提供高效的插入、查找和删除操作，时间复杂度接近O(1)。并且HashSet中的元素是不允许重复的，因为HashMap中的key是唯一的。

Set 中存储的数据是无序的，且不允许有重复，但元素在集合中的位置由元素的 hashcode 决定，位置是固定的（Set 集合根据 hashcode 来进行数据的存储，所以位置是固定的，但是位置不是用户可以控制的，所以对于用户来说 set 中的元素还是无序的）。

HashMap 底层实现原理

在早期版本（如JDK1.7）中，HashMap的底层实现主要包括一个Table数组和多个Entry链表。具体来说，Table数组中的每个元素都是一个链表，用于解决哈希冲突问题。当两个不同的键被哈希到同一个索引位置时，它们会分别插入到对应的链表中。

但是，这种实现方式在处理大量数据时存在一些问题，例如链表长度过长会影响查找效率。因此，从JDK1.8开始，HashMap的底层实现进行了优化。主要的变化包括引入了红黑树作为另一种存储结构，以及优化了扩容策略。当链表的长度超过 8 则转为红黑树, 当红黑树中的元素小于 6 时又变为链表，以提高查找效率。

HashMap是怎么解决哈希冲突的

哈希是指通过哈希算法将任意长度的输入数据映射成固定长度的输出值，该输出值通常被称为哈希值。哈希算法是一种将数据转换成固定长度值的方法，这个过程是单向的，不可逆的。

哈希冲突指的是当两个不同的输入值经过同一个哈希算法得到相同的哈希值的情况。在实际应用中，由于哈希算法输出值的范围通常是有限的，因此不同的输入值有可能会产生相同的哈希值。

• 拉链法（Chaining）：当发生哈希冲突时，HashMap会在相应的桶（数组位置）上维护一个链表或者红黑树。这意味着对于相同哈希值的键值对会被存储在同一个桶位置上，通过链表或者红黑树进行存储冲突的键值对。这样，当需要添加或查找一个键值对时，HashMap会通过哈希函数找到对应的桶，然后遍历链表或者红黑树来找到需要的键值对。
• 开放寻址法（Open Addressing）：当发生哈希冲突时，HashMap会通过一个探测序列来寻找下一个可用的槽位，直到找到一个空的槽位来存储冲突的键值对。开放寻址法包括线性探测、二次探测、双重散列等方法来解决哈希冲突。

这两种方法都能有效地解决哈希冲突问题，保证了HashMap的性能和准确性。在Java中，HashMap使用的是拉链法来解决哈希冲突，并在特定条件下会将链表转换为红黑树来提高查找效率。

HashMap的put方法的具体流程

• 首先，根据键的hashCode()方法计算键的哈希值。
• 然后，根据哈希值和HashMap的容量，使用哈希函数计算出键值对应的槽位（数组位置）的索引值。
• 如果该槽位上没有存储其他键值对，直接将键值对存储在该槽位上。如果已经有键值对存在，进入步骤4。
• 如果已经存在键值对，可能发生哈希冲突。HashMap会使用键的equals方法来比较新插入的键和已存储的键，如果键相等，替换对应的值；如果键不相等，即发生哈希冲突，则根据HashMap采用的解决冲突方法（如拉链法），将新的键值对插入到对应的槽位上（可能是链表或红黑树的形式）。

HashMap 扩容

默认情况下，HashMap的容量为16，加载因子为0.75，阈值则是容量与加载因子的乘积。当元素数量增加并触发扩容条件时，HashMap会创建一个新的Entry数组，通常是原数组的两倍大，然后将原来的元素重新哈希到新的数组中。

值得注意的是，由于扩容后数组的大小变化，可能会导致一些元素的下标发生改变。但是，HashMap处理这个问题的方法非常巧妙：它会将发生冲突的元素都放到新数组的同一个位置上，这个位置是通过原下标与新数组长度取模得到的。

此外，在多线程环境下，HashMap的扩容操作可能会引发问题。因为在扩容过程中，需要进行复制原数据到新数组的操作，如果此时有其他线程正在进行写操作，可能会导致环形链表的产生，进而引发死循环。因此，对HashMap的操作需要特别注意线程安全。

概括地讲：扩容需要重新分配一个新数组，新数组的长度是老数组的2倍，然后遍历整个老数组，把所有的元素挨个重新hash分配到新数组中去。PS：可见底层数据结构用到了数组，到最后会因为容量问题都需要进行扩容操作。

为何HashMap的数组长度一定是2的次幂

HashMap的数组长度一定是2的次幂的原因主要是为了提高HashMap的性能和效率。

首先，2的次幂长度的数组可以通过位与运算来计算索引位置，这样可以让哈希值在数组中的分布更加均匀，减少哈希碰撞的概率，提高存取数据的效率。

同时，2的次幂长度的数组在扩容时也能更加高效地调整数组大小，通过位运算来确定元素的新位置，实现了扩容操作的高效性。

此外，2的次幂长度的数组也有利于减少哈希碰撞，使得数据能够均匀地分配在不同的链表或红黑树中，进一步提高HashMap的性能和效率。

综上所述，HashMap选择2的次幂作为数组长度是为了优化存取数据的效率，减少哈希碰撞，提高HashMap的性能。

HashSet 和 TreeSet 区别

特点	HashSet	TreeSet
内部实现方式	基于哈希表实现，使用HashMap来存储元素	基于红黑树实现
元素顺序	不保证元素顺序，使用哈希码来存储和检索元素	保证元素有序，根据自然顺序或自定义的Comparator排序
元素唯一性	保证元素的唯一性，不允许重复元素	保证元素的唯一性
性能	添加、删除和查找单个元素性能较好（O(1)）	区间查找和有序遍历性能较好（O(log n)）

HashMap 和 HashSet 区别

特点	HashMap	HashSet
存储方式	键值对的集合，通过键来访问对应的值	基于HashMap实现，存储唯一的元素，没有键值对的概念
元素存储方式	元素以键值对形式存储，每个元素包含一个键和一个值	元素以单个对象存储，没有键值对的概念
重复元素	键是唯一的，值可以重复	元素是唯一的，不允许重复元素
性能	具有高效的增删改查操作，操作平均时间复杂度为 O(1)	利用哈希表实现，具有类似于HashMap的高效性能

HashMap，HashTable，ConcurrentHashMap 之间的区别及性能对比

• 线程安全性：
  • HashMap：HashMap是非线程安全的，多个线程同时操作HashMap可能导致数据不一致的问题。
  • HashTable：HashTable是线程安全的，使用同步机制确保在多线程环境下的并发安全性。但是同步机制会影响性能。
  • ConcurrentHashMap：ConcurrentHashMap是线程安全的，采用了更加精细的锁机制，比HashTable在多线程环境下具有更好的并发性能。
• 允许 null 键和值：
  • HashMap：HashMap允许使用null作为键和值。
  • HashTable：HashTable不允许使用null作为键或值，否则会抛出NullPointerException。
  • ConcurrentHashMap：ConcurrentHashMap允许使用null作为键或值。
• 继承关系：
  • HashMap：HashMap是AbstractMap类的子类，同时实现了Map接口。
  • HashTable：HashTable是Dictionary类的子类，而Dictionary是一个抽象类。
  • ConcurrentHashMap：ConcurrentHashMap是AbstractMap类的子类，同时实现了ConcurrentMap接口。
• 迭代器：
  • HashMap：HashMap使用迭代器（Iterator）进行遍历，并支持在迭代过程中进行元素的删除操作。
  • HashTable：HashTable使用枚举器（Enumeration）进行遍历，不支持在迭代过程中进行元素的删除操作。
  • ConcurrentHashMap：ConcurrentHashMap同样使用迭代器进行遍历，并支持在迭代过程中进行元素的删除操作。
• 扩容机制：
  • HashMap：HashMap内部使用了扩容机制，可以动态调整容量以适应元素的增加。
  • HashTable：HashTable的容量是固定的，无法自动扩容，需要手动调整初始容量。
  • ConcurrentHashMap：ConcurrentHashMap也支持动态扩容，可以根据元素的增加自动调整容量。

性能对比：

• 在单线程环境下，HashMap的性能通常优于HashTable，因为HashMap不需要进行同步操作。
• 在多线程环境下，ConcurrentHashMap的性能通常优于HashTable，因为ConcurrentHashMap采用了更细粒度的锁机制，允许多个线程同时读取数据，并发性能更好。

总的来说，对于新的代码开发，推荐使用HashMap或ConcurrentHashMap，具体选择取决于是否需要线程安全性。如果需要线程安全性，且并发量较低，可以选择HashTable；如果并发量较高，可以选择ConcurrentHashMap。而如果不需要线程安全性，可以选择性能更好的HashMap。

特点	HashMap	ConcurrentHashMap	HashTable
线程安全性	非线程安全	线程安全	线程安全
允许 null	键和值均允许使用null	键和值均允许使用null	不允许使用null
继承关系	继承自AbstractMap类，实现了Map接口	继承自AbstractMap类，实现了ConcurrentMap接口	继承自Dictionary类，Dictionary是抽象类
迭代器	使用迭代器进行遍历，并支持删除操作	使用迭代器进行遍历，并支持删除操作	使用枚举器进行遍历，不支持删除操作
扩容机制	内部使用了扩容机制	支持动态扩容	容量固定，无法自动扩容