集合

1.集合框架类结构图

2.List接口

Java中的List接口是Java集合框架（Java Collections Framework）的一部分，它继承自Collection接口。List接口用于表示一个有序的集合，它可以包含重复的元素。与Set接口不同，List保留了元素的插入顺序，并且允许通过索引访问元素。

主要特点

有序：元素按照插入的顺序存储。
可重复性：列表中可以包含重复的元素。
动态大小：列表的大小可以根据需要动态地增长和缩小。
索引访问：可以通过索引（位置）访问列表中的元素，索引范围从0到list.size()-1。

2.1.ArrayList

ArrayList是Java集合框架中的一个类，它实现了List接口。ArrayList是基于动态数组实现的，这意味着它可以自动调整其大小以存储元素。当元素被添加到ArrayList时，如果其当前容量不足以容纳所有元素，那么它会自动扩容，通常是将容量增加50%（具体实现可能有所不同，但这是一种常见的做法）。

2.1.1.特点

动态数组实现：
- ArrayList 内部通过一个动态数组（在 Java 中通常是 Object[] 类型的数组）来存储元素。这意味着它可以自动调整其大小以存储更多的元素。
- 当需要添加更多元素而当前数组大小不足时，ArrayList 会创建一个新的更大的数组，并将旧数组的元素复制到新数组中，然后添加新元素。
随机访问：
- ArrayList 提供了基于索引的访问方式（get(int index)），这使得它非常适合进行随机访问操作。通过索引访问元素的时间复杂度是 O(1)。
自动扩容：
- 当 ArrayList 的大小不足以容纳更多元素时，它会自动扩容。扩容的默认策略是将当前容量增加到原来的 1.5 倍（具体实现可能因 JVM 实现而异，但这是一个常见的做法）。
- 需要注意的是，自动扩容是一个相对昂贵的操作，因为它涉及到内存分配和数组复制。因此，如果事先知道列表的大致大小，最好使用带有初始容量的构造函数来创建 ArrayList。
允许重复元素：
- ArrayList 允许列表中存在重复的元素。这与 Set 接口的实现（如 HashSet）不同，后者不允许重复元素。
有序集合：
- ArrayList 维护了元素的插入顺序。这意味着可以通过元素的插入顺序来遍历它们。
非同步：
- ArrayList 不是同步的。如果多个线程同时访问一个 ArrayList 实例，并且至少有一个线程从结构上修改了列表，那么它必须保持外部同步。这通常通过同步封装器（如 Collections.synchronizedList(List<T> list)）来实现，或者通过其他并发集合（如 CopyOnWriteArrayList）来实现。
性能：
- 对于随机访问和遍历操作，ArrayList 通常提供比 LinkedList 更好的性能。但是，在列表的开头或中间插入或删除元素时，ArrayList 可能比 LinkedList 更慢，因为它需要移动其他元素来填补空位。
泛型支持：
- ArrayList 支持泛型，可以指定列表中元素的类型。这有助于在编译时捕获类型错误，并减少运行时类型转换的需要。
内存使用：
- 由于 ArrayList 使用数组作为其底层数据结构，因此它在内存使用方面通常比基于链表的实现（如 LinkedList）更紧凑。但是，这也意呀着在自动扩容时可能需要更多的内存分配和复制操作。

2.1.2.底层数据结构

ArrayList的底层数据结构是一个动态数组（在Java中通常是通过数组实现的，但数组的大小在创建后不能改变，所以ArrayList内部维护了一个数组，并在需要时创建一个更大的数组来替换它）。这意味着ArrayList在随机访问元素时（即通过索引访问）是非常高效的，但在列表的开头或中间插入或删除元素时可能会相对较慢，因为这可能需要移动其他元素以填补被删除或新增元素留下的空位。

2.1.3.常用方法

ArrayList提供了许多方法来操作列表中的元素，其中一些最常用的方法包括：

boolean add(E e): 向列表的末尾添加指定的元素。
void add(int index, E element): 在列表的指定位置插入指定的元素。
E remove(int index): 移除列表中指定位置的元素，并返回被移除的元素。
boolean remove(Object o): 移除列表中首次出现的指定元素（如果存在）。
E get(int index): 返回列表中指定位置的元素。
int size(): 返回列表中的元素数量。
void clear(): 移除列表中的所有元素。
boolean contains(Object o): 如果列表包含指定的元素，则返回true。
Object[] toArray(): 返回一个包含列表中所有元素的数组。
boolean isEmpty(): 如果列表不包含元素，则返回true。
List<E> subList(int fromIndex, int toIndex): 返回列表中从fromIndex（包含）到toIndex（不包含）部分的视图。

2.1.4.示例代码

import java.util.ArrayList;
import java.util.List;

public class ArrayListExample {
    public static void main(String[] args) {
        List<String> fruits = new ArrayList<>();

        // 添加元素
        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add("Cherry");

        // 访问元素
        System.out.println(fruits.get(1)); // 输出: Banana

        // 插入元素
        fruits.add(1, "Orange");

        // 移除元素
        fruits.remove("Banana");

        // 遍历列表
        for (String fruit : fruits) {
            System.out.println(fruit);
        }

        // 检查列表是否为空
        if (!fruits.isEmpty()) {
            System.out.println("The list is not empty.");
        }

        // 获取列表的大小
        System.out.println("The size of the list is: " + fruits.size());
    }
}

2.2.LinkedList

在Java中，LinkedList 是一个实现了 List 接口和 Deque 接口的双向链表。它允许所有可能的列表操作，并且其所有操作都是按照双重链接列表的规则进行的。LinkedList 是一种动态数据结构，它可以高效地在列表的开头和结尾添加或删除元素。

2.2.1.特点

双向链表实现：
- LinkedList底层是一个双向链表，这意味着每个节点都包含数据元素、指向前一个节点的引用（prev）和指向下一个节点的引用（next）。这种结构使得在链表的两端进行插入和删除操作非常高效。
动态调整：
- LinkedList的大小可以根据需要动态增长或缩小，以适应不同数量的元素存储需求。这意味着在添加或删除元素时，LinkedList能够自动调整其内部结构以容纳更多的元素或释放未使用的空间。
非同步：
- LinkedList是非同步的，这意味着在多线程环境下，如果不采取适当的同步措施，可能会导致数据不一致或并发修改异常。如果需要线程安全的LinkedList，可以使用Collections.synchronizedList(List<T> list)等方法进行封装，或者使用ConcurrentLinkedQueue等并发集合。
灵活的操作：
- LinkedList支持高效的插入、删除和访问操作，尤其是在链表的开头和结尾。同时，它也支持在链表的任意位置进行插入、删除和访问操作，但性能可能会随着元素位置的远离两端而下降。

2.2.2.底层数据结构

LinkedList的底层数据结构是双向链表。每个节点（Node）都包含三个部分：一个数据元素（E element），一个指向前一个节点的引用（Node prev）和一个指向下一个节点的引用（Node next）。这种结构使得在链表中进行向前或向后的遍历都变得非常高效。

2.2.3.常用方法

LinkedList提供了丰富的方法来操作链表中的元素，以下是一些常用的方法：

添加元素：
- boolean add(E e): 在列表末尾添加指定的元素。
- void add(int index, E element): 在列表的指定位置插入指定的元素。
- void addFirst(E e): 将指定元素插入此列表的开头。
- void addLast(E e): 将指定元素添加到此列表的末尾（等同于add(E e)）。
删除元素：
- E remove(int index): 移除列表中指定位置的元素。
- boolean remove(Object o): 移除列表中首次出现的指定元素（如果存在）。
- E removeFirst(): 移除并返回此列表的第一个元素。
- E removeLast(): 移除并返回此列表的最后一个元素。
- E poll(): 移除并返回此列表的头（第一个元素）。
- E pollFirst(): 移除并返回此列表的第一个元素（等同于removeFirst()）。
- E pollLast(): 移除并返回此列表的最后一个元素（如果此列表为空，则返回null）。
访问元素：
- E get(int index): 返回列表中指定位置的元素。
- E getFirst(): 返回此列表的第一个元素。
- E getLast(): 返回此列表的最后一个元素。
- E peek(): 获取但不移除此列表的头（第一个元素）。
- E peekFirst(): 获取但不移除此列表的第一个元素（等同于getFirst()）。
- E peekLast(): 获取但不移除此列表的最后一个元素（如果此列表为空，则返回null）。
修改元素：
- E set(int index, E element): 用指定元素替换列表中指定位置的元素。
其他方法：
- int size(): 返回列表中元素的数量。
- boolean isEmpty(): 如果列表不包含元素，则返回true。
- boolean contains(Object o): 如果列表包含指定的元素，则返回true。
- void clear(): 移除列表中的所有元素。
- Object[] toArray(): 返回包含列表中所有元素的数组。

2.2.4.注意事项

由于 LinkedList 的节点是动态分配的，因此在列表的中间位置添加或删除元素时可能会比 ArrayList 更昂贵，因为需要更新多个节点的链接。
遍历 LinkedList 时，如果可能的话，最好使用 ListIterator，因为它允许向前和向后遍历列表，并且可以添加、删除和修改元素。
考虑到线程安全，如果需要在多线程环境中使用 LinkedList，请考虑使用 Collections.synchronizedList(List<T> list) 进行包装，或者使用 ConcurrentLinkedQueue、ConcurrentLinkedDeque 等并发集合。

