集合类是Java数据结构的实现。Java的集合类是java.util包中的重要内容，它允许以各种方式将元素分组，并定义了各种使这些元素更容易操作的方法。Java集合类是Java将一些基本的和使用频率极高的基础类进行封装和增强后再以一个类的形式提供。集合类是可以往里面保存多个对象的类，存放的是对象，不同的集合类有不同的功能和特点，适合不同的场合，用以解决一些实际问题。

原文链接：

全网最完整Java学习笔记

java基础——java集合list详解、JUC中的List安全类集合

HashMap底层原理、HashMap安全性问题、Java中的ConcurrentHashMap原理详解

Java集合（四）Set的常用实现类

集合体系

集合和映射

在Java中，集合是一组用于操作和存储数据的接口和类。 它主要包括Collection和Map两种。

集合（Collection）：一组单独的元素。它通常应用了某种规则，例如 List（列表）必须按特定的顺序容纳元素，而一个Set（集）不可包含任何重复的元素。
映射（Map）：一系列“键－值”对的集合。它的存储内容是一系列键值对，如果知道了键（key），我们可以直接获取到这个键所对应的值（value），时间复杂度是O(1)。散列表是Map的一种较为普遍的展现。

Java中的集合类分为4大类,分别由4个接口来代表,它们是Set、List、Queue、Map。其中,Set、List、Queue接口都继承自Collection接口，Map接口不继承自其他接口。

Set代表无序的、元素不可重复的集合。

List代表有序的、元素可以重复的集合。有序说的是元素顺序直接由插入顺序决定。

Queue代表先进先出（FIFO）的队列。

Map代表具有映射关系（key-value）的集合。

Java提供了众多集合的实现类，它们都是这些接口的直接或间接的实现类，其中比较常用的有：HashSet、TreeSet、ArrayList、LinkedList、ArrayDeque、HashMap、TreeMap等。

常见集合的底层和性能对比

集合	使用场景	底层	性能
ArrayList	频繁查询但不经常增删元素	数组，允许存储多个null值	查询（get、contains）操作时间复杂度为O(1)，添加（add）和删除（remove）元素时，可能需要移动数组中的元素，导致时间复杂度为O(n)
LinkedList	频繁增删元素但不经常查询	链表，允许存储多个null值	查询很慢（需要从头（或尾）遍历链表，查询操作时间复杂度为O(n) ），增删很快（只需调整链表的指针，插入（add）和删除（remove）操作时间复杂度为O(1)）
Stack	需要后进先出（LIFO）访问顺序的数据结构，例如递归、回溯算法等。线程安全，因为它是Vector的实现类	数组（因为它是Vector的实现类），允许存储多个 null 值	增删改查都是在栈顶操作，所以时间复杂度都是O(1)
HashSet	需要高效去重、快速查找、不考虑内存浪费的场景	哈希表（快速查找）和Set（去重）。它自动对元素进行去重（通过 hashCode 和 equals 方法），并且无序（存入后顺序会乱），允许存储一个null值。	底层是哈希表，所以插入、删除和查找操作的时间复杂度都是O(1)，代价是浪费一些空间。
TreeSet	适用于多读少写、排序的场景	红黑树（快速查找、排序）和Set（去重），不允许存储null值	插入、删除、查找操作的时间复杂度为O(log n)，因为操作需要维护树的平衡，所以适用于多读少写的场景。
HashMap	适用于多读少写、需要快速读的场景。	哈希表（快速查找）和Map（键值对），可以存储一个null键（key）和多个null值（value）。	底层是哈希表，所以插入、删除和查找操作的时间复杂度都是O(1)，代价是浪费一些空间。

Stack常用方法：

• **push(E item)**：将元素压入栈顶
• **pop()**：移除并返回栈顶元素
• **peek()**：返回栈顶元素但不移除
• **isEmpty()**：检查栈是否为空
• **search(Object o)**：返回元素在栈中的位置，以 1 为基准

红黑树：

近似平衡二叉树，左右子树高差可能大于 1，查找效率略低于平衡二叉树，但增删效率高于平衡二叉树，适合频繁插入删除。

• 结点非黑即红；

• 根结点是黑色，叶节点是黑色空节点（常省略）；

• 任何相邻节点不能同时为红色；

• 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点；

• **查询性能稳定O(logN)**，高度最高2log(n+1)；

知识加油站

集合的线程安全性

线程不安全的集合：

Java提供了众多集合的实现类,它们都是这些接口的直接或间接的实现类，其中比较常用的有：HashSet、TreeSet、ArrayList、LinkedList、ArrayDeque、HashMap、TreeMap等。这些集合都是线程不安全的。

线程安全的集合：

1. Collections工具类：Collections工具类的synchronizedXxx()方法，将ArrayList等集合类包装成线程安全的集合类。例如

   List list = Collections.synchronizedList(new ArrayList());

2. 古老api：如Vector、Hashtable，在JDK1就出现了，不推荐使用，因为线程安全的方案不成熟，性能差。

3. 降低锁粒度的并发容器（推荐）：JUC包下Concurrent开头的、以降低锁粒度来提高并发性能的容器，如ConcurrentHashMap。适用于读写操作都很频繁的场景。

4. 复制技术实现的并发容器：JUC包下以CopyOnWrite开头的、采用写时写入时复制技术实现的并发容器，如CopyOnWriteArrayList。写操作时，先将当前数组进行一次复制，对复制后的数组进行操作，操作完成后再将原来的数组引用指向复制后的数组。避免了并发修改同一数组的线程安全问题。适用于读操作比写操作频繁且数据量不大的场景。适用于读操作远多于写操作的场景。

什么是线程不安全

线程不安全是指在多线程环境下，当多个线程并发地访问和修改共享数据时，由于缺乏适当的同步机制，可能导致数据的不一致、错误或者程序行为不可预测的现象。

Collection常用API

• **add()**：向集合中添加一个元素。
• 获取元素：没有直接提供获取指定位置元素的方法，因为它的实现类元素不一定有序。若需访问，需要通过迭代器iterator()
• **remove()**：从集合中移除一个指定的元素。
• **contains(Object o)**： 检查集合中是否包含指定元素。
• **size()**：返回集合中的元素数量。
• **isEmpty()**：检查集合是否为空。
• clear():：移除集合中的所有元素。

常用工具类

Java 的集合框架提供了许多有用的工具类，用于简化集合的操作。最常见的工具类是 java.util.Collections 和 java.util.Arrays。这些工具类提供了许多静态方法，可以对集合进行排序、搜索、填充、反转等操作

集合工具类Collections

Collections工具类常用方法：

• sort(List<T> list)：对指定的列表按自然顺序进行升序排序。
• sort(List list, Comparator<? super T> c)：使用指定的比较器对指定的列表进行排序。
• reverse(List<?> list)：反转指定列表中元素的顺序。
• max(Collection<? extends T> coll)：返回给定集合的最大元素，按自然顺序比较。
• max(Collection<? extends T> coll, Comparator<? super T> comp)：返回给定集合的最大元素，使用指定的比较器比较。
• binarySearch(List<? extends T> list, T key)：使用二分法搜索指定列表以查找指定对象。
• copy(List<? super T> dest, List<? extends T> src)：将源列表的所有元素复制到目标列表中。
• fill(List<? super T> list, T obj)：用指定的元素替换指定列表中的所有元素。
• frequency(Collection<?> c, Object o)：返回指定集合中等于指定对象的元素数。
• indexOfSubList(List<?> source, List<?> target)：返回指定源列表中首次出现指定目标列表的起始位置。
• swap(List<?> list, int i, int j)：交换指定列表中指定位置的元素。

代码示例：

public class CollectionsExample {
    public static void main(String[] args) {
        // 创建一个ArrayList并添加元素
        List<Integer> list = new ArrayList<>();
        list.add(5);list.add(3);list.add(8);list.add(1);list.add(6);
        // 输出原始列表
        System.out.println("原始列表: " + list);
        // 使用sort方法按自然顺序排序
        Collections.sort(list);
        System.out.println("排序后的列表: " + list);
        // 使用reverse方法反转列表
        Collections.reverse(list);
        System.out.println("反转后的列表: " + list);
        // 使用binarySearch方法查找元素
        int index = Collections.binarySearch(list, 3);
        System.out.println("元素3的索引: " + index);
        // 创建一个目标列表并使用copy方法复制元素
        List<Integer> destList = new ArrayList<>(Collections.nCopies(list.size(), 0));
        Collections.copy(destList, list);
        System.out.println("复制后的目标列表: " + destList);
        // 使用fill方法填充列表
        Collections.fill(list, 7);
        System.out.println("填充后的列表: " + list);
        // 使用swap方法交换元素
        Collections.swap(destList, 0, destList.size() - 1);
        System.out.println("交换后的目标列表: " + destList);
    }
}

7.1.3.2 数组工具类Arrays
Arrays工具类常用方法：

• asList(T... a)：将数组转换为固定大小列表。例如Arrays.asList(1,2,3);则返回有三个元素的数组

  • 基本类型数组视作单个元素：如果传入基本类型数组，会将其整个数组视作单个元素。

    int[] nums = {1,2};
    Arrays.asList(nums); 
    // 返回列表是List<int[]>类型，只有一个数组元素。而传入对象类型（String、包装类等），则会拆开。
    Integer[] nums={1,2};
    Arrays.asList(nums);
    // 返回列表是List<Integer>类型。其实主要原因是List<T>，T只能是包装类、数组、对象，不能是基本数据类型。

  • 与原数组共享内存：asList()后，修改列表的元素，变动会同步到原数组。

  • 列表固定大小：因为返回列表与原数组共享数据，所以列表是固定大小的，不能再增删元素。

• sort(T[] a)：对指定数组按自然顺序进行升序排序。

• sort(T[] a, Comparator<? super T> c)：使用指定的比较器对数组进行排序。

• binarySearch(T[] a, T key)：使用二分法搜索指定数组以查找指定对象。

• binarySearch(T[] a, T key, Comparator<? super T> c)：使用二分法搜索指定数组以查找指定对象，使用指定的比较器。

• copyOf(T[] original, int newLength)：复制指定的数组，截取或填充 null 以使副本具有指定的长度。

• copyOfRange(T[] original, int from, int to)：复制指定的数组，从指定的起始位置开始到终止位置结束。

• equals(Object[] a, Object[] a2)：如果两个指定数组彼此相等，则返回 true。一维数组时比较内容是否一致，多维数组时只比较最外层数组对象的内容。

• deepEquals(Object[] a1, Object[] a2)：如果两个指定数组彼此深度相等，则返回 true。一维和多维数组比较内容是否一致。

• fill(T[] a, T val)：用指定的值填充指定数组。

• toString(T[] a)：返回指定数组内容的字符串表示形式。

• deepToString(Object[] a)：返回指定数组内容的深层字符串表示形式。

