Java篇：大厂Java集合（容器）高频面试题及参考答案

介绍Java集合框架（如ArrayList、LinkedList等），并对比它们的特点。

Java集合框架是一组用于存储和操作对象集合的类和接口。它提供了多种数据结构来满足不同的编程需求，包括List、Set、Map等不同类型的集合。

ArrayList的特点：

基于数组的动态结构：如前面所述，ArrayList基于数组实现，具有连续的内存存储空间。

随机访问高效：由于可以根据元素的索引直接定位到元素在内存中的位置，随机访问元素的时间复杂度为

O(1)。例如，在一个存储大量数据的ArrayList中，如果要获取第100个元素，能够快速定位到。

插入和删除操作的复杂性：在中间插入或删除元素时，需要移动后面的元素，时间复杂度为O(n)。

但在末尾插入元素比较简单，时间复杂度为O(1)。

除了存储元素本身，不需要额外的指针等结构来维护元素之间的关系，相对比较紧凑，内存占用主要取决于元素的大小和数量。

LinkedList的特点：

基于双向链表的结构：每个节点包含数据部分以及指向前一个节点和后一个节点的指针。

随机访问低效：要访问链表中的元素，需要从链表的头部或者尾部开始逐个遍历节点，随机访问的时间复杂度为O(n)。

插入和删除操作高效：在任意位置插入或删除元素只需要修改节点之间的指针关系，时间复杂度为O(1)。不过在进行这些操作之前可能需要先找到操作的节点，这个查找操作在最坏情况下的时间复杂度为O(n)。

内存占用：每个节点除了存储数据还需要存储两个指针，相对ArrayList来说，在存储相同数量元素时，内存占用可能会更多。

HashSet的特点：

基于HashMap实现：实际上是将元素作为HashMap的键，值是一个固定的虚拟值。

元素唯一性：不允许元素重复。利用HashMap的键的唯一性来保证元素的唯一性。

无序性（一般情况）：元素的存储顺序是不固定的，取决于哈希值和哈希冲突的处理结果。

查找、添加和删除操作的平均效率高：平均情况下，这些操作的时间复杂度为O(1)。

基于TreeMap实现：元素作为TreeMap的键，值为固定虚拟值。

有序性：元素是按照自然排序或者自定义的比较器确定的顺序存储的。

查找、添加和删除操作的效率：这些操作的时间复杂度为O(logn)，因为TreeMap是基于红黑树实现的。

LinkedHashSet的特点

继承自HashSet并添加顺序性：在HashSet的基础上，通过一个双向链表来记录元素的添加顺序。

查找操作：首先利用HashMap的哈希查找功能来快速定位元素可能存在的位置，平均时间复杂度为O(1)。

顺序遍历：在遍历元素时，可以按照元素添加的顺序进行遍历。

Java集合框架包含多种集合类型，主要分为三大类：List、Set和Map。

List集合

ArrayList：基于数组的动态列表，适用于随机访问频繁的场景，在末尾添加元素快速，中间插入和删除元素相对较慢，前面已经详细介绍过。

LinkedList：基于双向链表的列表，插入和删除操作在任意位置都比较高效，随机访问效率低，常用于需要频繁插入和删除元素的场景。

Set集合

HashSet：基于HashMap实现，保证元素的唯一性，元素无序，查找、添加和删除操作平均效率高，最坏情况下效率可能降低。

TreeSet：基于TreeMap实现，元素有序（按照自然排序或自定义比较器排序），查找、添加和删除操作的时间复杂度为

O(logn)。

LinkedHashSet：继承自HashSet，通过链表维护元素添加顺序，既具有HashSet的高效性，又能按照添加顺序遍历元素。

Map集合

HashMap：键值对存储结构，基于数组 + 链表（或红黑树）实现。通过键的哈希值来快速定位元素，平均情况下查找、添加和删除操作的时间复杂度为

O(1)，哈希冲突严重时可能退化为O(n)。

