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，在现代编程中较少使用。

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方法也会导致类似的问题，因为哈希值相同的对象不一定是真正相等的对象，在比较时会出现错误的判断。

请介绍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方法的设计旨在在保证数据一致性的前提下，尽可能地提高读取的并发性能，减少不必要的锁竞争。

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方法主要用于根据给定的键（key）查找对应的值（value）。其流程如下：

首先，计算给定键的哈希值。这个哈希值是通过键对象的hashCode方法计算得到的，然后经过一些内部的哈希函数处理，目的是为了让哈希值能够在数组范围内均匀分布。例如，对于一个自定义的键类，它需要正确重写hashCode方法，这样才能保证哈希值的有效性。

接着，根据计算得到的哈希值确定在哈希表数组中的索引位置。这就像是在一个有很多格子的盒子里，根据某种规则找到对应的格子。

如果在该索引位置对应的哈希桶中只有一个元素（在没有哈希冲突的情况下），那么直接比较这个元素的键与传入的键是否相等。这里的比较是通过键对象的equals方法进行的。如果相等，就返回该元素的值。

然而，如果发生了哈希冲突，即该索引位置对应的哈希桶中有多个元素（可能是链表或者红黑树结构）。如果是链表结构，会遍历链表中的每个节点，逐个比较节点的键与传入的键是否相等。同样是使用equals方法进行比较，直到找到匹配的键或者遍历完整个链表为止。如果是红黑树结构，就会按照红黑树的查找算法在树中查找目标键，这个过程会比较键的大小关系来决定查找的方向，最终找到匹配的键或者确定键不存在。

如果整个查找过程中都没有找到匹配的键，就返回null，表示在HashMap中不存在这个键对应的元素。

HashMap的get方法，如果发生哈希冲突，如何找到目标key？用什么方法比较？

当HashMap的get方法发生哈希冲突时，在不同的哈希桶结构下有不同的查找目标key的方式。

如果哈希桶是链表结构，会沿着链表逐个节点进行查找。对于链表中的每个节点，使用键对象的equals方法来比较节点的键与目标键是否相等。这个equals方法非常关键，它定义了如何判断两个键是否相等。例如，对于一个存储用户对象为键的HashMap，如果用户类没有正确重写equals方法，可能会导致即使两个用户对象在业务逻辑上是相同的，但在HashMap中却被视为不同的键，从而无法正确获取到对应的元素。

在Java 8之后，如果哈希桶中的元素个数达到一定阈值（默认为8）并且数组的长度大于等于64时，链表会转化为红黑树结构。当是红黑树结构时，会按照红黑树的查找算法来查找目标键。在比较键时，同样是使用equals方法来确定是否找到目标键。红黑树的查找算法会根据键的大小关系（这要求键实现了Comparable接口或者在构造红黑树时传入了自定义的比较器）来决定查找的方向，向左子树或者右子树查找，逐步缩小查找范围，直到找到目标键或者确定目标键不存在。

ArrayList的容量和扩容机制是怎样的，扩容是深拷贝还是浅拷贝？

容量：ArrayList有一个初始容量，在Java中，如果没有指定初始容量，默认的初始容量为10。这个容量表示ArrayList可以容纳的元素个数。随着元素的不断添加，当元素个数接近或达到这个容量时，就会触发扩容机制。

扩容机制：当ArrayList中的元素个数达到当前容量时，就会进行扩容。扩容的操作是创建一个新的数组，新数组的大小通常是原来数组大小的1.5倍。这个倍数在Java的ArrayList实现中是通过位运算来计算的，例如原来容量为10，新容量就是10 + 10 >> 1 = 15。然后，将原数组中的所有元素复制到新数组中。这是一个相对耗时的操作，因为涉及到大量的元素复制。

关于深拷贝和浅拷贝：ArrayList的扩容是浅拷贝。浅拷贝意味着只复制对象的引用，而不是对象本身。在ArrayList扩容时，新数组中的元素只是原数组元素的引用，它们指向的是相同的对象。例如，如果ArrayList中存储的是自定义的对象，扩容后，新数组中的元素和原数组中的元素都指向同一个自定义对象实例。这就需要注意，如果在后续的操作中修改了对象的内部状态，由于是浅拷贝，可能会影响到所有引用这个对象的地方。

讲讲List的底层数据结构。