public class Test {
    public static void main(String[] args) {
        // 使用asList方法将数组转换为列表。列表与原数组共享内存，列表固定大小
        String[] stringArray = {"apple", "banana", "cherry"};
        List<String> stringList = Arrays.asList(stringArray);
        System.out.println("数组转换为列表: " + stringList);
        // 使用sort方法对数组进行排序
        int[] intArray = {5, 3, 8, 1, 6};
        System.out.println("原数组（直接打印）: " + intArray);
        System.out.println("原数组（用Arrays.toString()打印）：" + Arrays.toString(intArray));
        Arrays.sort(intArray);
        System.out.println("排序后的数组: " + Arrays.toString(intArray));
        // 使用binarySearch方法查找元素
        int index = Arrays.binarySearch(intArray, 3);
        System.out.println("元素3的索引: " + index);
        // 使用copyOf方法复制数组
        int[] copiedArray = Arrays.copyOf(intArray, intArray.length);
        System.out.println("复制后的数组: " + Arrays.toString(copiedArray));
        // 使用deepEquals方法比较多维数组
        Integer[][] deepArray1 = {{1, 2}, {3, 4}};
        Integer[][] deepArray2 = {{1, 2}, {3, 4}};
        boolean deepEqual = Arrays.deepEquals(deepArray1, deepArray2);
        System.out.println("多维数组是否深度相等: " + deepEqual);
        // 使用fill方法填充数组
        int[] fillArray = new int[5];
        Arrays.fill(fillArray, 7);
        System.out.println("填充后的数组: " + Arrays.toString(fillArray));
        // 使用toString方法将数组转换为字符串
        String arrayString = Arrays.toString(intArray);
        System.out.println("数组的字符串表示: " + arrayString);
    }
}

---

ArrayList

基本介绍

• 基本介绍：可以动态修改的数组，没有固定大小的限制。
• 使用场景：频繁查询但不经常增删元素
• 底层：数组 。允许存储多个null值。
• 性能：查询（get、contains）操作时间复杂度为O(1)，添加（add）和删除（remove）元素时，可能需要移动数组中的元素，导致时间复杂度为O(n)。
• 常用API：
  • Collection接口的add()、remove()等方法
  • get()：获取一个指定下标的元素
  • subList(int fromIndex, int toIndex)：返回从 fromIndex（包括）到 toIndex（不包括）之间的部分列表。
  • trimToSize()：将 ArrayList 的容量调整为当前元素的数量，以节省内存。

排序方法：

• Collections工具类的sort()方法：Collections.sort(list);
• stream流：list.stream().sort();
• 比较器：list.sort(new Comparator() {})
• 手写排序：冒泡排序、选择排序、插入排序、二分法排序、快速排序、堆排序。

代码示例：

public static void main(String[] args) {
    // 创建一个 ArrayList
    ArrayList<Integer> arrayList = new ArrayList<>();
    // 使用 add() 方法向集合中添加元素
    arrayList.add(10);arrayList.add(20);arrayList.add(30);arrayList.add(40);arrayList.add(50);
    System.out.println("添加元素后: " + arrayList);
    // 使用 get() 方法获取指定索引的元素
    int elementAtIndex2 = arrayList.get(2);
    System.out.println("索引 2 处的元素: " + elementAtIndex2);
    // 使用 set() 方法修改指定索引的元素
    arrayList.set(2, 35);
    System.out.println("修改索引 2 后: " + arrayList);
    // 使用 remove() 方法移除指定索引的元素
    arrayList.remove(1);
    System.out.println("移除索引 1 后: " + arrayList);
    // 使用 size() 方法获取集合的大小
    int size = arrayList.size();
    System.out.println("集合的大小: " + size);
    // 使用 contains() 方法检查集合中是否包含某个元素
    boolean contains30 = arrayList.contains(30);
    System.out.println("集合中是否包含 30: " + contains30);
    // 使用 isEmpty() 方法检查集合是否为空
    boolean isEmpty = arrayList.isEmpty();
    System.out.println("集合是否为空: " + isEmpty);
}

底层源码和扩容机制

数组实现：

ArrayList是基于数组实现的，它的内部封装了一个Object[]数组。通过默认构造器创建容器时,该数组先被初始化为空数组，之后在首次添加数据时再将其初始化成长度为10的数组。我们也可以使用有参构造器来创建容器，并通过参数来显式指定数组的容量，届时该数组被初始化为指定容量的数组。

// 复制的源码中的一部分
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    @java.io.Serial
    private static final long serialVersionUID = 8683452581122892189L;

    // Default initial capacity. 初始容量
    private static final int DEFAULT_CAPACITY = 10;

    transient Object[] elementData; // non-private to simplify nested class access 底层数组

}

每次扩容1.5倍：

如果向ArrayList中添加数据会造成超出数组长度限制,则会触发自动扩容,然后再添加数据。扩容就是数组拷贝,将旧数组中的数据拷贝到新数组里,而新数组的长度为原来长度的1.5倍。

// minCapacity 代表着最小扩容量
private void grow(int minCapacity) {
    // elementData 是 ArrayList 存储数据的数组，这里是获取当前数组的长度
    int oldCapacity = elementData.length;
    // 计算扩容后的数组长度 = 当前数组长度 + (当前数组长度 * 0.5)；也就是扩容到当前的 1.5 倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 判断新的数组是否满足最小扩容量，如果不满足就将新数组的扩容长度赋值为最小扩容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果扩容后的长度超过了最大数组大小，则将其设置为合适的容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity 通常接近于 size，因此这是一个有效的优化
    elementData = Arrays.copyOf(elementData, newCapacity);
}

手动缩容：

ArrayList支持缩容,但不会自动缩容,即便是ArrayList中只剩下少量数据时也不会主动缩容。如果我们希望缩减ArrayList的容量,则需要自己调用它的trimToSize()方法,届时数组将按照元素的实际个数进行缩减，底层也是通过创建新数组拷贝实现的。

public void trimToSize() {
    // 增加modCount，modCount是ArrayList的属性，用于记录集合被修改的次数。
    // 除了ArrayList，LinkedList、HashSet、TreeSet、HashMap、TreeMap等集合都有modCount属性
    modCount++;
    // 如果当前大小小于数组的长度，则进行缩容操作
    if (size < elementData.length) {
        // 如果 size 为 0，则将 elementData 置为 EMPTY_ELEMENTDATA
        // 否则将 elementData 缩容到 size 大小
        elementData = (size == 0) 
            ? EMPTY_ELEMENTDATA 
            : Arrays.copyOf(elementData, size);
    }
}

线程不安全问题和解决方案

添加元素add()方法的源码：

public boolean add(E e) {
    // 1.扩容：判断列表的capacity容量是否足够，是否需要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 2.添加：真正将元素放在列表的元素数组里面
    elementData[size++] = e;
    return true;
}

1.某线程刚扩容后就失去调度

在JVM中，CPU在多个线程中通过程序计数器来回调度，同一时刻一个CPU只能运行一个线程，所以就存在add()时，某个线程在刚刚ensureCapacityInternal()扩容后、还没往数组存元素时被暂停，等待被调度，然后其他线程add()成功把数组存满了，此时原线程恢复运行，执行elementData[size++] = e，因为数组容量已经满了，就会报错数组越界异常ArrayIndexOutOfBoundsException。

例如：

表大小为9，线程A新增一个元素，判断容量是不是足够，同时线程B也新增一个元素，判断容量是不是足够，线程A开始进行设置值操作， elementData[size++] = e 操作。此时size变为10，线程B也开始进行设置值操作，它尝试设置elementData[10] = e，而elementData没有进行过扩容，它的下标最大为9。于是此时会报出一个数组越界的异常ArrayIndexOutOfBoundsException。

2.数组存值时不是原子操作
另外第二步 elementData[size++] = e 设置值的操作同样会导致线程不安全。从这儿可以看出，这步操作也不是一个原子操作。

解决方案：

• 原子类

• volatile

• 锁

• 线程安全的集合：

  • Collections工具类：Collections工具类的synchronizedXxx()方法，将ArrayList等集合类包装成线程安全的集合类。例如

    Collections.synchronizedList(new ArrayList<>());

  • 古老api：java.util包下性能差的古老api，如Vector、Hashtable

  • 降低锁粒度的并发容器：JUC包下Concurrent开头的、以降低锁粒度来提高并发性能的容器，如ConcurrentHashMap。

  • 复制技术实现的并发容器：JUC包下以CopyOnWrite开头的、采用写时复制技术实现的并发容器，如CopyOnWriteArrayList。

六种遍历方法

常规 for 循环

普通 for 循环适用于遍历数组和实现了 List 接口的集合。它通过索引访问元素，性能通常较好。

优点：

• 性能高：性能通常优于增强 for 循环和迭代器，尤其是对于数组和 ArrayList。
• 复杂操作：允许在遍历过程中进行复杂的控制操作。

缺点：

• 可读性差：代码相对冗长，需要手动管理循环变量。
• 只能通过索引访问：仅适用于可以通过索引下标访问元素的集合。

通过for循环，用get(下标) 的方法遍历：

ArrayList<Integer> arrayList = new ArrayList<>(); // 通过arrayList.add(value)增加值
for (int i = 0; i < arrayList.size(); i++) {
    System.out.print(arrayList.get(i) + " ");
}

增强 for 循环（只遍历不修改）

在某些情况下，常规的遍历方式容易显得代码臃肿，增强for可以简化数组和Collection集合的遍历，增强代码的可读性。

增强 for 循环：一种简洁的遍历集合的方法，它适用于遍历数组和实现了 Iterable 接口的所有集合。

Collection实现类都实现了Iterable 接口：

在标准的 Java Collections Framework 中，所有主要的集合实现类都实现了 Iterable 接口。换句话说，如果一个类实现了 Collection 接口，那么它也会实现 Iterable 接口，因为这是 Collection 接口的一个基本要求。

tip：Map集合没有实现Iterable 接口，因为它也没有实现Collection接口。

IDEA快捷键：输入iter然后回车

格式

// 数据类型：即遍历对象中元素的数据类型。
// 变量名：遍历时声明的变量，每次遍历得到的元素都会赋值给这个变量。
// 数组或者集合对象：需要遍历的对象。
for (数据类型 变量名 : 数组或者Collection集合对象) {
    // 循环体
    System.out.println(变量名);
}

优点：

• 简洁易读：增强 for 循环语法简洁，代码更容易阅读。
• 避免错误：相比传统的 for 循环，不需要手动管理循环变量，减少了出错的可能性。

缺点：

• 性能略差：性能略差于普通for循环，以略微的性能代价，提高了可读性
• 不允许修改；

代码示例：

// 使用增强 for 循环遍历
for (Integer num : arrayList) {
    System.out.print(num + " ");
}

迭代器 Iterator（遍历并修改）

迭代器是遍历Collection集合的通用方式，它不需要关注集合和集合内元素的类型，对集合内的元素进行读取、添加、修改操作。

基本方法：

• hasNext()：返回 true 如果还有未遍历的元素。
• next()：返回下一个元素。
• remove()：从集合中移除 next() 返回的最后一个元素。

