本文详细介绍了Java中集合的基本概念、常用数据结构和核心特性。通过学习本文，读者可以了解到Java集合框架的核心接口和实现类，掌握各种数据结构在不同场景下的应用方法和优劣势，以及如何使用集合框架提供的方法进行数据操作和处理。同时，本文还对集合框架中的常见问题和解决方案进行了详细讨论，帮助读者更好地理解和应用Java集合框架，提高代码的质量和效率。

集合

  Java 的集合框架提供了一种方便和有效地存储和操作对象集合的方式。集合框架按照层次结构可以分为以下几个部分：

1、顶层接口 Collection 和 Map：

• Collection 接口是所有集合类的根接口，定义了集合的基本行为，如添加、删除、判断元素是否存在等操作。
• Map 接口表示键值对的集合，每个键对应一个值，提供了通过键快速查找值的功能。

2、Collection 的子接口：

• List 接口表示有序集合，允许重复元素，并且可以通过索引访问元素。
  • List 接口的实现类：ArrayList、LinkedList、Vector
• Set 接口表示无序集合，不允许重复元素。
  • Set 接口的实现类：HashSet、LinkedHashSet、TreeSet
• Queue 接口表示队列，用于按照先进先出（FIFO）
  -Queue 接口的实现类：LinkedList、PriorityQueue

3、Map 接口的实现类：

• HashMap
• LinkedHashMap
• TreeMap

Collection

List

  List 是 Java 集合框架中的一个接口，表示有序集合，允许重复元素，并且可以通过索引访问元素。

  List 接口的主要特点包括：

• 有序性： List 中的元素按照插入顺序排列，可以通过索引访问和操作元素。
• 允许重复元素： List 允许集合中存在重复的元素。
• 索引访问：可以使用索引值来获取、修改或删除指定位置的元素。
• 动态大小： 可以根据需要动态添加或删除元素，而不需要指定固定的大小。

  Java List 一共三个实现类：分别是 ArrayList、Vector 和 LinkedList。

ArrayList（数组）

ArrayList底层原理

  ArrayList 的底层实现是基于数组，它使用数组来存储元素。

  ArrayList 内部使用一个数组来存储元素。数组的初始大小可以通过构造函数指定，默认为10。当元素数量超过数组大小时，ArrayList 会进行扩容操作。

Array List 自动扩容

  向数组中添加元素时，要检查添加后元素的个数是否会超出当前数组的长度。如果超出，数组将会进行扩容。

  扩容操作会创建一个新的更大的数组，并将原数组中的元素复制到新数组中。默认情况下，扩容时新数组的大小为原数组大小的 1.5 倍。

ArrayList的特点

  ArrayList实现了 List 接口，具有以下特点：

• 基于动态数组： ArrayList 内部使用动态数组来存储元素，这使得它支持高效的随机访问和修改元素。
• 允许重复元素： ArrayList 允许集合中存在重复的元素，即同一个元素可以被多次添加到 ArrayList 中。
• 有序性： ArrayList 中的元素按照它们被添加的顺序排列，保持了插入顺序。
• 动态扩容： 当 ArrayList 中的元素数量超过当前数组的容量时，ArrayList 会自动进行扩容操作。
• 快速随机访问： 由于 ArrayList 基于数组实现，因此支持快速的随机访问元素，时间复杂度为 O(1)。可以通过索引直接访问数组中的元素。
• 尾部插入和删除效率高： 在 ArrayList 的尾部进行插入和删除元素的效率很高，时间复杂度为 O(1)。
• 中间插入和删除效率低： 在 ArrayList 的中间插入或删除元素时，需要移动数组中的元素，时间复杂度为 O(n)。
• 非线程安全： ArrayList 不是线程安全的，如果多个线程同时访问 ArrayList 并且有至少一个线程修改了 ArrayList 的结构（增加或删除元素），则必须通过外部同步来确保 ArrayList 的线程安全性。

