Java面试题-集合

1、什么是集合？

集合（Collection）是Java中一种用于存储对象的容器，它可以包含多个对象，这些对象可以是相同类型或不同类型（依赖于具体使用的集合类型）。Java集合框架提供了一系列的接口和实现（如List、Set、Map等），用于存储和操作对象群集，支持各种操作，如添加、删除、遍历、排序等。

2、集合和数组的区别是什么？

• 大小：数组大小固定，一旦创建无法改变；集合大小可变，可以根据需要动态增减。
• 类型限制：数组可以包含基本数据类型和对象；集合只能包含对象。
• 功能：集合提供了更多复杂的数据操作方法（如添加、删除、插入、遍历等），而数组操作相对简单。
• 性能：对于固定大小和类型的数据操作，数组通常会比集合更高效。

3、集合有哪些特点？

• List：有序集合（也称为序列），能够精确控制每个元素的插入位置，可以包含重复元素。
• Set：不允许重复的集合，没有索引，不能包含相同的元素。
• Map：键值对集合，持有键（唯一）到值的映射，一个键最多只能映射到一个值。
• Queue：队列，按照先进先出的原则对元素进行处理。
• Deque：双端队列，允许我们从两端添加或删除元素。

4、常用的集合类有哪些？

• List接口的实现类：ArrayList、LinkedList、Vector。
• Set接口的实现类：HashSet、LinkedHashSet、TreeSet。
• Map接口的实现类：HashMap、LinkedHashMap 、TreeMap、Hashtable 。
• Queue接口的实现类：PriorityQueue、ArrayDeque。
• 特殊集合类：Stack（继承自Vector）、EnumSet、 EnumMap（转为枚举类型设计）。

5、List， Set， Map三者的区别？

• List：有序集合，可包含重复元素，通过索引访问元素。
• Set：无序集合，不可包含重复元素，主要用于确保元素唯一性。
• Map：键值对集合，存储唯一键与值的映射，键不可重复，值可以重复。

6、说说集合框架底层数据结构？

• ArrayList：动态数组（Resizable Array）。
• LinkedList：双向链表。
• HashSet：基于哈希表（实际上是HashMap的一个实例）。
• LinkedHashSet：哈希表+双向链表，维护元素插入顺序。
• TreeSet：红黑树（自平衡的二又查找树）。
• HashMap：哈希表，存储键值对。
• LinkedHashMap：哈希表+双向链表，维护键值对的插入顺序或访问顺序。
• TreeMap：红黑树，根据键的自然顺序或Comparator排序。
• PriorityQueue：优先队列，基于堆结构。
• ArrayDeque：数组或循环数组实现的双端队列。

7、线程安全的集合类有哪些？

• Vector
• Hashtable
• Stack
• ConcurrentHashMap
• CopyOnWriteArrayList
• CopyOnWriteArraySet
• BlockingQueue的实现类（ArrayBlockingQueue，LinkedBlockingQueue等）
• ConcurrentLinkedQueue
• ConcurrentLinkedDeque

8、说说集合的快速失败机制"fail-fast"？

快速失败（fail-fast）机制是Java集合框架的一种错误检测机制，它用于在迭代器的操作过程中，如果检测到集合被结构性修改（增加、删除元素等），则立即抛出ConcurrentModificationException。这样做可以避免在迭代过程中因为集合的结构改变而产生不可预测的行为。快速失败行为主要通过集合的modCount（修改计数器）实现，迭代器创建时会记录下modCount，每次迭代时检查该值是否发生变化。

9、怎么确保一个集合不能被修改？

可以使用Collections类提供的unmodifiableCollection、unmodifiableLlist、unmodifiableSet、 unmodifiableMap等方法将集合包装为不可修改的视图。尝试修改这些不可修改的视图将抛出UnsupportedOperationException。例如：

List<String> list = new ArrayList<>();
List<String> unmodifiableList = Collections.unmodifiableList(list);

通过这种方式，原始集合list的任何修改都不会反映在unmodifiableList上，且unmodifiableList不允许任何修改操作。

10、说说你对Collection接口的了解？