List是Java中的一个接口，它有多种实现类，不同的实现类底层数据结构有所不同。

ArrayList：它的底层数据结构是数组。数组是一种连续的内存存储空间，它的优点是随机访问效率高。因为可以根据元素的索引直接计算出元素在内存中的存储位置，时间复杂度为O(1)。例如，在一个存储了100个元素的数组中，要访问第50个元素，只要知道数组的起始地址和每个元素所占的空间大小，就能很快定位到。但是数组的缺点是插入和删除操作比较复杂，在中间插入或删除一个元素时，需要移动后面的元素来填补空缺或者腾出空间，在中间位置插入和删除操作的时间复杂度为O(n)，其中n是数组的长度，在末尾插入元素的时间复杂度为O(1)。

LinkedList：LinkedList的底层数据结构是双向链表。链表中的每个节点包含数据部分以及指向前一个节点和后一个节点的指针。这种结构使得LinkedList在插入和删除操作方面比较有优势，在任意位置插入和删除元素只需要修改节点之间的指针关系，时间复杂度为O(1)。不过，由于要通过指针逐个节点地遍历才能找到目标元素，所以它的随机访问效率较低，随机访问一个元素的时间复杂度为O(n)。

请介绍List和Set的区别，以及它们的使用场景。

（1）元素的重复性

List：允许元素重复。例如，可以创建一个List，里面可以有多个相同的整数，像[1, 2, 2, 3]这样的List是完全合法的。这是因为List主要关注元素的顺序和存储，对于是否重复并没有严格限制。

Set：不允许元素重复。如果试图向Set中添加一个已经存在的元素，这个操作会被忽略。例如，创建一个HashSet（Set的一种实现），当添加元素1后，再次添加1时，Set中只会保留一个1。

（2）元素的顺序性

List：是有序的集合。元素的顺序取决于它们被添加到List中的顺序。可以通过索引来访问List中的元素，例如list.get(0)就可以获取到第一个添加的元素。并且可以根据索引对元素进行操作，比如在指定索引位置插入或删除元素。

Set：一般是无序的（除了一些特殊的Set实现，如LinkedHashSet，它可以按照元素添加的顺序保存元素，但这并不是Set的普遍特性）。它主要强调元素的唯一性，不关注元素的顺序，所以不能像List那样通过索引来访问元素。

（3）使用场景：

List的使用场景：需要按顺序存储和访问元素时：比如存储一个用户的操作历史记录，每个操作按照发生的先后顺序存储在List中，这样可以方便地按照顺序查看操作的顺序。

数据可能有重复并且需要根据索引进行操作时：例如，在一个音乐播放列表中，同一首歌曲可能会被多次添加，并且用户可能想要跳到指定的歌曲位置（通过索引），这时List就很合适。

Set的使用场景：需要确保元素唯一性时：比如在一个用户注册系统中，要存储所有已注册的用户名，使用Set可以确保不会有重复的用户名被添加。进行数学集合相关的操作时：例如求两个集合的交集、并集、差集等操作。在Java中，可以使用Set的各种实现类（如HashSet、TreeSet等）方便地进行这些数学集合操作。

如果Set中是对象，如何去重？

当Set中存储的是对象时，去重依赖于对象的两个方法：hashCode()和equals()。

对于大多数Set的实现类（如HashSet），在添加一个对象到Set中时，首先会根据对象的hashCode()方法计算出一个哈希值。这个哈希值用于确定对象在Set内部存储结构中的大致位置（例如在HashSet中是一个哈希表的桶位置）。如果在这个位置上没有其他对象，那么这个新对象就可以被添加到Set中。

但是，如果在这个位置已经有其他对象了，就会调用新对象的equals()方法来和这个位置上的对象进行比较。如果equals()方法返回true，说明这两个对象在业务逻辑上是相同的，那么这个新对象就不会被添加到Set中，从而实现了去重。

例如，假设我们有一个自定义的Person类，想要存储到HashSet中去重。我们需要正确重写Person类的hashCode()和equals()方法。

class Person {
    private String name;
    private int age;


    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }


    // 重写hashCode方法
    @Override
    public int hashCode() {
        int result = 17;
        result = 31 * result + name.hashCode();
        result = 31 * result + age;
        return result;
    }


    // 重写equals方法
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass()!= o.getClass()) return false;
        Person person = (Person) o;
        return age == person.age && name.equals(person.name);
    }
}