如何避免 ArrayList 的频繁扩容？

  可以在创建 ArrayList 实例时指定一个合适的初始容量，以减少扩容操作的频率，从而提高性能。

ArrayList 和 LinkedList 的区别是什么？

• ArrayList 基于动态数组实现，支持快速的随机访问，适合随机访问和修改元素的场景。
• LinkedList 基于双向链表实现，支持快速的插入和删除操作，适合在集合头部和尾部进行频繁的插入和删除操作。

ArrayList 和 Vector 的区别?

  ArrayList 和 Vector 的区别主要在于线程安全性和性能方面。ArrayList 是非线程安全的，在单线程环境下性能更好；而 Vector 是线程安全的，适合多线程环境，但性能相对较低。因此，在单线程环境下，推荐使用 ArrayList，而在多线程环境下需要线程安全性保证时，可以使用 Vector。

LinkedList

LinkedList 底层实现原理

  LinkedList 的底层实现原理是基于双向链表，双向链表是一种数据结构，每个节点包含指向前一个节点和后一个节点的引用。

   LinkedList 的每个节点由 Node 类表示，其中包含元素值（element）、指向前一个节点的引用（prev）和指向后一个节点的引用（next）。
  LinkedList 中有两个特殊的节点，即头节点（first）和尾节点（last）。头节点表示链表的第一个元素，尾节点表示链表的最后一个元素。

LinkedList 的特点

• 基于双向链表
• 不支持快速随机访问
• 支持快速头部和尾部操作
• 空间复杂度较高
• 适合频繁插入和删除操作
• 不适合大量随机访问操作
• 迭代器操作高效

如何在 LinkedList 的头部和尾部插入元素？

• 在链表头部插入元素可以使用 addFirst(E e) 方法。
• 在链表尾部插入元素可以使用 addLast(E e) 方法或者直接使用 add(E e) 方法。

如何在 LinkedList 中删除指定位置的元素？

   可以使用 remove(int index) 方法来删除指定位置的元素。

LinkedList 适合什么样的场景？

   LinkedList 适合在集合的头部和尾部进行频繁的插入和删除操作的场景，不适合需要大量随机访问元素的场景。

Vector

  Vector 与 ArrayList 一样，也是通过数组实现的，不同的是它支持线程的同步，即某一时刻只有一个线程能够写 Vector，避免多线程同时写而引起的不一致性，但实现同步需要很高的花费，因此，访问它比访问 ArrayList 慢。

Set

  Set表示无序、不重复的集合。Set 中不允许重复的元素，每个元素在集合中只能出现一次。常见的实现类有 HashSet、TreeSet 和 LinkedHashSet。

Set为什么不能重复/怎么去重

  Set 不能包含重复元素的原因是因为 Set 的实现类内部通常使用的是一种哈希表或树等数据结构，这些数据结构都是基于唯一键的存储方式。具体来说，HashSet 内部是基于哈希表实现的，而 TreeSet 内部是基于红黑树实现的，它们都是通过唯一键来存储元素的。

HashSet

HashSet的特点

• 不允许重复元素： HashSet 中不允许包含重复的元素，每个元素在集合中只能出现一次。
• 无序性： HashSet 中的元素没有固定的顺序，不保证元素的插入顺序和遍历顺序一致。
• 基于哈希表： HashSet 的底层实现是基于哈希表。
• 线程不安全： HashSet 不是线程安全的，如果多个线程同时修改 HashSet，可能会导致并发修改异常。
• 允许 null 元素： HashSet 允许存储 null 元素，但只能存储一个 null 元素。
• 动态扩容：会自动进行扩容。
  -性能优势： HashSet 的查询、插入和删除操作都具有较高的性能。