TreeMap：基于红黑树的键值对存储结构，键是有序的，查找、添加和删除操作的时间复杂度为O(logn)，适用于需要按照键的顺序进行操作的场景。

Hashtable：和HashMap类似，但Hashtable是线程安全的，不过由于它使用了较为重量级的同步机制，在性能上通常不如HashMap，在现代编程中较少使用。

请介绍ConcurrentHashMap，包括它如何保证线程安全。

ConcurrentHashMap是Java中用于多线程环境下的哈希表实现。它的设计目标是在高并发场景下提供高效的线程安全的哈希表操作。

从结构上来说，ConcurrentHashMap在Java 8之前采用了分段锁（Segment）的机制。它将整个哈希表分成多个段（Segment），每个段都是一个独立的哈希表，并且都有自己的锁。这样，在多线程并发访问时，不同的线程可以同时访问不同段中的元素，只要它们操作的是不同的段，就不会相互阻塞。例如，如果有两个线程，一个要对键值对A进行操作，另一个要对键值对B进行操作，并且A和B所在的段不同，那么这两个操作可以同时进行。

在Java 8之后，ConcurrentHashMap的结构进行了优化。它不再采用分段锁，而是采用了一种更细粒度的锁机制，即对每个哈希桶（数组中的每个元素）都可以单独加锁。这种设计进一步提高了并发度。当多个线程并发访问时，只要它们操作的不是同一个哈希桶，就可以并行执行。

在保证线程安全方面，当进行插入操作时，例如，一个线程要插入一个键值对，它会首先根据键的哈希值找到对应的哈希桶。如果此时没有其他线程在操作这个哈希桶，那么它就可以直接进行插入操作；如果有其他线程正在操作这个哈希桶，那么这个线程会等待，直到操作这个哈希桶的线程完成操作。同样，对于查找和删除操作，也遵循类似的规则，通过这种方式来确保在多线程环境下数据的一致性和正确性。

ConcurrentHashMap如何实现线程安全？

ConcurrentHashMap实现线程安全主要通过以下几个方面。

首先是它的锁机制。如前面提到的，在Java 8之前的分段锁和Java 8之后的对哈希桶的单独加锁机制。这种锁机制有效地控制了多线程对共享数据的并发访问。以Java 8之后的实现为例，当一个线程要对某个键值对进行操作时，它会根据键的哈希值确定要操作的哈希桶。如果这个哈希桶没有被其他线程锁定，那么这个线程就可以获取这个哈希桶的锁并进行操作。如果已经被锁定，这个线程就会等待，直到锁被释放。

其次是在并发操作的原子性保证上。例如在更新操作（如增加键值对的值或者替换键值对）中，ConcurrentHashMap使用了一些原子操作或者内部的同步机制来确保数据的一致性。即使在高并发的情况下，多个线程同时对同一个键值对进行更新操作，也不会出现数据不一致的情况。

另外，在遍历操作方面，ConcurrentHashMap也做了特殊的设计。当一个线程在遍历ConcurrentHashMap时，它不会被正在进行的插入、删除等操作所干扰。这是通过一些特殊的标记和版本控制机制来实现的。即使在遍历过程中有其他线程对哈希表进行了修改，遍历操作仍然能够正确地进行，不会出现遍历到一半数据突然改变或者抛出异常的情况。例如，当一个线程正在遍历一个包含多个键值对的ConcurrentHashMap时，另一个线程插入了新的键值对或者删除了某个键值对，这个正在遍历的线程依然可以按照原计划完成遍历，并且能够得到正确的结果。

ConcurrentHashMap的并发度大小是怎样的？ConcurrentHashMap的get方法是否上锁？

ConcurrentHashMap的并发度在不同版本有不同的体现。在Java 8之前，它采用分段锁（Segment）机制，并发度等于段（Segment）的数量。每个段都有自己的锁，不同的段可以被不同的线程同时访问，从而提高并发能力。例如，如果有16个段，理论上可以有16个线程同时对不同的段进行操作而互不干扰。