2.3.两者区别

1. 底层数据结构

ArrayList：基于动态数组实现。它使用数组来存储元素，当元素数量超过当前数组容量时，会自动进行扩容，通常是将数组容量增加到原来的1.5倍（具体实现可能略有不同），并复制原数组中的元素到新数组中。这种实现方式使得ArrayList在随机访问元素时非常高效，但在进行插入和删除操作时，可能需要移动大量元素，从而导致效率降低。
LinkedList：基于双向链表实现。每个元素都是一个节点，节点之间通过引用相互连接。这种实现方式使得LinkedList在插入和删除元素时非常高效，因为只需要修改相关节点的引用即可，而不需要移动大量元素。但是，由于链表结构，LinkedList在随机访问元素时效率较低，需要从头节点或尾节点开始遍历链表直到找到目标元素。

2. 性能特点

访问性能：ArrayList提供了快速的随机访问能力，通过索引可以在常数时间内访问任何元素（时间复杂度为O(1)）。而LinkedList的随机访问性能较差，需要从头节点或尾节点开始遍历链表直到找到目标元素（时间复杂度为O(n)）。
插入和删除性能：LinkedList在插入和删除元素时具有较高的效率，特别是在链表的头部或尾部进行操作时，时间复杂度为O(1)。而ArrayList在插入和删除元素时可能需要移动大量元素，效率较低，时间复杂度为O(n)。但是，当在ArrayList的末尾添加元素时，由于数组尾部有足够的空间，所以通常这个操作是高效的（摊销时间复杂度为O(1)）。

3. 内存消耗

ArrayList：由于ArrayList是基于数组实现的，所以它在内存中需要连续的空间来存储元素。这使得ArrayList在内存使用上相对紧凑，但也可能导致在扩容时需要额外的内存分配和复制操作。
LinkedList：LinkedList的每个节点都需要额外的空间来存储前后节点的引用，因此它在内存使用上相对较为浪费。但是，由于不需要连续的内存空间，LinkedList在动态扩展时更加灵活。

4. 线程安全性

ArrayList和LinkedList都不是线程安全的。如果多个线程同时访问同一个实例并对其进行修改，可能会导致数据不一致的问题。因此，在需要线程安全的场景中，应该使用Vector、CopyOnWriteArrayList等线程安全的集合类，或者使用Collections.synchronizedList()等方法对ArrayList或LinkedList进行同步封装。

5. 使用场景

ArrayList：适用于需要频繁进行随机访问的场景，如查询操作较多的场景。同时，如果元素数量相对固定，或者虽然元素数量变化较大但插入和删除操作较少，也可以使用ArrayList。
LinkedList：适用于需要频繁进行插入和删除操作的场景，特别是当这些操作主要集中在列表的头部或尾部时。同时，如果需要实现队列、栈等数据结构，也可以使用LinkedList，因为它提供了相应的方法支持。

3.Set接口

Java中的Set接口是Java集合框架（Java Collections Framework）的一部分，它代表了一个不允许有重复元素的集合。Set接口继承自Collection接口，并添加了一些约束来确保集合中元素的唯一性。与List接口不同，Set接口不保证集合中元素的顺序（尽管某些实现，如LinkedHashSet，会保持元素的插入顺序）。

主要特点

唯一性：Set接口的实现类必须确保集合中不包含重复的元素。如果尝试向Set中添加一个已经存在的元素，则添加操作会失败（对于大多数实现来说，会返回false，表示添加失败）。
无序性：Set接口不保证集合中元素的迭代顺序。这意味着每次遍历Set时，元素的顺序都可能是不同的（除非使用了保持插入顺序的Set实现，如LinkedHashSet）。
元素不可变性：Set接口本身不直接支持元素的修改操作（因为Set接口继承自Collection接口，而Collection接口中的add、remove等方法用于修改集合）。但是，如果Set中的元素是可变对象，那么这些对象的内部状态仍然可以被修改，但这不会改变它们在Set中的唯一性判断（除非这种修改导致了对象的hashCode()或equals()方法的返回值发生变化）。

常用实现类

HashSet：基于哈希表的实现，提供了快速的添加、删除和查找操作。它不保证集合的迭代顺序，并且允许使用null元素。
LinkedHashSet：HashSet的一个子类，它维护了一个运行于所有条目的双向链表。这允许以插入顺序遍历元素（插入顺序，而不是排序顺序）。
TreeSet：基于红黑树（一种自平衡二叉查找树）的实现，能够确保集合元素处于排序状态。TreeSet要求集合中的元素实现了Comparable接口，或者在创建TreeSet时提供了一个Comparator来定义元素的排序方式。

示例代码

import java.util.HashSet;
import java.util.Set;

public class SetExample {
    public static void main(String[] args) {
        Set<String> mySet = new HashSet<>();
        
        // 添加元素
        mySet.add("Apple");
        mySet.add("Banana");
        mySet.add("Cherry");
        
        // 尝试添加重复元素
        mySet.add("Apple"); // 这将不会改变集合，因为"Apple"已经存在
        
        // 遍历集合
        for (String fruit : mySet) {
            System.out.println(fruit);
        }
        
        // 输出顺序可能是不确定的，因为HashSet不保证顺序
    }
}

3.1.HashSet

HashSet 是 Java 集合框架中的一个类，它实现了 Set 接口。HashSet 基于哈希表（HashMap，实际上，在 Java 的实现中，HashSet 基本上是一个包装了 HashMap 的类，其中所有的值都是同一个虚拟值）来存储元素，因此它提供了快速的添加、删除和查找操作。

主要特点

唯一性：HashSet 不允许集合中存在重复的元素。如果尝试添加已经存在的元素，则添加操作会失败（实际上，add 方法会返回 false）。
无序性：HashSet 不保证集合中元素的迭代顺序。当你遍历 HashSet 时，元素的顺序是不确定的。
基于哈希表：HashSet 内部使用哈希表来存储元素，这意味着它使用元素的哈希码来快速定位元素。
允许 null 元素：HashSet 允许添加一个 null 元素。
线程不安全：HashSet 不是线程安全的。如果多个线程同时访问一个 HashSet 实例，并且至少有一个线程从结构上修改了集合，那么它必须保持外部同步。

构造函数

HashSet()：构造一个新的空集合，其底层 HashMap 的默认初始容量是 16，加载因子是 0.75。
HashSet(Collection<? extends E> c)：构造一个包含指定集合中所有元素的新集合，这些元素是使用其元素的 hashCode() 和 equals() 方法来判断唯一性的。
HashSet(int initialCapacity)：构造一个新的空集合，具有指定的初始容量和默认的加载因子（0.75）。
HashSet(int initialCapacity, float loadFactor)：构造一个新的空集合，具有指定的初始容量和指定的加载因子。

示例代码

import java.util.HashSet;

public class HashSetExample {
    public static void main(String[] args) {
        HashSet<String> myHashSet = new HashSet<>();

        // 添加元素
        myHashSet.add("Apple");
        myHashSet.add("Banana");
        myHashSet.add("Cherry");

        // 尝试添加重复元素
        myHashSet.add("Apple"); // 这将不会改变集合，因为"Apple"已经存在

        // 遍历集合
        for (String fruit : myHashSet) {
            System.out.println(fruit);
        }

        // 输出顺序可能是不确定的

        // 检查集合是否包含某个元素
        System.out.println(myHashSet.contains("Banana")); // 输出 true

        // 移除元素
        myHashSet.remove("Banana");

        // 再次遍历集合
        for (String fruit : myHashSet) {
            System.out.println(fruit);
        }
    }
}

3.2.LinkedHashSet

LinkedHashSet 是 Java 集合框架中的一个类，它实现了 Set 接口，并继承了 HashSet 类。LinkedHashSet 底层是通过一个由链表和哈希表组成的数据结构来实现的，其中链表用于保证元素插入的顺序，而哈希表用于保证元素的唯一性。

3.2.1.特点

有序性：与 HashSet 不同，LinkedHashSet 能够按照元素的插入顺序来遍历元素。
唯一性：与 Set 接口的其他实现一样，LinkedHashSet 不允许集合中存在重复的元素。
基于哈希表和链表：内部通过哈希表来提供快速的查找性能，并通过链表来维护元素的插入顺序。
允许 null 元素：与 HashSet 一样，LinkedHashSet 也允许添加一个 null 元素。
线程不安全：在多线程环境下，LinkedHashSet 不是线程安全的，需要额外的同步措施。

3.2.2.构造函数

LinkedHashSet 提供了多个构造函数，允许用户指定不同的初始容量和负载因子：

LinkedHashSet()：创建一个新的空的 LinkedHashSet 实例，其底层 LinkedHashMap 的默认初始容量是 16，加载因子是 0.75。
LinkedHashSet(int initialCapacity)：创建一个具有指定初始容量和默认加载因子（0.75）的 LinkedHashSet 实例。
LinkedHashSet(int initialCapacity, float loadFactor)：创建一个具有指定初始容量和加载因子的 LinkedHashSet 实例。
LinkedHashSet(Collection<? extends E> c)：创建一个包含指定集合中所有元素的 LinkedHashSet 实例。

3.2.3.主要方法

LinkedHashSet 实现了 Set 接口中的所有方法，并提供了以下主要方法：