HashSet的底层实现原理

  HashSet 的底层实现是基于哈希表（Hash Table）的。具体来说，HashSet 内部使用了一个 HashMap 来存储元素，而哈希表则是 HashMap 的核心数据结构之一。

  HashSet 中，元素存储的位置是根据元素的哈希码（Hash Code）来确定的。当向 HashSet 中添加元素时，首先会计算元素的哈希码，然后根据哈希码确定元素在哈希表中的存储位置。如果该位置上已经存在元素，则根据哈希表的冲突解决策略（通常是链地址法）来处理冲突，将新元素添加到相应位置的链表或树中。

HashSet 如何检查是否重复?

  HashSet 检查元素是否重复的方式是通过哈希表和哈希码来实现的。具体步骤如下：
1、计算哈希码： 当向 HashSet 中添加元素时，首先会调用元素的 hashCode() 方法来计算元素的哈希码。

2、确定存储位置： 根据元素的哈希码和哈希表的大小（即容量）来确定元素在哈希表中的存储位置。

3、检查重复： 当要添加的元素与已有的元素的哈希码相同时，HashSet 会认为这两个元素可能相同，需要进一步进行比较。

4、调用 equals 方法： 如果元素的 hashCode() 相同，HashSet 会调用元素的 equals() 方法来判断两个元素是否相等。如果 equals() 方法返回 true，表示元素重复，不会被添加到 HashSet 中；

HashSet 和 HashMap 有什么区别？

• HashSet 是基于哈希表实现的集合，用于存储不重复的元素，不保证元素的顺序。
• HashMap 是基于哈希表实现的映射，存储键值对，键是唯一的，不保证键值对的顺序。

HashSet 和 TreeSet 的区别是什么？

• HashSet 是基于哈希表实现的集合，不保证元素的顺序。
• TreeSet 是基于红黑树实现的集合，元素按照自然顺序或指定的比较器顺序进行排序。

TreeSet

TreeSet的底层实现

  TreeSet 的底层实现是基于红黑树，支持有序性操作。但是查找效率不如 HashSet。红黑树是一种自平衡的二叉搜索树。

TreeSet的特点

  有序性、不允许重复元素、基于比较器排序、线程不安全

如何自定义对象的比较器（Comparator），以在 TreeSet 中指定排序顺序？

  可以创建一个实现 Comparator 接口的类，并重写 compare 方法来定义比较规则。然后在创建 TreeSet 时传入该比较器对象。

TreeSet 中的元素是按照什么顺序进行排序的？

  如果没有指定比较器，TreeSet 中的元素会按照元素的自然顺序进行排序；如果指定了比较器，则按照比较器指定的顺序进行排序。

TreeSet 如何确保元素不重复？

  TreeSet 内部使用红黑树来存储元素，红黑树不允许重复元素，因此 TreeSet 中的元素也不会重复。

TreeSet 和 LinkedHashSet 有什么区别？

• TreeSet 是有序集合，元素按照比较器或自然顺序排序。
• LinkedHashSet 是有序集合，元素按照插入顺序排序。

Queue

  Queue用于表示队列数据结构。队列是一种先进先出（FIFO）的数据结构，元素按照插入顺序排列，最先插入的元素最先被取出。Queue 接口定义了一系列操作队列的方法，常见的实现类包括 LinkedList 和 ArrayDeque。

Queue 的特点

• 元素按照先进先出的顺序排列，即最先插入的元素最先被取出。
• 支持在队尾插入元素（入队）和从队头取出元素（出队）的操作。
• 队列中的元素通常不允许为 null（具体实现类可能会有不同的规定）。

应用场景：

  需要按照先进先出的顺序处理元素的场景，如任务调度、消息队列等。
  广度优先搜索（BFS）算法中用于存储待访问的节点。

Queue 接口和 Deque 接口有什么区别？

• Queue 接口表示队列数据结构，支持在队尾插入元素和从队头取出元素的操作，通常采用先进先出（FIFO）的策略。
• Deque 接口表示双端队列数据结构，支持在队头和队尾插入元素、从队头和队尾取出元素的操作，可以作为队列、栈或双端队列使用。