在Java 8之后，ConcurrentHashMap的并发度更加细粒度。它摒弃了分段锁，改为对每个哈希桶（数组中的元素）单独加锁。这使得并发度更高，只要不同的线程操作的不是同一个哈希桶，就可以并行执行。

关于ConcurrentHashMap的get方法，在Java 8之后的实现中，get方法通常不需要上锁。因为它采用了一种乐观的方式来进行读取操作。它主要通过对哈希桶的volatile修饰来确保数据的可见性。也就是说，在读取一个哈希桶中的元素时，由于volatile的保证，一个线程可以看到其他线程对这个桶中元素的修改。然而，如果在读取过程中发现哈希桶正在进行结构性的修改（如扩容或者元素的重新映射等），那么这个读取操作可能会有一些特殊的处理，但这种情况相对较少。总体而言，get方法的设计旨在在保证数据一致性的前提下，尽可能地提高读取的并发性能，减少不必要的锁竞争。

HashMap的结构，如果发生哈希冲突了怎么办？

HashMap是Java中的一个重要的数据结构，它是基于哈希表实现的。它的内部结构包含一个数组，数组中的每个元素都是一个链表（在Java 8之后，如果链表长度超过一定阈值会转化为红黑树来提高查找效率）。

当我们向HashMap中插入键值对时，首先会根据键的哈希值计算出它在数组中的索引位置。哈希函数会尽量保证不同的键有不同的哈希值，以便均匀地分布在数组中。但有时候不同的键可能会计算出相同的哈希值，这就产生了哈希冲突。

当发生哈希冲突时，在Java 8之前，会在该索引位置对应的链表上添加新的节点。这样，在查找元素时，就需要遍历这个链表来找到对应的键值对。在Java 8之后，如果链表的长度达到了8（默认值），并且数组的长度大于等于64，这个链表就会转化为红黑树。红黑树是一种自平衡的二叉查找树，它的查找、插入和删除操作的时间复杂度都是O(log n)，相比于链表的O(n)有了很大的提升。

在插入新元素时，如果遇到哈希冲突，它会判断当前节点是链表节点还是红黑树节点。如果是链表节点，就直接在链表末尾添加新节点；如果是红黑树节点，就按照红黑树的插入规则插入新节点。在查找元素时，同样会先根据哈希值找到对应的数组索引位置，然后如果是链表就遍历链表查找，如果是红黑树就按照红黑树的查找规则查找。

已知有代码HashMap get方法，它的时间复杂度是多少？

HashMap的get方法的时间复杂度在理想情况下是O(1)。这是因为它通过计算键的哈希值来直接定位到数组中的元素位置。然而，当发生哈希冲突时，情况会变得复杂一些。

如果发生哈希冲突并且是链表结构，那么在最坏的情况下，查找的时间复杂度会退化为O(n)，这里的n是链表的长度。因为需要遍历链表来找到对应的键值对。但在实际应用中，由于哈希函数的设计目的是尽量均匀地分布键值对，所以这种最坏情况很少发生。

在Java 8之后，如果哈希冲突导致链表转化为红黑树，那么查找的时间复杂度就变为O(log n)，其中n是红黑树中的节点数量。所以总体来说，虽然理论上存在最坏情况，但在正常使用中，由于哈希函数的特性以及对哈希冲突的优化处理，get方法的平均时间复杂度接近O(1)。

例如，当我们有一个存储了大量数据的HashMap，只要哈希函数能够较好地分散键值对，大多数情况下，get方法都能够快速定位到目标元素。即使偶尔发生哈希冲突，在链表长度较短或者转化为红黑树之后，查找的效率依然比较高。

看过HashMap的源码，除了resize之外，还有哪些设计给你留下深刻印象？如果hashCode和equals不一起重写，会有什么问题（从业务角度来说）？

除了resize操作，HashMap源码中的哈希函数设计和数据结构的转换机制也给人留下深刻印象。