优点：

• 各类型集合统一迭代器：不需要了解集合的内部实现，通过 Iterator 可以统一遍历不同类型的集合。
• 安全：在遍历过程中，如果其他线程修改了集合，Iterator 可以抛出 ConcurrentModificationException 以防止不一致性。

缺点：

• 性能略差：性能略差于普通for循环，以略微的性能代价，提高了可读性
• 复杂：相比增强for，需要next()、hasNext()，麻烦了一些
• 不能双向遍历

代码示例

import java.util.ArrayList;
import java.util.Iterator;
public class IteratorRemoveExample {
    public static void main(String[] args) {
        // 创建一个 ArrayList 并添加一些元素
        List<Integer> arrayList = new ArrayList<>();
        arrayList.add(10);arrayList.add(20);arrayList.add(30);arrayList.add(40);arrayList.add(50);
        // 获取 ArrayList 的迭代器
        Iterator<Integer> iterator = arrayList.iterator();
        // 使用迭代器遍历 ArrayList 并移除元素
        System.out.println("使用迭代器遍历 ArrayList 并移除元素:");
        while (iterator.hasNext()) {
            Integer num = iterator.next();
            if (num > 30) {
                iterator.remove(); // 移除大于 30 的元素
            }
        }
        // 打印修改后的 ArrayList
        System.out.println("修改后的 ArrayList:");
        for (Integer num : arrayList) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

迭代器 ListIterator （双向遍历并修改）

Set、List、Queue都是Collection的子接口，它们都继承了父接口的iterator()方法,从而具备了迭代的能力。Map使用迭代器必须通过先entrySet()转为Set，然后再使用迭代器或for遍历。

但相比于另外两个接口，List还单独提供了listIterator()方法,增强了迭代能力。iterator()方法返回Iterator迭代器，listIterator()方法返回ListIterator迭代器，并且ListIterator是Iterator的子接口。

ListIterator在Iterator的基础上，增加了listIterator.previous()向前遍历的支持，增加了listIterator.set()在迭代过程中修改数据的支持。与 Iterator 相比，ListIterator 提供了更多的方法，但只适用于实现了 List 接口的集合（如 ArrayList 和 LinkedList）。

常用方法：

• hasNext()：如果列表中有下一个元素，则返回 true。
• next()：返回列表中的下一个元素。
• hasPrevious()：如果列表中有上一个元素，则返回 true。
• previous()：返回列表中的上一个元素。
• nextIndex()：返回下一元素的索引。
• previousIndex()：返回上一元素的索引。
• remove()：移除上一个通过 next() 或 previous() 返回的元素。
• set(E e)：替换上一个通过 next() 或 previous() 返回的元素。
• add(E e)：在列表中插入指定元素。

优点：

• 可读性高；
• 安全：在遍历过程中，如果其他线程修改了集合，迭代器可以抛出 ConcurrentModificationException 以防止不一致性。
• 双向遍历；

缺点：

• 只支持List：只适用于实现了 List 接口的集合（如 ArrayList 和 LinkedList）。
• 性能略差：性能略差于普通for循环，以略微的性能代价，提高了可读性

代码示例

public class ListIteratorExample {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(10);arrayList.add(20);arrayList.add(30);arrayList.add(40);arrayList.add(50);
        // 使用 ListIterator 遍历（正向）
        System.out.println("使用 ListIterator 正向遍历:");
        ListIterator<Integer> listIterator = arrayList.listIterator();
        while (listIterator.hasNext()) {
            System.out.print(listIterator.next() + " ");
        }
        System.out.println();
        // 使用 ListIterator 反向遍历
        System.out.println("使用 ListIterator 反向遍历:");
        while (listIterator.hasPrevious()) {
            System.out.print(listIterator.previous() + " ");
        }
        System.out.println();
    }
}

forEach + Lambda 表达式（只遍历不修改）

在 Java 8 及以上版本中，forEach 方法与 Lambda 表达式的结合提供了一种简洁、功能强大的方式来遍历集合。forEach 方法属于 Iterable 接口，允许对集合中的每个元素执行指定的操作。

优点：

• 简洁：相比于传统的 for 循环和迭代器，代码更简洁，减少样板代码。
• 可读性强：使用 Lambda 表达式和方法引用，使代码更加易读和表达意图明确。

缺点：

• 性能略差：性能略差于普通for循环，以略微的性能代价，提高了代码的优雅性可读性 ；同时各个元素之间的遍历是顺序执行的，不像Stream流的forEach是并发执行的，性能略差。
• 不允许修改元素：因为 Lambda 表达式的参数是 final 或等效于 final 的，所以不允许修改集合中的元素。想修改的话，只能创建另一个集合，然后在遍历时将处理后的元素add进另一个集合。
• 版本限制：只适用JDK8及以上；

代码示例

import java.util.ArrayList;
public class ForEachLambdaExample {
    public static void main(String[] args) {
        List<Integer> arrayList = new ArrayList<>();
        arrayList.add(10);arrayList.add(20);arrayList.add(30);arrayList.add(40);arrayList.add(50);
        // 使用 forEach 方法和 Lambda 表达式遍历
        System.out.println("使用 forEach 方法和 Lambda 表达式遍历:");
        arrayList.forEach(num -> System.out.print(num + " "));
        System.out.println();
    }
}

Stream API 遍历（推荐，并发遍历并修改）

Stream 流是 Java 8 引入的一项新特性，用于对集合进行函数式编程风格的操作。它允许我们以声明性方式对数据进行过滤、加工、遍历、排序等操作，而不是以命令式方式逐个操作元素。

优点：

• 简洁：相比于传统的 for 循环和迭代器，代码更简洁，减少样板代码。
• 生成修改后的新集合：允许通过map()、filter()等方法修改元素，然后收集成一个新集合。
• 性能高：因为是并发的，所以性能高。

缺点：

• 版本限制：只适用JDK8及以上；

代码示例

import java.util.ArrayList;
public class StreamExample {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(10);arrayList.add(20);arrayList.add(30);arrayList.add(40);arrayList.add(50);
        // 使用 Stream API 遍历
        System.out.println("使用 Stream API 遍历:");
        arrayList.stream().forEach(num -> System.out.print(num + " "));
        System.out.println();
    }
}

小结：六种遍历方法的适用场景

• 需要根据索引下标遍历：普通for
• 只需要顺序读取元素：建议增强for，也可以用其他所有遍历方法
• 需要修改元素：普通for、迭代器、Stream流
• 需要双向遍历：ListIterator
• 需要过滤、加工、排序等高级操作：Stream流

---

List接口

主要实现类

Collection将集合划分为两大类，即List和Set。

常见的 List 实现类包括 ArrayList、LinkedList、Vector（JDK1的上古集合，虽然线程安全但性能差，已经基本不用） 和 Stack。

1. ArrayList：

   • 使用场景：频繁查询但不经常增删元素

   • 底层：数组 。允许存储多个null值。

   • 性能：查询（get、contains）操作时间复杂度为O(1)，添加（add）和删除（remove）元素时，可能需要移动数组中的元素，导致时间复杂度为O(n)。

2. LinkedList：

   • 使用场景：频繁增删元素但不经常查询

   • 底层：链表 。允许存储多个null值。

   • 性能： 查询很慢（需要从头（或尾）遍历链表，查询操作时间复杂度为O(n) ），增删很快（只需调整链表的指针，插入（add）和删除（remove）操作时间复杂度为O(1)）。

3. Vector：

   • 使用场景：需要线程安全且频繁查询的场景（JDK1的上古集合，虽然线程安全但性能差，已经基本不用。

   • 线程安全集合：

     • Collections工具类：Collections工具类的synchronizedXxx()方法，将ArrayList等集合类包装成线程安全的集合类。
     • 古老api：java.util包下性能差的古老api，如Vector、Hashtable
     • 无序列表降低锁粒度的并发容器：JUC包下Concurrent开头的、以降低锁粒度来提高并发性能的容器，如ConcurrentHashMap。
     • 复制技术实现的并发容器：JUC包下以CopyOnWrite开头的、采用写时复制技术实现的并发容器，如CopyOnWriteArrayList。

   • 底层：数组。允许存储多个 null 值。

     • 性能： 查询（get、contains）操作时间复杂度为O(1)，添加（add）和删除（remove）元素时，可能需要移动数组中的元素，导致时间复杂度为O(n)。

4. Stack：

   • 使用场景：需要后进先出（LIFO）访问顺序的数据结构，例如递归、回溯算法等。线程安全，因为它是Vector的实现类

   • 底层：数组（因为它是Vector的实现类）。允许存储多个 null 值。

   • 性能： 增删改查都是在栈顶操作，所以时间复杂度都是O(1)

   • 常用方法：

     • **push(E item)**：将元素压入栈顶
     • **pop()**：移除并返回栈顶元素
     • **peek()**：返回栈顶元素但不移除
     • **isEmpty()**：检查栈是否为空
     • **search(Object o)**：返回元素在栈中的位置，以 1 为基准

ArrayList，LinkedList，Vector 对比

	ArrayList	LinkedList	Vector
底层结构	动态数组	双向链表	动态数组
线程安全	不安全	不安全	安全，方法都加了Synchronized
是否允许重复元素	允许	允许	允许
是否有序	是	是	是
随机访问	快O(1)，索引访问	慢O(n)，需遍历链表	快O(1)，但因同步影响性能较低
插入/删除	慢O(n)，需移动元素	快O(1)，只需修改指针	慢，同步开销大
扩容机制	默认增长50%	无需扩容，动态添加节点	默认翻倍容量
加载因子	1	无	1

特点

• 有序【存储有序】
• 可重复
• 可以存储 null值
• 部分子集合线程安全，部分不安全 例如 ArrayList 和 Vector

常用方法

List接口继承自Collection接口，提供了额外的功能来处理索引位置上的元素。与Set、Map不同，List允许包含重复的元素，并且可以通过索引来访问或修改特定位置的元素。

/* 核心接口方法 */
void add(E e) // 添加指定元素到列表末尾。
void add(int index, E element)// 在指定索引处插入指定元素。
boolean addAll(int index, Collection<? extends E> c) // 在指定索引 index 处插入集合 c 中的所有元素。
E remove(int index) // 移除指定索引处的元素。
E get(int index) // 获取指定索引处的元素。
E set(int index, E element) // 替换指定索引处的元素。
int size() // 返回列表中的元素数量。
/* 其他常用方法 */ 
boolean isEmpty() // 判断列表是否为空。
boolean contains(Object o) // 检查列表是否包含指定元素。
int indexOf(Object o) // 返回指定元素首次出现的索引，如果不存在则返回-1。
int lastIndexOf(Object o) // 返回指定元素最后一次出现的索引，如果不存在则返回-1。
List<E> subList(int fromIndex, int toIndex) // 获取从fromIndex（包括）到toIndex（不包括）之间的子列表

代码示例