如何实现一个阻塞队列（BlockingQueue）？

  可以使用 java.util.concurrent.BlockingQueue 接口的实现类，如 ArrayBlockingQueue、LinkedBlockingQueue 等。
  阻塞队列支持在队列为空时阻塞等待元素插入或在队列已满时阻塞等待元素取出的操作，常用于生产者-消费者模式。

如何判断一个队列是否为空？

  可以使用 isEmpty() 方法来判断队列是否为空，如果队列为空，返回 true；否则返回 false。

如何实现队列的循环操作（循环队列）？

  可以通过在队列底层实现循环数组来实现循环队列，即当队列尾部元素达到数组末尾时，再次插入元素时从数组头部开始。

如何处理队列中的异常情况，比如队列已满或队列为空？

  可以使用队列提供的异常处理方法，如 add(E e) 方法在队列已满时会抛出异常，而 offer(E e) 方法会返回 false；remove() 方法在队列为空时会抛出异常，而 poll() 方法会返回 null。

ArrayDeque 与 LinkedList 的区别

  ArrayDeque 和 LinkedList 都实现了 Deque 接口，两者都具有队列的功能。

1. ArrayDeque 是基于可变长的数组和双指针来实现，而 LinkedList 则通过链表来实现。
2. ArrayDeque 不支持存储 NULL 数据，但 LinkedList 支持。
3. ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。

  从性能的角度上，选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外，ArrayDeque 也可以用于实现栈。

List、Set 、Queue对比分析

特性	List（列表）	Set（集合）	Queue（队列）
定义	元素有序排列的集合	不允许重复元素的集合	具有先进先出（FIFO）行为的有序集合
允许重复元素	允许	不允许	允许
实现方式	ArrayList、LinkedList 等	HashSet、TreeSet 等	ArrayDeque、LinkedList 等
访问方式	可以通过索引访问元素	不能直接通过索引访问元素	基于优先级访问元素
排序方式	保持插入顺序	无固定顺序，某些情况下有序	保持插入顺序
性能	索引访问快，插入相对较慢	访问和插入速度快（O(1)）	插入和移除速度快（O(1)）
使用场景	在需要保持顺序和重复元素的情况下使用	在需要保证元素唯一性的情况下使用	在需要先进先出行为的情况下使用

Array List、LinkedList、Hash Set、TreeSet、ArrayQueue对比分析

特性	ArrayList（数组列表）	LinkedList（链表）	HashSet（哈希集合）	TreeSet（树集合）	ArrayQueue（数组队列）
数据结构	基于数组实现	基于链表实现	基于哈希表实现	基于红黑树实现	基于数组实现
允许重复元素	允许包含重复元素	允许包含重复元素	不允许包含重复元素	不允许包含重复元素	允许包含重复元素
访问方式	可以通过索引访问元素	不支持索引访问，需要从头或尾遍历访问	无索引访问，通过哈希码快速访问	无索引访问，按照比较器或自然顺序访问	可以通过索引访问元素
插入和删除操作	随机访问快，插入和删除相对较慢	插入和删除操作比较灵活，但在中间插入和删除较慢	插入和删除操作快（O(1)）	插入和删除操作较慢（O(log n)）	插入和删除操作快（O(1)）
排序方式	不提供排序功能，保持插入顺序	不提供排序功能，保持插入顺序	无固定顺序，某些情况下有序	按照比较器或自然顺序排序	不提供排序功能，保持插入顺序
额外空间需求	需要额外空间用于扩容和存储空白元素	需要额外空间存储节点的引用	需要额外空间存储哈希表和链表节点	需要额外空间存储红黑树节点	需要额外空间用于扩容和存储空白元素
使用场景	需要频繁随机访问元素或保持插入顺序的情况	需要频繁插入和删除元素的情况	需要保证元素唯一性和快速访问的情况	需要有序集合和保证元素唯一性的情况	需要先进先出行为和随机访问元素的情况

