校招面试重点汇总之集合（非常非常重要）

一、 Arraylist与LinkedList区别

ArrayList和LinkedList都是Java集合框架中的List接口的实现，它们的主要区别在于底层数据结构的不同。ArrayList是通过数组实现的，而LinkedList是通过双向链表实现的。以下是它们的具体区别：

• （1）插入和删除操作的效率不同
  ArrayList的底层是一个动态数组，它的元素在内存中是连续存放的。因此，在数组中进行插入和删除操作时，需要移动元素来保持连续性，这可能需要花费大量时间。对于在末尾添加或删除元素，效率相对较高，因为不需要移动其他元素。而对于在数组中间插入或删除元素，效率较低，因为需要移动其他元素。
  LinkedList的底层是一个双向链表，每个元素存储了前一个元素和后一个元素的引用。因此，在链表中进行插入和删除操作时，只需要修改相应元素的引用，不需要移动其他元素。对于在链表末尾添加或删除元素，效率相对较低，因为需要遍历整个链表找到最后一个元素。而对于在链表中间插入或删除元素，效率相对较高，因为只需要修改相应元素的引用即可。

• （2）随机访问的效率不同
  由于ArrayList的元素在内存中是连续存放的，因此可以通过索引来随机访问元素。这个过程非常快，因为只需要通过索引计算出元素在内存中的地址即可。
  而在LinkedList中，每个元素只存储了前一个元素和后一个元素的引用，因此不能通过索引来访问元素。如果需要访问第N个元素，需要遍历整个链表，直到找到第N个元素。这个过程可能需要花费较长的时间。

• （3）内存占用不同
  由于ArrayList的底层是一个动态数组，因此它需要一段连续的内存空间来存储元素。如果元素数量较多，但是内存空间不足，就需要重新分配更大的内存空间，并将现有元素拷贝到新的内存空间中，这个过程比较耗时。因此，ArrayList可能会浪费一些内存空间。
  而在LinkedList中，每个元素只需要存储前一个元素和后一个元素的引用，因此不需要一段连续的内存空间来存储元素。每个元素可以随时分配内存空间，并且可以在不同的内存位置中存储。因此，LinkedList通常比ArrayList占用更少的内存空间。

注：在多线程环境下，ArrayList和LinkedList都不是线程安全的。如果需要在多线程环境中使用它们，可以使用线程安全的实现，比如Vector和CopyOnWriteArrayList。

二、详细介绍下Arraylist扩容机制

ArrayList 是一个基于数组实现的动态数组，它能够自动扩容以容纳更多的元素。当我们向 ArrayList 中添加元素时，如果元素数量已经达到了当前容量，则需要进行扩容。

ArrayList 扩容机制的具体实现如下：

• （1）初始化容量：ArrayList 在创建时需要指定一个初始容量。如果不指定，它将默认创建一个容量为 10 的数组。

• （2）容量不足：当我们向 ArrayList 中添加元素时，如果当前元素个数已经达到了数组容量，那么 ArrayList 将自动进行扩容操作。具体来说，它将创建一个新的数组，新数组的容量是原数组的 1.5 倍（如果元素个数比较少，会采用较小的增量，如增加一个常数值）。然后将原数组中的元素复制到新数组中，并将新元素添加到新数组的末尾。

• （3）扩容时机：在添加元素时，ArrayList 每次都会检查是否需要扩容，这个检查是有成本的，因此我们需要尽量减少扩容的次数。为了达到这个目的，Java 中的 ArrayList 内部会维护一个变量 modCount，表示 ArrayList 中实际存储的元素数量。当我们在添加元素时，如果 modCount 等于数组的容量，则触发扩容操作。

• （4）System.arraycopy()：在扩容时，ArrayList 使用 System.arraycopy() 方法将原数组中的元素复制到新数组中，这个方法的速度比使用 for 循环逐个复制要快得多。

• （5）扩容次数：ArrayList 的扩容次数与添加元素的个数有关。如果我们已知需要添加的元素个数，那么最好在创建 ArrayList 时指定一个合适的初始容量，以避免多次扩容。同时，在添加元素时，也可以使用 ensureCapacity() 方法手动指定 ArrayList 的容量，以减少扩容次数。

三、介绍下Hashmap的底层数据结构

HashMap 底层数据结构是数组加链表或红黑树，具体实现是一个桶数组（bucket array），每个桶里面存储一个链表或红黑树，用于存储键值对。每个键值对被封装成一个 Entry 对象，Entry 对象包含键值对的键和值，以及指向下一个 Entry 对象的指针。在 JDK 8 中，当一个桶中的链表长度超过阈值（默认为 8）时，链表会转化为红黑树，这样能够提高查找的效率。