public static void main(String[] args) {
    // 创建一个 ArrayList
    List<String> list = new ArrayList<>();
    // 增加元素
    list.add("元素1");list.add("元素2");list.add("元素3");
    System.out.println("增加元素后：" + list);
    // 在指定索引插入元素
    list.add(1, "元素4");
    System.out.println("在索引1插入元素4后：" + list);
    // 删除指定索引的元素
    list.remove(2);
    System.out.println("删除索引2的元素后：" + list);
    // 修改指定索引的元素
    list.set(1, "元素5");
    System.out.println("修改索引1的元素为元素5后：" + list);
    // 获取指定索引的元素
    String element = list.get(2);
    System.out.println("获取索引2的元素：" + element);
    // 获取元素的索引
    int index = list.indexOf("元素5");
    System.out.println("元素5的索引：" + index);
    // 获取子列表
    List<String> subList = list.subList(1, 3);
    System.out.println("子列表（从索引1到索引2）： " + subList);
}

遍历方式

1. for循环。

   List<String> list = new ArrayList<>();
   
   // 优点：可以灵活控制索引。支持随机访问（适合 ArrayList）。
   // 缺点：对于 LinkedList 来说效率较低（因为每次都要从头开始查找元素）。
   for (int i = 0; i < list.size(); i++) {
       System.out.println("Index: " + i + ", Value: " + list.get(i));
   }
   
   // 优点：简洁易读。适用于所有实现了 Iterable 接口的集合类。
   // 缺点：无法获取索引。不能修改集合结构（如删除元素会抛出异常）。
   for (String item : list) {
       System.out.println("Item: " + item);
   }

2. 使用 Iterator。可以安全地在遍历时进行删除操作。

   Iterator<String> iterator = list.iterator();
   while (iterator.hasNext()) {
       System.out.println("元素：" + iterator.next());
       String item = iterator.next();
       if ("B".equals(item)) {
           iterator.remove();  // 安全删除
       }
   }

去重方式

1. 利用 HashSet 或 LinkedHashSet。

   List<Integer> list = Arrays.asList(1, 2, 2, 3, 4, 4, 5);
   
   // HashSet 不保留顺序
   List<Integer> uniqueList = new ArrayList<>(new HashSet<>(list));
   System.out.println(uniqueList);  // 输出顺序可能不同
   
   // LinkedHashSet 保留插入顺序
   List<Integer> uniqueList = new ArrayList<>(new LinkedHashSet<>(list));
   System.out.println(uniqueList);  // 输出: [1, 2, 3, 4, 5]

2. 使用 Stream.distinct()，Java 8+ 。

   List<Integer> list = Arrays.asList(1, 2, 2, 3, 4, 4, 5);
   List<Integer> uniqueList = list.stream().distinct().collect(Collectors.toList());
   System.out.println(uniqueList);

List 与数组的转换

• List 转数组

  // 无类型参数：丢失类型信息
  Object[] array = list.toArray();
  // 带类型参数：推荐，自动匹配类型
  String[] array = list.toArray(new String[0]);
  // 函数式写法
  String[] array = list.toArray(String[]::new);

• 数组转 List

  List<String> list = List.of(array);（只读）
  new ArrayList<>(Arrays.asList(array));（可修改）

List 的元素判断机制

List的 contains(Object o) 和 indexOf(Object o) 方法通过 equals()而非 == 判断元素是否相等。

List的安全类

在单线程应用中，通常采取new ArrayList()，指定一个List集合，用于存放可重复的数据。但ArrayList是不安全的集合。多线程操作同一集合对象信息，往往会出现java.util.ConcurrentModificationException异常报错信息。

Java的安全类Vector

java提供了java.util.Vector类，多线程下不会出现java.util.ConcurrentModificationException报错信息。因为采取了 synchronized 针对方法执行调用者加锁，保证add操作的多线程安全性！

public class VectorTest {
    public static void main(String[] args) throws InterruptedException {
        // 创建lists集合
        List<String> lists = new Vector<>();
        // 开启十个线程增加数据
        for (int i = 1; i <= 40; i++) {
            new Thread(()->{
                lists.add(UUID.randomUUID().toString().substring(0,5));
                System.out.println(Thread.currentThread().getName() + "==" + lists);
            }, String.valueOf(i)).start();
        }
    }
}

JUC下的安全List集合

1. Collections.synchronizedList(new ArrayList<>());。该方法返回具有同步包装器的List，保证了对List的操作是安全的。

public class ListTest {
    public static void main(String[] args) throws InterruptedException {
        List<String> lists = Collections.synchronizedList(new ArrayList<>());
        // 开启十个线程增加数据
        for (int i = 1; i <= 40; i++) {
            new Thread(()->{
                lists.add(UUID.randomUUID().toString().substring(0,5));
                System.out.println(Thread.currentThread().getName() + "==" + lists);
            }, String.valueOf(i)).start();
        }
    }
}

// 底层源码
public static <T> List<T> synchronizedList( @NotNull List<T> list) {
    return(list instanceof RandomAccess ? 
           new SynchronizedRandomAccessList<>(list) : 
           new synchronizedList<>(list));
}

// 判断传入的 list 集合类型，判断类型是否为 java.util.RandomAccess，如果是则采取java.util.Collections.SynchronizedRandomAccessList构造集合，如果不是则采取java.util.Collections.SynchronizedList构造集合。

// 源码中对应的add操作逻辑如下所示。采取synchronized同步代码块的方式，对数据的add操作实现加锁！
public void add(int index, E element){ 
    synchron1zed (mutex) {
        list.add(index, element);
    }
}

2. new CopyOnWriteArrayList();。该类中所有修改操作都在一个独立的副本上进行，不会影响原始数据，保证了线程安全。

import java.util.concurrent.CopyOnWriteArrayList;
public class ListTest {
    public static void main(String[] args) throws InterruptedException {
        List<String> lists = new CopyOnWriteArrayList<>();
        // 开启十个线程增加数据
        for (int i = 1; i <= 40; i++) {
            new Thread(()->{
                lists.add(UUID.randomUUID().toString().substring(0,5));
                System.out.println(Thread.currentThread().getName()+"=="+lists);
            },String.valueOf(i)).start();
        }
    }
}