Map

HashMap

  HashMap 是 Java 中常用的基于哈希表实现的映射（Map）数据结构，它允许存储键值对，并通过键快速查找对应的值。

HashMap的特点

• 键的唯一性：HashMap 中的键是唯一的，不允许存在重复的键。
• 无序存储：HashMap 中的键值对是无序存储的，存储顺序不固定。
• 快速的查询、插入和删除操作：平均时间复杂度为 O(1)，具有较高的性能。
• 非线程安全：HashMap 是非线程安全的，如果多个线程同时访问和修改可能会导致不确定的结果。
• 适用场景：适用于需要键值对存储和快速访问的大多数场景，例如缓存、索引、映射数据等。

HashMap的底层实现原理

  HashMap 的底层实现原理主要是基于数组、链表和红黑树的组合。
  它使用哈希函数计算键的哈希码，然后将键值对存储在对应的桶中。如果发生哈希冲突，即多个键映射到同一个桶，HashMap 会采用链表或红黑树来存储这些键值对。链表用于存储少量冲突的键值对，而红黑树则用于存储高冲突的键值对，以提高查询、插入和删除操作的效率。当键值对数量达到一定比例时，HashMap 会自动扩容，并重新计算每个键的哈希码，将键值对重新分配到新的桶中，以保持性能。

注意：当链表长度大于8，数组的长度大于 64时，将链表转化为红黑树，以减少搜索时间。（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）

HashMap 的扩容

  HashMap 的扩容过程是指当键值对数量达到一定比例时，HashMap 会自动增加容量并重新哈希，将键值对重新分配到新的桶中，以保持性能和降低哈希冲突的可能性。

• 触发条件： 当键值对数量达到当前容量乘以负载因子（默认为 0.75）时，HashMap 将会触发扩容操作。
• 创建新桶数组： 扩容时，HashMap 会创建一个新的更大的桶数组，新的桶数量通常为原来的两倍。
• 重新哈希和数据迁移： 对于每个键值对，HashMap 会重新计算键的哈希码，并将键值对放入新的桶中。
• 更新容量和阈值： 扩容完成后，HashMap 更新容量为新桶数组的大小，并重新计算扩容阈值。新的扩容阈值为容量乘以负载因子。

HashMap 的负载因子是什么？为什么要设置负载因子？

  HashMap 的负载因子是键值对数量与桶容量的比值。默认负载因子为 0.75。负载因子的设置影响到 HashMap 的性能和内存利用率。较低的负载因子可以减少哈希冲突，但可能会导致空间浪费；较高的负载因子可以节省空间，但可能增加哈希冲突和性能损耗。

HashMap 的线程安全性如何？如何保证线程安全？

  HashMap 是非线程安全的，如果多个线程同时访问和修改可能会导致不确定的结果。要保证线程安全，可以使用 ConcurrentHashMap 或在多线程环境下进行同步操作

HashMap 和 Hashtable 的区别是什么？

  HashMap 和 Hashtable 都是键值对映射的数据结构，但有几点不同：HashMap 是非线程安全的，而 Hashtable 是线程安全的；HashMap 允许键和值为 null，而 Hashtable 不允许；HashMap 的迭代器是快速失败的，而 Hashtable 的是安全失败的。

为什么hashmap扩容是2的指数

  1、hashmap的数组默认大小是16，是2的N次方。随后以2的倍数扩容，将元素复制到新的数组后，元素的位置要么不变，要么有规律的变。这样能提高效率。

  2、其次，使用2倍扩容，可以使元素均匀的分布在hashmap中，减少哈希碰撞。

HashMap 常见的遍历方式?

1、使用迭代器遍历 EntrySet：