HashMap 的数组大小一般是 2 的整数次幂，这是因为在计算键的哈希值时，使用了取模运算，即 h = key.hashCode() % capacity，而当 capacity 是 2 的整数次幂时，取模运算可以通过位运算来代替，这样能够提高运算的效率。当我们向 HashMap 中插入键值对时，HashMap 会先根据键的哈希值计算出数组中的位置，然后将键值对添加到对应桶的链表或红黑树的头部。

HashMap 采用链表法解决哈希冲突，即当多个键的哈希值映射到同一个桶时，将它们存储在同一个链表中。在查找键值对时，HashMap 先根据键的哈希值找到对应的桶，然后再在桶中依次查找。当桶中的链表长度较长时，查找效率会比较低，因此 JDK 8 引入了红黑树，能够提高查找效率。在 JDK 8 中，当链表长度小于等于 8 时，会采用链表的方式进行查找，当链表长度大于 8 时，会采用红黑树的方式进行查找。

在 HashMap 中，数组大小和扩容因子是需要考虑的因素。数组大小决定了 HashMap 能够存储的键值对的数量，而扩容因子决定了何时进行扩容。默认情况下，数组大小为 16，扩容因子为 0.75。当数组中存储的键值对数量超过数组大小乘以扩容因子时，HashMap 就会自动扩容。扩容的过程是比较耗时的，因此如果我们已经知道 HashMap 中键值对的数量，就可以在创建 HashMap 时指定数组大小，以减少扩容的次数，提高性能。

四、什么是Hash冲突，该如何解决？

Hash冲突发生在散列表（Hash表）中，当两个或多个不同的键（key）被映射到相同的位置（index）时，就会发生冲突。
这是因为在散列表中，键被映射到数组的特定位置，而这个位置可能已经被其他键占用了。这种情况下，需要解决冲突以确保键值对能够被正确地存储和检索。

解决Hash冲突的方法有很多种，以下是其中几种：

• （1）开放地址法：当发生冲突时，继续查找数组中的下一个空位置，直到找到一个空位置为止。

• （2）链地址法：将每个位置的元素作为链表的头节点，并将新的键值对插入到该位置对应的链表中。

• （3）线性探测法：当发生冲突时，在数组中查找下一个空位置，并将键值对插入到该位置。

• （4）双重散列法：使用两个哈希函数，分别计算出两个哈希值，如果第一个哈希值产生了冲突，就使用第二个哈希值。

五、介绍下红黑树特点及其实现原理

红黑树是一种自平衡二叉查找树，具有以下特点：

• 每个节点要么是红色，要么是黑色。
• 根节点是黑色的。
• 每个叶子节点（NIL节点）是黑色的。
• 如果一个节点是红色的，则它的子节点必须是黑色的。
• 任意一条从根节点到叶子节点的路径上，不能出现连续的两个红色节点。
• 从任意节点出发到其子孙节点的所有路径包含相同数目的黑色节点。

这些特点保证了红黑树的平衡性，使得它的查找、插入、删除等操作的时间复杂度都能够达到O(log n)的级别。

红黑树的实现原理是通过在普通的二叉查找树的基础上增加了一些限制和规则来保持平衡。当需要插入或删除一个节点时，红黑树会保证整个树仍然满足上述五个特点。

（1）插入操作

红黑树的插入操作首先按照二叉查找树的规则找到插入位置。将新节点插入为红色节点。如果插入点的父节点是黑色的，那么直接插入完成，不需要进行其他调整。如果插入点的父节点是红色的，则违反了规则，需要执行旋转和重新着色等操作，以恢复平衡性。

插入操作需要考虑以下几种情况：

• 1）新节点的父节点为黑色，不需要调整。
• 2）新节点的父节点和叔父节点均为红色，需要将父节点和叔父节点都改为黑色，将祖父节点改为红色，然后以祖父节点为当前节点进行递归处理。
• 3）新节点的父节点是红色，而叔父节点是黑色或空节点。此时需要进行旋转来保持红黑树的性质。
• 4）新节点的父节点是红色，叔父节点也是红色。在这种情况下，需要将父节点和叔父节点都改为黑色，祖父节点改为红色，并将祖父节点作为当前节点继续进行递归处理。

（2）删除操作

红黑树的删除操作需要考虑以下几种情况：

• 1）待删除节点只有一个子节点或没有子节点。

• 2）待删除节点有两个子节点。

当待删除节点有两个子节点时，可以找到该节点的中序遍历的前驱或后继节点代替该节点，并将其删除。然后，将该前驱或后继节点的值赋给待删除节点，并将待删除节点改为该节点。最后，删除该前驱或后继节点。删除操作同样需要考虑旋转和重新着色等操作，以保持红黑树的平衡。

六、为什么HashMap中用红黑树，而不是二叉排序树、平衡二叉树和B+树？