这样，当我们创建多个Person对象，即使它们在内存中是不同的实例，但如果它们的name和age相同，根据重写的hashCode()和equals()方法，HashSet就会将它们视为相同的对象而只保留一个。

Java集合中HashSet底层是什么？

HashSet的底层是基于HashMap来实现的。HashSet只存储一个元素，这个元素实际上是作为HashMap的键（value被设置为一个固定的虚拟值，通常是一个静态的Object对象）。

当我们向HashSet中添加一个元素时，实际上是在HashMap中添加一个键值对，键就是要添加的元素，值是那个固定的虚拟值。HashSet利用了HashMap的键的唯一性来保证元素的唯一性。由于HashMap的底层是数组 + 链表（在Java 8中，链表长度达到一定阈值会转化为红黑树）的结构，所以HashSet在查找、添加和删除元素时的时间复杂度平均情况下是O(1)，但在最坏情况下（哈希冲突严重时）可能会退化为O(n)，这里的n是元素的个数。

说说TreeSet和LinkedHashSet的区别：

（1）元素顺序方面

TreeSet：是有序的集合，它的顺序是基于元素的自然排序或者在创建TreeSet时传入的比较器（Comparator）来确定的。例如，如果存储的是数字类型的元素，会按照数字的大小顺序存储；如果是自定义对象，需要实现Comparable接口或者传入比较器来定义对象之间的大小关系，这样TreeSet就可以按照定义好的顺序存储元素。

LinkedHashSet：它也是有序的集合，不过它的顺序是按照元素添加的顺序来保存的。就像一个记录添加顺序的清单，先添加的元素在前，后添加的元素在后。

（2）性能方面

TreeSet：在添加和删除元素时，需要维护元素的排序关系，所以在这些操作上相对较慢。查找操作的时间复杂度是O(log n)，这是因为TreeSet内部是基于红黑树实现的，红黑树的查找操作时间复杂度是对数级别的。

LinkedHashSet：由于它的底层是基于哈希表和链表实现的（继承自HashSet并添加了链表来维护顺序），添加、删除和查找操作的时间复杂度和HashSet类似，平均情况下是O(1)，最坏情况下是O(n)。

（3）内存占用方面

TreeSet：由于要维护红黑树结构，可能会占用相对较多的内存，特别是当元素个数较多时，红黑树的节点需要存储额外的指针和平衡信息等。

LinkedHashSet：除了哈希表的存储开销外，还需要额外的链表来维护元素的添加顺序，所以也会有一定的内存开销，但相对来说比TreeSet可能会少一些，具体取决于元素的数量和对象的大小。

Set.contains()方法的时间复杂度是多少？

对于不同的Set实现类，contains()方法的时间复杂度有所不同。

HashSet：在HashSet中，contains()方法的时间复杂度平均情况下是O(1)。这是因为HashSet基于HashMap实现，它通过计算元素的哈希值来快速定位元素可能存在的位置（哈希桶）。当没有哈希冲突或者哈希冲突较少时，只需要少量的比较操作就可以确定元素是否存在。然而，在最坏的情况下，即所有元素的哈希值都相同（哈希冲突非常严重），时间复杂度会退化为O(n)，这里的n是Set中的元素个数，因为此时需要遍历哈希桶中的所有元素（可能形成一个很长的链表）来确定元素是否存在。

TreeSet：TreeSet的contains()方法的时间复杂度是O(log n)。TreeSet内部是基于红黑树实现的。在红黑树中查找一个元素时，每次比较都会将查找范围缩小一半左右，类似于二分查找。所以，无论树中有多少个元素，查找操作的时间复杂度都是对数级别的，这里的n是TreeSet中的元素个数。

LinkedHashSet：LinkedHashSet的contains()方法的时间复杂度平均情况下是O(1)，最坏情况下是O(n)。LinkedHashSet的底层是基于哈希表和链表实现的，它首先通过哈希表来快速定位元素可能存在的位置，如果没有哈希冲突或者冲突较少，能够很快确定元素是否存在。但如果哈希冲突严重，可能需要遍历哈希桶中的链表来查找元素，此时时间复杂度会退化为O(n)。

线程安全的集合有哪些？挑一个讲讲底层。