哈希函数的设计是HashMap高效性的关键。它需要在尽可能短的时间内计算出一个较为均匀分布的哈希值。一个好的哈希函数能够使得不同的键有较大概率得到不同的哈希值，从而减少哈希冲突。这有助于提高HashMap的整体性能，无论是插入、查找还是删除操作。

数据结构的转换机制也很巧妙。如前面提到的，当链表长度达到一定阈值时转化为红黑树。这种自适应的设计使得HashMap能够在不同的数据规模和冲突频率下都保持较好的性能。它不需要用户手动去调整数据结构，而是根据实际的数据存储情况自动优化。

如果hashCode和equals不一起重写，从业务角度来看会有很多问题。假设我们有一个自定义的类作为HashMap的键。如果只重写了equals方法而没有重写hashCode方法，那么在计算哈希值时，可能会出现两个逻辑上相等（根据equals方法判断）的对象被分配到不同的哈希桶中。这会导致在查找元素时，可能无法正确地找到已经存储在HashMap中的对象。例如，在一个存储用户信息的HashMap中，我们以用户对象为键，如果没有正确重写这两个方法，可能会出现同一个用户被当作不同的键来处理，从而导致数据不一致或者重复存储等问题。另外，只重写hashCode方法而不重写equals方法也会导致类似的问题，因为哈希值相同的对象不一定是真正相等的对象，在比较时会出现错误的判断。

Hashtable、HashMap、ConcurrentHashMap的实现原理、底层结构、性能差异原因分别是什么？ConcurrentHashMap如何保证线程安全？put和map加锁时是怎么操作的（详细讲解）？

Hashtable

Hashtable是基于哈希表实现的。它通过计算键的哈希值来确定元素在哈希表中的存储位置。在存储和查找元素时，都会使用这个哈希值。它的底层是一个数组，数组中的每个元素是一个链表。当有新元素插入时，如果发生哈希冲突，新元素就会被添加到对应的链表中。Hashtable是线程安全的，它通过对整个哈希表加锁来实现线程安全。这就导致在多线程环境下，即使是不同键值对的并发操作，也需要等待锁的释放，从而严重影响了并发性能。例如，当一个线程在进行插入操作时，其他线程无论是插入、查找还是删除操作都必须等待，因为只有一把锁控制整个哈希表。

HashMap

和Hashtable类似，也是基于哈希表。通过哈希函数计算键的哈希值，然后确定在数组中的存储位置。如果发生哈希冲突，会采用链表（Java 8之后，链表过长会转化为红黑树）的方式解决。它的数组初始大小为16，当元素数量达到一定比例（负载因子 * 数组大小）时会进行扩容。HashMap是非线程安全的，这使得它在单线程环境下性能较好。因为没有线程安全的开销，在插入、查找和删除操作时不需要获取和释放锁。但是在多线程环境下，如果多个线程同时对HashMap进行操作，可能会导致数据不一致的问题。

ConcurrentHashMap

在Java 8之前，采用分段锁（Segment）机制，将哈希表分成多个段，每个段是一个独立的哈希表并带有自己的锁。Java 8之后，采用对每个哈希桶单独加锁的机制。在Java 8之前是分段的数组 + 链表结构，Java 8之后是数组 + 链表（或红黑树），但锁机制变为对哈希桶的单独加锁。它的性能优势在于高并发场景下的高效性。由于它的锁机制，无论是分段锁还是哈希桶单独加锁，都能在保证线程安全的前提下，允许不同的线程对不同的部分（段或者哈希桶）进行并发操作，大大提高了并发性能。在Java 8之后的put操作中，首先根据键的哈希值找到对应的哈希桶。如果这个哈希桶没有被其他线程锁定，就可以直接进行插入操作。如果已经被锁定，当前线程会等待，直到锁被释放。在插入过程中，如果发生哈希冲突，并且桶中的结构是链表，就按照链表的插入规则进行；如果是红黑树，就按照红黑树的插入规则进行。对于map操作（不太明确这里具体指的是map的哪种操作，如果是遍历映射操作），在遍历过程中，通过一些特殊的标记和版本控制机制，保证即使有其他线程对哈希表进行修改，遍历操作也能正确进行。