Collection接口是Java集合框架的根接口，不继承于其他接口。它提供了对集合对象进行基本操作的通用接口方法，如添加、删除、清空集合，以及检查集合的大小、判断集合是否为空或是否包含某个对象等。Collection接口是List、Set和Queue接口的父接口，因此这些接口继承并扩展了Collection接口的功能，以支持更具体的集合操作。Collection接口本身并不提供直接的实现，它的实现是通过其子接口（如List、Set等）和类（如 ArrayList、 HashSet等）提供的。

11、Iterator迭代器是什么？

Iterator是一个接口，提供了遍历集合（如List、 Set）的标准方法，包括检查序列中是否还有元素（hasNext()）、获取序列中的下一个元素（next()）和从集合中删除上一次通过next()方法返回的元素（remove()）。Iterator使得客户端代码可以统一地遍历集合，而不需要了解其底层的结构。

12、Iterator怎么使用？有什么特点？

使用Iterator的基本步骤如下：

1. 通过调用集合的iterator()方法获取迭代器实例。
2. 使用hasNext()方法检查集合中是否还有元素。
3. 使用next()方法访问集合中的下一个元素。
4. 如需从集合中删除元素，可调用remove()方法。

特点包括：

• 通用性：为不同类型的集合提供了统一的遍历方式。
• 安全删除：通过迭代器的remove()方法可以安全删除集合中的元素，避免ConcurrentModificationException。
• 单向遍历：迭代器仅支持向前遍历集合，不支持反向遍历。
• 无法访问索引：迭代器不提供获取当前元素索引的方法。

List<String> list = new ArrayList<>();
Iterator<String> it = list.iterator();
while(it.hasNext()){String obj = it.next();System.out.println(obj);
}

13、如何边遍历边移除Collection中的元素？

边遍历边移除Collection中的元素，应使用Iterator 的remove()方法。步骤如下：

1. 获取Collection的迭代器。
2. 使用hasNext()检查是否有更多元素。
3. 使用next()方法获取元素。
4. 使用remove()方法删除上一次通过next()方法访问的元素。

示例代码：

Iterator<Element> iterator = collection.iterator();
while (iterator.hasNext()) {Element element = iterator.next();//根据条件判断是否需要删除当前元素if (/*条件判断*/) {iterator.remove();// 删除元素}
}

这种方式安全，不会引发ConcurrentModificationException。

14、遍历一个List有哪些不同的方式？每种方法的实现原理是什么？

1. for循环：通过索引直接访问列表中的元素。实现原理是基于数组（如 ArrayList）或链表（如LinkedList）的结构，直接通过位置索引获取元素。

for (int i = 0; i < list.size(); i++) {Element element = list.get(i);
}

2. 增强for循环（for-each循环）：简化的遍历方式，内部使用 Iterator 实现。适用于所有实现了Iterable接口的集合类。

for (Element element : list){//使用element
}

3. lterator遍历：使用 Iterator 接口提供的hasNext()和 next()方法遍历元素。这是一种更通用的遍历方式，允许在遍历过程中安全地移除元素。

Iterator<Element> iterator - list.iterator()；
2while （iterator.hasNext()）{
Element element - iterator.next()；
4}

4. Listlterator遍历：仅适用于List接口。ListIterator提供了向前和向后遍历列表的能力，同时支持添加、替换和删除操作。

ListIterator<Element> listIterator = list.listIterator();
while (listIterator.hasNext()) {Element element = listIterator.next();
}

5. Java 8 Stream API：提供了一种更声明式的处理集合的方法，支持顺序和并行遍历，以及提供了丰富的操作如筛选、映射、排序等。

list.stream().forEach(element -> {//使用element
});

• for循环和增强for循环依赖于集合的内部结构进行直接访问或隐式使用Iterator。
• Iterator遍历和Listlterator遍历提供了显式的迭代器对象，允许在遍历时修改集合。
• Stream APl使用函数式编程方式，可以简化代码并利用多核架构。

15、List遍历的最佳实践是什么？

Java中List遍历的最佳实践取决于具体的使用场景和需求：