在Java中，HashMap使用的是数组加链表（或红黑树）的方式来存储数据。具体来说，当HashMap中某个桶(bucket)中的链表节点数超过8个时，链表就会被转换为红黑树。这种实现方式的原因主要有以下几点：

• （1）时间复杂度
  红黑树的查找、插入和删除的时间复杂度都是O(log n)，在大多数情况下要优于二叉排序树和平衡二叉树的O(n)，B+树也需要更多的磁盘读写操作，而HashMap中的操作频繁且数据量较小，因此红黑树是较为合适的选择。

• （2）数据结构的复杂度
  虽然红黑树比二叉排序树、平衡二叉树和B+树要复杂，但HashMap中红黑树的实现比较简单，代码易于理解和维护。

• （3）实际性能
  在实际应用中，由于HashMap中的数据量较小且操作频繁，红黑树的效率要优于B+树，而与平衡二叉树和二叉排序树相比，虽然它们的时间复杂度与红黑树相同，但红黑树的实现比较简单，代码可读性更高。

七、介绍下HashMap和HashTable的区别

HashMap和HashTable都是Java中常用的Map实现，它们都提供了键值对的存储和快速的查找功能。它们之间的区别主要体现在以下几个方面：

• （1）线程安全性不同
  Hashtable是线程安全的，即多个线程可以同时操作同一个Hashtable实例，而不会出现线程安全问题。但是Hashtable的线程安全是通过在每个方法上添加synchronized关键字来实现的，这会带来额外的性能开销。
  而HashMap是非线程安全的，如果多个线程同时操作同一个HashMap实例，会出现线程安全问题。但是可以通过一些方式（如使用ConcurrentHashMap）来实现HashMap的线程安全。
• （2）null值的处理方式不同
  HashTable不允许存储null键和null值，如果尝试放置null键或null值，将抛出NullPointerException异常。而HashMap可以存储null键和null值
• （3）初始容量和扩容机制不同
  HashTable的初始容量为11，随着元素数量的增加，会根据负载因子（默认为0.75）自动扩容为原来的两倍。而HashMap的初始容量一般为16，扩容时也是按照当前容量的两倍扩容（可设置负载因子），同时使用了渐进式哈希算法（incremental hashing），避免了扩容时大量元素的重新哈希过程。
  -（4）性能方面差异
  由于Hashtable的线程安全机制是通过在每个方法上添加synchronized关键字来实现的，因此在多线程环境下性能会受到影响。而HashMap在单线程环境下性能更优，因为它不需要进行额外的线程同步。
• （5）底层数据结构不同
  JDK1.8以后HashMap在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

八、HashMap 是线程安全的吗？该如何实现？

HashMap 不是线程安全的，多个线程同时对同一个 HashMap 进行读写操作可能会导致数据不一致或者抛出异常。因此，在多线程环境中需要使用线程安全的 HashMap。

下面介绍几种实现线程安全 HashMap 的方法：

• （1）使用 ConcurrentHashMap：ConcurrentHashMap 是线程安全的哈希表实现，它支持高并发读写操作，并且保证线程安全。
• （2）使用 Collections.synchronizedMap：使用 Collections.synchronizedMap 可以将 HashMap 转化为线程安全的 Map，它会使用 synchronized 关键字对 Map 进行同步控制，从而保证多个线程对 Map 的操作互斥，达到线程安全的目的。
• （3）使用读写锁（ReadWriteLock）：使用读写锁对 HashMap 进行读写控制，读操作可以并发执行，写操作需要互斥执行，从而提高了并发访问的效率。
• （4）使用 ThreadLocal：使用 ThreadLocal 来实现线程安全的 HashMap，它的实现方式是将 HashMap 存储在 ThreadLocal 变量中，每个线程拥有自己的 HashMap 实例，从而避免了多个线程对同一个 HashMap 进行并发访问的问题。

需要根据实际情况选择最合适的方法。ConcurrentHashMap 是一个高效的线程安全 Map 实现，但是它只能保证每个元素的原子性操作，不能保证多个操作之间的原子性。如果需要同时保证多个操作的原子性，需要使用显式的锁机制，如 synchronized 或者读写锁。使用 ThreadLocal 实现的线程安全 Map 可以避免多个线程之间的数据竞争问题，但是也会引入一些新的问题，例如内存泄漏、线程之间数据共享等。

九、介绍下HashMap 和 HashSet 区别

HashMap 和 HashSet 都是 Java 集合框架中的常用数据结构，它们的主要区别如下：