Java中有一些线程安全的集合，例如：Vector、Hashtable、ConcurrentHashMap、CopyOnWriteArrayList、CopyOnWriteArraySet等。

以ConcurrentHashMap为例讲讲底层：

ConcurrentHashMap是一个非常常用的线程安全的哈希表实现。

在Java 8之前，ConcurrentHashMap的底层是基于分段锁（Segment）机制实现的。它将整个哈希表分成多个段（Segment），每个段都是一个独立的哈希表，并且每个段都有自己的锁。当多个线程同时访问ConcurrentHashMap时，只要它们操作的是不同的段，就可以并发执行，从而提高了并发性能。例如，如果有16个段，理论上可以有16个线程同时对不同的段进行操作而互不干扰。

在Java 8之后，ConcurrentHashMap摒弃了分段锁机制，改为对每个哈希桶（数组中的元素）单独加锁。它的底层结构仍然是数组 + 链表（或红黑树，当链表长度达到一定阈值时）。当一个线程要对某个哈希桶进行操作（如put、get、remove等操作）时，如果这个哈希桶没有被其他线程锁定，就可以直接进行操作；如果已经被锁定，当前线程会等待，直到锁被释放。这种细粒度的锁机制进一步提高了并发性能，因为在高并发场景下，不同的线程往往操作的是不同的哈希桶，这样就可以并行执行更多的操作。

在put操作时，首先根据键的哈希值找到对应的哈希桶。如果这个哈希桶没有被其他线程锁定，就可以直接进行插入操作。如果已经被锁定，当前线程会等待，直到锁被释放。在插入过程中，如果发生哈希冲突，并且桶中的结构是链表，就按照链表的插入规则进行；如果是红黑树，就按照红黑树的插入规则进行。

在get操作时，不需要对整个哈希表或者某个段加锁。它采用一种乐观的方式来进行读取操作，主要通过对哈希桶的volatile修饰来确保数据的可见性。也就是说，在读取一个哈希桶中的元素时，由于volatile的保证，一个线程可以看到其他线程对这个桶中元素的修改。然而，如果在读取过程中发现哈希桶正在进行结构性的修改（如扩容或者元素的重新映射等），那么这个读取操作可能会有一些特殊的处理，但这种情况相对较少。

哈希和底层实现

哈希（Hash）的概念：哈希是一种将任意长度的数据映射为固定长度的较小数据（哈希值）的函数。这个哈希值可以看作是原始数据的一种“指纹”。好的哈希函数具有以下特点：

确定性：对于相同的输入，总是产生相同的哈希值。

均匀分布：不同的输入尽可能均匀地分布在哈希值的取值范围内，避免哈希冲突（不同的输入产生相同的哈希值）过多。

哈希的底层实现：在Java中，像HashMap、HashSet等集合类的底层很多都是基于哈希表实现的，而哈希表的底层通常是数组。例如，HashMap的底层是一个数组，数组中的每个元素称为哈希桶（bucket）。当我们要将一个键值对（对于HashSet来说，值可以看作是一个固定的占位符）添加到哈希表中时，首先计算键的哈希值，然后通过对数组长度取模（通常会有一些优化的计算方式）来确定这个键值对应在数组中的索引位置，也就是哈希桶的位置。

如果不同的键计算出的哈希值对应的哈希桶相同，就会发生哈希冲突。为了解决哈希冲突，常见的方法有链表法和开放地址法。

在链表法中（如Java的HashMap在处理哈希冲突时采用这种方法），当发生哈希冲突时，将新的键值对添加到同一个哈希桶对应的链表中。在Java 8中，如果链表的长度达到一定阈值（默认为8）并且数组的长度大于等于64时，链表会转化为红黑树，以提高查找效率。

开放地址法是另一种解决哈希冲突的方式，当发生哈希冲突时，通过一定的算法在哈希表中寻找下一个可用的位置来存储元素。

哈希函数的实现

对于基本数据类型，Java中的哈希函数通常是基于对象的内部表示来计算的。例如，对于整数类型，直接将整数作为哈希值（或者经过一些简单的位运算来保证哈希值在合适的范围内）。