boolean add(E e)：如果此集合不包含指定元素，则添加它。
boolean remove(Object o)：如果此集合包含指定元素，则从中移除它。
void clear()：移除此集合中的所有元素。
boolean contains(Object o)：如果此集合包含指定元素，则返回 true。
boolean isEmpty()：如果此集合不包含任何元素，则返回 true。
int size()：返回此集合中的元素数量（其容量）。
Iterator<E> iterator()：返回在此集合元素上进行迭代的迭代器，按元素的插入顺序进行迭代。

3.2.4.使用场景

LinkedHashSet 适用于需要保持元素插入顺序的场景，例如：

存储一组学生名单，并确保每个学生的名字都是唯一的且按照他们加入的顺序排列。
记录用户访问网站的历史记录，并保持访问的顺序。

3.2.5.注意事项

LinkedHashSet 是线程不安全的，如果在多线程环境中使用，需要考虑线程同步的问题，或者考虑使用线程安全的集合类如 ConcurrentLinkedHashSet。
当使用自定义对象作为 LinkedHashSet 的元素时，需要正确实现 hashCode() 和 equals() 方法，以确保对象在集合中的唯一性和正确性。

3.3.TreeSet

TreeSet 是 Java 集合框架中的一个类，它实现了 SortedSet 接口，用于存储唯一的元素，并且这些元素会根据其自然顺序或构造时提供的 Comparator 进行排序。

3.3.1. 底层数据结构

TreeSet 使用红黑树（Red-Black Tree）作为底层数据结构。红黑树是一种自平衡的二叉查找树，它通过旋转和重新着色操作来确保树的平衡，从而保证了高效的查找、插入和删除操作。这种结构使得 TreeSet 在进行这些操作时具有对数时间复杂度（O(log n)）。

3.3.2. 元素特性

有序性：TreeSet 中的元素按照自然顺序或指定的比较器进行排序。如果没有指定比较器，则元素必须实现 Comparable 接口，以便 TreeSet 可以根据元素的自然顺序进行排序。
唯一性：TreeSet 不允许存储重复的元素。如果尝试添加已经存在的元素，则添加操作会失败（实际上，add 方法会返回 false）。

3.3.3. 主要方法

boolean add(E e)：将指定的元素添加到集合中，如果该元素已存在，则不添加并返回 false。
boolean remove(Object o)：从集合中移除指定的元素，如果集合包含该元素，则返回 true。
void clear()：移除集合中的所有元素。
boolean contains(Object o)：如果集合包含指定的元素，则返回 true。
int size()：返回集合中的元素数量。
Iterator<E> iterator()：返回集合中元素的迭代器，元素将按照排序顺序进行迭代。
SortedSet<E> headSet(E toElement)：返回此集合中小于指定元素的所有元素的集合视图。
SortedSet<E> tailSet(E fromElement)：返回此集合中大于或等于指定元素的所有元素的集合视图。
SortedSet<E> subSet(E fromElement, E toElement)：返回此集合中从 fromElement（包括）到 toElement（不包括）之间的所有元素的集合视图。

3.3.4. 线程安全性

TreeSet 不是线程安全的。如果多个线程同时访问一个 TreeSet 实例，并且至少有一个线程从结构上修改了集合，那么必须通过外部同步来保持集合的线程安全。

3.3.5. 使用示例

import java.util.TreeSet;

public class TreeSetExample {
    public static void main(String[] args) {
        TreeSet<Integer> treeSet = new TreeSet<>();

        // 添加元素
        treeSet.add(5);
        treeSet.add(2);
        treeSet.add(8);
        treeSet.add(3);
        treeSet.add(1);

        // 尝试添加重复元素
        treeSet.add(5); // 不会被添加

        // 遍历元素
        for (Integer num : treeSet) {
            System.out.println(num); // 输出: 1, 2, 3, 5, 8
        }

        // 使用自定义比较器
        TreeSet<String> stringTreeSet = new TreeSet<>((s1, s2) -> s2.length() - s1.length());
        stringTreeSet.add("apple");
        stringTreeSet.add("banana");
        stringTreeSet.add("orange");

        for (String str : stringTreeSet) {
            System.out.println(str); // 根据字符串长度降序输出
        }
    }
}

3.3.6. 注意事项

当使用 TreeSet 存储自定义对象时，对象必须实现 Comparable 接口或在创建 TreeSet 时提供 Comparator，以确保元素可以正确排序和去重。
由于 TreeSet 使用红黑树作为底层数据结构，因此它适用于需要快速查找、插入和删除操作，同时保持元素有序的场景。然而，由于其线程不安全的特性，在多线程环境下使用时需要特别注意。

3.4.其它

3.4.1.EnumSet

EnumSet 是 Java 集合框架中专门为枚举类型设计的一个类，它提供了一种高效的方式来存储和操作枚举集合。

底层数据结构：

EnumSet 的底层数据结构通常是一个位向量（bit vector）。位向量是一种数据结构，它使用位（bit）的集合来表示元素的存在与否。在 EnumSet 的情况下，每个枚举常量都映射到位向量中的一个或多个位上。由于枚举类型的元素数量是有限的，并且通常在编译时就已确定，因此使用位向量来表示这些元素是非常高效和节省空间的。

主要特点：

高效性：
- 由于使用位向量实现，EnumSet 在空间和时间上都非常高效。添加、删除和检查元素是否存在的操作都非常快，因为它们只需要对位向量进行简单的位操作。
- 当枚举类型的常量数量较少时，EnumSet 相比其他集合类（如 HashSet 或 ArrayList）可以显著减少内存占用。
类型安全：
- EnumSet 只能存储特定枚举类型的元素，因此在编译时就可以进行类型检查，避免了类型错误。
- 这种类型安全特性使得 EnumSet 成为处理枚举集合时的首选工具。
便捷的工厂方法：
- EnumSet 提供了一组静态工厂方法来创建实例，如 allOf(Class<E> elementType)、noneOf(Class<E> elementType)、of(E e1, E... es)、range(E from, E to) 和 copyOf(Collection<E> c)。这些方法使得创建和初始化 EnumSet 变得非常方便。
迭代顺序：
- EnumSet 提供了按枚举常量定义的顺序迭代元素的能力。这意味着当使用迭代器遍历 EnumSet 时，元素将按照它们在枚举类型中声明的顺序被返回。
丰富的集合操作方法：
- EnumSet 提供了丰富的集合操作方法，如交集（retainAll）、并集（addAll）、差集（removeAll）等，这些操作都是基于位向量的高效实现。
适用场景：
- 当需要处理一组固定的常量，并且这些常量属于同一个枚举类型时，使用 EnumSet 是一个很好的选择。
- EnumSet 特别适用于需要高效地进行集合操作（如添加、删除、包含检查）的场景。

3.4.2.CopyOnWriteArraySet

CopyOnWriteArraySet 是 Java 并发集合框架中的一个类，它设计用于“读多写少”的并发场景。

底层数据结构：

CopyOnWriteArraySet 的底层数据结构是 CopyOnWriteArrayList，后者是一个线程安全的可变数组。CopyOnWriteArraySet 内部持有一个 CopyOnWriteArrayList 的引用，并通过委托的方式实现所有集合操作。具体来说：

数组结构：CopyOnWriteArrayList 采用数组作为其底层数据结构，而 CopyOnWriteArraySet 则通过封装这个列表来提供集合的行为。
写时复制：在修改集合时（如添加、删除元素），CopyOnWriteArrayList 会先复制整个数组，然后在新的数组上进行修改，最后将原数组的引用指向新数组。这个过程确保了修改操作的线程安全性，同时也使得读操作能够无锁进行。

特点

线程安全：
- CopyOnWriteArraySet 是线程安全的，允许多个线程同时读取数据，而无需进行外部同步。然而，在写入数据时（如添加或删除元素），它会通过复制底层数组的方式来实现线程安全，这可能会影响到写入操作的性能。
读操作无锁：
- 读取操作（如遍历、检查元素是否存在等）是无锁的，因为它们直接操作的是原始数据的快照或副本，而不需要对原始数据进行加锁。
写操作开销大：
- 写入操作（如添加、删除元素）时，会先复制整个底层数组，然后在新的数组上进行修改，最后再将原数组的引用指向新数组。这个复制过程可能会导致较大的开销，特别是在集合较大时。
适用于读多写少的场景：
- 由于其写操作开销大但读操作高效的特点，CopyOnWriteArraySet 特别适用于读操作远多于写操作的场景。
元素唯一性：
- CopyOnWriteArraySet 不允许存储重复的元素。如果尝试添加已经存在的元素，则添加操作会失败（实际上，add 方法会返回 false）。

4.Queue接口

4.1.阻塞队列

Java中的阻塞队列（BlockingQueue）是一种支持两个附加操作的队列，这两个操作分别是：在获取元素时等待队列变为非空，以及在存储元素时等待空间变得可用。阻塞队列是线程安全的，非常适合用于生产者-消费者场景，其中生产者线程负责向队列中添加元素，而消费者线程则从队列中移除元素。

4.1.1.ArrayBlockingQueue

ArrayBlockingQueue是Java并发包java.util.concurrent中的一个类，它是一个由数组支持的有界阻塞队列，提供了线程安全的队列操作。以下是关于ArrayBlockingQueue的详细解析：

阻塞队列的特点