// Creates an empty list
public CopyonWriteArrayList(){ setArray(new object[0]); }
// add 逻辑
public boolean add(E e){
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[]elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copy0f(elements, len +1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

add逻辑如下所示
1、调用add方法后，拿到java.util.concurrent.locks.ReentrantLock对象信息。
2、调用 lock.lock() 拿到锁！
3、将原数组对象copy操作，并创建原数组大小+1的新数组。
4、将新数据放入新数组中。
5、任何操作finally，都进行锁的释放

面向接口编程

面向接口编程（Programming to an Interface）是一种编程原则，它强调使用接口（Interface）而不是具体实现类（Concrete Class）来编写代码。

具体的使用方法是，声明一个接口的变量（接口的引用）可以指向一个实现类（实现该接口的类）的实例。

注意：因为是接口的引用，所以该引用的变量不能使用实现类中有、但接口中没有的方法（实现类中没有重写的方法，自添加的方法）。

以面向接口编程为原则，以多态的形式创建集合对象：

以下两种方法都可以创建ArrayList，但是更推荐第一种方法：

// 推荐，面向接口编程，多态形式，对象实例指向接口引用
List<Integer> arrayList = new ArrayList<>();
// 不推荐，常规创建对象形式
ArrayList<Integer> arrayList = new ArrayList<>();

因为前者符合设计模式中的依赖倒置原则。即程序要尽量依赖于抽象，不依赖于具体。

在Java语法中，这种方式符合Java三大特性中的多态，即使用接口引用指向具体实现。
依赖倒转的好处是，后期扩展方便。比如，你若希望用LinkedList的实现来替代ArrayList的话，只需改动一行即可，其他的所有的都不需要改动：

List<Integer> list = new LinkedList<>()；

优点：

• 解耦合：声明的变量与具体实现类解耦。变量只依赖于接口，而不是具体实现，这样可以很容易地替换具体实现类，而不需要修改客户端代码。
• 可扩展性：当需要添加新功能时，只需实现新的接口，让原引用指向新的实现类，而不需要修改现有代码。例如SpringBoot项目中，我们经常用XxxService接口和XxxServiceImpl1、XxxServiceImpl2等业务实现类，在使用时，通常将这个接口引用通过@Autowired等注解注入XxxService，然后通过@Primary、@Qualifier等注解指定具体注入XxxServiceImpl1还是XxxServiceImpl2，方便扩展。
• 可测试性：在单元测试中，可以轻松地使用接口的模拟实现来替换真实的实现，从而进行隔离测试。

符合设计原则：

• 开闭原则OCP(Open－Close Principle)： 对拓展开放、对修改关闭。
• 依赖倒置原则DIP(Dependency Inversion Principle)： 抽象不应该依赖于细节、细节应该依赖于抽象。例如我们开发中要用Service接口和ServiceImpl实现类，而不是直接一个ServiceImpl类中写业务。

设计原则详细参考：

设计模式——设计模式简介和七大原则_理解设计模式的核心思想和基本理念是什么-CSDN博客

---

LinkedList接口

基本介绍

LinkedList：

• 使用场景：频繁增删元素但不经常查询
• 底层：链表 。允许存储多个null值。
• 性能： 查询很慢（需要从头（或尾）遍历链表，查询操作时间复杂度为O(n) ），增删很快（只需调整链表的指针，插入（add）和删除（remove）操作时间复杂度为O(1)）。

常用方法

方法	描述
public void add(int index, E element)	向指定位置插入元素
public void addFirst(E e)	元素添加到头部
public void addLast(E e)	元素添加到尾部
public void clear()	清空链表
public E remove(int index)	删除指定位置的元素
public E removeFirst()	删除并返回第一个元素
public E removeLast()	删除并返回最后一个元素
public boolean contains(Object o)	判断是否含有某一元素
public E getFirst()	返回第一个元素
public E getLast()	返回最后一个元素

代码示例

public static void main(String[] args) {
    LinkedList<String> link=new LinkedList<String>();
    link.addLast("hello");link.addLast("world");
    for(String s:link) System.out.println(s);
    System.out.println(link);
}

ArrayList和LinkedList的区别

特性	ArrayList	LinkedList
使用场景	频繁查询但不经常增删元素	频繁增删元素但不经常查询
底层	数组	链表
允许存储 null 值	是。允许存储多个null值	是。允许存储多个null值
查询性能	快。根据索引查询（get、contains）操作时间复杂度为 O(1)	慢。根据索引查询很慢（需要从头（或尾）遍历链表，查询操作时间复杂度为 O(n)）
添加性能	慢。添加（add）元素时，可能需要移动数组中的元素，导致时间复杂度为 O(n)	快。插入（add）操作时间复杂度为 O(1)，插入后不需要移动元素
删除性能	慢。删除（remove）元素时，可能需要移动数组中的元素，导致时间复杂度为 O(n)	快。删除（remove）操作时间复杂度为 O(1)，删除后不需要移动元素

---

ListIterator

列表迭代器允许沿任一方向遍历列表

常用方法

Modifier and Type	Method	Description
void	add(E e)	将指定的元素插入列表（可选操作）
boolean	hasNext()	返回 true如果遍历正向列表，列表迭代器有多个元素
boolean	hasPrevious()	返回 true如果遍历反向列表，列表迭代器有多个元素
E	next()	返回列表中的下一个元素，并且前进光标位置
int	nextIndex()	返回随后调用 next()返回的元素的索引
E	previous()	返回列表中的上一个元素，并向后移动光标位置
int	previousIndex()	返回由后续调用 previous()返回的元素的索引
void	remove()	从列表中删除由 next()或 previous()返回的最后一个元素（可选操作）
void	set(E e)	用 指定的元素替换由 next()或 previous()返回的最后一个元素（可选操作）

代码示例

ListIterator<String> it=sites.listIterator();
while(it.hasNext()) System.out.println(it.next());

---

HashMap

HashMap是基于哈希表实现的键值对存储结构，提供高效的插入和查询操作（平均时间复杂度O(1)），允许null键/值，非线程安全，且不保证元素顺序。其核心实现包括数组+链表（JDK1.7及之前）或数组+链表+红黑树（JDK1.8及之后），通过哈希冲突解决机制（链地址法）和动态扩容优化性能。

基本介绍

使用场景: 适用于需要基于键值对快速查找数据的场景。“键”可以理解为钥匙，通过这个钥匙，可以找到它唯一对应的“值”。

底层: 哈希表（数组+链表/红黑树）。

性能:

• 查询性能: 快，时间复杂度为 O(1)。
• 添加性能: 快，时间复杂度为 O(1)。
• 删除性能: 快，时间复杂度为 O(1)。

是否允许 null:

• 键可以为 null（但最多一个键为 null）。
• 值可以为 null。

常用方法

• put()：向映射中添加一个键值对。如果键已经存在，则更新其对应的值
  1. 计算键的哈希值并定位桶索引。
  2. 桶为空：直接插入新节点。
  3. 桶非空：遍历链表或红黑树，若存在相同键（通过equals判断），则更新值；否则追加节点。
  4. 触发扩容：插入后检查元素总数是否超过阈值
• get()：根据键获取对应的值。根据哈希值定位桶，遍历链表或红黑树，通过equals匹配键
• getOrDefault()：获取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值
• keySet()：返回所有key的Set集合
• remove(Object key): 根据键移除键值对
• containsKey(Object key): 检查是否包含指定键
• containsValue(Object value): 检查是否包含指定值
• size(): 返回映射中的键值对数量
• isEmpty(): 检查映射是否为空
• clear(): 移除映射中的所有键值对

代码示例

public class Test {
    public static void main(String[] args) {
        // 创建一个 HashMap
        Map<String, String> fruitColor = new HashMap<>();
        // 使用 put() 方法向映射中添加键值对
        fruitColor.put("苹果", "红色");fruitColor.put("香蕉", "黄色");fruitColor.put("樱桃", "红色");
        System.out.println("添加键值对后: " + fruitColor);
        // 使用 get() 方法根据键获取对应的值
        String value = fruitColor.get("香蕉");
        System.out.println("键 '香蕉' 对应的值: " + value);
        // 遍历 keySet
        Set<String> keys = fruitColor.keySet();
        System.out.println("遍历 keySet:");
        for (String key : keys) {
            System.out.println("水果: " + key + " 颜色: " + fruitColor.get(key));
        }
        // 使用 containsKey() 方法检查是否包含指定键
        boolean containsKeyBanana = fruitColor.containsKey("香蕉");
        System.out.println("包含键 '香蕉': " + containsKeyBanana);
        // 使用 containsValue() 方法检查是否包含指定值
        boolean containsValueYellow = fruitColor.containsValue("黄色");
        System.out.println("包含值 '黄色': " + containsValueYellow);
        // 使用 size() 方法返回映射中的键值对数量
        int size = fruitColor.size();
        System.out.println("映射的大小: " + size);
        // 使用 isEmpty() 方法检查映射是否为空
        boolean isEmpty = fruitColor.isEmpty();
        System.out.println("映射是否为空: " + isEmpty);
        // 使用 remove() 方法根据键移除键值对
        fruitColor.remove("香蕉");
        System.out.println("移除键 '香蕉' 后: " + fruitColor);
        // 再次使用 size() 方法返回映射中的键值对数量
        size = fruitColor.size();
        System.out.println("移除后映射的大小: " + size);
        // 使用 clear() 方法移除映射中的所有键值对
        fruitColor.clear();
        System.out.println("清空映射后: " + fruitColor);
        // 使用 isEmpty() 方法检查映射是否为空
        isEmpty = fruitColor.isEmpty();
        System.out.println("清空后映射是否为空: " + isEmpty);
    }
}

底层原理

HashMap是基于哈希表实现的键值对存储结构，HashMap的核心实现结合了数组、链表和红黑树。

数据结构

数组：默认初始容量为16，数组的每个位置称为一个桶(Bucket)。容量始终为2的幂次方(如16、32)，便于通过位运算快速定位索引。
链表：当多个键的哈希值冲突时，这些键值对以链表形式存储在同一个桶中（链地址法）。
红黑树：当链表长度超过阈值（默认8）且数组容量≥64时，链表会转换为红黑树，以提高查找效率（从O(n)优化为O(log n)）。

哈希函数与索引定位

HashMap通过哈希函数将键映射到数组的索引位置。具体步骤如下：

1. 调用键的hashCode()方法获取哈希值。

2. 扰动处理：将高16位与低16位异或(h = key.hashCode()) ^ (h >>> 16)，减少哈希碰撞概率。

   static final int hash(Object key) {
       int h;
       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
   }

3. 通过(n-1) & hash计算桶位置，等价于hash % n，但性能更高‌。

冲突处理机制

1. 链地址法：冲突的键值对以链表形式链接。在JDK 8之前采用头插法，JDK 8之后采用尾插法以避免多线程下的死循环问题‌

2. 红黑树转换：

   1. 当链表长度≥8且数组容量≥64时，链表会转换为红黑树‌。

   2. 红黑树节点数≤6时，退化为链表

      

红黑树： 近似平衡二叉树，左右子树高差有可能大于 1，查找效率略低于平衡二叉树，但增删效率高于平衡二叉树，适合频繁插入删除。

• 结点非黑即红；
• 根结点是黑色，叶节点是黑色空节点（常省略）；
• 任何相邻节点不能同时为红色；
• 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点；
• 查询性能稳定O(logN)，高度最高2log(n+1)；

动态扩容机制

HashMap的扩容机制基于负载因子（默认值为0.75）。当元素数量超过容量乘以负载因子时，比如当数组添加到16*0.75=12时，HashMap会自动触发扩容，扩容为自身的两倍：16*2=32。扩容步骤如下：

1. 创建一个新的数组，容量为原容量的两倍（保持2的幂次方）。采用2的指数进行扩容，是为了利用位运算，提高扩容运算的效率。
2. 重新计算所有元素的位置并放入新数组的对应位置，利用高位快速判断元素是否需要移动（如原索引为oldIndex，新索引可能为oldIndex或oldIndex + oldCapacity）。
3. 数组每个元素存的是链表头结点地址，链地址法处理冲突，若链表的长度达到了8，红黑树代替链表。扩容后，链表或红黑树可能会被拆分到不同的桶中‌。

HashMap如何计算key

key=value&(2^n-1) # 结果相当于value%(2^n)，使用位运算只要是为了提高计算速度。

例如当前数组容量是16，我们要存取18，那么就可以用18&15==2。相当于18%16==2。

put()里，计算key的部分源码：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    // 此处省略了代码
    // i = (n - 1) & hash]
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        // 省略了代码
    }
}

HashMap容量为什么是2的n次方

计算value对应key的Hash运算：