ArrayList的扩容机制以及删除操作的时间复杂度。

扩容机制

ArrayList是一种动态数组，它的容量是可以自动增长的。当我们创建一个ArrayList时，它会有一个初始容量（默认为10）。当向ArrayList中添加元素时，如果元素的数量达到了当前容量，就会触发扩容操作。扩容的过程是创建一个新的数组，这个新数组的大小通常是原来数组大小的1.5倍（在Java中具体实现是通过位运算，例如原来容量为10，新容量就是10 + 10 >> 1 = 15）。然后将原数组中的元素复制到新数组中，最后将新元素添加到新数组中。这个过程相对比较耗时，因为涉及到数组的创建和元素的复制。

删除操作的时间复杂度

对于ArrayList的删除操作，如果是根据索引删除元素，时间复杂度为O(n - i)，其中n是数组的长度，i是要删除元素的索引。这是因为在删除一个元素之后，需要将后面的元素向前移动来填补空缺。在最坏的情况下，当删除第一个元素时，需要移动n - 1个元素，所以时间复杂度为O(n)。如果是根据对象来删除元素，首先需要找到这个对象的索引，这个查找操作的时间复杂度在最坏情况下为O(n)，然后再进行删除操作，所以总体时间复杂度也是O(n)。

ArrayList和LinkedList的区别是什么？

ArrayList：是基于动态数组实现的。它在内存中是连续的存储空间，这使得它在随机访问元素时效率很高，因为可以通过索引直接计算出元素在内存中的地址。在数组中间插入或者删除元素时，需要移动后面的元素来填补空缺或者为新元素腾出空间。所以在中间位置插入和删除操作的时间复杂度为O(n)，其中n是数组的长度。在末尾插入元素的时间复杂度为O(1)，因为不需要移动其他元素。

LinkedList：是基于双向链表实现的。每个节点包含数据和指向前一个节点和后一个节点的指针。在内存中，节点的存储位置不是连续的。在链表中插入或者删除元素，只需要修改节点之间的指针关系。在任意位置插入和删除操作的时间复杂度都是O(1)，但需要先找到要操作的节点，这个查找操作的时间复杂度在最坏情况下为O(n)。

为什么常用ArrayList

在很多实际应用中，例如在对数据库查询结果进行缓存时，经常需要随机访问元素来获取特定的数据。ArrayList的随机访问效率高的优势就非常明显。ArrayList的连续内存布局符合计算机的局部性原理，对于CPU缓存和内存读取都比较友好。相比之下，LinkedList的节点分散存储，在访问元素时可能会导致更多的缓存未命中。ArrayList的使用相对简单，对于大多数不需要频繁在中间进行插入和删除操作的场景，它的性能和易用性都能满足需求。而且在一些Java的框架和库中，很多数据结构和算法都是基于数组的，ArrayList可以更好地与这些组件进行集成。

Java中的ArrayList了解吗？其插入元素的过程是怎样的？

ArrayList是Java中非常常用的一个类，用于存储和操作一组对象。

在末尾插入元素

如果是在ArrayList的末尾插入元素，过程相对简单。首先，ArrayList会检查当前的元素个数是否小于数组的容量。如果小于，就直接将新元素添加到数组的下一个空闲位置。例如，数组当前已经有5个元素，容量为10，那么新元素就会被添加到索引为5的位置。这个操作的时间复杂度为O(1)，因为不需要移动其他元素，只需要在数组末尾进行一次赋值操作。

在中间插入元素

当要在ArrayList的中间某个位置插入元素时，情况就比较复杂了。假设要在索引为3的位置插入一个元素。首先，ArrayList会检查当前的元素个数是否等于数组的容量。如果等于，就会触发扩容操作，这是一个比较耗时的过程，前面已经提到过，会创建一个新的、更大的数组，并把原数组中的元素复制到新数组中。