阻塞添加：当队列满时，继续添加元素的操作将被阻塞，直到队列中有空间可用。
阻塞移除：当队列空时，继续移除元素的操作将被阻塞，直到队列中有元素可取。
线程安全：阻塞队列的所有实现都是线程安全的，无需外部同步。

4.1.1.1.特性

有界性：ArrayBlockingQueue在创建时需要指定一个固定的大小，之后这个大小就不能再改变了。这有助于防止队列无限制地增长，从而避免内存溢出。
阻塞控制：
- 当队列满时，如果再有新的元素试图加入队列，那么这个操作会被阻塞，直到队列中有空间可用。
- 同样地，如果队列为空，那么从队列中取元素的操作也会被阻塞，直到队列中有元素可供消费。
线程安全性：ArrayBlockingQueue是线程安全的，它通过内部锁机制保证了在多线程环境下的安全性。因此，在多线程环境中，可以放心地使用它而不需要担心数据的一致性问题。
FIFO（先进先出）：ArrayBlockingQueue是一个基于数组实现的FIFO队列，元素按照它们被添加到队列的顺序被移除。
可选的公平性：ArrayBlockingQueue的构造函数允许指定一个公平性参数。如果设置为true，等待时间最长的线程将优先获得访问队列的机会。但需要注意的是，公平性可能会降低性能。

4.1.1.2.应用场景

ArrayBlockingQueue非常适用于生产者-消费者模式，其中生产者和消费者在不同的线程中运行。这种队列的应用场景包括任务调度、日志记录、消息传递等。例如，一个生产者线程可以将任务放入队列中，而一个或多个消费者线程可以从队列中取出任务并执行它们。这种模式可以提高系统的并发性能和可靠性。

4.1.1.3.主要方法

ArrayBlockingQueue提供了多种方法来操作队列，包括：

put(E e)：将指定的元素插入到此队列的尾部（如果立即可行且不会超出此队列的容量），在成功之前会等待可用的空间。
offer(E e)：如果当前没有超过容量限制，则将指定元素插入到此队列的尾部。如果当前已经满容量，则返回false。
offer(E e, long timeout, TimeUnit unit)：尝试将指定元素放入队列中，等待指定的等待时间，直到空间可用。
take()：移除此队列的头部（即在此队列上已存在的最久的元素），如果此队列为空，则等待可用元素。
poll()：移除此队列的头部（即在此队列上已存在的最久的元素），如果此队列为空，则返回null。
poll(long timeout, TimeUnit unit)：检索并移除此队列的头部，在指定的等待时间前等待可用的元素（如果有必要）。

4.1.1.4.使用注意事项

选择合适的队列大小：队列的大小应根据具体的应用场景来设置。如果设置得太小，可能会导致频繁的阻塞和上下文切换，影响性能；如果设置得太大，可能会浪费内存资源。
避免死锁：不要在持有其他锁的情况下调用ArrayBlockingQueue的阻塞方法，否则可能会导致死锁。
公平性与性能：在决定是否使用公平策略时，需要综合考虑系统的性能和公平性要求。公平性可能会降低性能。

4.1.1.5.示例代码

import java.util.concurrent.ArrayBlockingQueue;