key=value&(2^n-1）#结果相当于value%(2^n)。例如18&15和18%16值是相等的

2^n-1和2^(n+1)-1的二进制除了第一位，后几位都相同。这样使得添加的元素均匀分布在HashMap的每个位置上，防止哈希碰撞。

例如15的二进制为1111，31的二进制为11111，63的二进制为111111，127的二进制为1111111。

扩容均匀散列演示：从2^4扩容成2^5

0&(2^4-1)=0；0&(2^5-1)=0

16&(2^4-1)=0；16&(2^5-1)=16。所以扩容后，key为0的一部分value位置没变，一部分value迁移到扩容后的新位置。

1&(2^4-1)=1；1&(2^5-1)=1

17&(2^4-1)=1；17&(2^5-1)=17。所以扩容后，key为1的一部分value位置没变，一部分value迁移到扩容后的新位置。

put()流程

1. 计算key存取位置，与运算hash&(2^n-1），实际就是哈希值取余，位运算效率更高。
2. 判断数组，若发现数组为空，则进行首次扩容为初始容量16。
3. 判断数组存取位置的头节点，若发现头节点为空，则新建链表节点，存入数组。
4. 判断数组存取位置的头节点，若发现头节点非空，则看情况将元素覆盖或插入链表（JDK7头插法，JDK8尾插法）、红黑树。
5. 插入元素后，判断元素的个数，若发现超过阈值则以2的指数再次扩容。

其中，第3步又可以细分为如下三个小步骤：

1. 若元素的key与头节点的key一致，则直接覆盖头节点。

2. 若元素为树型节点，则将元素追加到树中。

3. 若元素为链表节点，则将元素追加到链表中。追加后，需要判断链表长度以决定是否转为红黑树。若链表长度达到8、数组容量未达到64，则扩容。若链表长度达到8、数组容量达到64，则转为红黑树。

哈希表处理冲突：开放地址法（线性探测、二次探测、再哈希法）、链地址法

遍历方法

迭代器遍历

• 遍历EntrySet（键值对）：支持通过iterator.remove()安全删除元素(优点)。

  Iterator<Map.Entry<K, V>> iterator = map.entrySet().iterator();
  while (iterator.hasNext()) {
      Map.Entry<K, V> entry = iterator.next();
      System.out.println(entry.getKey() + " : " + entry.getValue());
  }

• 遍历KeySet（仅键）：性能低于EntrySet遍历，需多次调用get()（缺点）。

  Iterator<K> keyIterator = map.keySet().iterator();
  while (keyIterator.hasNext()) {
      K key = keyIterator.next();
      V value = map.get(key); // 需要额外查询值
  }

for-each循环

// 遍历EntrySet
for (Map.Entry<K, V> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " : " + entry.getValue());
}
// 遍历键
for (K key : map.keySet()) { ... }
// 遍历值
for (V value : map.values()) { ... }

Lambda表达式遍历（Java 8+）

map.forEach( (key, value) -> System.out.println(key + " : " + value) );

Stream API遍历（Java 8+）

// 单线程遍历
map.entrySet().stream().forEach(entry -> ...);
// 多线程遍历
map.entrySet().parallelStream().forEach(entry -> ...);

性能对比

遍历方式	时间复杂度	适用场景	线程安全
EntrySet迭代器	O(n)	需要删除元素	需手动同步
EntrySet for-each	O(n)	常规遍历	需手动同步
KeySet遍历	O(n)（性能较低）	仅需键	需手动同步
Lambda表达式	O(n)	代码简洁性优先	需手动同步
Stream API	O(n)	大数据量处理或并行计算	需手动同步

推荐选择：

• 需键值对：优先使用entrySet()（迭代器或for-each）。
• 仅需键或值：直接遍历keySet()或values()。
• 代码简洁性：Java 8+环境下推荐Lambda表达式。
• 线程安全：改用ConcurrentHashMap或使用同步包装类。

HashMap和HashSet区别

相同点：

• 他们的前缀的是HashXxx，代表他们底层都是哈希表，用hashCode()判断元素是否重复。

  哈希表增删改查的时间复杂度是O(1)，缺点是可能出现冲突。

  HashXxx都使用哈希算法来确定元素的存储位置，因此插入元素的速度通常比较快。哈希表插入时主要看是否发生冲突，如果key通过哈希算法计算后的值所处位置已有元素，则需要根据链地址法或开放地址法处理冲突。

不同点：

特性	HashMap	HashSet
接口	实现了 Map 接口	实现了 Set 接口
存储结构	存储键值对（Key-Value pairs）	仅存储对象（Unique elements）
存储方式	使用 put() 方法将元素放入 Map 中	使用 add() 方法将元素放入 Set 中
底层实现	基于哈希表，使用数组+链表+红黑树	基于 HashMap 实现HashMap 的key是每个元素value是一个私有常量对象PRESENT，仅用于占位。
存储内容	键和值都可以为 null，键最多只能有一个 null	仅允许一个 null 元素因为它底层是HashMap的key，键只允许一个null
是否允许重复	键不允许重复，值可以重复	不允许重复元素
时间复杂度	插入、删除、查找的平均时间复杂度为 O(1)	插入、删除、查找的平均时间复杂度为 O(1)，但 contains() 时间复杂度可能更高
插入速度	比较快，因为底层是哈希表	比较快，因为底层是哈希表
使用场景	需要键值对映射的场景	需要存储唯一元素、自动去重的场景

HashMap安全

HashMap是线程不安全的，多线程环境下建议使用Collections工具类和JUC包的ConcurrentHashMap。

• 线程安全：程序在多线程环境下可以持续进行正确的处理，不会产生数据竞争（例如死锁）和不一致的问题。

HashMap线程不安全的表现

1. JDK8 put时数据覆盖（丢失）
   场景：多线程同时调用 put() 方法插入数据。
   原因：两个线程同时计算哈希值并定位到同一个桶(bucket)时，若该位置为空，可能发生数据覆盖。无锁导致复合操作非原子性。

   // 假设线程A和线程B同时执行以下代码
   if (table[bucket] == null) {
    table[bucket] = new Entry(key, value); // 可能被覆盖
   }
   // JDK 1.8 的数据覆盖问题
   public class HashMapUnsafeDemo {
    public static void main(String[] args) throws InterruptedException {
        Map<String, Integer> map = new HashMap<>();
        Thread t1 = new Thread(() -> {
            for (int i = 0; i < 1000; i++) {
                map.put("key" + i, i);
            }
        });
        Thread t2 = new Thread(() -> {
            for (int i = 0; i < 1000; i++) {
                map.put("key" + i, i);
            }
        });
        t1.start();
        t2.start();
        t1.join();
        t2.join();
        System.out.println("Map size: " + map.size()); // 结果可能小于 1000
    }
   }
   // 底层源码
   final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
       Node<K,V>[] tab; Node<K,V> p; int n, i;
       if ((tab = table) == null || (n = tab.length) == 0)
           n = (tab = resize()).length;
       if ((p = tab[i = (n - 1) & hash]) == null)     // 如果没有 hash 碰撞，则直接插入
           tab[i] = newNode(hash, key, value, null);
   }

2. 链表成环（JDK7 的经典问题）
   场景：多线程同时触发 resize()（扩容）。
   原因：JDK7 的 HashMap 使用头插法迁移链表，并发扩容时可能导致链表成环，后续的 get()操作触发死循环。

   单线程扩容流程：JDK7中，HashMap链地址法处理冲突时采用头插法，在扩容时依然头插法，所以链表里结点顺序会反过来。

   假如有T1、T2两个线程同时对某链表扩容，他们都标记头结点和第二个结点，此时T2阻塞，T1执行完扩容后链表结点顺序反过来，此时T2恢复运行再进行翻转就会产生环形链表，即B.next=A; A.next=B，从而死循环。

   

   // JDK 1.7 的扩容代码（简化）
   void transfer(Entry[] newTable) {
    for (Entry<K,V> e : table) {
        while (e != null) {
            Entry<K,V> next = e.next; // 线程A执行到这里挂起
            e.next = newTable[bucket]; // 线程B先执行，导致链表成环
            newTable[bucket] = e;
            e = next;
        }
    }
   }

   JDK8 尾插法：JDK8中，HashMap采用尾插法，扩容时链表节点位置不会翻转，解决了扩容死循环问题，但是性能差了一点，因为要遍历链表再查到尾部。 例如A——>B——>C要迁移，迁移时先移动头结点A，再移动B并插入A的尾部，再移动C插入尾部，这样结果还是A——>B——>C。顺序没变，扩容线程。

3. size 不准确
   场景：多线程同时调用 put() 或 remove()。
   原因：size 变量是非原子操作（如 size++），并发修改可能导致最终值错误。非原子操作 + 无可见性保证。

4. modCount非原子性自增问题

   modCount： HashMap的成员变量，用于记录HashMap被修改次数

   put会执行modCount++操作（modCount是HashMap的成员变量，用于记录HashMap被修改次数），这步操作分为读取、增加、保存，不是一个原子性操作，也会出现线程安全问题。

   final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
       Node<K,V>[] tab; Node<K,V> p; int n, i;
       if ((tab = table) == null || (n = tab.length) == 0)
           n = (tab = resize()).length;
       if ((p = tab[i = (n - 1) & hash]) == null)
           tab[i] = newNode(hash, key, value, null);
       else {
           Node<K,V> e; K k;
           if (p.hash == hash &&
               ((k = p.key) == key || (key != null && key.equals(k))))
               e = p;
           else if (p instanceof TreeNode)
               e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
           else {
               for (int binCount = 0; ; ++binCount) {
                   if ((e = p.next) == null) {
                       p.next = newNode(hash, key, value, null);
                       if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                           treeifyBin(tab, hash);
                       break;
                   }
                   if (e.hash == hash &&
                       ((k = e.key) == key || (key != null && key.equals(k))))
                       break;
                   p = e;
               }
           }
           if (e != null) { // existing mapping for key
               V oldValue = e.value;
               if (!onlyIfAbsent || oldValue == null)
                   e.value = value;
               afterNodeAccess(e);
               return oldValue;
           }
       }
       // put会执行modCount++操作，这步操作分为读取、增加、保存，不是一个原子性操作，也会出现线程安全问题。 
       ++modCount;
       if (++size > threshold)
           resize();
       afterNodeInsertion(evict);
       return null;
   }

HashMap线程不安全的根本原因

1. 无同步机制
   HashMap 的设计目标是单线程高性能，未对多线程操作进行同步（如 synchronized 或 CAS）。
   关键操作（put()、get()、resize()）没有锁保护。
2. 可见性问题
   多线程修改共享变量（如 table、size）时，未使用 volatile 关键字，可能导致一个线程的修改对其他线程不可见。
3. 复合操作非原子性
   例如 put() 操作包含多个步骤（计算哈希、定位桶、插入节点），多线程交叉执行时可能破坏内部结构。

解决方案

原子类、volatile、锁、线程安全的集合

1. 使用线程安全的替代类

   `Collections.synchronizedMap()`：通过包装类对所有方法加锁（性能较差）。
   `ConcurrentHashMap`：分段锁（JDK 1.7）或 CAS + synchronized（JDK 1.8），高并发性能更好。
   

2. 避免多线程直接操作 HashMap
   限制为单线程使用，或通过副本、消息队列等方式隔离并发访问。

ConcurrentHashMap

数据结构

• 在jdk1.7版本
  • ConcurrentHashMap的数据结构是由一个Segment数组和多个HashEntry组成。
  • 主要实现原理是实现了锁分离的思路，采用分段锁的机制，实现并发的更新操作。
  • 底层采用数组+链表的存储结构，包括两个核心静态内部类 Segment 和 HashEntry。
  • Segment数组的意义就是将一个大的table分割成多个小的table来进行加锁，也就是上面的提到 的锁分离技术。每一个Segment元素存储的是HashEntry 数组+链表（若干个桶），这个和HashMap的数据存储结构一样。
  • HashEntry用来封装映射表的键值对，每个桶是由若干个HashEntry对象链接起来的链表。
• 在jdk1.8后
  • 取消了Segment类，直接用table数组存储键值对。采用Node + CAS + Synchronized来保证并发安全。
  • Node数据结构比较简单，就是一个链表，但是只允许对数据进行查找，不允许进行修改。
  • 当HashEntry对象组成的链表长度超过8时，或数组长度小于64 就会扩容，则链表转换为红黑树，提升性能。底层变更为数组＋链表＋红黑树。

底层原理（jdk1.8）

1. Node节点数字用的是volatile修饰。

   //ConcurrentHashMap使用volatile修饰节点数组，保证其可见性，禁止指令重排。
   transient volatile Node<K,V>[] table;

2. ConcurrentHashMap的put()方法。

   //put()方法直接调用putVal()方法
   public V put(K key, V value) {
    return putVal(key, value, false);
   }
   //所以直接看putVal()方法。
   final V putVal(K key, V value, boolean onlyIfAbsent) {
       if (key == null || value == null) throw new NullPointerException();
       int hash = spread(key.hashCode());
       int binCount = 0;
       for (Node<K,V>[] tab = table;;) {
           Node<K,V> f; int n, i, fh;
           if (tab == null || (n = tab.length) == 0) {
               tab = initTable();
           } else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
               if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) {
                   break;  
               }                  
           } else if ((fh = f.hash) == MOVED) {
               tab = helpTransfer(tab, f);
           } else {
               V oldVal = null;
               synchronized (f) {
                   if (tabAt(tab, i) == f) {
                       if (fh >= 0) {
                           binCount = 1;
                           for (Node<K,V> e = f;; ++binCount) {
                               K ek;
                               if (e.hash == hash &&
                                   ((ek = e.key) == key ||
                                    (ek != null && key.equals(ek)))) {
                                   oldVal = e.val;
                                   if (!onlyIfAbsent) {
                                       e.val = value;
                                   }
                                   break;
                               }
                               Node<K,V> pred = e;
                               if ((e = e.next) == null) {
                                   pred.next = new Node<K,V>(hash, key, value, null);
                                   break;
                               }
                           }
                       } else if (f instanceof TreeBin) {
                           Node<K,V> p;
                           binCount = 2;
                           if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) {
                               oldVal = p.val;
                               if (!onlyIfAbsent)
                                   p.val = value;
                           }
                       }
                   }
               }
               if (binCount != 0) {
                   if (binCount >= TREEIFY_THRESHOLD)
                       treeifyBin(tab, i);
                   if (oldVal != null)
                       return oldVal;
                   break;
               }
           }
       }
       addCount(1L, binCount);
       return null;
   }

   put方法并未用synchronized修饰。put过程如下：
   （1）根据 key 计算出 hashcode，然后开始遍历 table；
   （2）判断是否需要初始化；
   （3）f 即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。
   （4）如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。
   （5）如果都不满足，则利用 synchronized 锁写入数据。
   （6）如果数量大于 TREEIFY_THRESHOLD ，则要转换为红黑树。