对于自定义对象，需要重写hashCode()方法来提供一个合适的哈希函数。例如，对于一个包含多个属性的自定义类，可以根据这些属性的值来计算哈希值。一个简单的方式是将各个属性的哈希值进行组合，如先计算每个属性的hashCode()，然后通过一些数学运算（如乘法、加法等）将它们组合起来。但是要注意，重写hashCode()方法时，也要考虑到与equals()方法的一致性，即如果两个对象的equals()方法返回true，那么它们的hashCode()方法应该返回相同的值。

哈希计算时会产生哈希冲突吗？如何解决？链表和红黑树如何转换？红黑树如何退化成链表？

哈希冲突的产生：哈希计算时是会产生哈希冲突的。哈希函数将任意长度的数据映射为固定长度的哈希值，由于输入数据的无限性和哈希值范围的有限性，不可避免地会出现不同的输入产生相同哈希值的情况，这就是哈希冲突。

哈希冲突的解决方法：链表法：当发生哈希冲突时，在哈希表中每个哈希桶（数组元素）对应的位置维护一个链表。将所有哈希值相同的元素（键值对）都添加到这个链表中。例如在Java的HashMap中，当计算出的键的哈希值对应的哈希桶已经有元素时，新的键值对就会以链表节点的形式添加到这个桶对应的链表末尾。这样，在查找元素时，先定位到哈希桶，然后在链表中逐个比较元素的键是否与目标键相同。

开放地址法：当发生哈希冲突时，不是使用链表来存储冲突的元素，而是通过一定的算法在哈希表中寻找下一个可用的位置来存储元素。例如线性探测法，当哈希值为h的位置已经被占用时，就依次尝试h + 1，h + 2等位置，直到找到一个空的位置。

链表和红黑树的转换

在Java的HashMap中，当链表的长度达到一定阈值（默认为8）并且哈希表的数组长度大于等于64时，链表会转换为红黑树。这是为了提高在哈希冲突比较严重时的查找效率。转换过程涉及到将链表中的每个节点重新构建为红黑树的节点，并按照红黑树的构建规则（如节点颜色的设置、平衡调整等）构建红黑树。

红黑树退化成链表的情况：当红黑树中的元素不断被删除，导致红黑树的节点数量减少到一定程度（例如在Java的HashMap中，当红黑树的节点个数小于等于6时），红黑树会退化成链表。这个过程需要将红黑树的节点逐个提取出来，重新构建为链表结构。

已知Java常见集合，List有哪些？Set和List的区别是什么？

Java中的List常见的实现有ArrayList和LinkedList，此外还有Vector（不过在现代编程中使用相对较少，因为它是线程安全的，但是性能相对较差）。

Set和List的区别

List：允许元素重复。例如，可以创建一个List，里面可以有多个相同的整数，像[1, 2, 2, 3]这样的List是合法的。List是有序的集合。元素的顺序取决于它们被添加到List中的顺序。可以通过索引来访问List中的元素，例如list.get(0)就可以获取到第一个添加的元素。

Set：不允许元素重复。如果试图向Set中添加一个已经存在的元素，这个操作会被忽略。例如，创建一个HashSet，当添加元素1后，再次添加1时，Set中只会保留一个1。一般是无序的（除了LinkedHashSet这种特殊的Set实现可以按照元素添加的顺序保存元素）。它主要强调元素的唯一性，不关注元素的顺序，所以不能像List那样通过索引来访问元素。

讲一下队列和栈这两种数据结构。

栈是一种后进先出（Last In First Out，LIFO）的数据结构。可以把它想象成一摞盘子，最后放上去的盘子会最先被拿走。栈有两个主要的操作：入栈（push）和出栈（pop）。入栈操作是将一个元素添加到栈顶，出栈操作是将栈顶的元素移除并返回这个元素的值。

应用场景

函数调用栈：在程序运行时，当一个函数调用另一个函数时，会将当前函数的执行上下文（包括局部变量、返回地址等）压入函数调用栈。当被调用的函数执行完毕后，会从栈顶弹出相应的执行上下文，然后继续执行调用函数。

表达式求值：例如在计算一个算术表达式时，可以利用栈来实现。将操作数和运算符按照一定的规则压入栈中，然后根据运算符的优先级进行计算，最后得到表达式的结果。

实现方式

栈可以使用数组或者链表来实现。

如果使用数组实现，需要一个变量来记录栈顶元素的索引。入栈操作就是将元素放到数组中栈顶索引的下一个位置，并更新栈顶索引；出栈操作就是返回栈顶元素，并将栈顶索引减1。