• 读取操作：如果仅进行遍历读取，推荐使用增强for循环（for-each循环），因为它简洁易读。
• 性能敏感：对于ArrayList，直接使用基于索引的for循环可能更高效，尤其是在大列表中；对于LinkedList，使用增强for循环或Iterator遍历效率更高。
• 需要修改列表：如果在遍历过程中需要修改列表（添加、删除、替换元素），使用Iterator或ListIterator，它们提供了安全修改集合的方法。
• Java 8及以上：考虑使用Stream API，它提供了更高级的操作（如过滤、转换等），并可以利用并行处理来提高性能。

16、说一下 ArrayList 的优缺点？

优点：

1. 随机访问效率高：基于动态数组实现，支持快速随机访问，通过索引直接访问元素的时间复杂度为O(1)。
2. 动态扩容：能根据需要自动增加存储容量，使用方便。
3. API丰富：提供了丰富的方法用于操作列表中的元素，包括添加、删除、查找、遍历等。

缺点：

1. 插入和删除效率低：在列表的中间或开始位置添加或删除元素需要移动后续所有元素，时间复杂度为O(n)。
2. 内存开销：在动态扩容时，需要重新分配数组并复制旧数组的内容到新数组，可能会有额外的内存开销。
3. 容量浪费：自动扩容机制可能会导致实际分配的容量大于实际所需，造成空间浪费。

17、如何实现数组和List之间的转换？

数组转List：
使用Arrays.asList(T...a)方法将数组转换为固定大小的列表。

String[] array = {"a","b","c"};
List<String> list = Arrays.asList(array);

List转数组：
使用List的toArray(T[] a)方法将列表转换为数组。

List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
String[] array = list.toArray(new String[0]);

注意：Arrays.aslList返回的列表是固定大小的，对其进行添加或删除操作会抛出UnsupportedOperationException。若要创建一个可变的列表，可以使用新的ArrayList<>(Arrays.asList(array))。

18、ArrayList 和 LinkedList 的区别是什么？

• 内部结构：ArrayList基于动态数组实现，支持快速随机访问；LinkedList基于双向链表实现，每个元素都有指向前后元素的引用。
• 性能：ArrayList的随机访问速度快（O(1)），但在列表中间或开头插入和删除元素的速度较慢（O(n)）；LinkedList的插入和删除操作速度快（O(1)），但随机访问速度慢（O(n)）。
• 内存占用： ArrayList因为大小可变，可能会有额外的内存占用；LinkedList对于每个元素都需要额外的内存空间来存储前后元素的引用。
• 使用场景：ArrayList适合频繁的查找操作，LinkedList适合频繁的插入和删除操作。

19、ArrayList 和 Vector的区别是什么？

• 同步性：Vector是同步的，适用于多线程环境，但因为同步带来额外开销，性能较低；ArrayList是非同步的，适用于单线程环境，性能较高。
• 数据增长：ArrayList的数据增长率默认为50%，而Vector默认增长率是100%，也可以在创建时指定增长率。
• 遗留性：Vector是Java早期版本的一部分，被视为遗留类，ArrayList是Java集合框架（JCF）的一部分，是较新的、更轻量级的选择。

20、多线程场景下如何使用ArrayList？

在多线程场景下使用ArrayList时，可以采取以下措施以确保线程安全：

1. 使用**Collections.synchronizedList**方法：将ArrayList包装为同步的列表。

List<String> syncList = Collections.synchronizedList(new ArrayList<String>());

2. 使用**CopyOnWriteArrayList**：适用于读多写少的并发场景，因为每次修改（添加、删除、设置等）都会复制整个基础数组。

List<String> cowList = new CopyOnWriteArrayList<>();

3. 手动同步：在对ArrayList进行操作的代码块前后使用synchronized关键字手动同步。

synchronized(list) {// list操作
}

21、为什么 ArrayList 的 elementData要加上transient修饰？

ArrayList的elementData数组被声明为transient是为了在序列化过程中控制哪些数据被序列化，避免将数组中的空元素也序列化。这样做可以最小化序列化存储空间的使用，只序列化数组中实际存储的元素，而不是整个底层数组。在反序列化时，只根据存储的元素重新构建数组，从而提高了效率和节省了存储空间。