3. ConcurrentHashMap的get()方法

   // ConcurrentHashMap的get()方法是不加锁的，方法内部也没加锁。
   // 因为table有`volatile`关键字修饰，保证每次获取值都是最新的。
   public V get(Object key)

   get方法源码：

   public V get(Object key) {
       Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
       int h = spread(key.hashCode());
       if ((tab = table) != null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) != null) {
           // 判断头节点是否就是我们需要的节点
           if ((eh = e.hash) == h) {
               if ((ek = e.key) == key || (ek != null && key.equals(ek))) {
                   return e.val;
               }
           } else if (eh < 0) { // 如果头节点的 hash 小于 0，说明 正在扩容，或者该位置是红黑树
               // 参考 ForwardingNode.find(int h, Object k) 和 TreeBin.find(int h, Object k)
               return (p = e.find(h, key)) != null ? p.val : null;
           }
           // 遍历链表
           while ((e = e.next) != null) {
               if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek)))) {
                   return e.val;
               } 
           }
       }
       return null;
   }

   get过程如下：
   （1）首先根据key计算出来的 hashcode 寻址，如果就在桶上那么直接返回值，
   （2）如果是红黑树那就按照树的方式获取值，
   （3）都不满足那就按照链表的方式遍历获取值。

---

Set

List是有序集合的根接口，Set是无序集合的根接口，无序也就意味着元素不重复。更严格地说，Set集合不包含一对元素e1和e2 ，使得e1.equals(e2) ，并且最多一个空元素。
使用Set存储的特点与List相反：元素无序、不可重复。常用的实现方式：HashSet、LinkedHashSet和TreeSet。

具体实现	优点	缺点
HashSet	底层数据结构是哈希表，可以存储null元素，效率高	线程不安全，需要重写hashCode()和equals()来保证元素唯一性
LinkedHashSet	底层数据结构是链表和哈希表(链表保证了元素的顺序与存储顺序一致，哈希表保证了元素的唯一性)，效率高	线程不安全
TreeSet	底层数据结构是二叉树，元素唯一且已经排好序	需要重写hashCode和equals()来保证元素唯一性

当向HashSet结合中存入一个元素时，HashSet会调用该对象的hashCode()方法来得到该对象的hashCode值，然后根据hashCode值来决定该对象在HashSet中存储位置。简单的说，HashSet集合判断两个元素相等的标准是两个对象通过equals方法比较相等，并且两个对象的hashCode()方法返回值也相等。
LinkedHashSet集合同样是根据元素的hashCode值来决定元素的存储位置，但是它同时使用链表维护元素的次序。这样使得元素看起来像是以插入顺序保存的，也就是说，当遍历该集合时候，LinkedHashSet将会以元素的添加顺序访问集合的元素。

在使用Set存储数据时，为保障元素唯一性，常常要重写hashCode。重写hashCode方法时，尽量遵循以下原则：

• 相同的对象返回相同的hashCode值。
• 不同的对象返回不同的hashCode值，否则，就会增加冲突的概率。
• 尽量的让hashCode值散列开（用异或运算可使结果的范围更广）。

Hashset

基本介绍

HashSet是一个无序集合，其底层结构是HashMap，简单来说，HashSet是value是固定值（Object PRESENT = new Object()）的HashMap。HashSet的特点(底层是HashMap/元素无序且不能重复/线程不安全)：

• 使用场景：需要高效去重、快速查找、不考虑内存浪费的场景

• HashSet的底层实现是HashMap（HashSet的值存放于HashMap的key上，HashMap的value是一个统一的值）。

• 底层：哈希表（快速查找）和Set（去重）。它自动对元素进行去重（通过 hashCode 和 equals 方法），并且无序（存入后顺序会乱），允许存储一个null值。

• 性能：底层是哈希表，所以插入、删除和查找操作的时间复杂度都是O(1)，代价是浪费一些空间。

• 线程不安全。如果要保证线程安全，其中一种方法是将其改造成线程安全的类，示例：

  Set set = Collections.synchronizedSet(new HashSet(...));

哈希表是元素为链表的数组，默认容量16，负载因子0.75，处理冲突方法是链地址法。

import java.util.HashSet;
import java.util.LinkedList;
 
public class Test2 {
    public static void main(String[] args) {
        HashSet<String > h = new HashSet<String>();
        h.add("nihao");
        String s1 = new String("nihao");
        h.add(s1);
        System.out.println(s1 == "nihao");        //false
        for(String s:h) System.out.println(s);     //不含重复元素 
    }
}

// 如果Hashset里的元素是对象，若想将成员变量相同视为对象相同，要重写hashCode()：
public class Test {
    public static void main(String[] args) {    //输出23
        Dog dog1 = new Dog(23);
        Dog dog2 = new Dog(23);
        HashSet<Dog> h = new HashSet<Dog>();
        h.add(dog1);h.add(dog2);
        for(Dog dog:h){
            System.out.println(dog.weight); 
        }  
    }
}
public class Dog extends Animal{
     int weight = 4;
     public Dog(){
//         System.out.println("doggouzaao");
     }
     public Dog(int weight){
         this.weight=weight;
     }
    @Override
    public void show() {
        name = "dogname";
        System.out.println("dog");
    }
    @Override
    public boolean equals(Object o) {
        // alt+insert生成equals()和hashCode()方法。这里只需重写hashCode方法就能保证自动去重，equals方法用于元素间的比较
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Dog dog = (Dog) o;
        return weight == dog.weight;
    }
    @Override
    public int hashCode() {
        return weight;
    }
}

HashSet如何检查重复

HashSet自动去重的原理：hashCode值。

所有Java的类或接口都直接或间接继承了Object类，Object类是一切类的根类。Object类有clone()，HashCode()，equals()，toString()，wait()，notify()等基本方法，可以重写这些方法，对类的特性进行设置。

例如给测试类新加一个hashCode()方法，而不加@Override注解（用于声明一个方法为重写的方法），编译器将进行警告：

public class Test {
//    @Override
    public int hashCode() {
        return 1;
    }
    public static void main(String[] args) {
    }
}
// 编译器将进行警告：hashCode()'缺少'@Override'注解

默认情况下，哈希值是根据对象的地址计算出的一个整数值，故同一对象的哈希值一定相同（因为地址是同一地址），不同对象的哈希值默认不同（因为地址不同）。

把对象加入HashSet时，HashSet会先计算对象的hashcode值来判断对象加入的位置，同时也会与Set中其他元素的hashcode值作比较，如果没有相同的hashcode，HashSet会假设对象没有重复出现。如果发现有相同hashcode值的对象，这时会调用equals方法来检查hashcode相等的对象是否真的相同。如果两者相同，HashSet就不再存储该元素。hashCode()与 equals()的相关规定：

• 如果两个对象相等，则hashcode一定也是相同的；
• 两个对象相等，对两个equals方法返回true；
• 两个对象有相同的hashcode值，它们也不一定是相等的；
• 如果equals方法被覆盖过，则hashCode方法也必须被覆盖；
• hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode()，则该 class的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）。

重写hashCode()后哈希值可以相同，例如给Student类重写hashCode()，返回学生的学号，那么学号相同的学生，哈希值就一定相等。

class Student {
    private String name;
    private int id;
    public Student(String name, int id) {
        this.name = name;
        this.id = id;
    }
    // 重写 hashCode() 方法，返回学号作为哈希值
    @Override
    public int hashCode() {
        return id;
    }
    // 重写 equals() 方法，判断学号是否相同
    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj == null || getClass() != obj.getClass()) {
            return false;
        }
        Student student = (Student) obj;
        return id == student.id;
    }
    // 重写 toString() 方法，返回学生姓名和学号
    @Override
    public String toString() {
        return "Student{name='" + name + "', id=" + id + "}";
    }
     // main方法
    public static void main(String[] args) {
        Student student1 = new Student("Tom", 1);
        Student student2 = new Student("Tom", 1);
        // 根据重写的 equals() 方法输出
        System.out.println(student1.equals(student2)); // true
        System.out.println(student1.hashCode()); // 1
        System.out.println(student2.hashCode()); // 1
        // 根据重写的 toString() 方法输出
        System.out.println(student1.toString()); // Student{name='Tom', id=1}
    }
}

常用方法

/* 构造方法 */
public HashSet() // 默认初始容量为16，负载因子为0.75
public HashSet(int initialCapacity) // 指定初始容量，负载因子为0.75
public HashSet(int initialCapacity, float loadFactor) // 指定初始容量和负载因子
/* 增、删、包含 */
public boolean add(E e)
public boolean remove(Object o)
public boolean contains(Object o)
/* 其他方法 */
public void clear() // 清空集合
public boolean isEmpty() // 判断Set是否为空    
public Iterator<E> iterator() //获取迭代器
public int size() // 返回此集合中的元素数        

知识加油站

equals()和hashcode()的关系

两者在用途上的区别：

• hashCode()方法的主要用途是获取哈希码；
• equals()主要用来比较两个对象是否相等。

为什么重写equals()就要重写hashcode()

因为二者之间有两个约定，相等对象的哈希码也要相等。所以equals()方法重写时，通常也要将hashCode()进行重写，使得这两个方法始终满足相关的约定。 例如HashSet排序机制底层就是通过计算哈希码进行排序的，如果只重写equals()将达不到根据哈希码排序的效果。

如果两个对象相等，它们必须有相同的哈希码；但如果两个对象的哈希码相同，他们却不一定相等。

==与equals()的区别

• == 比较基本数据类型时，比较的是两个数值是否相等； 比较引用类型是，比较的是对象的内存地址是否相等。

• equals() 未重写时，Object类默认以==来实现，即比较两个对象的内存地址是否相等； 重写以后，按照重写的逻辑进行比较。

  public boolean equals(0bject obj) { return(this == obj); }

LinkedHashSet