如果使用链表实现，栈顶元素就是链表的头节点。入栈操作就是将新元素作为新的头节点插入链表；出栈操作就是移除链表的头节点并返回其值。

队列（Queue）队列是一种先进先出（First In First Out，FIFO）的数据结构。就像排队买票一样，先到的人先买到票离开。队列有两个主要的操作：入队（enqueue）和出队（dequeue）。入队操作是将一个元素添加到队列的末尾，出队操作是将队列头部的元素移除并返回这个元素的值。

应用场景

任务调度：在操作系统中，多个任务可能需要按照一定的顺序执行，例如打印任务队列。先提交的打印任务会先被执行打印。

消息传递系统：在分布式系统中，消息队列用于在不同的组件之间传递消息。发送方将消息发送到队列中，接收方按照消息到达的先后顺序从队列中获取消息进行处理。

实现方式

队列同样可以使用数组或者链表来实现。

使用数组实现时，需要两个变量来分别记录队列的头部和尾部索引。入队操作就是将元素添加到队列尾部索引的位置，并更新尾部索引；出队操作就是返回队列头部元素的值，并更新头部索引。不过要注意处理队列空和队列满的情况，可能需要一些特殊的逻辑，比如循环队列的设计。

使用链表实现时，入队操作就是将新元素添加到链表的末尾，出队操作就是移除链表的头节点并返回其值。

说一下红黑树，它相比于链表有哪些优点？

红黑树是一种自平衡的二叉查找树。它的每个节点除了包含数据、左子节点指针、右子节点指针外，还有一个表示颜色（红色或者黑色）的属性。红黑树具有以下几个特性：

每个节点要么是红色，要么是黑色。

根节点是黑色的。

所有的叶子节点（NIL节点，空节点）都是黑色的。

如果一个节点是红色的，则它的两个子节点都是黑色的。

对于任意节点而言，从该节点到其每个叶子节点的所有路径上包含相同数目的黑色节点。

与链表相比的优点：红黑树是一种二叉查找树，查找操作的时间复杂度为O(logn)。这是因为在查找一个元素时，可以根据元素与节点的大小关系（对于存储数字等可比较类型的红黑树）快速决定是向左子树还是右子树查找，每次查找都会将搜索范围缩小一半左右，类似于二分查找。

红黑树具有自平衡的特性。在插入和删除元素后，红黑树会通过一系列的旋转和颜色调整操作来保持树的平衡。这保证了红黑树的高度始终保持在一个相对较低的水平，从而保证了查找、插入和删除操作的时间复杂度不会因为树的高度过高而退化为线性时间复杂度。

链表：链表在查找一个元素时，需要从链表的头部或者尾部开始逐个遍历节点，时间复杂度为O(n)，其中n是链表的长度。例如，在一个有100个节点的链表中查找一个特定的节点，平均需要遍历50个节点。链表没有平衡性的概念，随着链表中元素的不断增加，链表的长度会线性增长，查找操作会变得越来越慢。

ArrayList和HashMap的内部结构是怎样的？

ArrayList的内部结构

ArrayList是基于数组实现的动态数组。它有一个数组来存储元素，这个数组在内存中是连续的存储空间。

在ArrayList中，有一个变量用于记录数组的大小（元素个数）。当创建一个ArrayList时，如果没有指定初始容量，默认会创建一个初始容量为10的数组。随着元素的不断添加，如果元素个数达到数组的当前容量，就会触发扩容机制。扩容操作会创建一个新的、更大的数组，通常是原来数组大小的1.5倍（通过位运算来计算新容量，例如原容量为10，新容量就是10 + 10 >> 1 = 15），然后将原数组中的所有元素复制到新数组中。

由于数组的连续存储特性，ArrayList在随机访问元素方面效率很高。可以根据元素的索引直接计算出其在内存中的存储位置，时间复杂度为O(1)。但是，在中间插入或删除元素时，需要移动后面的元素来填补空缺或者腾出空间，在中间位置进行插入和删除操作的时间复杂度为O(n)，其中n是数组的长度，在末尾插入元素的时间复杂度为O(1)。

HashMap的内部结构

HashMap的内部结构是数组 + 链表（在Java 8中，链表长度达到一定阈值会转换为红黑树）。