HashMap<String, Integer> map = new HashMap<>();
// 添加键值对
Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<String, Integer> entry = iterator.next();
    String key = entry.getKey();
    Integer value = entry.getValue();
    // 处理键值对
}

2、使用 For-Each 循环遍历 EntrySet：

for (Map.Entry<String, Integer> entry : map.entrySet()) {
    String key = entry.getKey();
    Integer value = entry.getValue();
    // 处理键值对
}

3、遍历键集合并获取值

for (String key : map.keySet()) {
    Integer value = map.get(key);
    // 处理键值对
}

4、遍历值集合

for (Integer value : map.values()) {
    // 处理值
}

通常情况下，使用迭代器遍历 EntrySet 或者 For-Each 循环遍历 EntrySet 是比较常见和推荐的方式，因为可以同时获取键和值，而且性能较好。

注意：
  entrySet 的性能比 keySet 的性能高出了一倍之多，因此我们应该尽量使用 entrySet 来实现 Map 集合的遍历。因为 KeySet 相当于循环了两遍 Map 集合，而 EntrySet 只循环了一遍。

  我们不能在遍历中使用集合 map.remove() 来删除数据，这是非安全的操作方式，但我们可以使用迭代器的 iterator.remove() 的方法来删除数据，这是安全的删除集合的方式。

HashMap和LinkedHashMap的区别

  LinkedHashMap在HashMap结构的基础上，增加了一条双向链表，保持了键值对的插入顺序。

  LinkedHashMap可以按照插入顺序或者访问顺序来迭代元素，这个顺序由链表中节点的顺序决定。

  如果需要按照插入顺序或者访问顺序来迭代元素，可以选择使用LinkedHashMap；如果不需要关心迭代顺序，只需要快速地查找和插入元素，可以选择使用HashMap。

hashmap、hashtable、hashset、treemap、Linkedhashmap的对比

特性	HashMap	Hashtable	HashSet	TreeMap	LinkedHashMap
线程安全性	非线程安全	线程安全	非线程安全	非线程安全	非线程安全
是否允许 null 值	键和值均允许为 null	不允许 null 键和值	允许存储一个 null 元素，但只能有一个 null 元素	键和值均不允许为 null	键和值均允许为 null
排序	无序	无序	无序	键有序（根据键的自然顺序或自定义比较器）	插入顺序或访问顺序（最近访问的元素放在最后）
存储结构	数组 + 链表/红黑树	数组 + 链表	哈希表	红黑树	数组 + 双向链表/红黑树
性能	高效，平均时间复杂度为 O(1)	低效，因为使用 synchronized 关键字，影响性能	高效，平均时间复杂度为 O(1)	高效，平均时间复杂度为 O(log n)	高效，插入和删除操作比 HashMap 慢，但迭代速度更快
迭代顺序	不保证迭代顺序	不保证迭代顺序	不保证迭代顺序	根据键的自然顺序或自定义比较器排序	根据插入顺序或访问顺序排序

Concurrent Hash Map

在Java1.7和Java1.8比较

Java1.7

• 数据结构：Java 1.7中的ConcurrentHashMap采用了分段锁的机制来实现线程安全，每个段上都有一个锁。
• 实现方式：Java 1.7中的ConcurrentHashMap采用的是数组加链表的方式来存储键值对
• 容量大小：Java 1.7中的ConcurrentHashMap在初始化时必须指定容量大小，且容量大小必须是2的幂次方。

Java1.8

• 数据结构：Java 1.8中的ConcurrentHashMap废弃了分段锁的机制，采用了一种更为高效的CAS（Compare And Swap）操作来保证线程安全。
• 实现方式：采用了数组+链表+红黑树的方式来存储键值对，当链表长度超过8时，会自动将链表转换为红黑树，以提高查找效率。
• 容量大小：Java 1.8中的ConcurrentHashMap可以在初始化时不指定容量大小，它会自动根据元素数量来计算容量大小，并且容量大小也不需要是2的幂次方。
• 并发性能：Java 1.8中的ConcurrentHashMap在高并发环境下的性能比Java 1.7中的ConcurrentHashMap更好。这是因为Java 1.8中的ConcurrentHashMap采用了更为高效的CAS操作来实现线程安全，同时它的数组加链表加红黑树的方式也可以提高查找效率。