22、List 和 Set 的区别有哪些？

• 元素唯一性：List允许重复的元素，按照插入顺序排序；Set不允许重复的元素，通常不保证元素的顺序（除LinkedHashSet）。
• 索引访问：List支持通过索引位置访问元素；Set不支持索引访问。
• 接口实现：List 和 Set是Java集合框架中的两个不同的接口，分别有各自的实现类，如ArrayList、LinkedList 为 List接口的实现，而HashSet、LinkedHashSet 、TreeSet 为 Set接口的实现。

23、说一下HashSet的实现原理？

HashSet是基于HashMap实现的。它使用HashMap的键来存储元素，每个元素都映射到一个固定的虚拟值（HashMap的值部分）。HashSet利用HashMap键的唯一性来确保其元素的唯一性，并且通过哈希表实现，因此具有很高的查找和插入效率。当向HashSet添加元素时，实际上是将元素作为HashMap的键添加，而对应的值则是一个预定义的静态的新对象（因为HashMap是键值对映射，而HashSet只关心键）。

24、HashSet如何检查重复？HashSet是如何保证数据不可重复的？

HashSet检查重复并保证数据不可重复的机制基于其底层的 HashMap实现。当向HashSet添加元素时，实际上是将该元素作为HashMap的键：

1. 哈希值计算：首先，利用元素的hashCode()方法计算其哈希值，这个哈希值用于定位在哈希表中的存储位置。
2. 键的唯一性：HashMap保证了每个键的唯一性。如果插入的元素（作为HashMap的键）的哈希值与已存在的某个元素的哈希值相同，HashMap会进一步调用equals()方法来检查这两个元素是否真的相等。
   1. 如果equals()返回 true，则认为这两个元素相等，新的插入操作不会发生，从而保证了HashSet 中元素的唯一性。
   2. 如果equals()返回false，则认为这两个元素虽然哈希值相同但不等（发生了哈希冲突），HashMap将通过某种冲突解决机制（如链表或红黑树）来存储这两个元素，保证它们都被保存在结构中。

通过这种方式，HashSet利用HashMap的键的唯一性来保证自身存储的元素的唯一性。

25、HashSet与HashMap有什么区别？

• 用途差异：HashSet是一个不允许重复元素的集合，用于存储唯一的值；HashMap是一个键值对集合，存储键值映射，允许通过键快速访问数据。
• 数据结构：HashSet内部实际上是通过HashMap实现的，它存储元素作为HashMap的键，所有的值都映射到一个预定义的常量上；HashMap存储键值对，每个键映射到一个具体的值。
• 方法和功能：HashSet主要提供添加、删除、包含等操作，关注点在于元素的唯一性；而HashMap提供了更丰富的操作，如获取和设置键值对，检查键或值是否存在等。
• 性能：在使用上，两者的性能考量主要依赖于hashCode()方法的实现，以及冲突解决策略，但HashSet主要关注集合操作，而HashMap关注键值对的映射和访问。

26、什么是Hash算法？

Hash算法是一种将任意长度的输入（或称为消息）通过散列算法处理，转换成固定长度输出的过程。该输出称为散列值或哈希值。Hash算法的特点包括：对于任何给定的输入，输出都是确定的；不同的输入尽可能产生不同的输出（尽管会有哈希碰撞的可能性）；算法执行过程是单向的，即从哈希值不能逆向推导出原始数据。Hash算法广泛应用于数据检索、加密、数据完整性验证等领域。

27、链表是什么？

链表是一种数据结构，由一系列节点组成，每个节点包含数据部分和一个或多个指向其他节点的引用（指针）。链表允许高效的元素插入和删除操作，因为这些操作只需要改变相邻节点的引用。

28、说说链表的分类和优缺点？

链表主要分为三种类型：

1. 单向链表：每个节点包含数据和指向下一个节点的指针。可以高效地进行插入和删除操作，但只能向一个方向遍历。
2. 双向链表：每个节点包含数据、指向前一个节点的指针和指向下一个节点的指针。可以向两个方向遍历，插入和删除操作相对更灵活和高效。
3. 循环链表：单向或双向链表的变种，其中最后一个节点的下一个指针指向第一个节点，形成一个环。便于从任何节点开始遍历整个链表。