它有一个数组，数组中的每个元素称为哈希桶（bucket）。当向HashMap中添加一个键值对时，首先计算键的哈希值，然后通过对数组长度取模（通常会有一些优化的计算方式）来确定这个键值对在数组中的索引位置，也就是哈希桶的位置。

如果不同的键计算出的哈希值对应的哈希桶相同，就会发生哈希冲突。在Java 8之前，处理哈希冲突的方式是使用链表。将新的键值对添加到同一个哈希桶对应的链表中。在Java 8中，如果链表的长度达到一定阈值（默认为8）并且数组的长度大于等于64时，链表会转换为红黑树。这种转换是为了提高在哈希冲突比较严重时的查找效率。

在查找、添加和删除元素时，首先通过哈希值定位到哈希桶，然后在链表或者红黑树中进行操作。平均情况下，这些操作的时间复杂度为O(1)，但在最坏情况下（哈希冲突非常严重时）可能会退化为O(n)，这里的n是元素的个数。

讲讲Vector。

Vector是Java中的一个古老的集合类，它和ArrayList有很多相似之处，但也有一些重要的区别。

内部结构与扩容机制：Vector也是基于数组实现的动态数组，和ArrayList类似。但是，Vector的扩容机制和ArrayList不同。当Vector中的元素个数达到当前容量时，它的扩容方式是将数组的容量增加一倍。例如，初始容量为10，当添加第11个元素时，会创建一个新的容量为20的数组，并将原数组中的元素复制到新数组中。

Vector是线程安全的集合类。它的线程安全性是通过在每个可能会修改集合结构的方法（如add、remove等）上加上synchronized关键字来实现的。这意味着在多线程环境下，多个线程可以安全地访问和修改Vector对象。然而，这种方式虽然保证了线程安全，但在高并发场景下，由于synchronized关键字的加锁机制，会导致性能下降。

与ArrayList的比较：

性能方面：在单线程环境下，ArrayList的性能通常要优于Vector。因为ArrayList不需要进行线程安全相关的操作，如加锁和解锁，所以在操作速度上会更快。例如，在频繁的读取和写入操作中，ArrayList没有加锁的开销，可以更快地完成操作。

应用场景方面：由于Vector的线程安全性，在一些多线程并且对集合操作的并发要求不高的场景下可以使用。但如果对性能有较高的要求，并且是在单线程环境下，ArrayList是更好的选择。

介绍HashMap，以及ConcurrentHashMap和HashMap的区别。

HashMap是Java中常用的一种数据结构，用于存储键值对（Key - Value pairs）。

结构方面：它的底层结构是数组 + 链表（在Java 8中，链表长度达到一定阈值会转换为红黑树）。有一个初始容量的概念，默认初始容量是16。当向HashMap中添加键值对时，先计算键的哈希值，通过哈希值对数组长度取模来确定在数组中的存储位置（也就是哈希桶的位置）。如果多个键计算出的哈希值对应的哈希桶相同，就会产生哈希冲突，此时就会在对应的哈希桶上以链表（或红黑树）的形式存储这些键值对。

性能方面：在理想情况下，也就是没有哈希冲突或者哈希冲突较少时，查找、添加和删除操作的时间复杂度接近

O(1)。这是因为通过计算哈希值能快速定位到元素所在的哈希桶。但在哈希冲突严重的情况下，操作的时间复杂度可能会退化为

O(n)，这里的𝑛n是元素的个数。

用途方面：广泛应用于需要快速查找、插入和删除元素的场景，例如缓存系统、数据映射等。

ConcurrentHashMap和HashMap的区别

（1）线程安全性

HashMap：不是线程安全的。在多线程环境下，如果多个线程同时对HashMap进行写操作（比如添加、删除元素），可能会导致数据不一致、死循环等问题。例如，两个线程同时对同一个哈希桶进行插入操作，可能会破坏链表的结构。

ConcurrentHashMap：是线程安全的。它专门为多线程并发环境设计，多个线程可以同时对ConcurrentHashMap进行读和写操作而不会出现数据不一致等问题。

（2）性能方面

HashMap：在单线程环境下性能较好，因为没有线程安全相关的开销。但在多线程环境下，由于缺乏线程安全机制，不能直接用于多线程并发操作。