public class ArrayBlockingQueueExample {
    public static void main(String[] args) {
        ArrayBlockingQueue<String> queue = new ArrayBlockingQueue<>(5);

        // 生产者线程
        Thread producer = new Thread(() -> {
            try {
                for (int i = 0; i < 10; i++) {
                    queue.put("Item " + i);
                    System.out.println("生产者生产了数据: " + "Item " + i);
                }
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        });

        // 消费者线程
        Thread consumer = new Thread(() -> {
            try {
                while (true) {
                    String item = queue.take();
                    System.out.println("消费者消费了数据: " + item);
                }
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        });

        producer.start();
        consumer.start();
    }
}

4.1.2.了解

4.1.2.1.ArrayDeque

底层数据结构：

ArrayDeque 底层使用一个可变的 Object[] 数组来存储元素。此外，它还有两个关键的整型变量 head 和 tail，分别表示队列的头部和尾部的位置索引。数组的大小总是 2 的幂次方，以便于进行扩容和元素定位操作。

特性：

无容量大小限制：ArrayDeque 的容量可以按需增长，它会在需要时自动扩容。
非线程安全：ArrayDeque 不是线程安全的，如果在多线程环境下使用，需要外部同步。
高性能：在用作栈或队列时，ArrayDeque 的性能通常优于 Stack 和 LinkedList。
两端操作：支持在队列的两端添加、删除元素，实现了双端队列的特性。
fail-fast：ArrayDeque 的迭代器具有快速失败（fail-fast）特性，即当迭代器创建后，如果集合被修改（结构上的修改，如添加或删除元素），迭代器将抛出 ConcurrentModificationException 异常。
不支持 null 元素：ArrayDeque 不允许存储 null 元素。

4.1.2.2.PriorityQueue

底层数据结构：

PriorityQueue的底层实现是一个小顶堆（默认情况下），这是一种特殊的完全二叉树，其中每个父节点的值都小于或等于其任何子节点的值。通过数组来存储堆中的元素，其中数组的第一个元素（索引为0）是堆顶元素，即优先级最高的元素。

特性：

无界队列：PriorityQueue的容量可以动态增长，理论上没有上限（受限于JVM的堆内存大小）。
基于优先级：队列中的元素不是按照它们被添加的顺序进行排序的，而是根据它们的自然顺序或者通过Comparator指定的顺序进行排序。
不允许null元素：尝试向PriorityQueue中添加null元素会抛出NullPointerException。
非线程安全：在多线程环境下，需要外部同步来确保线程安全。

4.2.非阻塞队列

Java中的非阻塞队列是一类特殊的队列，它们在尝试进行插入或删除操作时，如果队列状态不允许（如已满或为空），则不会使操作线程阻塞，而是会立即返回一个结果（如特殊值或异常）。这种特性使得非阻塞队列在多线程环境下能够提供更高的吞吐量和更低的延迟。

4.2.1.LinkedList

LinkedList是Java中的一个集合类，它实现了List接口和Deque接口，是一个双向链表结构。以下是对LinkedList的详细解析：

4.2.1.1.数据结构

LinkedList的底层数据结构是一个双向链表。每个节点（Node）都包含三个部分：数据元素（element）、指向前一个节点的引用（prev）和指向下一个节点的引用（next）。这种结构使得LinkedList在插入和删除操作上具有高效性，因为这些操作只需要修改相邻节点的引用，而不需要移动大量数据。

4.2.1.2.特点

动态扩容：LinkedList的大小可以动态增长，不受固定内存大小的限制。
增删快，查询慢：由于链表结构的特性，LinkedList在添加、删除元素时具有较高的效率（时间复杂度通常为O(1)），但在访问元素时效率较低（时间复杂度为O(n)），因为需要从头节点开始遍历链表。
双向遍历：由于是双向链表，LinkedList支持从头部到尾部以及从尾部到头部的双向遍历。

4.2.1.3.常用方法

LinkedList提供了丰富的方法来操作集合中的元素，包括但不限于：

boolean add(E e)：在链表末尾添加元素。
void add(int index, E element)：在链表的指定位置插入元素。
boolean addAll(Collection<? extends E> c)：将指定集合中的所有元素添加到链表的末尾。
E remove()：移除并返回链表的头元素（即第一个元素）。
E remove(int index)：移除链表中指定位置的元素。
E getFirst()：返回链表的头元素（不移除）。
E getLast()：返回链表的尾元素（不移除）。
boolean offer(E e)：在链表末尾添加一个元素（如果可能立即进行，且不会违反容量限制）。
E poll()：检索并移除此队列的头部（即第一个元素），如果此队列为空，则返回null。
E peek()：检索但不移除此队列的头部（即第一个元素），如果此队列为空，则返回null。

4.2.1.4.使用场景

LinkedList适用于需要频繁进行插入和删除操作的场景，如队列、栈等。由于它的双向遍历特性，也适用于需要双向访问元素的场景。然而，在需要频繁访问元素的场景中，使用ArrayList等基于数组实现的集合可能更为高效。

4.2.1.5.注意事项

LinkedList是非同步的，如果多个线程同时访问一个LinkedList实例，并且至少有一个线程从结构上修改了列表，那么它必须保持外部同步。
LinkedList允许包含null元素。
LinkedList的size()方法返回链表中元素的数量，但它是一个估计值，因为迭代器和分割器提供的是弱一致性的视图。

4.2.2.了解

4.2.2.1.LinkedBlockingQueue

底层数据结构：

LinkedBlockingQueue内部采用单向链表结构来存储元素。链表由一系列的节点（Node）组成，每个节点包含元素本身以及指向下一个节点的引用。这种结构使得LinkedBlockingQueue在插入和删除元素时具有较高的效率，尤其是在队列的头部和尾部进行操作时。

特点：

线程安全：LinkedBlockingQueue通过内部的锁机制和其他同步措施，确保在并发情况下数据的完整性和一致性。
阻塞特性：当队列满时，尝试插入元素的线程将被阻塞；当队列空时，尝试取出元素的线程将被阻塞。这种阻塞特性使得LinkedBlockingQueue在生产者-消费者模型中非常有用。
可选容量：LinkedBlockingQueue可以指定容量大小。如果不指定，其默认容量将等于Integer.MAX_VALUE，此时队列可以看作是无界的，但需要注意内存使用情况，避免内存溢出。
高并发性能：LinkedBlockingQueue采用两把锁的锁分离技术（putLock和takeLock），使得入队和出队操作可以并行执行，提高了并发性能。

4.2.2.2.PriorityBlockingQueue

数据结构：

PriorityBlockingQueue内部使用了一个基于数组的二叉堆来存储元素。二叉堆是一种特殊的完全二叉树，其中每个父节点的值都大于或等于（最大堆）或小于或等于（最小堆）其子节点的值。在PriorityBlockingQueue中，默认情况下，它使用自然顺序（即元素的自然排序，要求元素实现Comparable接口）来构建最大堆，但也可以通过构造函数传递一个Comparator来指定不同的排序规则。

特点：

无界性：PriorityBlockingQueue在理论上是无界的，即它可以无限地增长，直到耗尽系统资源。然而，在实际应用中，由于系统资源的限制，它可能会受到JVM堆内存大小的限制。
线程安全：PriorityBlockingQueue是线程安全的，它使用内部锁（如ReentrantLock）来确保在并发环境下的数据一致性和线程安全。
阻塞特性：虽然PriorityBlockingQueue在理论上可以无限增长，但在实际应用中，当队列中的元素数量非常多时，可能会导致较高的延迟或性能问题。不过，由于其无界性，它通常不会因为队列满而阻塞生产者线程。然而，当队列为空时，消费者线程可能会被阻塞，直到队列中有元素可用。
优先级排序：队列中的元素会根据其优先级进行排序，优先级最高的元素会最先被移除。这使得PriorityBlockingQueue非常适合用于需要按优先级处理任务的场景。

4.2.2.3.DelayQueue

底层数据结构：

PriorityQueue（优先级队列）

类型：DelayQueue的底层实现使用了PriorityQueue（优先级队列），通常是一个小顶堆或最小堆，用于存储延时元素。
特性：PriorityQueue能够快速找到剩余延时时间最小的元素，即堆顶元素，从而保证最先到期的元素能够被最先取出。
排序：PriorityQueue会根据元素的延时时间进行排序，这要求队列中的元素必须实现Delayed接口，并重写compareTo方法或提供Comparator来定义排序规则。

特点：

延时性：
- DelayQueue允许元素在插入后按照自定义的延时时间进行排序，只有延时时间小于或等于0的元素才能够被取出。这意味着元素在队列中等待直到其指定的延时时间到期。
无界性：
- DelayQueue是无界队列，可以动态增长，因此可以不断地向队列中添加元素，而不会因为队列容量限制而阻塞。然而，实际使用中需要注意内存限制，避免造成内存溢出。
线程安全性：
- DelayQueue是线程安全的，它通过内部的锁机制（如ReentrantLock）实现了线程间的互斥访问，确保了并发环境下数据的一致性和完整性。
阻塞操作：
- DelayQueue提供了阻塞式的获取元素方法（如take()），当队列为空时，调用该方法的线程会被阻塞，直到有元素到期并可以被取出。这种机制使得DelayQueue非常适合用于生产者-消费者模型中的延时任务处理。
应用场景：
- DelayQueue广泛应用于需要定时处理任务的场景，如缓存过期删除、任务调度等。通过将任务封装为具有延时属性的对象并加入DelayQueue中，可以方便地实现定时任务的自动处理。

5.Map接口

Map接口是Java中的一个重要接口，它定义了一组用于操作键值对的方法。以下是关于Map接口的详细解析：

定义：Map接口储存一组成对的键-值对象，提供key（键）到value（值）的映射。Map中的key不要求有序，不允许重复；value同样不要求有序，但可以重复。
特点：
- 键（Key）唯一性：Map中的每个键都是唯一的，不允许重复。
- 值（Value）可重复性：Map中的值可以重复。
- 映射关系：每个键都映射到一个值，但一个值可以被多个键映射（尽管在实际应用中，我们通常认为一个键映射到一个值）。
- 无序性：Map不保证元素的顺序，具体的顺序取决于具体的实现类。

二、常用实现类

HashMap：最常用的Map实现类之一，基于哈希表实现。它允许使用null键和null值，但不保证映射的顺序。HashMap的查询效率非常高，因为它通过哈希码快速定位到键所对应的值。
TreeMap：基于红黑树实现的Map接口，能够确保映射按照键的自然顺序或构造TreeMap时所提供的Comparator进行排序。
LinkedHashMap：继承自HashMap，同时保持了插入顺序。它使用双向链表来维护键值对的顺序，使得迭代遍历时的顺序与插入顺序一致。

5.1.HashMap

HashMap是Java中的一种基于哈希表的Map接口实现，它允许使用null值和null键（除了不同步和允许使用null之外，HashMap类与Hashtable大致相同）。HashMap通过哈希码（hash code）来快速定位键（key）对应的值（value），从而提供高效的存取操作。

5.1.1.HashMap的基本属性

初始容量（Initial Capacity）：HashMap在创建时的容量大小，默认为16（static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;）。容量是哈希表中桶（bucket）的数量，用于存储键值对。
加载因子（Load Factor）：HashMap在其容量自动增加之前可以达到多满的一种尺度，默认为0.75（static final float DEFAULT_LOAD_FACTOR = 0.75f;）。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则需要对哈希表进行扩容操作（即重建内部数据结构），扩容后的容量大约是原来的两倍。

5.1.2.HashMap的构造方法

HashMap提供了多个构造方法，包括：

HashMap()：无参构造方法，使用默认初始容量和加载因子。
HashMap(int initialCapacity)：指定初始容量的构造方法。
HashMap(int initialCapacity, float loadFactor)：指定初始容量和加载因子的构造方法。
HashMap(Map<? extends K, ? extends V> m)：指定一个Map集合，将其内容转换为新的HashMap。

5.1.3.HashMap的底层实现

数据结构：HashMap采用数组加链表（在Java 8及以后版本中，当链表长度超过一定阈值时，会转换为红黑树以提高查询效率）的方式来存储键值对。数组中的每个元素都是一个链表或红黑树的头节点，链表或红黑树中的节点存储了具体的键值对信息。
哈希函数：HashMap通过调用键的hashCode()方法来获取哈希码，并通过一定的算法（如位运算）将哈希码映射到数组的一个索引位置上。如果多个键的哈希码相同（即哈希冲突），则它们会被存储在同一索引位置的链表或红黑树中。
put原理：当向HashMap中添加键值对时，首先计算键的哈希码，并根据哈希码和数组长度确定存储位置。如果该位置已经存在元素，则遍历链表或红黑树以查找是否已存在相同的键。如果存在，则替换旧的值；如果不存在，则添加新的键值对到链表或红黑树的末尾（在Java 8及以后版本中，新插入的元素会放在链表的头部，但在链表转换为红黑树后，会按照红黑树的规则进行插入）。
get原理：通过键的哈希码和数组长度确定存储位置，然后遍历该位置上的链表或红黑树以查找对应的值。

5.1.4.HashMap的优缺点

优点：
- 存取效率高：通过哈希码快速定位键值对。
- 允许使用null键和null值。
- 容量和加载因子可调，以适应不同的使用场景。
缺点：
- 不保证映射的顺序。
- 迭代器的分割器是弱一致性的，这反映在弱一致性的视图上，它反映的是某一时间点或者迭代开始时的集合状态，而在实际的应用中，集合的状态是可以变化的。
- 非线程安全：在多线程环境下，如果多个线程同时修改HashMap，可能会导致数据不一致的问题。如果需要线程安全的Map，可以考虑使用ConcurrentHashMap。

5.1.5.注意事项

在使用HashMap时，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低），因为迭代集合视图所需的时间与HashMap实例的容量及其大小成比例。
HashMap不是线程安全的，如果需要在多线程环境下使用，请考虑使用ConcurrentHashMap或其他线程安全的Map实现。
在选择HashMap的初始容量和加载因子时，应根据实际的应用场景和需求进行合理设置，以平衡空间和时间成本。

5.2.TreeMap

TreeMap是Java中一个基于红黑树实现的、支持自动排序的Map接口实现类。它提供了丰富的导航和排序操作，适用于需要对键值对进行排序和区间查找的场景。然而，由于TreeMap不是线程安全的，因此在多线程环境下使用时需要注意线程安全问题。

5.2.1.TreeMap概述

数据结构：TreeMap的底层数据结构是红黑树，这是一种自平衡的二叉查找树，它通过维护节点的颜色（红色或黑色）来确保树的高度保持平衡，从而保证了插入、删除和查找操作的时间复杂度均为O(log n)。
接口继承：TreeMap实现了NavigableMap接口，而NavigableMap接口又继承了SortedMap接口。这意味着TreeMap不仅支持普通的键值对映射操作，还支持一系列的导航定位以及导航操作的方法。
其他特性：TreeMap还实现了Cloneable接口，因此可以被克隆；同时实现了Serializable接口，支持序列化操作。

5.2.2.TreeMap的特点

自动排序：TreeMap中的键值对默认按照键的自然顺序进行排序，如果键实现了Comparable接口。如果键没有实现Comparable接口，或者需要按照特定的顺序进行排序，可以在创建TreeMap时传入一个Comparator对象。
不允许null键：与HashMap不同，TreeMap不允许使用null作为键，但允许使用null作为值。
有序性：由于是基于红黑树实现的，TreeMap中的元素是有序的，可以根据键的顺序进行遍历。
区间查找：TreeMap支持按照键的范围进行查找，例如获取某个范围内的所有键或值。

5.2.3.TreeMap的常用方法

put(K key, V value)：向TreeMap中添加一个键值对。如果键已存在，则更新其对应的值。
get(Object key)：根据键获取对应的值。
remove(Object key)：根据键删除对应的键值对，并返回被删除的值。
headMap(K toKey)：返回此映射中其键小于给定键的所有键值对组成的子映射。
tailMap(K fromKey)：返回此映射中其键大于或等于给定键的所有键值对组成的子映射。
subMap(K fromKey, K toKey)：返回此映射中其键位于fromKey（包括）和toKey（不包括）之间的所有键值对组成的子映射。

5.2.4.TreeMap的适用场景

需要对Map中的键值对进行排序的场景。
需要频繁进行区间查找的场景。
需要保持元素有序性的场景。

5.2.5.TreeMap的线程安全性

TreeMap不是线程安全的，如果在多线程环境中进行并发操作，可能会导致数据不一致的问题。如果需要线程安全的Map，可以考虑使用Collections.synchronizedSortedMap对TreeMap进行包装，或者使用ConcurrentSkipListMap作为线程安全的替代。

5.3.了解

5.3.1.LinkedHashMap

LinkedHashMap是Java集合框架中的一个重要类，它继承自HashMap，并在其基础上增加了一个双向链表来维护元素的插入顺序或访问顺序。LinkedHashMap是一种结合了哈希表和双向链表优点的数据结构，它能够在保持高效查找和插入操作的同时，提供元素顺序的保证。这使得LinkedHashMap在需要保持元素顺序的场景中非常有用，如缓存系统、LRU算法等。

数据结构：

LinkedHashMap的数据结构主要由两部分组成：

哈希表：用于存储键值对，通过哈希函数将键映射到哈希表中的特定位置。哈希表解决了哈希冲突的问题，即当多个键的哈希码相同时，它们会被存储在同一索引位置的链表或红黑树中（在Java 8及以后版本中，链表长度超过一定阈值时，会转换为红黑树以提高查询效率）。
双向链表：LinkedHashMap在HashMap的基础上增加了一个双向链表，用于维护元素的顺序。这个双向链表将所有put到LinkedHashMap的节点一一串成了一个双向循环链表，因此它保留了节点插入的顺序，或者根据accessOrder的设置，可以保持元素的访问顺序。

特点：

保持遍历顺序和插入顺序一致性：默认情况下，LinkedHashMap按照元素的插入顺序进行迭代。这意味着，当你遍历LinkedHashMap时，元素的顺序将与它们被添加到映射中的顺序相同。
支持按照元素访问顺序排序：通过设置accessOrder为true，LinkedHashMap可以改为按照元素的访问顺序进行排序。在这种模式下，最近访问的元素会被移动到链表的尾部，而最久未访问的元素则位于链表的头部。这种特性使得LinkedHashMap非常适合实现LRU（最近最少使用）缓存。
高效的查找和插入操作：由于LinkedHashMap底层使用了哈希表，因此它可以在常数时间内进行查找和插入操作，无论数据规模的大小。
非线程安全：与HashMap一样，LinkedHashMap也不是线程安全的。如果多个线程同时访问并修改LinkedHashMap，可能会导致数据不一致的问题。因此，在需要线程安全的场景中，应该使用Collections.synchronizedMap对LinkedHashMap进行包装，或者使用ConcurrentHashMap等线程安全的Map实现。
占用额外的内存空间：由于需要维护双向链表的顺序，LinkedHashMap相比于HashMap会占用更多的内存空间。然而，这种额外的内存开销通常是可以接受的，特别是在需要保持元素顺序的场景中。
实现了Map接口：LinkedHashMap实现了Map接口，因此它提供了Map接口定义的所有方法，包括put、get、remove等。
可序列化：LinkedHashMap实现了Serializable接口，因此它支持序列化操作。这意味着你可以将LinkedHashMap对象的状态保存到文件中，或者通过网络发送给其他程序进行恢复或共享。

5.3.2.ConcurrentHashMap

ConcurrentHashMap是Java集合框架中的一个重要类，专为高并发环境设计。适用于读写操作都非常频繁的高并发场景，并提供了出色的性能和线程安全性。

数据结构

JDK 1.7及之前版本

分段锁（Segment Locking）：在JDK 1.7及之前的版本中，ConcurrentHashMap使用了分段锁的机制。整个Map被分为多个Segment，每个Segment都独立地维护着自己的锁，这样不同的线程可以同时访问不同的Segment，从而提高并发性能。每个Segment内部使用哈希表来存储键值对，当哈希冲突发生时，使用链表解决。

JDK 1.8及之后版本

桶级锁（Bucket Locking）：从JDK 1.8开始，ConcurrentHashMap放弃了分段锁，转而使用更细粒度的桶级锁。Map内部使用一个Node数组来存储键值对，每个数组元素（桶）可能包含一个链表或红黑树。当哈希冲突发生时，会根据冲突的情况选择链表或红黑树来存储数据。这种结构使得ConcurrentHashMap在处理哈希冲突时既高效又灵活。
CAS（Compare-And-Swap）算法：在JDK 1.8中，ConcurrentHashMap还引入了CAS算法来辅助实现无锁的线程安全操作，以提高并发性能。

特点

高性能：通过细粒度的锁机制（如分段锁和桶级锁）和高效的内部数据结构（如链表和红黑树），ConcurrentHashMap能够提供出色的并发性能。
线程安全：ConcurrentHashMap是线程安全的，允许多个线程同时读取和写入数据，而无需进行外部同步。读操作通常不需要加锁，写操作则只在必要的桶上加锁，从而减少了锁的竞争。
分段锁/桶级锁：通过分段锁或桶级锁的机制，ConcurrentHashMap能够减少锁的粒度，提高并发访问的效率。在JDK 1.8及以后版本中，桶级锁进一步细化了锁的粒度，使得性能得到了进一步提升。
锁分离：在JDK 1.7及之前版本中，ConcurrentHashMap通过分段锁实现了锁分离，每个Segment都有自己的锁。在JDK 1.8及以后版本中，虽然不再使用分段锁，但桶级锁也实现了类似的锁分离效果，使得不同的桶可以并行地进行读写操作。
惰性锁释放：在写操作时，ConcurrentHashMap只需要锁住当前操作的桶或Segment，其他的桶或Segment仍然可以被读取。这种惰性锁释放的策略有助于提高并发的效率。
不支持空键值对：ConcurrentHashMap不支持将null作为键或值存储。如果尝试添加null键或值，将会抛出NullPointerException异常。
弱一致性：ConcurrentHashMap提供了弱一致性的原则。这意味着当一个线程进行写入后，不保证其他线程立即可见修改结果。这种设计是为了提供更好的吞吐量并减少同步的开销。
扩容机制：在需要扩容时，ConcurrentHashMap能够高效地进行扩容操作。在JDK 1.8及以后版本中，扩容操作只会影响需要扩容的桶或Segment，而不会对整个Map进行锁定，从而减少了扩容对并发性能的影响。

5.3.3.identityHashMap

IdentityHashMap是Java集合框架中的一个特殊Map实现，IdentityHashMap是一个基于引用相等性的特殊Map实现，它提供了与HashMap不同的键值比较方式和一些特定的用途。然而，由于其无序性和对null键的特殊处理，它并不适合所有场景下的Map需求。

数据结构

IdentityHashMap的数据结构相对简单，底层实际就是一个Object数组。但是，在存储上，它并没有像HashMap那样使用链表或红黑树来处理哈希冲突，而是直接将K（键）和V（值）都存放在Object数组上。具体来说，如果某个键的索引为i，那么其对应的值就会存放在索引i+1的位置上。当数组中的元素个数达到一定阈值时，IdentityHashMap会自动进行扩容处理，扩容后的数组长度为当前长度的两倍。

特点

引用相等性：
- IdentityHashMap在比较键（Key）时，使用的是引用相等（==）而不是equals()方法。这意味着在IdentityHashMap中，两个对象被认为是相等的当且仅当它们是同一个对象的引用。这与HashMap不同，HashMap在默认情况下使用equals()方法来比较键的相等性。
无序性：
- IdentityHashMap不会对其中的键值对进行排序。它会根据键的插入顺序来遍历键值对，但并不会按照键的自然顺序或任何特定的排序规则进行排序。
允许null键和null值：
- IdentityHashMap允许使用null作为键和值。但是，需要注意的是，由于它使用引用相等来比较键，因此即使有两个null键，它们也被视为是同一个键，后插入的null键会覆盖先插入的null键的值。
性能：
- 由于IdentityHashMap在比较键时不需要调用equals()方法，因此在某些情况下（特别是当键是自定义对象且equals()方法的实现较为复杂时），它的性能可能会优于HashMap。但是，这种性能优势并不是绝对的，因为HashMap在扩容和哈希冲突处理方面也有其优化措施。
典型用途：
- IdentityHashMap的一个典型用途是保留拓扑的对象图转换，例如序列化或深度复制。在这些场景中，程序需要维护一个“节点表”来跟踪已经处理的所有对象引用，而IdentityHashMap能够确保不同的对象引用不会被视为相等，即使它们的内容相同。
扩容机制：
- 当IdentityHashMap中的元素个数超过当前容量的某个阈值时（通常是容量的某个比例），它会进行扩容操作。扩容后的数组长度为当前长度的两倍，并且会重新计算所有元素的哈希值并插入到新的数组中。这个过程是自动进行的，无需用户干预。

5.4.HashTable（过时）

HashTable（哈希表），也被称为散列表，是一种基于哈希函数实现的数据结构，主要用于存储键值对，并允许通过键快速访问对应的值。HashTable是一种基于哈希函数实现的高效数据结构，具有快速查找、高效插入和删除、灵活扩容等特点。然而，它也需要消耗较多的存储空间，并且其性能受到哈希函数质量的影响。

数据结构

1. 哈希函数

哈希函数是HashTable的核心，它将输入的键（Key）映射到表中的一个位置（即哈希地址）。不同的哈希函数可能会产生不同的映射效果，常见的哈希函数包括CRC32、MD5、SHA等。
哈希函数的设计需要考虑到计算时间、关键字的长度、哈希表的大小以及关键字的分布情况，以尽量减少哈希冲突的发生。

2. 哈希表

哈希表是一个数组，用于存储通过哈希函数映射后的键值对。每个数组元素（也称为槽或桶）可以存储一个键值对或指向一个数据结构（如链表、红黑树等）的指针，用于处理哈希冲突。

3. 冲突解决机制

当多个键映射到哈希表的同一位置时，会发生哈希冲突。为了解决这个问题，HashTable通常采用以下几种冲突解决机制：
- 链地址法（拉链法）：每个数组元素指向一个链表，链表中的每个节点存储一个键值对。当发生冲突时，新的键值对将添加到相应链表的末尾。
- 开放寻址法：当发生冲突时，根据一定的探测序列在哈希表中寻找下一个空闲位置，并将新的键值对存储在该位置。常见的探测序列包括线性探测、二次探测和双重哈希等。

特点

1. 快速查找

通过哈希函数可以直接定位到键值对在哈希表中的位置，因此查找操作的时间复杂度通常为O(1)，即常数时间复杂度。这使得HashTable在需要快速查找的场景下非常有用。

2. 高效插入和删除

插入和删除操作也只需要计算一次哈希函数并处理可能的冲突即可，因此这些操作也具有较高的效率。

3. 灵活扩容

当哈希表中的元素数量超过一定阈值时，HashTable会自动进行扩容操作，以维持操作的效率。扩容后，哈希函数和冲突解决机制可能需要重新调整。

4. 存储空间利用率

HashTable通过牺牲一定的存储空间来换取查找、插入和删除操作的高效性。在实际应用中，需要根据具体需求来平衡存储空间和操作效率之间的关系。

5. 依赖于哈希函数

HashTable的性能在很大程度上取决于哈希函数的质量。一个好的哈希函数能够减少哈希冲突的发生，从而提高HashTable的整体性能。

过时原因：

性能问题

同步开销：Hashtable是线程安全的，其所有公共方法都是同步的。这种同步机制在多线程环境下虽然保证了数据的一致性，但也带来了显著的性能开销。相比之下，现代Java集合框架中的其他并发集合，如ConcurrentHashMap，通过更细粒度的锁（如分段锁或CAS操作）来提高并发性能，减少了不必要的同步开销。
迭代性能：Hashtable的迭代器不是fail-fast的，这意味着在迭代过程中如果集合被修改，可能会抛出异常。而现代集合类提供了更好的迭代控制机制，允许更灵活和安全地遍历集合。

功能限制

键和值不能为null：Hashtable不允许键和值为null，这在某些场景下可能不太方便。相比之下，HashMap允许一个null键和多个null值，提供了更大的灵活性。
可扩展性：Hashtable在扩容时可能需要重新计算所有元素的哈希值，并重新分配到新的数组中，这可能导致性能下降。而现代集合类在扩容时通常采用了更高效的策略来减少这种影响。

可读性和维护性

代码风格：Hashtable的代码风格相对古老，可能不符合现代Java编程的命名规范和最佳实践。这可能导致代码难以阅读和维护。
替代品的普及：随着Java集合框架的不断发展和完善，出现了许多功能更强大、性能更优的集合类。这些类不仅提供了与Hashtable相似的功能，还在多个方面进行了改进和优化。因此，开发者更倾向于使用这些现代集合类来替代Hashtable。

并发性能

分段锁与CAS操作：现代并发集合类，如ConcurrentHashMap，采用了分段锁或CAS（Compare-And-Swap）操作等技术来提高并发性能。这些技术允许多个线程同时访问集合的不同部分，从而减少了锁竞争和提高了吞吐量。相比之下，Hashtable的全局锁机制在多线程环境下可能导致性能瓶颈。

6.集合泛型

Java的集合泛型是Java SE 1.5（也称为Java 5）引入的一个重要特性，它允许在定义类、接口和方法时通过类型参数来指定类或接口中某些属性的类型，或者是方法的返回值及参数类型。这一特性极大地提高了代码的重用性、安全性和可读性。

6.1.泛型的定义

泛型（Generics）的本质是参数化类型，即所操作的数据类型被指定为一个参数。这种参数类型可以用在类、接口和方法的创建中，分别称为泛型类、泛型接口和泛型方法。

6.2.泛型的好处

类型安全：泛型可以在编译时期检查类型错误，避免在运行时出现ClassCastException。
消除强制类型转换：使用泛型后，编译器会自动进行类型转换，无需程序员手动进行强制类型转换，减少了出错的可能性。
提高代码的重用性：通过泛型，可以编写更加通用的代码，使其能够应用于多种数据类型。

6.3.泛型的使用

6.3.1. 泛型类

在定义类时，可以在类名后添加一对尖括号，并在其中填写类型参数。例如：

public class GenericClass<T> {
    private T value;

    public GenericClass(T value) {
        this.value = value;
    }

    public T getValue() {
        return value;
    }

    public void setValue(T value) {
        this.value = value;
    }
}

6.3.2. 泛型接口

泛型接口的定义与泛型类类似，也是在接口名后添加类型参数。例如：

public interface GenericInterface<T> {
    void show(T value);
}

实现泛型接口时，可以指定具体的类型，也可以不指定（称为原始类型）。

6.3.3. 泛型方法

泛型方法可以在泛型类中定义，也可以在普通类中定义。泛型方法是在方法声明时指定类型参数，而不是在类声明时。例如：

public class GenericMethods {
    public static <T> void printArray(T[] inputArray) {
        for (T element : inputArray) {
            System.out.printf("%s ", element);
        }
        System.out.println();
    }
}

6.4.泛型在集合中的应用

Java集合框架（Java Collections Framework）是Java提供的一套用于存储和操作集合的统一架构。集合类主要负责保存、盛装和管理对象，因此也被称为容器类。Java集合类主要分为List、Set、Map和Queue四大体系。

List：代表有序、可重复的集合。常见的实现类有ArrayList和LinkedList。
Set：代表无序、不可重复的集合。常见的实现类有HashSet、LinkedHashSet和TreeSet。
Map：代表具有映射关系的集合，每个元素都是一个键值对。键是唯一的，值可以重复。常见的实现类有HashMap和TreeMap。

在集合中使用泛型可以指定集合中元素的类型，从而提高代码的类型安全性和可读性。例如：

List<String> stringList = new ArrayList<>();
stringList.add("Hello");
stringList.add("World");

// 无需强制类型转换即可直接获取String类型的元素
String firstElement = stringList.get(0);

7.集合遍历

Java中集合的遍历方式多种多样，每种方式都有其适用的场景和优缺点。下面列举了一些常见的集合遍历方式：

Java中集合（如List、Set、Map等）的遍历方法有多种，每种方法都有其适用的场景和优缺点。下面将分别介绍你提到的几种遍历方法：for循环（更准确地说是增强型for循环，即for-each循环的一种）、for-each循环、Iterator迭代器以及Stream流处理。

7.1. for循环（传统方式，适用于数组）

对于数组，我们通常使用传统的for循环来遍历。但对于集合，这种方式不太常见，因为Java集合类没有直接支持通过索引访问元素（除了List接口的实现类如ArrayList、LinkedList等，但即便如此，也推荐使用下面的方法）。

7.2. for-each循环（增强型for循环）

for-each循环（也称为增强型for循环）是Java 5中引入的，用于简化数组的遍历和实现了Iterable接口的集合的遍历。这种方式代码更简洁，易读性更高。

List<String> list = Arrays.asList("apple", "banana", "cherry");
for (String fruit : list) {
    System.out.println(fruit);
}

7.3. Iterator迭代器

Iterator是Java集合框架的一部分，提供了一种遍历集合的通用方式。使用Iterator可以在遍历过程中安全地删除元素，同时提供对集合遍历的更多控制。

List<String> list = Arrays.asList("apple", "banana", "cherry");
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String fruit = iterator.next();
    System.out.println(fruit);
    // 可以在这里进行删除操作，如 iterator.remove();
}

7.4. Stream流处理

Java 8引入了Stream API，提供了一种高效且表达性强的方式来处理数据集合（包括数组、集合等）。Stream API可以通过声明性方式处理数据集合（如筛选、排序和映射），并可以利用多核处理器的优势进行并行处理。

List<String> list = Arrays.asList("apple", "banana", "cherry");
list.stream()
    .forEach(fruit -> System.out.println(fruit));

// 使用Stream进行更复杂的数据处理
list.stream()
    .filter(fruit -> fruit.startsWith("a"))
    .sorted()
    .forEach(System.out::println);

7.5.总结

for-each循环：简单、直观，适用于简单的遍历操作。
Iterator迭代器：提供了更多的遍历控制，如删除元素，同时兼容所有实现了Iterable接口的集合。
Stream流处理：强大的数据处理能力，支持复杂的集合操作，如过滤、映射、排序等，并且可以并行处理，提高性能。

如果数据在1万以内的话，for循环效率高于foreach和stream；如果数据量在10万的时候，stream效率最高，其次是foreach,最后是for。另外需要注意的是如果数据达到100万的话，parallelStream异步并行处理效率最高，高于foreach和for

8.集合工具类

8.1.Properties

在Java中，Properties 类是 java.util 包的一部分，它继承自 Hashtable<Object,Object> 类。但是，Properties 类被设计用来处理以持久的存储方式（如文件）存在的配置数据。尽管它继承自 Hashtable，但它有两个主要的区别：

键和值的类型限制：Properties 类中的键和值通常是字符串。虽然技术上可以存储其他类型的对象（因为它是基于 Hashtable 的），但通常不建议这样做，因为 Properties 类提供了许多专门处理字符串键和值的方法。
持久化：Properties 类提供了将属性列表（键和元素对）保存到流中以及从流中加载属性列表的方法。这使得 Properties 类成为处理配置文件（如 .properties 文件）的理想选择。

主要方法

load(InputStream inStream)：从字节输入流中读取属性列表（键和元素对）。
load(Reader reader)：按简单的面向行的格式从输入字符流中读取属性列表（键和元素对）。
loadFromXML(InputStream in)：从 XML 文档读取属性列表（键和元素对）。
store(OutputStream out, String comments)：将此 Properties 表中的属性列表（键和元素对）写入输出流。
store(Writer writer, String comments)：以适合使用 load(Reader) 方法加载到 Properties 表中的格式，将此 Properties 表中的属性列表（键和元素对）写入输出字符流。
storeToXML(OutputStream os, String comment)：以 XML 文档的形式将此 Properties 表中的属性列表（键和元素对）写入输出流。
setProperty(String key, String value)：调用 Hashtable 的方法 put。
getProperty(String key)：用指定的键搜索属性。
getProperty(String key, String defaultValue)：用指定的键搜索属性；如果找不到该键，则返回默认值。

示例

以下是一个简单的示例，展示了如何使用 Properties 类加载和保存属性文件：

import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.Properties;

public class PropertiesExample {
    public static void main(String[] args) {
        Properties prop = new Properties();
        try {
            // 加载属性文件
            prop.load(new FileInputStream("config.properties"));

            // 获取属性值
            String dbUrl = prop.getProperty("db.url");
            System.out.println("DB URL: " + dbUrl);

            // 设置属性值
            prop.setProperty("db.user", "newUser");

            // 保存更新后的属性文件
            prop.store(new FileOutputStream("config.properties"), "Updated Configuration");

        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

在这个示例中，我们首先加载了一个名为 config.properties 的文件，该文件包含了一些配置属性（如数据库URL）。然后，我们读取了一个属性值，并更新了另一个属性值。最后，我们将更新后的属性列表保存回同一个文件。

请注意，Properties 文件通常以 .properties 为文件扩展名，并且它们的格式非常简单，每行包含一个键=值的对，其中键和值之间用等号（=）分隔，键和值周围可以有空格。

8.2.Collections

在Java中，Collections 是一个帮助类和接口操作的工具类，它位于 java.util 包中。Collections 类提供了多种静态方法，用于对集合（如 List、Set、Map 等）进行排序、搜索、替换、填充、复制等操作，而无需修改集合类本身的源代码。这些操作使得集合的使用更加灵活和强大。

主要方法

以下是 Collections 类中一些常用的方法：

排序：
- sort(List<T> list)：对列表进行自然排序。
- sort(List<T> list, Comparator<? super T> c)：根据提供的比较器对列表进行排序。
搜索：
- binarySearch(List<? extends Comparable<? super T>> list, T key)：使用二分查找算法在列表中搜索指定对象的索引。
- binarySearch(List<? extends T> list, T key, Comparator<? super T> c)：根据提供的比较器，使用二分查找算法在列表中搜索指定对象的索引。
替换：
- replaceAll(List<T> list, T oldVal, T newVal)：将列表中的所有旧值替换为新值。
填充：
- fill(List<? super T> list, T obj)：使用指定对象填充指定列表的所有位置。
复制：
- copy(List<? super T> dest, List<? extends T> src)：将源列表中的所有元素复制到目标列表中。
不可修改集合：
- unmodifiableList(List<? extends T> list)：返回指定列表的不可修改视图。
- unmodifiableSet(Set<? extends T> s)：返回指定集合的不可修改视图。
- unmodifiableMap(Map<? extends K, ? extends V> m)：返回指定映射的不可修改视图。
最大/最小值：
- max(Collection<? extends T> coll, Comparator<? super T> comp)：根据提供的比较器，返回集合中的最大值。
- min(Collection<? extends T> coll, Comparator<? super T> comp)：根据提供的比较器，返回集合中的最小值。
其他：
- shuffle(List<?> list)：使用默认随机源对列表进行随机排序。
- shuffle(List<?> list, Random rnd)：根据指定的随机源对列表进行随机排序。
- reverse(List<?> list)：反转列表中元素的顺序。
- rotate(List<?> list, int distance)：将列表中的元素向右（正距离）或向左（负距离）旋转指定的距离。

示例

如何使用 Collections 类对列表进行排序和搜索：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class CollectionsExample {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>();
        numbers.add(5);
        numbers.add(3);
        numbers.add(9);
        numbers.add(1);

        // 对列表进行排序
        Collections.sort(numbers);
        System.out.println("Sorted list: " + numbers);

        // 使用二分查找搜索元素
        int index = Collections.binarySearch(numbers, 3);
        if (index >= 0) {
            System.out.println("Element found at index: " + index);
        } else {
            System.out.println("Element not found");
        }
    }
}

8.3.Arrays

在Java中，Arrays 类是一个提供用来操作数组（比如排序和搜索）的各种方法的工具类。这个类位于 java.util 包中，是Java集合框架的一部分，尽管它实际上并不直接实现集合接口。Arrays 类提供的方法都是静态的，因此你不需要创建 Arrays 类的实例来使用它们，而是直接通过类名调用它们。

主要方法

以下是一些 Arrays 类中常用的方法：

排序：
- sort(int[] a)：对指定 int 型数组按数字升序进行排序。
- sort(Object[] a)：对指定对象数组根据其元素的自然顺序进行排序。
- sort(T[] a, Comparator<? super T> c)：根据指定比较器产生的顺序对指定对象数组进行排序。
搜索：
- binarySearch(int[] a, int key)：使用二分查找算法在指定 int 型数组中搜索特定值的索引。
- binarySearch(Object[] a, Object key)：使用二分查找算法在指定对象数组中搜索特定值的索引。
- binarySearch(T[] a, int fromIndex, int toIndex, T key)：使用二分查找算法在指定对象数组的指定范围内搜索特定值的索引。
填充：
- fill(int[] a, int val)：将指定 int 型数组的所有元素设置为指定的值。
- fill(Object[] a, Object val)：将指定对象数组的所有元素设置为指定的对象值。
复制：
- copyOf(int[] original, int newLength)：复制指定的数组，返回所需长度的新数组。
- copyOfRange(int[] original, int from, int to)：复制指定数组范围的元素到新数组。
比较：
- equals(int[] a, int[] a2)：如果两个指定的 int 型数组彼此相等，则返回 true。
- deepEquals(Object[] a1, Object[] a2)：如果两个指定数组的内容相同，则返回 true。
转换：
- asList(T... a)：返回由指定数组支持的固定大小的列表。

示例

如何使用 Arrays 类对数组进行排序和搜索：

import java.util.Arrays;

public class ArraysExample {
    public static void main(String[] args) {
        int[] numbers = {5, 3, 9, 1};

        // 对数组进行排序
        Arrays.sort(numbers);
        System.out.println("Sorted array: " + Arrays.toString(numbers));

        // 搜索数组中的元素
        int index = Arrays.binarySearch(numbers, 3);
        if (index >= 0) {
            System.out.println("Element found at index: " + index);
        } else {
            System.out.println("Element not found");
        }

        // 填充数组
        Arrays.fill(numbers, 0);
        System.out.println("Array filled with zeros: " + Arrays.toString(numbers));

        // 复制数组
        int[] copiedNumbers = Arrays.copyOf(numbers, numbers.length);
        System.out.println("Copied array: " + Arrays.toString(copiedNumbers));
    }
}

注意，Arrays.asList() 方法是一个特殊的方法，它返回的是一个固定大小的列表，该列表是由原始数组支持的。这意味着如果你修改了列表的结构（比如添加或删除元素），将会抛出 ConcurrentModificationException 异常，因为列表的大小是固定的。但是，你可以修改列表中的元素（如果它们是可变对象的话）。

标签：元素,列表,链表,线程,哈希,集合
From： https://www.cnblogs.com/tubby233/p/18344806