ConcurrentHashMap特点

1. 线程安全：
  使用了数组加链表加红黑树的数据结构来存储键值对。这样，在查找、插入和删除操作时，只需要锁住当前操作所在的数组下标或者链表节点，而不是整个数据结构。这样可以避免不必要的锁竞争，提高了并发性能。

  其次，Java 1.8中的ConcurrentHashMap使用了CAS操作来保证线程安全。CAS（Compare And Swap）是一种乐观锁，它允许多个线程同时访问同一个变量，但只有一个线程能够成功地更新该变量的值。当多个线程同时尝试更新同一个变量时，只有其中的一个线程能够成功执行更新操作，其他线程需要重试。CAS操作可以避免锁的使用，因此可以提高并发性能。

  Java 1.8中的ConcurrentHashMap在扩容时也采用了类似CAS的机制，它会将多个线程的扩容请求合并为一个请求，这样可以避免多个线程同时执行扩容操作而导致的线程安全问题。

2. 高效性能：
  Java 1.8中的ConcurrentHashMap采用了数组加链表加红黑树的方式来存储键值对，同时它还采用了CAS操作来保证线程安全，因此它具有较高的并发性能和查找效率。

3. 动态扩容：
  ConcurrentHashMap的容量可以动态扩容，它能够根据当前的元素数量来自动计算合适的容量大小，并且在扩容时能够保证线程安全。

4. 可设置并发度：
  Java 1.8中的ConcurrentHashMap允许用户在创建时指定并发度，即同时允许多少个线程访问。这样可以在一定程度上提高并发性能。

5. 支持函数式编程：
  Java 1.8中的ConcurrentHashMap支持函数式编程，可以使用Lambda表达式和Stream API对其进行操作，使代码更为简洁、清晰。
6. 支持空值和空键：
  Java 1.8中的ConcurrentHashMap支持空值和空键，这是Java 1.7中的ConcurrentHashMap所不支持的。

ConcurrentHashMap扩容机制

Java 1.7和1.8中的ConcurrentHashMap在扩容机制上有一些区别。

1.7版本

  在Java 1.7中，ConcurrentHashMap的扩容机制比较简单。当元素数量达到阈值时，它会创建一个新的数组，将原数组中的元素重新散列到新数组中，并用新数组替换旧数组。这个过程需要锁住整个ConcurrentHashMap，因此会导致其他线程的阻塞。这也是Java1.7ConcurrentHashMap的一个瓶颈。

1.8版本

  在Java 1.8中，ConcurrentHashMap的扩容机制进行了优化，采用了类似CAS的技术。

  1、当元素数量达到阈值时，它会创建一个新的数组，并将旧数组中的元素懒散地移动到新数组中。在这个过程中，ConcurrentHashMap会将多个线程的扩容请求合并为一个请求，并用CAS操作来保证线程安全。这样就不需要锁住整个ConcurrentHashMap，其他线程可以继续访问ConcurrentHashMap，提高了并发性能。

  2、Java 1.8中，ConcurrentHashMap还引入了一个新的概念——分段锁（Segment）。它将ConcurrentHashMap分成了若干个段，每个段都有自己的锁。当对ConcurrentHashMap进行操作时，只需要锁住对应的段，而不需要锁住整个ConcurrentHashMap。这样可以提高并发性能，避免不必要的锁竞争。每个段的大小可以通过设置ConcurrentHashMap的并发度来调整。

  Java 1.8中的ConcurrentHashMap采用了类似CAS的技术和分段锁的机制，提高了并发性能和扩展性能