优点：

• 动态数据结构：链表可以根据需要动态地分配内存，不需要在创建时确定大小。
• 插入和删除高效：相较于数组，链表在插入和删除节点时不需要移动其他元素，只需修改指针即可。

缺点：

• 访问时间：相较于数组，链表的访问时间较长，不能直接通过索引访问元素，需要从头开始遍历。
• 内存占用：由于每个元素需要额外存储指针，所以相较于数组链表的内存占用更大。
• 逆向遍历困难：单向链表的逆向遍历非常困难，需要额外的数据结构或算法。

29、说一下HashMap的实现原理？

HashMap是基于哈希表实现的。核心原理如下：

1. 数据存储：HashMap存储键值对，其中键是唯一的。
2. 哈希函数：使用键的hashCode()方法计算哈希码，然后通过散列函数将此哈希码映射到哈希表中的一个位置（桶）以决定键值对的存储位置。
3. 处理哈希冲突：当不同的键产生相同的哈希码（哈希冲突）时，HashMap采用链表（JDK 1.8之前）或红黑树（JDK 1.8及以后，链表长度超过一定阈值时转换为红黑树）来存储相同哈希码的不同键值对。
4. 动态扩容：当哈希表中的数据量超过负载因子（load factor）和当前容量的乘积时，哈希表将进行扩容（通常是翻倍），然后重新计算已有的键值对在新哈希表中的位置。
5. 键值访问：通过键的哈希码快速定位到其值的存储位置，实现高效的数据查找、插入和删除操作。

30、HashMap在JDK1.7和JDK1.8中有哪些不同？

主要区别在于内部数据结构和扩容机制的改进：

1. 内部数据结构：
   1. JDK 1.7：使用数组+链表的结构。当多个键的哈希值相同（哈希冲突）时，会在相同哈希值的桶位置形成一个链表。
   2. JDK 1.8：引入了数组+链表+红黑树的结构。当链表长度超过阈值（默认为8）时，链表转换为红黑树，以减少搜索时间。
2. 扩容机制：
   1. JDK 1.7：在扩容时，新的数组大小是原来的两倍，所有元素需要重新计算哈希值并分配到新的桶中，这个过程效率较低。
   2. JDK 1.8：优化了扩容算法，通过保留原有节点的顺序，减少了重新计算哈希值的需要，只需判断节点存储在原位置还是移动到新的位置，提高了扩容的效率。

这些改进提升了HashMap在处理大量数据时的性能，尤其是减少了搜索时间和扩容成本。

31、什么是红黑树？

红黑树是一种自平衡的二又搜索树，它通过每个节点增加一个存储位表示节点的颜色（红或黑），并通过一系列的规则和旋转操作来保持树的平衡。这些规则包括：

1. 每个节点要么是红的，要么是黑的。
2. 根节点是黑的。
3. 所有叶子节点（NIL节点，空节点）都是黑的。
4. 每个红节点的两个子节点都是黑节点（从每个叶子到根的所有路径上不能有两个连续的红节点）。
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

红黑树的这些性质确保了最长的路径不会超过最短的路径的两倍，因而接近于平衡。这保证了红黑树在插入、删除和查找操作中都能保持较高的性能，最坏情况下的时间复杂度为O(log n)。

32、HashMap的put方法的具体流程是怎样的？

HashMap的put方法流程（基于JDK 1.8）如下：

1. 计算键的哈希值：首先，使用键对象的hashCode()方法计算哈希值，然后通过哈希函数处理这个哈希值以减少碰撞。
2. 定位桶位置：使用处理后的哈希值与数组长度减一进行位运算（假设数组长度是2的幕），确定键值对应该存放的桶（数组索引）位置。
3. 检查键是否存在：
   1. 如果目标桶为空，直接在该位置创建一个节点存储键值对；
   2. 如果目标桶不为空（即发生了哈希碰撞）则遍历该桶（可能是链表或红黑树）：
      1. 如果键已存在，更新其对应的值；
      2. 如果键不存在，则在适当的位置添加一个新节点（链表末尾或红黑树中）。