• （1）存储方式不同：HashMap 是基于键值对的存储方式，每个元素都包含一个键和一个值；而 HashSet 是基于哈希表的存储方式，每个元素只包含一个值，没有键。
• （2）存储元素的唯一性：HashMap 中的键是唯一的，值可以重复；而 HashSet 中的元素是唯一的，不能重复。在 HashSet 中，元素的唯一性是通过 hashCode 和 equals 方法来判断的，如果两个元素的 hashCode 值相同并且 equals 方法返回 true，那么这两个元素就被认为是相同的。
• （3）访问元素的方式不同：HashMap 可以根据键来访问值，而 HashSet 只能通过迭代器来访问元素。
• （4）遍历顺序不同：HashMap 不保证元素的顺序，遍历元素的顺序是不确定的；而 HashSet 中元素的顺序是无序的。
• （5）内部实现机制不同：HashMap 底层实现是基于哈希表的数据结构，而 HashSet 底层实现也是基于哈希表的数据结构，只不过 HashSet 中的元素只有键没有值，相当于 HashMap 中的键作为 HashSet 中的元素。
• （6）使用场景不同：HashMap适用于需要存储已知关联关系的数据，例如字典、缓存等。而HashSet则适用于需要快速判断某个元素是否存在的场景，例如去重、判断某个元素是否属于某个集合等。

十、为什么HashMap的底层数组长度为何总是2的n次方？

在HashMap中，元素的插入和查找操作是通过将键转换为哈希码，并使用该哈希码对数组长度取模来实现的。如果数组长度不是2的幂次，那么取模操作就需要使用较慢的除法运算，而使用2的幂次作为数组长度，可以将取模操作转化为更快速的位运算。

例如，如果数组长度为16，那么取模操作就可以通过对哈希码的低4位进行位运算来实现，即哈希码 & 0b1111。而如果数组长度为15，则需要对哈希码进行除法运算。

此外，使用2的幂次作为数组长度还可以减少哈希碰撞的概率，因为哈希码的低位在数组中的位置可以更均匀地分布。因此，HashMap底层数组长度总是2的n次方，这是为了使其哈希算法更高效和更少的哈希碰撞。

十一、什么是ConcurrentHashMap，如何实现？

ConcurrentHashMap是Java中线程安全的哈希表实现，它可以同时支持多个线程对数据的读写操作，而不会出现数据不一致的情况。在并发环境下，ConcurrentHashMap比Hashtable和同步的HashMap等其他线程安全的Map实现具有更好的性能。

ConcurrentHashMap的实现原理：ConcurrentHashMap的底层是由一个Segment数组构成，每个Segment相当于一个小的HashMap。每个Segment拥有自己的锁（synchronized关键字），即对于Segment内部的所有操作都是线程安全的，不同的Segment之间访问是互相独立的，也就是说不同的线程可以同时访问不同的Segment。在进行插入、删除、查询等操作时，ConcurrentHashMap会根据元素的hash值将其放入不同的Segment中，从而实现了支持高并发访问的功能。

ConcurrentHashMap通过将整个数据结构分成多个段来实现高效的并发访问。它通过细粒度的锁机制来保证线程安全，同时避免了对整个数据结构加锁所带来的性能问题。

十二、List 和 Set，Map 的区别

List 和 Set，Map 都是Java中的集合类型。它们之间的区别主要如下：

• （1）数据结构
  List 和 Set 都是基于 Collection 接口实现的，而 Map 则是基于 Map 接口实现的。
• （2）元素唯一性
  List 中的元素可以重复，Set 中的元素不可重复，而 Map 中的键值对是唯一的。
• （3）存储顺序
  List 和 Map 都可以维护元素的插入顺序，而 Set 则无法维护元素的插入顺序。
• （4）数据访问方式
  List 的元素可以通过索引访问，也可以使用迭代器访问。而 Set 的元素只能使用迭代器访问，因为 Set 内部元素存储是无序的。Map 的元素可以通过键来访问。
• （5）性能特点
  List 和 Map 的插入、删除等操作的效率会受到元素数量的影响，而 Set 的插入、删除等操作效率相对稳定。

十三、 ArrayList集合加入1万条数据，应该怎么提高效率？

向ArrayList集合中添加大量数据会导致性能问题，因为每次添加元素时，ArrayList都会检查其内部数组是否需要扩容，这将导致不必要的内存分配和复制。

以下是一些提高ArrayList添加大量数据效率的方法：

• （1）指定ArrayList的初始容量
  在创建ArrayList对象时，可以指定其初始容量，避免多次扩容造成的性能损耗。
• （2）使用addAll()方法一次性添加数据
  可以将要添加的数据封装到一个集合中，然后使用ArrayList的addAll()方法一次性将数据添加到集合中，避免多次单独添加造成的性能损耗。
• （3）使用线程池分批添加数据
  将要添加的数据分成固定大小的块，然后使用线程池对每个块进行添加操作，可以有效减少单次添加大量数据带来的性能压力。

ISO9000网