LinkedHashSet是有序集合，其底层是通过LinkedHashMap来实现的，LinkedHashMap其实也就是value是固定值的LinkedHashMap。因此LinkedHashSet中的元素顺序是可以保证的，也就是说遍历序和插入序是一致的。LinkedHashSet继承了HashSet。LinkedHashSet的特点(底层是LinkedHashMap/线程不安全/元素有序)：

• 底层是用LinkedHashMap来实现的。

• 线程不安全 。

• 元素有序，是按照插入的顺序排序的。

• 最多只能存一个null。

• 不支持按访问顺序对元素排序

  LinkedHashSet所有的构造方法都是调用HashSet的同一个构造方法：（accessOrder = false）

  HashSet(int initialCapacity, float loadFactor, boolean dummy) {
      map = new LinkedHashMap<>(initialCapacity, loadFactor);
  }
  
  public LinkedHashMap(int initialCapacity, float loadFactor) {
      super(initialCapacity, loadFactor);
      accessOrder = false;
  }

TreeSet

基本介绍

• 使用场景：适用于多读少写、排序的场景。

• 底层：红黑树（快速查找、排序）和Set（去重）。不允许存储null值

• 性能：插入、删除、查找操作的时间复杂度为O(log n)，因为操作需要维护树的平衡，所以适用于多读少写的场景。

特点

TreeSet是一个有序集合，基于TreeMap实现。TreeSet特点(支持元素排序/线程不安全/去重复):

• TreeSet的基本操作（增删）的时间复杂度是log(n) 。

• TreeSet是非线程安全的。

• TreeSet的迭代器是fail-fast策略的。

• TreeSet中元素不允许为null，不允许重复值。

• TreeSet有序（自然顺序或自定义排序器）。支持元素自然排序和按照在创建时指定Comparator比较器(外比较器)进行排序：

  • TreeSet使用二叉树原理对新增对象按照指定顺序排序，每增加一个对象都会进行排序，将对象插入的二叉树指定的位置。

- TreeSet中存储自定义类的对象时， 自定义的类必须实现Comparable接口，并且覆写相应`compareTo()`函数。


- **元素为基本类型时自然有序：**new TreeSet<int>()。如果TreeSet内元素是**基本数据类型**，它会自动去重有序。Integer和String对象都可以进行默认的TreeSet排序。


- **元素为类时自然或比较器排序：**new TreeSet<类>(Comperable c)。如果TreeSet内元素是类，要实现去重有序，有两种方法。

  - **自然排序：**类要实现Comparable<>接口，并重写compareTo（T）方法；

  - **比较器排序：**以比较器作为构造参数，创建TreeSet对象。如果即实现了Comparable<>接口，又指定了比较器，则使用比较器排序。

  - 在重写compareTo()函数时，要返回相应的值才能使 TreeSet 按照一定的规则来排序。比较此对象与指定对象的顺序。如果该对象小于、等于或大于指定对象，则分别返回负整数、零或正整数。示例：

    
@Data
public class student  implements Comparable<student>{
    private String name;
    private int age;
    
    @Override
    public int compareTo(student s) {
        // 主要条件：按照年龄从小到大
        int num = this.age - s.age;
        //次要条件：年龄相同时，按照姓名的字母顺序排序
        int num2 = num == 0 ? this.name.compareTo(s.name) : num;
        return num2;
    }
}
public class Comparabledemo {
    public static void main(String[] args) {
        TreeSet<student> tree = new TreeSet<student>();
        student s1 = new student("wuer",27);
        student s2 = new student("weuers",250);
        tree.add(s1);
        tree.add(s2);
    }   
}

方法一：自然排序

// 狗类：按自然排序时要实现Comperable<>并重写compareTo()方法
public class Dog  implements Comparable<Dog>{        
    int weight;
    String name;
 
    public Dog(int weight, String name) {
        this.weight = weight;
        this.name = name;
    }
 
    @Override
    public String toString() {
        return "Dog{ weight=" + weight + ", name='" + name + '\'' + '}';
    }
 
    @Override
    public int compareTo(Dog dog){    // 实参是上一只狗，本狗与上狗做比较
        // 返回正数，即本狗比上只狗大，按存取顺序排序
        return 1;
        // return -1; 存储逆序排序
        // return 0; 视为相等，后插入的重复元素会被删除。
        // return this.weight-dog.weight; 按体重从小到大排序，后狗-前狗。
    }
}
// 测试
public class Test {
    public static void main(String[] args) {
        // 创建两个小狗对象，让他们按自己compareTo()逻辑排序，即按存取顺序排序
        Dog dog1 = new Dog(23,"abc");
        Dog dog2 = new Dog(45,"abc"); Dog dog3 = new Dog(45,"abc");
        TreeSet<Dog> dogs = new TreeSet<>();
        dogs.add(dog1);dogs.add(dog2);dogs.add(dog3);
        // 因为第三只狗和第二只狗存取顺序不同，所以他们被认为是两只狗
        // [Dog{weight=23, name='abc'}, Dog{weight=45, name='abc'}, Dog{weight=45, name='abc'}]
        System.out.println(dogs);
    }
}

方法二：比较器排序

无需Dog类再实现Comparable接口，直接TreeSet类带参构造方式创建对象即可，参数为比较器Comparator<>。

// 狗类：按比较器排序时不需要再实现Comperable<>
public class Dog {
    int weight;
    String name;
    public Dog(int weight, String name) {
        this.weight = weight;
        this.name = name;
    }
    @Override
    public String toString() {
        return "Dog{ weight=" + weight + ", name='" + name + '\'' + '}';
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        Dog dog = (Dog) o;
        return weight == dog.weight && Objects.equals(name, dog.name);
    }
    @Override
    public int hashCode() {
        return Objects.hash(weight, name);
    }
}

// 测试类
public class Test {
    public static void main(String[] args) {
        //下面比较器也可以用Lambda表达式形式，即TreeSet<>((a,b)->{..})
        TreeSet<Dog> dogs=new TreeSet<>(new Comparator<Dog>() {
            @Override
            public int compare(Dog a, Dog b){
                if(a.weight!=b.weight) {
                    return a.weight-b.weight;
                }
                else {
                    return a.name.compareTo(b.name);
                }
            }
        });
        dogs.add(new Dog(34,"abc")); dogs.add(new Dog(26,"abc"));
        dogs.add(new Dog(26,"abcd")); dogs.add(new Dog(26,"abcd"));
        // 可以看见，前三只狗按体重、名称排序，第四只狗被去重了
        // [Dog{weight=26, name='abc'}, Dog{weight=26, name='abcd'}, Dog{weight=34, name='abc'}]
        System.out.println(dogs);
    }
}

常用方法

/* 构造方法 */
public TreeSet() // 创建一个空的 TreeSet，使用自然排序
public TreeSet(Comparator<? super E> comparator) // 指定比较器，如果比较器是 null 将使用自然排序
/* 增 */
public boolean add(E e) // 添加一个元素
public  boolean addAll(Collection<? extends E> c) // 添加集合中的元素
/* 删 */  
public boolean remove(Object o)
public E pollFirst() // 检索和删除最小（第一个）元素
public E pollLast() // 检索和删除最大（最后）元素
/* 包含 */
public boolean contains(Object o)
/* 获取特殊元素 */
public E last() // 返回此TreeSet中存在的最大元素
public E first() // 返回此TreeSet中存在的最小元素
public E floor(E e) // 返回在这个集合中小于或者等于给定元素的最大元素
public E ceiling(E e) // 返回在这个集合中大于或者等于给定元素的最小元素
public E higher(E e) // 返回此集合中大于某个元素的最小的元素
public E lower(E e) // 返回此集合中小于某个元素的最大的元素   
/* 其他方法 */
public int size() // 获取TreeSet元素个数
public boolean isEmpty() // 判断TreeSet是否为空
public void clear() // 清空TreeSet

HashSet和TreeSet的区别

相同点：元素都可以自动去重

不同点：

	HashSet	TreeSet
实现	基于哈希表 实现	基于红黑树 (Red-Black Tree) 实现
排序	不保证顺序	按自然顺序或指定的比较器排序
性能	插入、删除和查找操作的时间复杂度为 O(1)	插入、删除和查找操作的时间复杂度为 O(log n)
是否允许 null 元素	允许存储一个 null 元素	不允许存储 null 元素
适用场景	适用于对顺序无要求、自动去重、快速查找和插入的场景	适用于需要自动有序、去重存储的场景
去重原理	通过复写hashCode()方法和equals()方法来保证	Treeset通过Compareable接口的compareto来保证。

---

ArrayDeque：双端队列

ArrayDeque 是 Java 中基于动态数组实现的双端队列（Double-Ended Queue），同时支持栈（Stack）和队列（Queue）的操作。在刷力扣等算法题时经常使用这个集合。

特点

• 双端操作：可以在队列的头部和尾部高效地插入/删除元素（时间复杂度 O(1)）。
• 动态扩容：底层是循环数组，容量不足时自动扩容（默认初始容量为 16）。
• 非线程安全：需手动处理并发问题。
• 性能高：对比 LinkedList（基于链表），数组结构对 CPU 缓存更友好，随机访问更快。

作为栈（先进后出）的核心方法

操作类型	方法名	功能描述	返回值/异常
增	push(E element)	压栈（元素添加到头部）	无返回值，队列满时自动扩容
	addFirst(E element)	同 push	队列满时抛出 IllegalStateException（但 ArrayDeque 动态扩容，一般不会）
删	pop()	弹栈（移除并返回头部元素）	返回头部元素；栈为空时抛出 NoSuchElementException
	removeFirst()	同 pop()	同上
查	peek()/peekFirst()	查看栈顶元素（不删除）	返回头部元素；栈为空时返回 null
	peekLast()	查看栈尾元素（不删除）	返回尾部元素；栈为空时返回 null

作为队列（先进先出）的核心方法

操作类型	方法名	功能描述	返回值/异常
增	offer(E element)	入队（元素添加到尾部）	成功返回 true，队列满时返回 false（但 ArrayDeque 动态扩容，总是成功）
	addLast(E element)	同 offer	队列满时抛出 IllegalStateException（理论上不会触发）
删	poll()	出队（移除并返回头部元素）	返回头部元素；队列为空时返回 null
	removeFirst()	同 poll()	队列为空时抛出 NoSuchElementException
查	peek()/peekFirst()	查看队首元素（不删除）	返回头部元素；队列为空时返回 null
	peekLast()	查看队尾元素（不删除）	返回尾部元素；队列为空时返回 null

// 栈
ArrayDeque<Integer> stack = new ArrayDeque<>();
// 压栈
stack.push(1); stack.push(2);
// 查看栈顶
System.out.println(stack.peek()); // 输出 2
// 弹栈
int top = stack.pop(); // 返回 2，栈中剩余 [1]
 
// 队列
ArrayDeque<Integer> queue = new ArrayDeque<>();
// 入队
queue.offer(1); queue.offer(2);
// 查看队首
System.out.println(queue.peek()); // 输出 1
// 出队
int head = queue.poll(); // 返回 1，队列中剩余 [2]