4. 树化检查：如果链表长度超过阈值（默认为8），并且数组长度大于或等于64，那么将链表转换为红黑树，以提高后续的查找和插入效率。
5. 检查是否需要扩容：如果当前HashMap的大小超过了容量与负载因子（默认为0.75）的乘积，那么进行扩容（容量翻倍）并重新分配所有的键值对。
6. 返回值：如果插入的键已经存在，则返回旧值；如果是新插入的键，则返回null。

33、HashMap的扩容操作是怎么实现的？

HashMap的扩容操作主要包括以下步骤：

1. 创建新数组：创建一个新的数组，大小通常是原数组大小的两倍。
2. 重新计算索引：遍历原数组中的所有元素，对每个元素重新计算其在新数组中的位置。这是通过使用元素的哈希值与新数组的长度进行位运算来完成的。
3. 重新分配元素：根据重新计算得到的索引，将所有元素重新放置到新数组的相应位置上。如果原位置是链表或红黑树，则需要遍历这些结构，并对每个节点进行同样的重新索引操作。
4. 更新引用：最后，将HashMap的内部引用从旧数组更新为指向新数组。

34、HashMap是怎么解决哈希冲突的？

HashMap解决哈希冲突的主要方式是通过链地址法，即在发生冲突的桶位置使用链表（JDK 1.8之前）或红黑树（JDK 1.8及以后，在链表长度超过一定阈值时，链表转换为红黑树）来存储多个元素。这样，即使多个键映射到同一个桶（索引位置），它们也可以通过链表或红黑树结构被有效地存储和检索。在查找、插入或删除操作时，HashMap会先定位到桶的位置，然后遍历链表或红黑树来进行具体操作。这种方法允许多个键共享同一个桶位置，同时保持操作的效率。

35、什么是哈希？

哈希是一种将任意长度的输入通过哈希函数转换成固定长度输出的过程，输出结果称为哈希值。哈希过程的主要特点是高效性和确定性，即相同的输入总是产生相同的输出，不同的输入尽量产生不同的输出。哈希广泛应用于数据检索、数据加密、数据完整性校验等领域。

36、什么是哈希冲突？

哈希冲突是指两个或多个不同的输入值在经过哈希函数处理后得到了相同的哈希值的情况。由于哈希函数的输出空间有限，而输入空间可能是无限的，因此不同的输入有可能映射到同一个输出，即发生哈希冲突。处理哈希冲突是哈希表等数据结构设计中的一个重要考虑因素。

37、说说HashMap的数据结构？

HashMap的数据结构是一个结合了数组和链表（或红黑树）的复合结构。它使用一个数组来存储数据，数组的每个槽位（桶）可以指向一个链表或红黑树的结构，用于存储具有相同哈希值（经过哈希函数处理后的索引）的多个键值对。在JDK 1.8及以后版本中，当链表长度超过一定阈值时，链表会被转换为红黑树，以提高搜索效率。

38、能否使用任何类作为Map的key？

是的，理论上可以使用任何类作为Map的key。但是，为了确保Map正常工作，该类应正确重写hashCode()和 equals()方法。这是因为Map（特别是HashMap）依赖这两个方法来确定键的唯一性并维护键值对。如果这两个方法没有被适当地重写，可能导致Map表现出不正确的行为，如丢失数据或无法检索到数据。

39、为什么HashMap中String、Integer这样的包装类适合作为Key？

String、Integer等包装类适合作为HashMap中的Key，因为它们已经正确地重写了hashCode()和 equals()方法，确保了相同的实例会有相同的哈希码，且只有当两个对象逻辑上等价时，equals()方法才返回 true。这使得这些类型的对象能够保持键的唯一性和一致性，从而在HashMap中高效地存储和检索数据。

40、如果要使用Object作为HashMap的Key，应该怎么办？

1. 重写**hashCode()**方法：确保逻辑上相等的对象返回相同的哈希码。
2. 重写**equals()**方法：确保正确比较两个键对象的逻辑等价性，即当且仅当两个对象逻辑上相等时，equals()方法返回 true。