如何选用集合?

  根据集合的特点来选用。

  需要根据键值获取到元素值时就选用 Map 接口下的集合，需要排序时选择 TreeMap,不需要排序时就选择 HashMap,需要保证线程安全就选用 ConcurrentHashMap。

   只需要存放元素值时，就选择实现Collection 接口的集合，需要保证元素唯一时选择实现 Set 接口的集合比如 TreeSet 或 HashSet，不需要就选择实现 List 接口的比如 ArrayList 或 LinkedList，然后再根据实现这些接口的集合的特点来选用。

线程安全的集合有哪些

   1、java.util包下的集合类中,大部分都是非线程安全的，有少数的线程安全的集合类，如Vector、Hash Table。一般使用Collections工具类中的synchronizedXxX()方法把他们包装成线程安全的集合类。

   2、java5之后，concurrent包中提供了大量的支持并发访问的集合类。例如ConcurrentHashMap和CopyOnWriteArrayList等。

如何保证集合的线程安全性？

  可以使用 Collections.synchronizedXXX 方法或使用线程安全的集合类（如 ConcurrentHashMap、CopyOnWriteArrayList 等）来保证集合的线程安全性。

红黑树

什么是红黑树

   红黑树是一种自平衡二叉搜索树，能够在插入和删除操作时自动保持平衡，从而保证树的深度不会过高。使得 查找、插入、删除的时间复杂度保持在O(logN)

特点：

1、每个节点要么是红色，要么是黑色
2、根节点是黑色的
3、叶子节点是黑色的空节点
4、如果一个叶子是红色的，那么它的子节点就是黑色的
5、从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑色节点

红黑树的实现

   红黑树的实现主要包括以下几个步骤：

1. 插入操作：当要向红黑树中插入一个节点时，首先将该节点插入到红黑树中，然后通过变换颜色和旋转操作来重新平衡红黑树，以保持树的平衡状态。
2. 删除操作：当要从红黑树中删除一个节点时，首先删除该节点，然后通过变换颜色和旋转操作来重新平衡红黑树，以保持树的平衡状态。
3. 旋转操作：红黑树中的旋转操作包括左旋和右旋两种。左旋和右旋的目的是为了让红黑树保持平衡。左旋操作将一个节点的右子节点变为该节点的父节点(逆时针)，同时该节点成为其右子节点的左子节点。右旋操作则是左旋操作的镜像操作。
4. 颜色变换：红黑树中的颜色变换操作包括变色、颜色翻转和颜色变换三种。颜色变换的目的是为了保证红黑树中的红色节点和黑色节点的数量满足红黑树的特点。

   红黑树的实现是比较复杂的，需要结合以上几个步骤来完成，通过这些操作的协调和配合，红黑树能够实现自平衡并保证性能。在Java中，TreeSet和TreeMap就是基于红黑树实现的有序集合和有序映射。

Collections 工具类

   Collections 是 Java 中的一个实用工具类，提供了一系列静态方法，用于操作集合对象。
1、排序

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>(Arrays.asList(5, 3, 8, 1, 6));
        
        // 使用 Collections.sort 对列表进行排序
        Collections.sort(numbers);
        System.out.println("Sorted numbers: " + numbers);
        
        // 使用 Comparator 自定义排序规则
        Collections.sort(numbers, Comparator.reverseOrder());
        System.out.println("Reverse sorted numbers: " + numbers);
    }
}

2、查找和替换示例

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<String> colors = new ArrayList<>(Arrays.asList("red", "blue", "green", "yellow", "blue"));
        
        // 使用 binarySearch 查找元素索引
        int index = Collections.binarySearch(colors, "green");
        System.out.println("Index of 'green': " + index);
        
        // 使用 replace 替换元素
        Collections.replaceAll(colors, "blue", "purple");
        System.out.println("Colors after replacement: " + colors);
    }
}