ConcurrentHashMap：虽然保证了线程安全，但相比HashMap在单线程下的性能会稍差一些。不过，它采用了高效的并发控制机制，如分段锁（Java 7及之前版本）或者CAS（Compare - And - Swap）操作 + 同步机制（Java 8及之后版本），使得在多线程环境下能够高效地进行读写操作。

（3）结构方面

HashMap：前面已经介绍了其结构为数组 + 链表（或红黑树）。

ConcurrentHashMap：在Java 8之前，采用分段锁的机制，将整个哈希表分成多个段（Segment），每个段相当于一个独立的小哈希表，不同的段可以被不同的线程并发操作。在Java 8及之后，采用了数组 + 链表（或红黑树）的结构，并且在元素操作时使用CAS操作和synchronized关键字进行更细粒度的同步控制。

ArrayList继承了哪些接口？

ArrayList继承了List接口、RandomAccess接口、Cloneable接口和java.io.Serializable接口。

List接口：这是一个有序的集合接口，它定义了一系列对元素进行操作的方法。例如，添加元素（add方法），可以在指定位置或者列表末尾添加元素。像list.add("element");或者list.add(2, "newElement");，前者在末尾添加元素，后者在索引为2的位置添加元素。

还可以获取元素（get方法），通过指定索引来获取列表中的元素，如String element = list.get(3);，这里就是获取索引为3的元素。

以及删除元素（remove方法），既可以根据索引删除元素，如list.remove(1);，也可以根据元素本身来删除，如果列表中存在某个特定的元素，如list.remove("specificElement");。

RandomAccess接口：这个接口是一个标记接口，没有定义任何方法。它主要是用来表明实现这个接口的类支持快速（通常是常量时间）的随机访问。ArrayList基于数组实现，能够通过索引快速访问元素，所以实现了这个接口。这使得在使用随机访问算法时，例如遍历元素时，可以直接使用索引进行高效的访问，而不像某些不支持随机访问的集合（如LinkedList）需要逐个节点进行遍历。

Cloneable接口：实现这个接口表示这个类支持被克隆。对于ArrayList来说，当调用clone()方法时，会创建一个ArrayList的浅拷贝。浅拷贝意味着新的ArrayList和原ArrayList共享内部数组中的元素引用。例如，如果原ArrayList中存储的是对象引用，克隆后的ArrayList中的元素将指向相同的对象。不过，如果对克隆后的ArrayList进行结构上的改变（如添加或删除元素），是不会影响到原ArrayList的。

java.io.Serializable接口：这表示ArrayList可以被序列化，即将对象转换为字节流以便于存储或者传输。在分布式系统或者将对象保存到文件中时非常有用。例如，当我们想要把一个ArrayList保存到磁盘上，或者通过网络发送到另一个系统中时，可以将其序列化。序列化后的ArrayList可以在需要的时候再进行反序列化，重新构建出原来的ArrayList对象。

HashMap继承了哪些接口？

HashMap继承了Map接口、Cloneable接口和java.io.Serializable接口。

Map接口：Map接口用于存储键值对（Key - Value pairs）。它定义了很多操作键值对的方法。例如，添加键值对（put方法），像map.put("key", "value");，将一个键和对应的值添加到Map中。

获取值（get方法），通过键来获取对应的值，如String value = map.get("key");。

还可以判断键或者值是否存在，例如boolean hasKey = map.containsKey("specificKey");用于判断是否存在特定的键，boolean hasValue = map.containsValue("specificValue");用于判断是否存在特定的值。

以及删除键值对（remove方法），根据键来删除对应的键值对，如map.remove("keyToRemove");。

Cloneable接口：与ArrayList类似，HashMap实现Cloneable接口意味着它支持克隆。当调用clone()方法时，会创建一个HashMap的浅拷贝。浅拷贝在HashMap中意味着键和值的引用被复制，但实际的键和值对象是共享的。如果键和值是可变对象，在克隆后的HashMap中修改这些对象可能会影响到原始的HashMap。

java.io.Serializable接口：这使得HashMap能够被序列化。在需要将HashMap保存到文件或者在网络中传输时，就可以利用序列化功能。例如，在一个缓存系统中，如果想要将HashMap形式的缓存数据保存到磁盘上以便下次启动时恢复，就可以将其序列化，之后再进行反序列化来重新加载缓存数据。