这样做是为了保证HashMap能够正确地处理键的唯一性和检索操作。未正确重写这些方法可能导致HashMap行为不正确，比如查找失败或意外的数据覆盖。

41、HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标？

使用hashCode()处理后的哈希值直接作为数组下标的话，会面临几个问题：

1. 数组大小限制：直接使用哈希值作为下标可能导致非常大的数组索引，远远超过HashMap的实际数组大小，这是不切实际的。
2. 负数问题：hashCode()方法返回的是int类型，可能是负数，而数组索引不能是负数。

为了解决这些问题，HashMap通过对哈希值进行额外的哈希函数处理，并与数组长度-1进行位运算（通常是与操作），来确保计算出来的索引在数组的有效范围内，同时也帮助分散哈希值，减少哈希冲突。

42、HashMap的长度为什么是2的幂次方？

主要有两个原因：

1. 位运算效率：使用2的幂次作为数组长度，允许HashMap通过位运算（hashCode & (length-1)）代替模运算来计算索引，大大提高了计算索引的效率。
2. 均匀分布：2的幂次方作为长度可以帮助哈希值更均匀地分布在整个数组中，减少哈希冲突，从而提高HashMap的性能。

43、HashMap与HashTable 有什么区别？

1. 线程安全：HashTable是线程安全的，所有方法都是同步的；而HashMap是非线程安全的。
2. 性能：因为HashTable的方法是同步的，所以在单线程环境下比HashMap性能低。
3. 空值： HashMap允许键和值为null；HashTable不允许键或值为null 。
4. 迭代器：HashMap的迭代器是快速失败的（fail-fast），而HashTable的枚举器不是。

44、什么是TreeMap？

TreeMap是基于红黑树（一种自平衡二叉查找树）的Map接口实现。它能够保持键的自然排序（根据其compareTo()方法）或根据构造时提供的Comparator进行排序。TreeMap实现了SortedMap 接口，因此它支持有序集合操作，如返回指定范围的子映射、获取第一个（最低）和最后一个（最高）键等。由于其基于红黑树，TreeMap的插入、删除、查找等操作的时间复杂度为O(log n)。

45、如何决定使用 HashMap 还是TreeMap？

• 性能需求：如果关注插入、删除、查找的性能，并且不需要排序，HashMap（平均O(1)的时间复杂度）通常是更好的选择。如果需要一个按照自然顺序或自定义顺序来遍历键，TreeMap（保证了O(log n)的时间复杂度）可能更适合。
• 排序需求：如果需要键值对保持有序，选择TreeMap；如果不需要排序，HashMap效率更高。
• 线程安全：如果需要线程安全，两者都不是最佳选择，可能需要考虑ConcurrentHashMap或Collections.synchronizedMap包装器。但就单个线程或已有外部同步措施情况而言，选择依据是性能和排序需求。
• 内存使用：HashMap通常使用较少的内存，因为TreeMap需要维护红黑树的结构。

46、HashMap 和 ConcurrentHashMap 的区别？

• 线程安全：ConcurrentHashMap是线程安全的，提供了高效的并发访问；而HashMap是非线程安全的，不适合在并发环境下使用而不进行外部同步。
• 内部结构：ConcurrentHashMap在内部使用了分段锁（JDK1.7）或使用 CAS操作和synchronized关键字来减少锁竞争（JDK1.8），从而提高并发访问性能；HashMap没有这样的机制，其所有操作都不是同步的。
• 迭代器弱一致性：ConcurrentHashMap的迭代器提供弱一致性遍历，而不是HashMap的快速失败遍历方式。
• 性能：由于ConcurrentHashMap的并发优化，它在多线程环境下比同步的HashMap（如通过Collections.synchronizedMap包装的HashMap）提供了更好的读写性能。
• 功能差异：ConcurrentHashMap移除了一些如contains方法，改为containsValue和containsKey，更明确地表达了方法的意图。

47、ConcurrentHashMap 和 Hashtable的区别？