扩容完成后，从插入位置（这里是索引3）开始，将后面的元素依次向后移动一位，为新元素腾出空间。这意味着索引为3及以后的元素都要往后移动一个位置。然后，将新元素插入到索引为3的位置。这个过程中，移动元素的操作时间复杂度为O(n−i)，其中n是数组的长度，i是插入的索引位置。在最坏的情况下，比如在数组的开头插入元素（i=0），就需要移动所有的元素，时间复杂度为

O(n)。

HashMap 1.8的扩容流程是怎样的？

扩容流程如下：当HashMap中的元素个数达到了阈值（threshold）时，就会触发扩容操作。阈值的计算方式是：负载因子（load factor）乘以数组的容量（capacity）。默认的负载因子是0.75。

新的容量通常是原来容量的2倍。例如，原来的容量是16，那么新容量就是32。这是通过位运算来实现的，具体来说就是将原来的容量向左移一位（相当于乘以2）。

对于原来哈希表中的每个元素（键值对），都需要重新计算它在新哈希表中的索引位置。这是因为哈希桶的数量增加了，哈希函数计算出来的索引可能会发生变化。

在重新计算索引时，会根据元素的键的哈希值和新的容量来确定新的索引位置。如果是链表结构的哈希桶，会遍历链表中的每个节点，重新计算它们在新哈希表中的位置。如果是红黑树结构的哈希桶（在Java 8中，当链表长度达到一定阈值后会转化为红黑树），会对红黑树中的每个节点进行重新定位。

在重新计算索引之后，将原来哈希表中的元素迁移到新的哈希表中。这个过程需要注意的是，在多线程环境下，如果不进行特殊处理，可能会导致数据不一致的问题。但是HashMap本身不是线程安全的，所以在单线程环境下按照上述步骤进行数据迁移就可以了。

迁移过程中，如果在新的哈希表中发生了哈希冲突，对于链表结构，会按照链表的插入规则将元素添加到相应的链表中；对于红黑树结构，会按照红黑树的插入规则进行操作。

ArrayList是线程安全的吗？哪一步会导致线程不安全？

ArrayList不是线程安全的。当多个线程同时对ArrayList进行修改操作时，就可能会出现问题。例如，一个线程正在对ArrayList进行插入操作，而另一个线程同时在进行删除操作。在插入操作中，可能涉及到数组的扩容、元素的移动和赋值等操作。如果多个线程同时执行这些操作，可能会导致数据覆盖、数组越界或者其他不可预期的结果。比如，一个线程正在扩容数组并复制元素，另一个线程却在修改数组中的元素，这就可能会使复制的元素顺序错乱或者丢失。同样，在删除操作中，如果多个线程同时删除不同的元素，可能会导致元素的索引混乱。例如，一个线程删除了索引为3的元素，另一个线程可能还以为索引为3的元素存在，从而引发错误。

如何删除ArrayList中的偶数？

首先，创建一个ArrayList的迭代器对象。迭代器提供了一种安全的方式来遍历集合，并且可以在遍历过程中删除元素。

然后，使用迭代器的hasNext()方法来判断是否还有下一个元素。如果有，就使用next()方法获取下一个元素。

当获取到一个元素后，检查这个元素是否为偶数。如果是偶数，就使用迭代器的remove()方法来删除这个元素。迭代器的remove()方法会正确地处理元素的删除，并且不会引发像普通for循环中使用remove方法那样的并发修改异常（ConcurrentModificationException）。例如：

import java.util.ArrayList;
import java.util.Iterator;


public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);


        Iterator<Integer> iterator = list.iterator();
        while (iterator.hasNext()) {
            Integer num = iterator.next();
            if (num % 2 == 0) {
                iterator.remove();
            }
        }
        System.out.println(list);
    }
}

HashMap 1.8的get方法流程是怎样的？

在HashMap 1.8中，get方法主