• 线程安全实现：ConcurrentHashMap使用分段锁（JDK 1.7） 和CAS操作（JDK 1.8及以后）来提高并发访问性能，只锁定部分数据结构；而Hashtable使用方法级的同步，每个方法都是同步的，锁定整个数据结构，导致并发性能较低。
• 性能：因为ConcurrentHashMap的并发优化，它在多线程环境下提供比 Hashtable 更高的读写性能。
• 迭代器：ConcurrentHashMap的迭代器提供弱一致性视图，不会抛出ConcurrentModificationException；而Hashtable的枚举器和迭代器在结构被并发修改时可能抛出此异常。
• 空键和空值：ConcurrentHashMap不允许键（keys）或值（values）为null；而Hashtable允许非空键和值。
• 设计目的：ConcurrentHashMap专为并发使用场景设计，提供了一些原子操作方法；Hashtable是早期Java版本的遗留类，主要用于单线程或通过外部同步机制在多线程中使用。

48、ConcurrentHashMap 底层具体实现原理是什么？

ConcurrentHashMap的底层实现原理在JDK1.7和JDK1.8中有所不同：

• JDK 1.7：ConcurrentHashMap使用分段锁（Segment锁）机制。它内部维护一个Segment数组，每个Segment实质上是一个小的哈希表，拥有自己的锁。对ConcurrentHashMap的操作只会锁定必要的 Segment，从而减少锁竞争，提高并发效率。每个Segment负责管理它所包含的键值对。
• JDK 1.8：改进了数据结构，去掉了Segment，直接使用节点数组加链表和红黑树的结构。通过使用synchronized 和 CAS（无锁机制）来控制并发，同时使用了红黑树来优化长链表的查找时间。在JDK1.8中，ConcurrentHashMap在链表长度超过一定阈值时将链表转换为红黑树，提高搜索效率。

在两个版本中，ConcurrentHashMap都能够通过细粒度的锁控制或无锁机制来实现高效的并发访问，尤其是在读操作远远多于写操作的场景下表现良好。

49、Array 和 ArrayList 有何区别？

• 类型：Array是固定大小的，可以存储基本类型或对象；ArrayList是可变大小的，只能存储对象。
• 大小：Array的大小在创建时确定，不能动态改变；ArrayList的大小可动态增长。
• 性能：对于基本类型数据，Array有更好的性能，因为ArrayList使用包装类作为泛型存储，有装箱和拆箱的开销。
• 功能：ArrayList提供了更多的方法和功能，如自动扩容、便捷的插入、删除等操作。

50、comparable 和 comparator的区别？

• Comparable：是一个对象自比较其自身与另一个对象的接口。如果一个类实现了Comparable接口，就意味着该类支持排序。Comparable接口有一个compareTo(Object o)方法，用于定义默认的排序方式。
• Comparator：是一个比较器接口，可以定义两个对象的比较方式。如果你想要控制某个类的排序逻辑，但是这个类不能修改或者你想要有多种排序方式，可以通过实现Comparator接口，使用它的compare(Object o1, Object o2)方法来实现。

简而言之，Comparable用于实现自然排序，而Comparator用于实现自定义排序逻辑。

51、Collection 和 Collections有什么区别？

• Collection：是一个接口，它是各种集合结构（如 list、 Set等）的根接口，提供了对集合对象进行基本操作的通用接口方法。
• Collections：是一个包含有关集合操作的静态方法的工具类，如排序、搜索等，用于操作或返回集合。

52、TreeMap 和 TreeSet 在排序时如何比较元素？

TreeMap 和 TreeSet在排序元素时，可以依赖元素的自然排序或者通过提供一个自定义的Comparator对象来定义排序规则。

• 自然排序：当没有提供Comparator 时，元素类必须实现Comparable接口，并且compareTo(Object o)方法定义了其自然排序的逻辑。
• 自定义排序：通过构造函数传入一个Comparator对象，使用该比较器的compare(Object o1, Object o2)方法来比较元素。

53、Collections 工具类中的sort()方法如何比较元素？

Collections.sort()方法比较元素的方式取决于传入的集合元素类型：

• 如果集合元素实现了Comparable接口， sort()方法会使用这些元素的compareTo()方法进行自然排序。
• 可以重载 sort() 方法，传入一个自定义的Comparator 对象，这时候会使用该Comparator的compare()方法来比较元素，实现自定义排序。