Java 集合

学习视频：
【韩顺平讲Java】Java集合专题 -ArrayList HashMap HashSet List Map TreeMap TreeSet等_哔哩哔哩_bilibili

1. 集合介绍

数组的不足：不够灵活
- 长度开始时必须指定，而且一旦指定，不能更改
- 保存的必须为同一类型的元素
- 使用数组进行增加元素的示意代码比较麻烦

// 数组扩容示例代码
Person[] pers = new Person[1];
pers[0] = new Person();

// 扩容
Person[] pers2 = new Person[pers.length + 1]  // 创建新数组
for() {}  // 拷贝 pers 数组的元素到 pers2
pers2[pers2.length - 1] = new Person();  // 添加新的对象

集合的好处：
- 可以动态保存任意多个对象，使用比较方便
- 提供了一系列方便的操作对象的方法(crud)：add、remove、set、get 等
- 使用集合添加，删除新元素代码更加简洁

2. 集合的框架体系-背

Collection 接口继承了 Iterable 接口
- List Set 接口继承了 Collection 接口
- List 接口常用的实现类有 ArrayList,LinkedList
- Set 接口常用的实现类有 HashSet,TreeSet

Map 接口
- 常见实现类：HashMap、LinkedHashMap、TreeMap
- LinkedHashMap 继承了 HashMap 的同时实现了 Map 接口

集合主要有2组：
- 一组是单列集合（集合里面放的是单个对象）
  - Collection 接口有 List 和 Set 这两个主要的接口，他们的实现类都是单列集合
- 另一组是双列集合（存储的往往是键值对形式的）
  - Map 接口的实现子类是双列集合，存放 key 和 value 数据

3. Collection

3.1 Collection 接口实现类的特点

接口声明： Collection 是一个泛型接口，继承自 Iterable 接口，允许其实现类的对象能被迭代

1	public interface Collection<E> extends Iterable<E>

Collection 实现子类可以存放多个元素，每个元素可以是Object
不同的 Collection 实现具有不同的元素存储特性：
- 允许重复元素：例如 List 实现类（如 ArrayList, LinkedList）允许插入重复元素。
- 不允许重复元素：Set 实现类（如 HashSet, TreeSet）保证元素唯一性。
集合是否有序取决于具体实现：
- 有序集合：List 接口的实现类保持元素插入的顺序。
- 无序集合：Set 接口的实现类通常不保持任何特定顺序（LinkedHashSet 除外，它按照插入顺序维护元素）。
Collection 接口没有直接的实现子类，是通过它的子接口 Set 和 List 来实现的

3.2 Collection 接口常用方法

/**
 * Collection 接口常用方法
 */
public class CollectionMethod {
    public static void main(String[] args) {
        List list = new ArrayList<>();

        // add: 添加单个元素
        list.add("hhh");
        list.add("10");  // 自动装箱 相当于 list.add(new Integer(10))
        list.add(true);
        System.out.println("list = " + list);

        // remove: 删除指定元素
        // list.remove(0);  // 删除第一个元素
        list.remove(true);  // 指定删除某个元素
        System.out.println("list = " + list);

        // contains: 查找元素是否存在
        System.out.println(list.contains("hhh"));  // true

        // size: 获取元素个数
        System.out.println(list.size());  // 2

        // isEmpty: 判断是否为空
        System.out.println(list.isEmpty());  // false

        // clear: 清空
        list.clear();
        System.out.println("list = " + list);  // list = []

        // addAll: 添加多个元素
        ArrayList<Object> list2 = new ArrayList<>();
        list2.add("111");
        list2.add("222");
        list2.add("333");
        list.addAll(list2);
        System.out.println("list = " + list);  // list = [111, 222, 333]

        // containsAll: 查找多个元素是否都存在
        System.out.println(list.containsAll(list2));  // true

        // removeAll: 删除多个元素
        list.add("444");
        list.removeAll(list2);
        System.out.println("list = " + list);  // list = [444]
    }
}

3.3 Collection 接口遍历元素

遍历元素方式1—使用 Iterator 迭代器

迭代器是一个对象，这个对象实现了 Iterator 接口，主要用于遍历 Collection 集合中的元素，该接口包含几个方法：
- hasNext(): 检查集合中是否还有元素可以遍历。如果有，返回 true；如果没有，返回 false。
- next(): 迭代器将其内部游标向前移动到下一个元素的位置，同时返回游标所到达位置的元素。
在调用 next() 方法之前必须要调用 hasNext() 进行检测，若不调用且下一条记录无效，直接调用 next() 会抛出 NoSuchElementException 异常
- remove(): 删除最近通过 next() 方法返回的元素。这个方法是可选的，集合本身可以不支持这个操作。

使用迭代器可以通过一个统一的接口遍历不同类型的集合（如 ArrayList, HashSet 等），而不必关心它们内部是如何组织数据的
所有实现了Collection 接口的集合类都有一个 iterator() 方法，用于返回一个实现了 Iterator 接口的对象，即可以返回一个迭代器

Iterator 仅用于遍历集合，Iterator 本身不存放对象
代码示例：快捷键 itit
- （提示所有快捷键的快捷键：ctrl + j）

public class CollectionIterator {
    public static void main(String[] args) {
        Collection col = new ArrayList();

        col.add(new Book("11", "1", 1.1));
        col.add(new Book("22", "2", 2.2));
        col.add(new Book("33", "3", 3.3));

        System.out.println("col = " + col);

        // 遍历集合
        // 1. 先得到 col 对应的迭代器
        Iterator iterator = col.iterator();

        // 2. 使用 while 循环遍历, 快捷键 itit
        while (iterator.hasNext()) {  // 判断是否还有数据
            // 返回下一个元素, 类型为 Object
            Object obj = iterator.next();
            System.out.println("obj = " + obj);
        }
        // 3. 当退出 while 循环后, 这时 iterator 迭代器指向最后的元素
        // 4. 若希望再次遍历, 需要重置迭代器
        iterator = col.iterator();
        System.out.println("======第二次遍历");
        while (iterator.hasNext()) {  
            Object obj = iterator.next();
            System.out.println("obj = " + obj);
        }
    }
}

遍历元素方式2—使用 for 循环增强

增强 for循环，可以代替 iterator 迭代器，特点：增强 for 就是简化版的 iterator，本质一样。只能用于遍历集合或数组
基本语法：
“元素类型”是集合或数组中包含的元素的数据类型
“元素变量”是在循环体内部用于访问当前遍历元素的变量名
“集合名或数组名”是要遍历的集合或数组的变量名

1
2
3

for (元素类型 元素变量 : 集合对象或数组) {
    // 访问元素变量
}

代码示例：快捷键 I 或者 集合对象.for
- 补充：传统 for 循环的快捷键：fori

// 使用增强 for 遍历集合
for (Object book : col) {
    System.out.println("book = " + book);
}

// 增强 for 也可以直接在数组使用
int[] nums = {1, 8, 10, 90};
for (int i : nums) {
    System.out.println("i = " + i);
}

使用注意事项：
- 只读遍历：使用增强 for 循环时，不能修改正在遍历的集合的结构，例如添加或删除元素，这可能会导致 ConcurrentModificationException 异常。如果需要在遍历过程中修改集合，应使用显式的迭代器并调用其 remove() 方法
- 遍历对象类型：增强 for 循环可以遍历任何实现了 Iterable 接口的集合类以及所有类型的数组
- 局限性：尽管增强 for 循环语法简单，但它不适合在需要使用元素索引或需要从集合中间开始遍历的场景。在这种情况下，使用传统的 for 循环会更合适

3.4 练习题

编写程序 CollectionExercise：

创建3个Dog{name,age}对象,放入到ArrayList中，赋给List使用
用迭代器和增强for循环两种方式来遍历
重写Dog的toString方法，输出name和age

public class CollectionEx {
    public static void main(String[] args) {
        List<Dog> dogLists = new ArrayList<>();  // 接口多态的传递

        dogLists.add(new Dog("aa", "1"));
        dogLists.add(new Dog("bb", "2"));
        dogLists.add(new Dog("cc", "3"));

        // 迭代器遍历
        Iterator<Dog> iterator = dogLists.iterator();
        while (iterator.hasNext()) {
            Dog dog = iterator.next();
            System.out.println("dog = " + dog);
        }

        System.out.println("==============");
        // 增强 for 遍历
        for (Dog dog : dogLists) {
            System.out.println("dog = " + dog);
        }
    }
}

4. List

4.1 List 接口基本介绍

List 接口是 Collection 接口的子接口，特点如下：

有序性：List 集合类中元素有序(即添加顺序和取出顺序一致)
元素重复：与 Set 接口不同，List 允许重复的元素，即同一个值可以出现多次
索引访问：List 集合支持索引，每个元素都有其对应的顺序索引，开始于0
整数型序号：List 容器中的元素都对应一个整数型的序号，记录其在容器中的位置，可以根据序号存取容器中的元素
List 接口的常用实现类有：ArrayList、LinkedList 和 Vector

public class List_ {
    public static void main(String[] args) {
        // 1. List集合类中元素有序(即添加顺序和取出顺序一致)、且可重复
        List list = new ArrayList();
        list.add("jack");
        list.add("tom");
        System.out.println("list=" + list);

        // 2. List集合中的每个元素都有其对应的顺序索引, 即支持索引
        // 索引是从0开始的
        System.out.println(list.get(1));  // tom
    }
}

4.2 List 接口常用方法

void add(int index, Object ele)：在index位置插入ele元素，没有index，默认在最后插入
boolean addAll(int index, Collection eles)：从index位置开始将eles中的所有元素添加进来
Object get(int index)：获取指定index位置的元素
int indexOf(Object obj)：返回obj在集合中首次出现的位置
int lastIndexOf(Object obj)：返回obj在当前集合中末次出现的位置
Object remove(int index)：移除指定index位置的元素，并返回此元素
Object set(int index, Object ele)：设置指定index位置的元素为ele , 相当于是替换
List subList(int fromIndex, int toIndex)：返回从fromIndex到toIndex位置的子集合，注意返回的子集合 fromIndex <= subList < toIndex

public class ListMethod {
    public static void main(String[] args) {
        List list = new ArrayList();
        list.add("111");
        list.add("222");

        // void add(int index, Object ele): 在index位置插入ele元素
        // 在 index = 1 的位置插入一个对象
        list.add(1, "333");
        System.out.println("list = " + list);  // list = [111, 333, 222]

        // boolean addAll(int index, Collection eles): 从index位置开始将eles中的所有元素添加进来
        List list2 = new ArrayList();
        list2.add("44");
        list2.add("55");
        list.addAll(1, list2);
        System.out.println("list = " + list);  // list=[111, 44, 55, 333, 222]

        // Object get(int index): 获取指定index位置的元素
        System.out.println(list.get(1));  // 44

        // int indexOf(Object obj): 返回obj在集合中首次出现的位置
        System.out.println(list.indexOf("44"));  // 1

        // int lastIndexOf(Object obj): 返回obj在当前集合中末次出现的位置
        list.add("333");
        System.out.println("list = " + list);  // list=[111, 44, 55, 333, 222, 333]
        System.out.println(list.lastIndexOf("333"));  // 5

        // Object remove(int index): 移除指定index位置的元素，并返回此元素
        list.remove(0);
        System.out.println("list = " + list);  // list = [44, 55, 333, 222, 333]

        // Object set(int index, Object ele): 设置指定index位置的元素为ele, 相当于是替换
        list.set(1, "66");
        System.out.println("list = " + list);  // list = [44, 66, 333, 222, 333]

        // List subList(int fromIndex, int toIndex): 返回从fromIndex到toIndex位置的子集合
        // 注意返回的子集合 fromIndex <= subList < toIndex
        List returnList = list.subList(0, 2);
        System.out.println("returnList = " + returnList);  // returnList = [44, 66]
    }
}

4.3 List 的三种遍历方式

ArrayList, LinkedList,Vector 三种遍历使用的方式一致

方式一：使用迭代器
方式二：增强for循环
方式三：使用普通for循环

public static void main(String[] args) {

        // List 接口主要的实现子类
        List list = new ArrayList();
//        List list = new Vector();
//        List list = new LinkedList();

        list.add("11");
        list.add("22");
        list.add("33");
        list.add("44");

        // 遍历
        // 1. 迭代器
        Iterator iterator = list.iterator();
        while (iterator.hasNext()) {
            Object obj = iterator.next();
            System.out.println(obj);
        }

        System.out.println("=====增强for=====");
        // 2. 增强 for
        for (Object o : list) {
            System.out.println("o = " + o);
        }

        System.out.println("=====普通for====");
        // 3. 使用普通 for
        for (int i = 0; i < list.size(); i++) {
            System.out.println("对象 = " + list.get(i));
        }
}

练习：

public static void main(String[] args) {
    List<Book> list = new ArrayList<>();
    //        List<Book> list = new LinkedList<>();
    //        List<Book> list = new Vector<>();

    list.add(new Book("11", 5.1, "aa"));
    list.add(new Book("22", 1.1, "bb"));
    list.add(new Book("33", 2.1, "cc"));

    BubbleSort(list);

    for (Book book : list) {
        System.out.println(book);
    }
}

// 冒泡排序
public static void BubbleSort(List<Book> list) {
    for (int i = 0; i < list.size() - 1; i++) {
        for (int j = 0; j < list.size() - i - 1; j++) {
            if (list.get(j).getPrice() > list.get(j + 1).getPrice()) {
                Book temp = list.get(j);
                list.set(j, list.get(j + 1));
                list.set(j + 1, temp);
            }
        }
    }
}

4.4 List 接口实现类-ArrayList

注意事项

空元素支持：ArrayList 允许包含任意数量的 null 元素。这使得它在某些使用场景中非常灵活，例如在数据集中可能存在的缺失数据可以用 null 表示
内部数据存储：ArrayList 是基于动态数组实现的，这意味着它的元素存放在数组中。这也解释了为什么 ArrayList 可以提供快速的随机访问能力
与 Vector 的比较：
- 相似性：ArrayList 和 Vector 都是基于数组的实现，提供快速的随机访问和有序的元素存储
- 线程安全：ArrayList 是非同步的，因此它是线程不安全的，而 Vector 是同步的，因此是线程安全的。这使得 ArrayList 在单线程环境下性能更优，但在多线程环境中可能需要外部同步措施
对于需要线程安全的 ArrayList 替代方案：
- 使用 Vector 容器
- 使用 Collections 的静态方法 synchronizedList(List< T> list)
- 采用 CopyOnWriteArrayList 容器

三种线程安全的List-CSDN博客

读多写少的情况下，推荐使用 CopyOnWriteArrayList 方式

读少写多的情况下，推荐使用Collections.synchronizedList() 的方式

底层结构和源码分析

ArrayList 中维护了一个 Object 类型的数组 elementData

1
2
3

// transient 表示瞬间，短暂的，表示该属性不能被序列化
// 序列化是将对象的状态信息转换为可以存储或传输的形式的过程
transient Object[] elementData;

在 Java 中，序列化通常指的是将对象转换为字节流，以便可以将其写入磁盘、通过网络等发送。反序列化是序列化的逆过程，它从字节流中重构对象。

序列化的目的是持久化存储/网络通信等等，使 elementData 成为 transient 的原因：

空间效率：通常 elementData 的大小（容量）比实际存储的元素数量要大，如果 elementData 被序列化，那么即使数组中有大量未使用的空间，这些空间也会被序列化，导致不必要的存储和传输开销。

时间效率：序列化和反序列化一个包含许多 null 值的大数组会显著降低性能，尤其是在网络传输等场景中。

当创建 ArrayList 对象时，
- 如果使用的是无参构造器，则初始 elementData 容量为0，第1次添加，则扩容 elementData 为 10，如果需要再次扩容，则扩容 elementData 为1.5倍
1
2
int newCapacity = oldCapacity + (oldCapacity >> 1); // 10 + 10/2 = 15 (即 10 的 1.5 倍)
// 0 => 10 => 15 => 22 => 33 => ...
- 如果使用的是指定大小的构造器，则初始 elementData 容量为指定大小，如果需要扩容，则直接扩容 elementData 为 1.5 倍
1
2
// 假设初始指定为 8, 则:
// 8 => 12(8+8/2) => 18 => 27 => ...

注意：Idea 默认情况下，Debug 显示的数据是简化后的(比如数组不会显示 null 的元素)，如果希望看到完整的数据，需要做如下设置：

加断点分析源码：

public static void main(String[] args) {
    // 使用无参构造器创建 ArrayList 对象
    ArrayList list = new ArrayList();
    // ArrayList list = new ArrayList(8);

    // 使用 for 给 list 集合添加 1-10 数据
    for (int i = 1; i <= 10; i++) {
        list.add(i);  // 触发 Integer 类的 valueOf(int i) 方法，自动装箱
    }

    // 使用 for 给 list 集合添加 11-15 数据
    for (int i = 11; i <= 15; i++) {
        list.add(i);
    }

    list.add(100);
    list.add(200);
    list.add(null);
}

使用无参构造器，创建和使用 ArrayList：

创建静态空数组 elementData，DEFAULTCAPACITY_EMPTY_ELEMENTDATA 是一个静态的空数组实例

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

添加元素
- 调用 add(E e) 来添加一个元素
- add 方法首先调用 ensureCapacityInternal(size + 1) 来确保容量
- ensureCapacityInternal 调用 calculateCapacity 来确定所需的容量，然后调用 ensureExplicitCapacity
- ensureExplicitCapacity 检查当前容量是否足够，如果不够，调用 grow 来扩容
- 添加元素到数组，增加 size

public boolean add(E e) {
    // 确保 ArrayList 有足够的空间来存储新添加的元素
    ensureCapacityInternal(size + 1);  
    // 将新元素 e 存储在 elementData 数组的 size 索引位置, 赋值完成后增加 size 的值
    elementData[size++] = e;
    return true;
}

// 确保内部数组 elementData 有足够的容量
private void ensureCapacityInternal(int minCapacity) {
    // 调用 calculateCapacity 来确定所需的容量
    // 然后调用 ensureExplicitCapacity
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

// 计算并返回 ArrayList 所需的最小容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 检查是否是默认空数组，如果是，意味着这是首次添加元素，此将容量设为 DEFAULT_CAPACITY = 10 和 minCapacity 中的较大值，以避免过早的数组扩容
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);  // max(10, 1)，返回 10
    }
    // 如果不是空数组，直接返回传入的 minCapacity
    return minCapacity;
}

// ensureExplicitCapacity 检查当前容量是否足够，如果不够，调用 grow 来扩容
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;  // 记录当前集合被修改的次数，防止多线程操作出现异常
    // 如果所需最小容量大于当前数组长度，则需要扩容
    // 10 - 0 > 0 不够的
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

// 扩容
private void grow(int minCapacity) {  // 10
    // 获取旧容量
    int oldCapacity = elementData.length;  // 0
    // 新容量为旧容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);  // 首次 0 + 0/2 = 0
    // 如果1.5倍仍不满足需求，则直接使用所需最小容量
    if (newCapacity - minCapacity < 0)  // 0-10<0 第一次由于初始容量为0，没法按照 1.5 倍机制扩容，所以新容量就是 newCapacity = 10
        newCapacity = minCapacity;  
    // 如果新容量超出了最大数组大小，则调用 hugeCapacity 来处理
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 将 elementData 数组扩展到 newCapacity 指定的大小，并保留所有现有元素，新扩展的部分（如果有）将初始化为 null
    elementData = Arrays.copyOf(elementData, newCapacity);
}

// 处理在数组需要扩容到非常大的尺寸时的特殊情况，，保证 ArrayList 不会因为数组大小请求不当而导致程序崩溃或安全问题
private static int hugeCapacity(int minCapacity) {
    // 如果 minCapacity 小于 0，这通常是由于整数溢出导致的，抛出 OutOfMemoryError，表示内存溢出错误
    if (minCapacity < 0) 
        throw new OutOfMemoryError();
    // Java 的数组最大长度是 MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8，因为某些 JVM 实现通过使用数组的一部分作为数组头部
    // 如果 minCapacity 要求的容量超过了 MAX_ARRAY_SIZE 但未溢出，方法返回 MAX_ARRAY_SIZE，即数组能达到的最大安全容量
    // 如果 minCapacity 请求超过了 Integer.MAX_VALUE，则方法返回 Integer.MAX_VALUE
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}

使用指定大小的构造器，创建和使用 ArrayList：

创建一个指定大小的 elementData 数组：传入的初始化容量 (initialCapacity) 大于 0，构造函数会创建一个新的 Object 数组，其长度等于指定的 initialCapacity
第一次扩容就按照elementData 的 1.5 倍扩容，其他步骤同无参构造器

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        // 如果传入的初始化容量为 0，则构造函数不分配任何数据存储空间，而是将 elementData 初始化为 EMPTY_ELEMENTDATA（一个预定义的空数组）
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        // 如果传入的初始化容量小于 0，则构造函数抛出 IllegalArgumentException
        throw new IllegalArgumentException("Illegal Capacity: " +
                                           initialCapacity);
    }
}

4.5 List 接口实现类-Vector

基本介绍

Vector 类的定义说明：

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    // ...
}

Vector 底层也是一个对象数组，

1	protected Object[] elementData

Vector 是线程同步的，即线程安全，Vector 类的操作方法基本都带有 synchronized

public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

开发中一般用 JUC 包中绝对线程安全的集合，Vector 只是相对安全，add、remove 这些方法不是原子操作，所以还是别用 Vector

Vector VS. ArrayList

Vector()无参构造器内部调用了另一个构造器Vector(int initialCapacity)，并且传递了一个默认的初始容量值10
- 如果初始容量不是负数，这个构造器将创建一个新的对象数组elementData，数组的长度为initialCapacity

public Vector() {
    this(10);
}

// 若是有参构造器，就直接进入这个函数里，其他区别不大
public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

public Vector(int initialCapacity, int capacityIncrement) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}

ArrayList使用的是一种称为延迟初始化的策略（Lazy Initialization）。这意味着除非真正需要（即首次添加元素），否则不会创建存储元素的内部数组

在很多使用场景中，ArrayList可能仅仅是被实例化但并未使用，或者只添加了少量元素。使用延迟初始化可以避免在这些情况下分配不必要的内存，从而更高效地使用资源

Vector 的底层扩容结构

**调用 add(E e)**：开始添加元素。
**调用 ensureCapacityHelper(int minCapacity)**：确保有足够的容量。
调用 grow(int minCapacity)（如果需要）：进行实际的数组扩容。
**完成 add(E e)**：元素添加到数组，方法结束。

// 添加一个元素 e 到 Vector 的末尾
public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

// 检查并确保有足够的容量来存储至少 minCapacity 个元素
private void ensureCapacityHelper(int minCapacity) {
    // 如果所需的最小容量 minCapacity 大于当前数组 elementData 的长度，则调用 grow 方法来扩容数组
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

// 扩容
private void grow(int minCapacity) {
    // 获取旧容量
    int oldCapacity = elementData.length;
    // 如果 capacityIncrement 大于 0，则新容量为 oldCapacity + capacityIncrement；否则，新容量为 oldCapacity * 2（默认行为是翻倍扩容）
    // capacityIncrement 是构造时指定的扩容大小(如果有)
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

4.6 List 接口实现类-LinkedList

底层结构

LinkedList 实现了双向链表和双端队列特点
- 双向链表的结构 LinkedList 不仅支持普通的列表操作（如添加、删除、查找等），还支持双端队列的操作
- 双端队列（deque，全称“double-ended queue”）是一种允许从两端添加和删除元素的队列，意味着 LinkedList 可以作为栈（后进先出）和队列（先进先出）使用
可以包含任意元素：可以添加任意元素(元素可以重复)，包括 null
线程不安全：没有实现同步

操作机制

双向链表结构：LinkedList 底层维护了一个双向链表，允许向前或向后遍历
首尾节点引用：LinkedList 中维护了两个属性 first 和 last 分别指向首节点和尾节点，是管理链表添加或删除元素时的关键
节点结构：每个节点(Node 对象)里又维护了 prev,next,item 三个属性，其中通过 prev 指向前一个，通过 next 指向后一个节点，最终实现双向链表

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

添加和删除元素：LinkedList 的元素的添加和删除，不是通过数组完成的，相对来说效率较高

LinkedList VS. ArrayList

如何选择 ArrayList和ListedList：

如果改查的操作多，选择ArrayList
如果增删的操作多，选择ListedList
一般在程序中，80-90% 都是查询，大部分情况下会选择ArrayList
在项目中，会根据业务灵活选择，可能一个模块用ArrayList，另一个用ListedList

LinkedList 底层 crud 方法 debug 分析

LinkedList 的无参构造器创建了一个空的 LinkedList，因为元素是通过节点 (Node) 动态连接的。以下是在这个构造器中隐式初始化的成员：
- **size**：追踪 LinkedList 中元素的数量，初始值为 0
- **first**：指向链表中的第一个节点，初始值为 null
- **last**：指向链表中的最后一个节点，初始值为 null

这些属性是 transient 的，这意味着它们不是由序列化机制自动保存和恢复的，这主要是出于链表元素的序列化需要特殊处理的考虑

transient int size = 0;
transient Node<E> first;
transient Node<E> last;

public LinkedList() {
}

实现双向链表添加元素的核心代码：
- 获取当前尾节点：将当前的尾节点引用存储在局部变量 l 中。这是链表中最后一个节点，如果链表为空，则 l 为 null
- 创建新节点：创建一个新的节点 newNode，其数据域为 e，prev 指针指向当前的尾节点 l（如果存在），next 指针为 null（因为它将成为新的尾节点）
- 更新尾节点引用：将 last 引用更新为新创建的节点 newNode，这样 newNode 现在正式成为链表的尾节点
- 更新头节点引用（如果需要）：如果 l 为 null，意味着链表之前是空的（没有节点），因此新节点也是链表的第一个节点。故将 first 引用指向 newNode
- 链接前一个尾节点到新节点：如果链表不为空（即 l 不是 null），将原来尾节点的 next 指针指向新节点 newNode
- 增加链表大小
- 更新修改计数：增加 modCount，这是用于迭代器的快速失败机制（fail-fast behavior），即在迭代过程中如果检测到结构性修改，会抛出 ConcurrentModificationException

// 向 LinkedList 的末尾添加一个新元素 e
public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    // 获取当前尾节点
    final Node<E> l = last;
    // 创建新节点, 其数据域为 e，prev 指针指向当前的尾节点 l（如果存在），next 指针为 null（因为它将成为新的尾节点）
    final Node<E> newNode = new Node<>(l, e, null);
    // 更新尾节点引用, 将 last 引用更新为新创建的节点 newNode
    last = newNode;
    // 如果 l 为 null，意味着链表之前是空的（没有节点），因此新节点也是链表的第一个节点, 故更新头节点引用
    if (l == null)
        first = newNode;
    else  // 链接前一个尾节点到新节点
        l.next = newNode;
    size++;  // 增加链表大小
    modCount++;  // 支持快速失败行为，确保集合在结构上的修改能够即时被迭代器感知，从而在发生并发修改时快速响应，抛出异常，避免迭代器行为不确定
}

实现双向链表删除链表的第一个节点的核心代码：
- 获取和清除数据：
  - 存储第一个节点的值到局部变量 element。
  - 将节点的 item 和 next 设置为 null，帮助垃圾收集器进行回收。
- 更新头部链接：
  - 将 first 更新为 next，如果 next 为 null（即原链表只有一个节点），则同时将 last 设置为 null。
  - 如果 next 不是 null，更新 next.prev 为 null，断开它与原首节点的链接。
- 维护链表状态：
  - 减小 size。
  - 增加 modCount，支持迭代器的快速失败行为。

public E remove() {
    return removeFirst();
}

public E removeFirst() {
    // 获取首节点
    final Node<E> f = first;
    if (f == null)  // 若是空链表则抛异常
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

// 删除链表的第一个节点
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;  // 获取节点存储的元素
    final Node<E> next = f.next;  // 获取节点的下一个节点引用
    f.item = null;  // 清除节点的数据项，帮助垃圾收集器回收
    f.next = null;  // 断开节点的下一个链接，也是为了垃圾回收
    first = next;  // 将头指针更新为下一个节点
    if (next == null)  // 如果下一个节点不存在，说明链表只有一个节点
        last = null;  // 更新尾指针为 null
    else
        next.prev = null;  // 否则，设置新的头节点的前一个节点为 null
    size--;  // 链表大小减 1
    modCount++;  // 修改计数增加，用于迭代器的快速失败机制
    return element;  // 返回被删除的元素
}

5. Set

5.1 Set 接口基本介绍

特点：
- 无序性：Set 集合中的元素没有固定的顺序，元素的存储位置由 Set 的实现方式决定。添加和移除元素的顺序不保证一致性，也就是说，迭代 Set 时元素的返回顺序不一定反映它们被添加的顺序
- 唯一性：Set 不允许重复的元素。每个元素在 Set 中只能出现一次。如果尝试添加重复的元素，添加操作通常会被忽略
- 有限的 null 支持：大多数 Set 实现允许至少一个 null 元素（如果允许的话），但添加多个 null 会被视为重复

// 以 Set 接口的实现类 HashSet 为例
// 1. set 接口的实现类的对象(Set接口对象), 不能存放重复的元素, 可以添加一个 null
// 2. set 接口对象存放数据是无序(即添加的顺序和取出的顺序不一致, 但取出顺序每次固定)
Set set = new HashSet();
set.add("john");
set.add("lucy");
set.add("john");  // 重复
set.add("jack");
set.add(null);  // 添加 null
set.add(null);  // 再次添加null

// 输出 set, 3 次输出的顺序都是固定的
for (int i = 0; i < 3; i++) {
    System.out.println("set = " + set);  // set = [null, john, lucy, jack]
}

JDK 中的 Set 接口实现类：
- HashSet：基于哈希表的 Set 实现，提供快速的查询速度，不保证顺序
- TreeSet：基于红黑树实现，元素会按照自然顺序或创建 TreeSet 时提供的比较器进行排序
- LinkedHashSet：类似于 HashSet，但维护了一个运行于所有条目的双重链接列表，保留了插入的顺序
- ….
常用方法：和 List 接口一样， Set 接口也是 Collection 的子接口，因此，常用方法和 Collection 接口一样

5.2 Set 接口的遍历方式

Set 集合的遍历方式与 Collection 接口的其他实现相同，因为 Set 是 Collection 接口的一个子接口

使用迭代器

// 方式1: 使用迭代器
Iterator iterator = set.iterator();
while (iterator.hasNext()) {  // 快捷键: itit
    Object obj = iterator.next();
    System.out.println("obj = " + obj);
}

增强 for 循环

1
2
3

for (Object o : set) {  // 快捷键: set.for
    System.out.println("o=" + o);
}

不能使用索引的方式来获取

补充：Java 8 及更高版本的流

在 Java 8 引入的流（Streams）API 是一种高效处理集合（如 List、Set 等）的方法，特别适用于对集合执行复杂的查询和转换操作。流 API 可以用来遍历、筛选、映射、归约以及更多其它操作 List 或任何其他类型的 Collection

简单遍历：

1	set.stream().forEach(System.out::println);

更复杂的操作举例 List：

List<String> items = List.of("apple", "banana", "avocado", "cherry", "date");

// 使用流过滤、转换并收集结果
List<String> result = items.stream()
    .filter(s -> s.startsWith("a"))  // 只选择以"a"开头的元素
    .map(String::toUpperCase)        // 将每个元素转换为大写
    .sorted()                        // 排序
    .collect(Collectors.toList());   // 收集为列表

System.out.println(result);  // 输出: [APPLE, AVOCADO]

5.3 Set 接口实现类-HashSet

基本介绍

实现 Set 接口：HashSet 是 Set 接口的一个实现，提供了集合的基本操作，如添加、删除元素以及查询等，同时确保集合中的元素不重复
底层使用 HashMap：
- HashSet 内部实际上使用了一个 HashMap 来存储其元素，每个插入 HashSet 的元素都作为 HashMap 的键存储，而其值则使用一个固定的对象（通常是一个预定义的私有静态的 final 对象
- 使用 HashMap 支持使得 HashSet 在添加元素、删除元素和包含元素检查等操作上非常高效，时间复杂度为 O(1)

1
2
3

public HashSet() {
    map = new HashMap<>();
}

允许一个 null 值：HashSet 允许包含一个 null 元素，因为底层的 HashMap 允许其中一个键为 null。这对于某些需要表示特定场景的空值非常有用
无序性：
- HashSet 不保证集合中元素的顺序，元素的存储取决于它们的哈希码
- 当元素被添加到 HashSet 中时，其位置是根据哈希码计算得到的，这意味着元素的遍历顺序可能与添加顺序不同
哈希冲突与重新哈希：当哈希表的负载因子达到一定程度（默认是 0.75）时，哈希表会进行扩容（通常扩容为原来的两倍），这个过程可能会改变现有元素的顺序
不允许重复元素：HashSet 不允许重复元素。当尝试添加一个已存在的元素时，添加操作将不会改变集合，也不会抛出异常

代码示例

HashSet set = new HashSet();

// 1. 在执行add方法后, 返回一个 boolean 值
// 2. 添加成功,返回 true, 否则返回 false
System.out.println(set.add("john"));  // T
System.out.println(set.add("lucy"));  // T
System.out.println(set.add("john"));  // F
System.out.println(set.add("jack"));  // T
System.out.println(set.add("Rose"));  // T

// 3. 可以通过 remove 指定删除哪个对象
set.remove("john");
System.out.println("set = " + set);  // 3个  set = [Rose, lucy, jack]

// 重新实例化 set, 将 set 指向新的 HashSet, 原来的 HashSet 实例将失去引用
// 原来的 HashSet 实例被垃圾收集器回收（前提是没有其他引用指向它）
set = new HashSet();
System.out.println("set = " + set);  // 0  set = []

// 4. Hashset 不能添加相同的元素/数据?
set.add("lucy");  // 添加成功
set.add("lucy");  // 加入不了
set.add(new Dog("tom"));  // OK
set.add(new Dog("tom"));  // Ok
System.out.println("set = " + set);  // set = [Dog{name='tom'}, Dog{name='tom'}, lucy]


// 看源码, 即 add 到底发生了什么? => 底层机制
set.add(new String("hhh"));  // ok
set.add(new String("hhh"));  // 加入不了  set = [Dog{name='tom'}, hhh, Dog{name='tom'}, lucy]
// String 类重写了 equals() 和 hashCode() 方法
// String 的 hashCode() 方法确保所有内容相同的字符串对象返回相同的哈希码
// 而 equals() 方法确保只有当两个字符串对象的内容完全相同时才返回 true
// HashSet 使用这些方法来检查是否已经存在相等的字符串, 因此这次添加操作不会改变 set 的内容
System.out.println("set = " + set);

模拟哈希表(数组+链表)

HashSet 的底层是 HashMap，HashMap的底层是数组+链表/红黑树

// 模拟一个 HashSet 的底层(其实也就是 HashMap 的底层结构)

// 1. 创建一个数组, 数组的类型是 Node[], 每个数组存放的元素可以理解为一个链表头
// 2. 有时也直接把 Node[] 数组称为 table 表
Node[] table = new Node[16];

// 3. 创建结点,实现:
// [2]: john => jack => rose
// [3]: lucy
Node john = new Node("john", null);
table[2] = john;

Node jack = new Node("jack", null);
john.next = jack;  // 将 jack 结点挂载到 john

Node rose = new Node("Rose", null);
jack.next = rose;  // 将 rose 结点挂载到 jack

Node lucy = new Node("lucy", null);
table[3] = lucy; // 把 lucy 放到 table 表的索引为 3 的位置

System.out.println("table=" + table);

底层机制

分析HashSet的添加元素底层是如何实现：hash() + equals()
- HashSet 底层使用 HashMap 存储所有元素，在 HashSet 中添加一个元素实际上是将该元素作为键添加到内部的 HashMap 中
- 添加一个元素时，会得到 hash 值 -> 索引值
- 处理哈希碰撞：找到存储数据表table，看这个索引位置是否已经存放了元素
  - 如果没有，直接将元素存储到该位置
  - 如果有，调用 equals() 方法比较
    - 如果 equals() 返回 true，就放弃添加
    - 如果 equals() 返回 false，则继续与链表中的下一个元素比较，直到找到相同的元素或链表结束
- 链表与树化：
  - 链表处理：如果一个索引位置上的冲突元素较多（但未达到树化阈值），则以链表形式存储
  - 在 Java 8 及更高版本中，如果某个索引位置的链表长度 >= TREEIFY_THRESHOLD（默认为8），并且整个 HashMap 的容量>= MIN_TREEIFY_CAPACITY（默认为64），则这个链表会转化为红黑树，以提高搜索效率
- 添加成功与否：
  - 如果在整个链表或红黑树中没有找到相同的元素，则将新元素添加到链表的末尾或红黑树中
  - HashSet 的 add() 方法返回一个 boolean 值，表示元素是否被添加。如果元素因为已存在而未被添加，则返回 false4
构造器：初始化一个 HashSet 实例时，内部实际上创建了一个 HashMap 来存储集合中的元素
- 默认负载因子：HashMap 默认的负载因子是 0.75，这意味着当 HashMap 的容量达到其容量的 75% 时，会自动扩容(重新调整内部数据结构的大小)

// HashSet.java 代码
// 构造器
public HashSet() {
    map = new HashMap<>();
}

// HashMap.java 代码
static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; 
}

HashSet的add 方法：HashSet 添加元素实际上是调用内部 HashMap 的 put 方法，将元素 e 作为键存入。所有键共享同一个值 PRESENT，这只是一个占位符，没有实际意义

// add 方法
private static final Object PRESENT = new Object();  // 方便让HashSet使用HashMap, 用一个Object作为 value 值进行占位
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

HashMap 的 put 方法：put 方法首先计算键的哈希值，然后调用 putVal 方法处理实际的插入逻辑

// HashMap.java 代码
// 倒数第二个参数对应 putVal 方法的 onlyIfAbsent 参数, 决定了如果 key 已存在，是否要替换旧的值, false 表示如果发现 key 已存在，将替换旧值
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

计算哈希值(不等价于hashCode)：通过将对象的 hashCode() 结果与其自身右移 16 位的结果进行异或操作，从而减少高位和低位的冲突，改进了哈希碰撞的问题：(h ^ (h >>> 16))
- 异或：异1同0，用于混合原始哈希码的高位和低位，增加哈希码的随机性和均匀性
- **无符号右移 (>>>)**：将数值的二进制位向右移动指定的位数，右边超出的部分被丢弃，左边空出的位用 0 填充，用来混合哈希码，避免高位的信息在计算索引时被忽略

// force step into 到 hash(key) 方法
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// String 类的 hashCode() 方法
private int hash; // 默认为 0
public int hashCode() {
    int h = hash;
    // 遍历字符串中的每个字符
    // 使用公式 h = 31 * h + val[i]; 计算哈希值
    if (h == 0 && value.length > 0) {
        char val[] = value;

        // 数字 31 被选择是因为它是一个奇质数，如果用更小的数字，容易造成哈希碰撞
        // 同时，计算 31*h 可以被 JVM 优化为 (h << 5) - h，这是一次位移和一次减法，比乘法更快
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

putVal 方法：
- 寻找插入位置：首先检查是否需要扩容。如果对应的桶（数组位置）是空的，则直接插入新节点
- 处理哈希碰撞：如果桶中已有元素，则通过链表或红黑树（当链表长度太长时转换为红黑树以优化搜索效率）处理碰撞
  - 代码：既提高了性能（通过快速的引用比较），又保证了准确性（通过内容比较）
    - 引用比较 (==) 是一种非常快速的操作，比调用任何方法都要快，因为它直接比较内存地址。如果两个引用指向同一个对象，那么它们肯定相等，不需要进一步使用 equals 方法比较
    - 即使两个对象的引用不同（它们位于内存中不同的位置），它们仍可能表示相同的数据。例如，两个不同的 String 对象可能包含相同的文本。通过 equals 方法，可以确保逻辑上相等的对象能够被正确识别
  1
  2
  3
  if (p.hash == hash &&
  ((k = p.key) == key || (key != null && key.equals(k))))
  e = p;
- 键的比较：使用 equals 方法检查键是否已存在。如果已存在，根据 onlyIfAbsent 参数决定是否更新值

transient Node<K,V>[] table;
transient int size;  // 默认为 0
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    // ...
}
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
    return new Node<>(hash, key, value, next);
}
void afterNodeInsertion(boolean evict) { }
void afterNodeAccess(Node<K,V> p) { }

// putVal()
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    // 1. 定义辅助变量
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 2. 检查哈希表是否为空或者尚未初始化
    // table 就是 HashMap 的一个数组, 类型是 Node[]
    if ((tab = table) == null || (n = tab.length) == 0)  // 如果为空，则进行初始化或扩容
        n = (tab = resize()).length;

    // 3. 计算插入v的位置并检查该位置是否已有元素存在
    // (1) 计算索引: i = (n - 1) & hash, 使用位与运算 & 来确定元素在表中的索引位置
    // (1.1) 因为 n 是 2 的幂，n - 1 的二进制表示将是一个全 1 的序列（例如，如果 n 是 16，n - 1 是 15，二进制是 1111）
    // (1.2) 意味着 (n - 1) & hash 将使用 hash 的低位作为数组索引。这是一个常用技巧，用于替代模运算（hash % n），因为位运算比模运算更高效
    // (2) 访问数组并赋值给 p: p = tab[i]
    // (3) 判断条件 (p == null)
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 3.1 如果没有节点，则直接插入新节点, value 对象是共享的
        tab[i] = newNode(hash, key, value, null);
    else {  // 3.2 如果该位置已经有节点存在，则处理哈希碰撞
        Node<K,V> e; K k;
        // 3.2.1 检查当前节点的哈希值和键是否与插入的键相同
        // (1) 先检查当前节点 p 的哈希值是否与待插入键 key 的哈希值相同
        // (2) 键的比较
        // (2.1) 首先，p.key 被赋值给变量 k
        // (2.2) 使用 == 操作符检查 k 和 key 是否为同一个对象的引用
        // (2.3) 如果 k 和 key 不是同一个引用，那么继续使用 equals 方法检查两者的内容是否相等, 有一个额外的空值检查 key != null, 避免抛出 NPE
        // (3) 条件成立，执行赋值 (e = p)
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;  // 如果节点已存在，将其赋给 e 用于后续操作
        
        // 3.2.2 如果当前节点是树节点，则调用树节点的插入方法
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        
        // 3.2.3 如果是链表，则遍历链表
        else {  
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    // 如果到达链表末尾，插入新节点
                    p.next = newNode(hash, key, value, null);
                    // 如果链表长度达到阈值，则尝试将当前链表转换为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1因为从0开始计数
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果在链表中找到了相同哈希且键相等的节点，则停止搜索
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;  // 如果找到相同的键，停止遍历
                p = e;  // 继续遍历链表
            }
        }
        // 3.2.4 如果找到了已存在的节点，根据参数决定是否更新其值
        if (e != null) { 
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 更新修改次数
    ++modCount;
    // 如果大小超过阈值，则进行扩容
    if (++size > threshold)
        resize();
    // 对于 ashMap 来说, 这个方法是个空方法
    afterNoeInsertion(evict);  // 钩子方法，用于 LinkedHashMap 后续处理
    // 钩子方法通常是在基类中预定义的方法，它们在默认情况下可能不做任何事（即可能是空方法），或者提供默认行为。派生类可以根据需要重写这些方法来提供特定的行为
    return null; 
}

resize 扩容方法：
- 初始化和条件检查：
  - 保存旧数组：首先，旧数组 oldTab 被保存，用于之后的元素迁移。
  - 检查旧容量：获取旧数组的长度 oldCap。如果数组未初始化（即为 null），oldCap 设为 0。
  - 旧阈值：保存旧的扩容阈值 oldThr。
- 判断是否需要扩容：
  - 达到最大容量：如果旧容量已经等于最大可能容量 MAXIMUM_CAPACITY（即 1 << 30），将阈值设置为 Integer.MAX_VALUE 并直接返回旧表，不再扩容。
  - 一般扩容条件：如果旧容量小于最大容量且大于默认初始容量，新容量 newCap 设为旧容量的两倍，新阈值 newThr 也相应翻倍。
- 处理特殊初始化条件：
  - 初次初始化：如果是首次初始化（即旧阈值大于 0 且旧容量为 0），直接使用旧阈值作为新容量。
  - 默认初始化：如果旧容量和旧阈值都是 0（未初始化状态），设置新容量为默认初始容量（16），计算新阈值为容量与默认负载因子（0.75）的乘积。
- 重新计算新阈值：
  - 阈值计算：如果新阈值未设定（即 newThr == 0），根据新容量和负载因子计算新阈值。如果计算结果接近最大容量，直接将阈值设置为 Integer.MAX_VALUE。
- 创建新数组并设置新表：
  - 新数组创建：基于新容量创建新的节点数组 newTab。
  - 更新哈希表：将 HashMap 的 table 引用更新为新数组。
- 重新散列旧元素：
  - 遍历旧数组：遍历每个索引位置的旧数组元素。
    - 单节点直接移动：如果该位置只有一个节点，直接计算新位置并放入新数组。
    - 处理树或链表：如果节点形成了链表或树：
      - 树节点分割：对于树节点，执行分割操作，将节点根据当前的容量分散到新的索引位置。
      - 链表重分布：对于链表，节点被分为两组，一组索引位置不变，另一组移动到 原索引 + oldCap 的位置。
        
        链表节点迁移：根据节点哈希值的高位决定分组。
- 返回新数组：返回新的哈希表数组 newTab，完成扩容和重新散列过程。

int threshold;  // 默认为 0
static final int MAXIMUM_CAPACITY = 1 << 30;  // 2^30
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;  // 默认容量 16 
static final float DEFAULT_LOAD_FACTOR = 0.75f;  // 默认负载因子

final Node<K,V>[] resize() {
    // 保存旧数组
    Node<K,V>[] oldTab = table;
    // 旧数组的容量
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;  // 旧阈值
    int newCap, newThr = 0;
    // 如果旧容量大于 0
    if (oldCap > 0) {
        // 如果旧容量已达到最大值
        if (oldCap >= MAXIMUM_CAPACITY) {
            // 更新阈值为 int 最大值，防止进一步扩容
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 如果旧容量小于最大容量，将容量翻倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 翻倍阈值
            newThr = oldThr << 1; // double threshold
    }
    
    // 如果旧容量为 0，但旧阈值大于 0，通常是初始情况
    else if (oldThr > 0) 
        newCap = oldThr;
    else {  // 使用默认容量和默认负载因子            
        newCap = DEFAULT_INITIAL_CAPACITY;
        // 默认阈值: 16*0.75=12
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 如果新阈值为 0, 重新计算新阈值
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;  // 更新阈值
    
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];  // 创建新数组
    table = newTab;  // 将新数组设为当前表
    // 重新散列旧数组中的所有元素到新数组
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                // 如果节点没有后续节点，直接重新定位
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 如果是树节点，执行树相关的分割
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // 重新链接扩展的节点
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 根据哈希的高位决定是放在原位置还是新位置
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                     // 重新链接低位链表和高位链表
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;  // 返回新的哈希表数组
                    }
                }
            }
        }
    }
    return newTab;
}

treeifyBin 转红黑树方法

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 如果表为空或表的长度小于最小树化容量，进行扩容
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    // 如果表不为空且长度大于等于最小树化容量
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;  // hd 用于保存头节点，tl 用于保存尾节点
        do {
            // 将普通节点转换为树节点
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;  // 如果尾节点为空，表示这是第一个节点，设置为头节点
            else {
                p.prev = tl;  // 设置当前节点的前一个节点为尾节点
                tl.next = p;  // 将尾节点的下一个节点设置为当前节点
            }
            tl = p;  // 更新尾节点为当前节点
        } while ((e = e.next) != null);  // 遍历链表中的所有节点
        // 如果头节点不为空，开始树化操作
        if ((tab[index] = hd) != null)
            hd.treeify(tab);  // 将链表转换为红黑树
    }
}

扩容机制的触发？
- 一种是总的键值对数量超过了负载因子与当前容量的乘积所定义的阈值
  - 初始设置：HashMap 默认的初始容量是 16 (DEFAULT_INITIAL_CAPACITY), 负载因子是 0.75 (DEFAULT_LOAD_FACTOR)。
  - 计算阈值：阈值 (threshold) 是触发扩容的点，计算为 容量 * 负载因子。初始情况下，阈值是 16 * 0.75 = 12。
  - 扩容条件：每次向 HashMap 添加元素后，如果哈希表中的元素数量超过当前阈值，就会触发扩容。扩容通常将容量翻倍（例如从 16 增加到 32，阈值相应地从 12 增加到 24）。
  - 扩容过程：在扩容过程中，旧数组中的元素会被重新计算索引并移动到新的数组中，这个过程称为重新散列（rehashing）。
- 另一种是单个哈希桶（链表或树）的结构因为太长而需要转换
  - 链表长度阈值：如果 HashMap 中某个桶的链表长度达到 TREEIFY_THRESHOLD（默认为 8），则可能触发树化。但树化之前还有一层检查，即桶数组的总容量是否足够大。
  - 最小树化容量：树化发生之前，桶数组的容量必须达到 MIN_TREEIFY_CAPACITY（默认为 64）。这意味着如果容量小于这个值，即使链表长度达到了 8，系统也会选择先扩容而不是树化。
  - 先扩容还是先树化：如果在链表长度达到 8 时容量已经达到或超过了 64，将直接进行树化；如果容量还不足 64，则会先进行扩容，容量通常翻倍，这有助于分散哈希碰撞并可能避免立即树化。

练习

当一个对象作为哈希基础集合（如 HashSet 或 HashMap）的元素时，不仅该对象本身需要适当重写 hashCode() 和 equals() 方法，其内部属性对象（如果这些属性对等价性判断有影响）同样需要重写这些方法
eg. 当一个对象（如 Emp）的等价性判断依赖于另一个对象（如 MyDate）时，后者也必须正确实现 hashCode() 和 equals() 方法。这是因为前者的方法实现直接依赖于后者的等价性逻辑

public class HashSetPractice01 {
    public static void main(String[] args) {

        HashSet hashSet = new HashSet();
        hashSet.add(new Emp("111", 3000.0, new MyDate(1,2,3)));
        hashSet.add(new Emp("111", 3000.0, new MyDate(1,2,3)));

        for (Object o : hashSet) {
            System.out.println(o);
        }
    }
}

class MyDate {
    private Integer year;
    private Integer month;
    private Integer day;

    public MyDate(Integer year, Integer month, Integer day) {
        this.year = year;
        this.month = month;
        this.day = day;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        MyDate myDate = (MyDate) o;
        return Objects.equals(year, myDate.year) && Objects.equals(month, myDate.month) && Objects.equals(day, myDate.day);
    }

    @Override
    public int hashCode() {
        return Objects.hash(year, month, day);
    }
}

class Emp {
    private String name;
    private Double sal;
    private MyDate birthday;

    public Emp(String name, Double sal, MyDate birthday) {
        this.name = name;
        this.sal = sal;
        this.birthday = birthday;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Emp emp = (Emp) o;
        return Objects.equals(name, emp.name) && Objects.equals(birthday, emp.birthday);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, birthday);
    }
}

5.4 Set 接口实现类-LinkedHashSet

基本介绍

继承关系：LinkedHashSet 是 HashSet 的子类

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
    // ...
}

底层由 LinkedHashMap 实现：LinkedHashSet 底层是一个 LinkedHashMap，内部结构包括一个哈希表（用于存储数据）和一个双向链表（用于维护插入顺序）
- 每个添加到 LinkedHashMap 中的元素都会被插入到双向链表的尾部
元素顺序：LinkedHashSet 根据元素 hashCode 来决定元素的存储位置，同时使用链表维护元素的次序，这使得元素看起来是以插入顺序保存的
不允许重复元素：同 HashSet，LinkedHashSet 也是基于集合的性质，不允许添加重复的元素。它使用 hashCode() 和 equals() 方法来检测重复

底层机制

数据结构：LinkedHashSet 内部实际上使用了 LinkedHashMap 来存储元素。LinkedHashMap 本质上是 HashMap 的一个子类，但它在每个节点中额外维护了两个指针，分别指向链表中的前一个和后一个节点

节点结构：
- 除了键值对信息外，每个节点还有 prev（前驱）和 next（后继）两个属性，用于链接前一个和后一个节点，形成一个双向链表
- 这个链表通过头指针 head 和尾指针 tail 维护，确保插入顺序
节点类型：
- 添加第一次时，直接将数组 table 扩容到 16 ,存放的结点类型是 LinkedHashMap$Entry
- 数组 table 是 HashMap$Node[] 存放的元素/数据是 LinkedHashMap$Entry 类型，(数组多态？)，
- LinkedHashMap.Entry 类继承了 HashMap.Node 类(静态内部类，因为是通过类名去访问的)，不仅存储键值对（即数据部分），还包括两个额外的指针：before, after，用于维护节点的插入顺序
1
2
3
4
5
6
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
添加元素：

这里其实都类似，就是功能增强，增加的双指针没有破坏原来的结构，感觉就是多了一个有序的功能
- 当添加一个新元素时，首先计算该元素的哈希值，然后根据哈希值计算其在哈希表中的索引
- 如果元素是首次添加（即在哈希表中找不到对应的条目），该元素将被封装为一个新的节点，并添加到双向链表的末尾（如果已经存在，不添加［原则和hashset一样］）
1
2
3
tail.next＝ newElement; // 简单指定
newElement.pre tail;
tail newEelment;
遍历顺序：由于元素是按照添加顺序连续链接的，遍历 LinkedHashSet 时，可以通过从 head 开始，沿着 next 指针顺序遍历，确保遍历顺序与插入顺序一致

6. Map

6.1 Map 接口和常用方法

JDK8 的 Map 接口实现类的特点

并列于 Collection：Map 接口是与 Collection 接口平行的一个独立接口。意味着 Map 和 Collection 处理的是不同类型的数据结构——Map 主要用于存储键值对，而 Collection 用于存储一组元素
键值对存储：Map 存储的是键值对，每个键映射到一个特定的值。key 和 value 可以是任何引用类型的数据，封装到HashMap$Node 对象中，HashMap$Node 是 HashMap 中实现键值对存储的内部类，它封装了键（Key）和值（Value）

编译器使用 $ 符号将外部类名和内部类名连接起来。例如，如果 HashMap 类中有一个名为 Node 的内部类，编译后的类名会是 HashMap$Node

static class Node<K,V> implements Map.Entry<K,V> {  // HashMap$Node 实现了 Map$Entry
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    // ...
}

键（Key）的特性：
- 唯一性：每个键在 Map 中必须是唯一的。如果尝试插入一个已存在的键，其对应的值将被新的值替换（除非操作特别指定不这么做）
- null 键：大多数 Map 实现（如 HashMap）允许有一个键为 null 的条目，这在使用时需要特别注意，因为不是所有的 Map 实现都支持 null 键（例如 TreeMap 默认不支持 null 键）
值（Value）的特性：Map 中的值可以重复，即不同的键可以映射到相同的值
使用场景：
- 字符串键：String 类型是作为 Map 的键非常常见的选择，主要是因为其不变性和已经有效重写的 hashCode() 和 equals() 方法，这使得 String 作为键既安全又高效
- 单向关联：每个键与一个值之间存在单向的一对一关系，通过键总能检索到一个确定的值，这是 Map 结构的核心特征
EntrySet、KeySet 和 ValueCollection：
- Map 中一对 k-v 最后是 HashMap$Node node = newNode(hash, key, value, null)，又因为Node 实现了 Entry 接口，有些书上也说一对 k-v 就是一个 Entry
- 为了方便 k-v 遍历，还会创建 EntrySet 集合
1
2
// HashMap
transient Set<Map.Entry<K,V>> entrySet;
- EntrySet：
  - EntrySet 是 HashMap 的一个视图，用于以 Map.Entry 对象的形式访问 HashMap 中的每一个键值对。每个 Map.Entry 实际上是 HashMap 内部节点 Node 的表示，它包含键和值的引用（地址）
  - 遍历 EntrySet 时，实际上是在访问 HashMap 内部存储的每个节点，每个节点都是 Map.Entry 实例，它包含了键值对的信息
- KeySet：
  - KeySet 也是 HashMap 的一个视图，它包含 HashMap 中所有的键。它是从 EntrySet 派生出来的，每个元素都是从 EntrySet 中的每个 Entry（即 Node）中提取的键
  - 遍历 KeySet 或对其进行操作时，实际上是在间接操作那些存储在 Node 中的键
- ValueCollection：
  - 类似地，ValueCollection 是 HashMap 中所有值的集合。它也是从 EntrySet 派生的，每个元素都是从 EntrySet 中的 Entry（即 Node）中提取的值
  - ValueCollection 允许你遍历或查看所有值，但是和键不同，值是可以重复的

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class MapExample {
    public static void main(String[] args) {
        // 创建一个HashMap
        HashMap<String, Integer> map = new HashMap<>();

        // 向HashMap中添加一些键值对
        map.put("apple", 10);
        map.put("banana", 20);
        map.put("orange", 30);

        // 使用entrySet()获取Map中的所有键值对
        Set<Map.Entry<String, Integer>> entries = map.entrySet();

        // 遍历entries集合
        for (Map.Entry<String, Integer> entry : entries) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }
    }
}

常用方法：

public static void main(String[] args) {
    Map map = new HashMap();
    map.put("11", new Book("", 100));  // OK
    map.put("11", "22");  // 替换-> 一会分析源码
    map.put("33", "44");  // OK
    map.put("55", "44");  // OK
    map.put("66", null);  // OK
    map.put(null, "77");  // OK
    map.put("88", "99");  // OK
    map.put("hh", "ee");

    System.out.println("map = " + map);
    // map = {11=22, 33=44, 55=44, 66=null, null=77, 88=99, hh=ee}

    // remove: 根据键删除映射关系
    map.remove(null);
    System.out.println("map = " + map);
    // map = {11=22, 33=44, 55=44, 66=null, 88=99, hh=ee}

    // get: 根据键获取值
    Object val = map.get("88");
    System.out.println("val = " + val);  // val = 99

    // size: 获取元素个数
    System.out.println("k-v = " + map.size());  // k-v = 6

    // isEmpty: 判断个数是否为 0
    System.out.println(map.isEmpty());  // false

    // clear: 清除k-v
    // map.clear();
    // System.out.println("map = " + map);  // map = {}

    // containsKey: 查找键是否存在
    System.out.println("result = " + map.containsKey("hh"));  // result = true
}

6.2 Map 六大遍历方式

entrySet：获取所有的关系K-V

KeySet：获取所有的键

values：获取所有的值

通过 keySet() 遍历键并获取对应的值
- 增强 for 循环：直接遍历键集合，然后使用 map.get(key) 来获取每个键对应的值
- 迭代器：使用迭代器来遍历键集合，同样使用 map.get(key) 获取值
通过 values() 遍历所有值：这种方法只关注值，不涉及键
- 增强 for 循环：直接遍历值集合
- 迭代器：使用迭代器遍历值集合
通过 entrySet() 直接遍历键值对：
- 增强 for 循环：遍历 Entry 集合，可以直接使用 Map.Entry 接口的 getKey() 和 getValue() 方法访问键和值
- 迭代器：使用迭代器遍历 Entry 集合，对于每个迭代出的对象，同样使用 Map.Entry 的方法来获取键和值

// 第一组: 先取出 所有的 Key, 通过 Key 取出对应的 Value
Set keySet = map.keySet();
// (1) 增强 for
System.out.println("-----第一种方式-------");
for (Object key : keySet) {
    System.out.println(key + "-" + map.get(key));
}
// (2) 迭代器
System.out.println("----第二种方式--------");
Iterator iterator = keySet.iterator();
while (iterator.hasNext()) {
    Object key =  iterator.next();
    System.out.println(key + "-" + map.get(key));
}

// 第二组: 把所有的 values 取出
Collection values = map.values();
// 这里可以使用所有的 Collections 使用的遍历方法
// (1) 增强 for
System.out.println("---取出所有的value 增强for----");
for (Object value : values) {
    System.out.println(value);
}
// (2) 迭代器
System.out.println("---取出所有的value 迭代器----");
Iterator iterator2 = values.iterator();
while (iterator2.hasNext()) {
    Object value =  iterator2.next();
    System.out.println(value);
}

// 第三组: 通过 EntrySet 来获取 k-v
Set entrySet = map.entrySet();  // EntrySet<Map.Entry<K,V>>
// (1) 增强 for
System.out.println("----使用 EntrySet 的 for 增强----");
for (Object entry : entrySet) {
    // 将 entry 转成 Map.Entry
    Map.Entry m = (Map.Entry) entry;
    System.out.println(m.getKey() + "-" + m.getValue());
}
// (2) 迭代器
System.out.println("----使用 EntrySet 的 迭代器----");
Iterator iterator3 = entrySet.iterator();
while (iterator3.hasNext()) {
    Object entry =  iterator3.next();
    // System.out.println(next.getClass());  // HashMap$Node -实现-> Map.Entry (getKey,getValue), 后者提供了获取 k-v 的方法
    // 向下转型 Map.Entry
    Map.Entry m = (Map.Entry) entry;
    System.out.println(m.getKey() + "-" + m.getValue());
}

使用 forEach() 方法（Java 8+）：使用 forEach() 方法和 Lambda 表达式来遍历 Map

1
2
3

map.forEach((key, value) -> {
    // 处理键和值
});

注意：
- 在遍历集合时尝试修改集合的结构（添加或删除元素）通常是不安全的，除非通过迭代器的 remove() 方法删除元素
- 修改集合中元素的内部状态（不是集合结构）通常是安全的，如更改对象的属性
- 增加对集合的任何操作，特别是在遍历过程中，都应该非常小心处理以避免运行时错误

// 练习
Map<Integer, Emp> hashMap = new HashMap<>();

hashMap.put(1, new Emp(1, "h", 1.0));
hashMap.put(2, new Emp(2, "hh", 2.0));
hashMap.put(3, new Emp(3, "hhh", 3.0));

// 增强 for keySet
System.out.println("======使用增强for======");
Set<Integer> integers = hashMap.keySet();
for (Integer integer : integers) {
    if (hashMap.get(integer).getSal() > 1) {
        System.out.println(hashMap.get(integer));
    }
}

// 迭代器 keySet
System.out.println("=====使用迭代器=====");
Iterator<Integer> iteratorKey = integers.iterator();
while (iteratorKey.hasNext()) {
    Integer key = iteratorKey.next();
    if (hashMap.get(key).getSal() > 1) {
        System.out.println(hashMap.get(key));
    }
}

// 增强 for entrySet
System.out.println("=====使用增强for=====");
Set<Map.Entry<Integer, Emp>> entries = hashMap.entrySet();
for (Map.Entry<Integer, Emp> entry : entries) {
    if (entry.getValue().getSal() > 1) {
        System.out.println(entry.getValue());
    }
}

// 迭代器 entrySet
System.out.println("=====使用迭代器=====");
Iterator<Map.Entry<Integer, Emp>> iterator = entries.iterator();
while (iterator.hasNext()) {
    Map.Entry<Integer, Emp> entry = iterator.next();
    if (entry.getValue().getSal() > 1) {
        System.out.println(entry.getValue());
    }
}

6.3 Map 接口实现类-HashMap

基本介绍

HashMap 是 Map 接口使用频率最高的实现类
线程不安全：HashMap 没有实现同步

底层机制和源码

初始化和负载因子：
- 默认构造函数：在实例化 HashMap 时，内部数组 table 是 null。直到第一次插入元素时，才进行实际的内存分配
- 负载因子：负载因子 loadFactor 默认为 0.75，这是空间和时间成本的折中选择。负载因子决定了 HashMap 扩容的时间点

1
2
3

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; 
}

内部数组和节点：HashMap 使用 Node 类型的数组 table 来存储键值对。Node 是 HashMap 的一个内部静态类，每个 Node 对象包含一个键、一个值、一个哈希值和指向下一个节点的引用（链表结构）
添加元素的处理：
- 索引计算：通过键的哈希值经过处理后确定在数组 table 中的索引位置
- 无冲突时：如果计算得到的索引位置上没有元素，则直接添加
- 有冲突时：如果位置上已有元素（链表头），则使用链地址法解决冲突：
  - 遍历链表，检查是否有相同的键：
    - 如果找到相同的键，则替换其值
    - 如果未找到相同的键，根据链表的长度决定是添加到链表末尾还是树化

扩容与树化：

扩容：当 HashMap 的大小超过 threshold（容量 * 负载因子）时，进行扩容，通常是当前容量的两倍。在扩容时，元素需要重新计算索引并分配到新的数组中

第一次添加，则需要扩容table容量为16，临界值（threshold）为12（16*0.75）

final Node<K,V>[] resize() {
    // ...
    else { 
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // ...
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    // ...
}

以后再扩容，则需要扩容table容量为原来的的2倍（32），临界值为原来的2倍，即24，以此类推；

if (oldCap > 0) {
    if (oldCap >= MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return oldTab;
    }
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
             oldCap >= DEFAULT_INITIAL_CAPACITY)
        newThr = oldThr << 1; 
}

树化：在 Java 8 中，如果某个索引位置上的链表长度 >= TREEIFY_THRESHOLD（默认为 8），并且数组大小 >= MIN_TREEIFY_CAPACITY（默认为 64），则链表转换为红黑树，以改善查找效率

6.4 Map 接口实现类-Hashtable

基本介绍

键值对存储：Hashtable 是 Java 早期的一部分，用于存储键值对（K-V），每个键映射到一个特定的值。
空值限制：在 Hashtable 中，键（Key）和值（Value）都不能为 null，尝试使用 null 作为键或值都会抛出 NullPointerException
线程安全：Hashtable 的每个方法几乎都是用 synchronized 关键字同步的，因此它是线程安全的，但这也导致了性能上的开销，其他使用方法基本上和 HashMap 一样

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {
    // ...
}

逐渐被 ConcurrentHashMap 替代：
- 尽管 Hashtable 是线程安全的，但它的一个主要缺点是它锁定整个集合来同步不同的方法调用，这可能导致严重的性能瓶颈
- 现代的替代品，如 ConcurrentHashMap，提供了更高的并发性能，因为它使用分段锁

扩容机制

初始容量和负载因子：Hashtable 默认的初始容量是 11，而负载因子是 0.75。这意味着当 Hashtable 中的条目数量达到容量和负载因子乘积的结果时（大约是 8），Hashtable 会进行扩容

public Hashtable() {
    // 默认构造函数创建一个初始容量为 11 和负载因子为 0.75 的 Hashtable
    this(11, 0.75f);
}

public Hashtable(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal Load: "+loadFactor);

    if (initialCapacity==0)
        initialCapacity = 1;
    this.loadFactor = loadFactor;
    table = new Entry<?,?>[initialCapacity];
    // 计算触发扩容的阈值，是初始容量与负载因子的乘积，但不超过 MAX_ARRAY_SIZE + 1
    threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}

// Hashtable 中的节点，存储每个键值对
private static class Entry<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Entry<K,V> next;
    // ...
}

put 方法：
- 使用 synchronized 关键字声明，确保在多线程环境中的线程安全
- 检查传入的 value 是否为 null，因为 Hashtable 不允许存储 null 值。如果 value 为 null，抛出 NPE
- 使用键的 hashCode() 方法计算哈希值，并通过与数组长度的取模操作得到数组索引
- 如果在链表中没有找到相同的键，调用 addEntry 方法将新的键值对添加到链表的头部

public synchronized V put(K key, V value) {
    // 确保值不为 null，Hashtable 不允许 null 值
    if (value == null) {
        throw new NullPointerException();
    }

    // 获取哈希表的引用
    Entry<?,?> tab[] = table;
    // 计算键的哈希值
    int hash = key.hashCode();
    // 计算哈希值对应的索引，使用掩码 0x7FFFFFFF 确保索引为正数
    int index = (hash & 0x7FFFFFFF) % tab.length;
    // 获取对应索引处的链表头节点
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    // 遍历链表，查找是否存在相同的键
    for (; entry != null; entry = entry.next) {
        if ((entry.hash == hash) && entry.key.equals(key)) {
            // 如果找到相同的键，则更新其值
            V old = entry.value;
            entry.value = value;
            // 返回旧值
            return old;
        }
    }

    // 如果没有找到相同的键，添加新的键值对
    addEntry(hash, key, value, index);
    return null;  // 插入新键值对时返回 null
}

扩容过程：HashTable 用的头插，HashMap 用的尾插
- 添加新键值对（addEntry() 方法）
  - 如果 Hashtable 中的元素数量达到了阈值（threshold），则触发 rehash() 方法进行扩容
  - 扩容完成后，重新计算当前新元素键的哈希索引，以确定它在新表中的位置
  - 在确定的索引位置，使用链表的头插法将新元素插入
- 执行扩容操作（rehash() 方法）
  - 计算新容量
  - 根据新的容量创建一个新的 Entry 数组并重新哈希旧元素，更新 threshold 为新容量与负载因子的乘积

// addEntry()
private void addEntry(int hash, K key, V value, int index) {
    modCount++;  // 增加修改次数，用于迭代器快速失败行为

    Entry<?,?> tab[] = table;  // 获取当前哈希表的引用
    if (count >= threshold) {  // 检查当前元素数量是否达到阈值
        rehash();  // 执行扩容和重新哈希

        tab = table;  // 重新获取扩容后的哈希表引用
        hash = key.hashCode();  // 重新计算键的哈希值，因为数组大小已改变
        index = (hash & 0x7FFFFFFF) % tab.length;  // 根据新的哈希表大小重新计算索引
    }

    @SuppressWarnings("unchecked")
    Entry<K,V> e = (Entry<K,V>) tab[index];  // 获取当前索引位置的头节点
    tab[index] = new Entry<>(hash, key, value, e);  // 创建新节点并将其插入链表头部（头插法）
    count++;  // 增加Hashtable的元素计数
}

// rehash()
protected void rehash() {
    int oldCapacity = table.length;
    Entry<?,?>[] oldMap = table;

    // 新容量是旧容量的两倍加一
    int newCapacity = (oldCapacity << 1) + 1;
    // 如果新容量超过了 MAX_ARRAY_SIZE
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        // 检查旧容量是否已是最大
        if (oldCapacity == MAX_ARRAY_SIZE)
            return;
        // 不是则调整为最大容量
        newCapacity = MAX_ARRAY_SIZE;
    }
    // 创建新的 Entry 数组以容纳更多元素
    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

    modCount++;
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    table = newMap;

    // 遍历旧数组，将每个元素重新哈希到新数组
    for (int i = oldCapacity ; i-- > 0 ;) {
        for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
            Entry<K,V> e = old;
            old = old.next;

            // 使用元素的哈希值和新容量计算新索引
            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            // 将元素重新链接到新数组的相应位置
            e.next = (Entry<K,V>)newMap[index];
            newMap[index] = e;
        }
    }
}

6.5 Map 接口实现类-Properties

基本介绍

继承和实现：Properties 类继承自 Hashtable。因此，它本质上是一个 Hashtable，键和值不允许为 null

public class Properties extends Hashtable<Object,Object> {
	protected Properties defaults;
    public Properties() {
        this(null);
    }
    public Properties(Properties defaults) {
        this.defaults = defaults;
    }
    // ...
}

用途：Properties 主要用于管理配置数据，这些数据存储在键值对形式的属性文件（.properties 文件）中
文件操作：Properties 提供了方便的方法来从文件加载数据 (load()) 和向文件写入数据 (store())，使其非常适合读取和存储配置文件
功能特点：
- 加载和存储：
  - 加载（load() 方法）：可以从一个输入流（如文件输入流）中读取属性列表（键和元素对）。支持从 XML 和普通属性文件格式加载
  - 存储（store() 方法）：可以将 Properties 对象中的数据写入到输出流，同样支持 XML 和普通属性文件格式
- 与系统属性的交互：
  - Properties 类可以与系统属性直接交互，使用 System.getProperties() 获取当前系统属性
- 默认值机制：
  - Properties 可以指定一个包含默认值的 Properties 对象。如果主 Properties 对象中没有找到相应的键，那么将会搜索这个默认值 Properties

基本使用

public static void main(String[] args) {
    // 解读
    // 1. Properties 继承  Hashtable
    // 2. 可以通过 k-v 存放数据, key 和 value 不能为 null
    Properties properties = new Properties();
    // 增加
    // properties.put(null, "abc");  // 抛出 空指针异常
    // properties.put("abc", null);  // 抛出 空指针异常
    properties.put("john", 100);  // k-v
    properties.put("lucy", 100);
    properties.put("lic", 100);
    properties.put("lic", 88);  // 如果有相同的 key, value被替换

    System.out.println("properties=" + properties);
    // properties={john=100, lic=88, lucy=100}

    // 查找, 通过 key 获取对应值
    // get(Object key) 方法来自 Hashtable 类，它返回与指定键关联的值
    // 这个方法会返回任何类型的对象
    System.out.println(properties.get("lic"));  // 88

    // getProperty(String key) 方法是 Properties 类特有的，它只返回字符串类型的值
    // 如果值不是字符串，getProperty 方法将返回 null
    System.out.println(properties.getProperty("lic"));  // null

    // 删除
    properties.remove("lic");
    System.out.println("properties = " + properties);  // properties = {john=100, lucy=100}

    // 修改
    properties.put("john", "约翰");
    System.out.println("properties = " + properties);  // properties = {john=约翰, lucy=100}
}

使用 Properties 类加载和存储属性文件的示例：

config.properties 示例：

username=admin
password=secret
database=localhost
port=3306

代码示例：

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

public class PropertiesExample {
    public static void main(String[] args) throws Exception {
        Properties props = new Properties();

        // 加载属性文件
        FileInputStream in = new FileInputStream("config.properties");
        props.load(in);
        in.close();

        // 获取属性
        String username = props.getProperty("username");
        System.out.println("Username: " + username);

        // 修改/添加属性
        props.setProperty("username", "newUsername");

        // 存储修改后的属性文件
        FileOutputStream out = new FileOutputStream("config.properties");
        props.store(out, "Updated username");
        out.close();
    }
}

7. TreeSet 和 TreeMap 源码分析

7.1 TreeSet 分析

TreeSet 是基于 TreeMap 实现的，它利用 TreeMap 来保持元素的有序性和唯一性。TreeMap 本质上是一个红黑树实现的排序映射表，TreeMap 有一个属性是 comparator

// TreeMap.java
private final Comparator<? super K> comparator;
public TreeMap() {
    comparator = null;
}
public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

TreeSet 实现了 Set 接口，与 HashSet 最大的区别是可以排序

TreeSet 继承自 AbstractSet，后者提供了 Set 接口的骨架实现；TreeSet 实现了 NavigableSet 接口，该接口扩展了 SortedSet 并提供导航方法

构造函数：
- 无参构造器：使用无参构造器创建 TreeSet 时，默认情况下是基于自然排序的，需要存储在 TreeSet 中的元素实现 Comparable 接口
自然排序指的是基于元素自身的特性进行排序，而不需要外部指定排序规则

对于整数，自然排序就是按照数字大小进行排序；对于字符串，自然排序是按照字典顺序进行排序

对于字符串，String 类实现了 Comparable 接口，因此它支持自然排序。String 类的 compareTo 方法会按照字典顺序比较字符串的大小
- 带比较器构造器：如果提供了一个比较器(传入了匿名内部类并指定排序规则)，TreeSet 会使用这个比较器来创建一个 TreeMap，允许对元素进行自定义排序

// TreeSet.java
public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable {
    // TreeSet 的内部使用了一个 NavigableMap 来存储其元素, 元素作为键存储在此 Map 中
    private transient NavigableMap<E,Object> m;
    // 用于与 TreeSet 中的每个元素（作为键）关联, 方便利用 TreeMap 来实现 TreeSet
    private static final Object PRESENT = new Object();

    // 无参数构造器, 内部会创建一个基于自然排序的 TreeMap
    // 意味着元素需要具有可比性, 即元素类型 E 必须实现 Comparable 接口
    public TreeSet() {
        this(new TreeMap<E,Object>());
    }

    // 允许用户提供一个自定义的比较器 Comparator 用于元素的排序
    public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator));
    }

    // ...
}

// Comparator 接口
public interface Comparator<T> {
    // ...
}

代码示例：

// TreeSet treeSet = new TreeSet();
// 创建一个 TreeSet 实例，提供自定义的 Comparator 比较器
TreeSet treeSet = new TreeSet(new Comparator() {
    @Override
    public int compare(Object o1, Object o2) {
        // 调用 String 的 compareTo 方法进行字符串大小比较，若字符串内容完全相同，则不再添加
        // o2 - o1 是从大到小, 此处若想从小到大可直接利用 String 的自然排序(无参构造即可)
        // 从大到小也有使用有参构造的更加方便的写法: new TreeSet<>(Comparator.reverseOrder());
        // return ((String) o2).compareTo((String) o1);  // treeSet=[tom, sp, jack, abc, a]

        // 将对象 o1 和 o2 强制类型转换为 String，然后按照它们的长度进行比较，从而实现自定义排序
        // 如果 o1 的长度小于 o2 的长度，返回负数；如果长度相等，返回 0；如果 o1 的长度大于 o2 的长度，返回正数
        // 返回 0 时，TreeSet 认为这两个元素相等，因此不会添加重复长度的元素
        // 此处 o1 - o2 为从短到长排序
        return ((String) o1).length() - ((String) o2).length();  // treeSet=[a, sp, tom, jack]
    }
});

// 可以用 lambda 表达式简写为:
// TreeSet treeSet = new TreeSet(Comparator.comparingInt(o -> ((String) o).length()));

// 添加数据
treeSet.add("jack");
treeSet.add("tom");  // 3
treeSet.add("sp");
treeSet.add("a");
treeSet.add("abc");  // 3

System.out.println("treeSet=" + treeSet);

String 类的 compareTo 方法：

public final class String
    implements java.io.Serializable, Comparable<String>, CharSequence {
    // ...
    public int compareTo(String anotherString) {
        // 获取字符串的长度
        int len1 = value.length;
        int len2 = anotherString.value.length;

        // 计算两个字符串中长度较小的值
        int lim = Math.min(len1, len2);

        // 获取字符串的字符数组
        char v1[] = value;
        char v2[] = anotherString.value;

        int k = 0;
        // 循环比较两个字符串的每个字符，直到其中一个字符串结束
        while (k < lim) {
            char c1 = v1[k];
            char c2 = v2[k];
            if (c1 != c2) {
                // 返回两个字符的差值，如果 c1 < c2，结果为负，反之为正
                return c1 - c2;
            }
            k++;
        }
        // 如果所有比较的字符都相同，则比较字符串长度，返回长度差, 意味着较短的字符串被视为较小
        return len1 - len2;
    }
}

带比较器构造器调用过程：
- 构造器把传入的比较器对象，赋给了 TreeSet 底层的 TreeMap 的属性 this.comparator

// TreeSet.java
public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}
// TreeMap.java
private final Comparator<? super K> comparator;
public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

// TreeSet.java 的 add 方法
// NavigableMap 接口继承了 SortedMap 接口, 后者又继承自 Map 接口, 这里 NavigableMap 实际使用的是 TreeMap 实例
// 使用接口类型声明一个变量时, 可以将任何实现了该接口的类的实例赋值给这个变量, 变量在编译时表现为接口类型，在运行时表现为实际对象的类型
private transient NavigableMap<E,Object> m;
public boolean add(E e) {
    return m.put(e, PRESENT)==null;
}

// TreeMap.java 里的 put 方法
//  内部使用红黑树的数据结构来存储键值对
// 插入、删除和查找操作的最坏情况时间复杂度为 O(log n)
public V put(K key, V value) {
    Entry<K,V> t = root;  // 从根节点开始
    if (t == null) {  // 如果树为空
        // 用于确保在没有提供 Comparator 的情况下，键 key 是可比较的
        compare(key, key);  // 验证 key 是否可比较
        // 第一次添加,把 k-v 封装到 Entry 对象放入root
        root = new Entry<>(key, value, null);  // 创建新的根节点
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    // 获取比较器
    Comparator<? super K> cpr = comparator;  
    if (cpr != null) {  // 如果使用自定义比较器
        do {
            parent = t;
            // 使用比较器比较键, 动态绑定到匿名内部类的 compare 方法
            cmp = cpr.compare(key, t.key); 
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    else {
        // 没有比较器，键必须是可比较的
        if (key == null)  // 键不能为 null
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            // 使用键的自然顺序比较
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    // 创建新节点
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;  // 添加为左子节点
    else
        parent.right = e;  // 添加为右子节点
    fixAfterInsertion(e);  // 调整树以保持平衡
    size++;
    modCount++;
    return null;
}

// 检查是否有自定义的比较器 (Comparator) 提供
// 如果 没有提供比较器 (comparator==null)，那么假设 k1 必须实现 Comparable 接口。它尝试将 k1 强制类型转换为 Comparable，然后使用 compareTo 方法比较 k1 和 k2
// 如果 k1 没有实现 Comparable 接口，这个类型转换会失败，抛出 ClassCastException
final int compare(Object k1, Object k2) {
    return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
        : comparator.compare((K)k1, (K)k2);
}

7.2 TreeMap 分析

TreeMap 是一个基于红黑树的有序映射，支持按照键的自然顺序或者根据指定的 Comparator 进行排序
插入元素的逻辑：
- 首先检查根节点是否为空，如果是，则简单地将新元素设置为根节点（第一次添加，把 k-v 封装到 Entry 对象，放入root）
- 如果根节点不为空，则使用比较器（如果存在）或键的自然顺序来找到适当的插入位置
  - 涉及在树中逐级向下搜索正确的插入点，直到找到空位置插入新节点
  - 如果找到相同键的节点，则更新该节点的值
- 插入新节点后，可能需要进行红黑树的调整操作以保持树的平衡
代码示例：

TreeMap treeMap = new TreeMap(new Comparator() {
    @Override
    public int compare(Object o1, Object o2) {
        //按照 K(String) 的长度大小排序
        return ((String) o2).length() - ((String) o1).length();
    }
});
treeMap.put("jack", "杰克");
treeMap.put("tom", "汤姆");
treeMap.put("kristina", "克瑞斯提诺");
treeMap.put("smith", "斯密斯");
treeMap.put("hhh", "hhh");  // 加入不了, 并且会覆盖前面 tom 键所对应的值

System.out.println("treemap=" + treeMap);
// treemap={kristina=克瑞斯提诺, smith=斯密斯, jack=杰克, tom=hhh}

8. 集合选型规则

开发中如何选择集合实现类？

主要取决于业务操作特点，然后根据集合实现类特性进行选择

判断存储的类型

一组对象[单列]（使用 Collection 接口）
- 允许重复：
  - List 接口：
    - ArrayList：适用于查找和修改操作频繁的场景（底层维护 Object 类型的可变数组）
    - LinkedList：适合于增加和删除操作频繁的场景（底层维护一个双向链表）
- 不允许重复：
  
  以下的无序指存取的顺序不一致，但是取出的顺序是固定一致的
  - Set 接口：
    - HashSet：最常用的集合，提供快速访问，保持元素唯一，但元素是无序的。内部通过哈希表实现，包括数组、链表和红黑树（Java 8 及以上）
    - TreeSet：当需要一个有序集合时选择，它根据元素的自然顺序或构造器提供的 Comparator 进行排序
    - LinkedHashSet：维护元素插入顺序，性能略低于 HashSet，但迭代访问所有元素时有更高的性能（维护哈希表+双向链表）
      - LinkedHashSet 底层是 LinkedHashMap；LinkedHashMap 的底层是 HashMap
一组键值对[双列]（使用 Map 接口）
- HashMap：是最常用的 Map 实现，键无序，按键的哈希码存储数据（底层数组+链表/红黑树）
- TreeMap：基于红黑树的 Map 实现，它根据键的自然排序或构造器提供的 Comparator 对键进行排序。适用于需要按自然顺序或特定顺序遍历键时
- LinkedHashMap：保持插入顺序，通常比 HashMap 慢一点，但在迭代访问时更快
特殊用途
- Properties：用于读取 .properties 文件，适用于配置数据的加载和存储。它是 Hashtable 的一个子类，其中键和值都是字符串

9. Collections 工具类

9.1 基本介绍

Collections 是 Java 中的一个工具类，专门用于操作集合，如 Set、List 和 Map 等
该类提供了多种静态方法，用于执行集合上的操作，如排序、查询、修改等

9.2 主要方法

static操作

// 创建ArrayList 集合, 用于测试
List list = new ArrayList();
list.add("tom");
list.add("smith");
list.add("king");
list.add("milan");
list.add("tom");

排序和调整：
- reverse(List): 反转 List 中元素的顺序。
- shuffle(List): 对 List 集合元素进行随机排序。
- sort(List): 根据元素的自然顺序对指定 List 集合元素按升序排序。
- sort(List, Comparator): 根据指定的 Comparator 定制的顺序对 List 集合元素进行排序。
- swap(List, int, int): 将指定 List 集合中的 i 处元素和 j 处元素进行交换。

// reverse(List): 反转 List 中元素的顺序
Collections.reverse(list);
System.out.println("list = " + list);  // list = [tom, milan, king, smith, tom]

// shuffle(List): 对 List 集合元素进行随机排序
// for (int i = 0; i < 5; i++) {
//     Collections.shuffle(list);
//     System.out.println("list = " + list);
// }

// sort(List): 根据元素的自然顺序对指定 List 集合元素按升序排序
Collections.sort(list);
System.out.println("=======自然排序后=========");
System.out.println("list = " + list);  // list = [king, milan, smith, tom, tom]

// sort(List，Comparator): 根据指定的 Comparator 产生的顺序对 List 集合元素进行排序
// 如: 按照字符串的长度大小排序, 传递匿名内部类
Collections.sort(list, new Comparator() {
    @Override
    public int compare(Object o1, Object o2) {
        // 严谨些需要加入校验代码, 避免转型异常
        // 确保两个对象都是字符串类型
        // if (o1 instanceof String && o2 instanceof String) {
        //     // 正确的情况下，比较它们的长度
        //     return ((String) o2).length() - ((String) o1).length();  // 从长到短
        // } else {
        //     // 如果任一对象不是字符串，可以选择抛出异常或返回0
        //     // 抛出异常
        //     throw new IllegalArgumentException("Both objects must be strings");
        //     // 或者可以选择处理为相等，取决具体的业务逻辑
        //     // return 0;
        // }
        return ((String) o2).length() - ((String) o1).length();  // 从长到短
    }
});
System.out.println("=======字符串长度大小排序后=========");
System.out.println("list = " + list);  // list = [milan, smith, king, tom, tom]

// swap(List，int， int): 将指定 list 集合中的 i 处元素和 j 处元素进行交换
Collections.swap(list, 0, 1);
System.out.println("=======交换后的情况=========");
System.out.println("list = " + list);  // list = [smith, milan, king, tom, tom]

查找和统计：
- max(Collection): 根据元素的自然顺序，返回给定集合中的最大元素。
- max(Collection, Comparator): 根据 Comparator 指定的顺序，返回给定集合中的最大元素。
- min(Collection): 返回集合中的最小元素，根据自然排序。
- min(Collection, Comparator): 根据指定的比较器返回集合中的最小元素。
- frequency(Collection, Object): 返回指定集合中指定元素的出现次数。

// Object max(Collection): 根据元素的自然顺序，返回给定集合中的最大元素
System.out.println("自然顺序最大元素 = " + Collections.max(list));  // 自然顺序最大元素 = tom

// Object max(Collection，Comparator): 根据 Comparator 指定的顺序, 返回给定集合中的最大元素
// 比如: 返回长度最大的元素
Object maxObject = Collections.max(list, new Comparator() {
    @Override
    public int compare(Object o1, Object o2) {
        // 从短到长 ==> 返回长度最大
        return ((String) o1).length() - ((String) o2).length();

        // 从长到短 ==> 返回长度最小
        // return ((String) o2).length() - ((String) o1).length();
    }
});
System.out.println("长度最大的元素 = " + maxObject);  // 长度最大的元素 = smith

// 下面两个方法参考 max 即可
// Object min(Collection)
// Object min(Collection，Comparator)

// int frequency(Collection，Object): 返回指定集合中指定元素的出现次数
System.out.println("tom 出现的次数 = " + Collections.frequency(list, "tom"));  // 2

复制和替换：
- copy(List dest, List src): 将 src 中的内容复制到 dest 中，执行的是浅复制(如果列表中的元素是对象，那么两个列表中的相应位置将指向同一个对象)。
- replaceAll(List, Object oldVal, Object newVal): 使用新值替换 List 对象中所有的旧值。

// void copy(List dest, List src): 将 src 中的内容复制到 dest 中
ArrayList dest = new ArrayList();
// 先给 dest 赋值, 大小和 list.size() 一样
for (int i = 0; i < list.size(); i++) {
    dest.add("");
}
// 拷贝, 将 list 内容复制到 dest 中
Collections.copy(dest, list);
System.out.println("dest = " + dest);  // dest = [smith, milan, king, tom, tom]

// boolean replaceAll(List list, Object oldVal, Object newVal): 使用新值替换 List 对象的所有旧值
// 如果list中, 有 tom 就替换成 汤姆
Collections.replaceAll(list, "tom", "汤姆");
System.out.println("list 替换后 = " + list);  // list 替换后 = [smith, milan, king, 汤姆, 汤姆]

10. 课后习题

10.1 Homework01

public class Homework01 {
    public static void main(String[] args) {
        ArrayList<News> news = new ArrayList<>();
        news.add(new News("news01xxxxxxxxxxxxxxxxxxxxxx"));
        news.add(new News("news02"));

        // 倒序遍历+截取字符串(这里截取前按理来说要判断下标题非 null)
        for (int i = news.size() - 1; i >= 0; i--) {
            if (news.get(i).getTitle().length() > 15) {
                System.out.println(news.get(i).getTitle().substring(0, 15) + "...");
            } else {
                System.out.println(news.get(i).getTitle());
            }
        }
    }
}

10.2 Homework03

public class Homework03 {
    public static void main(String[] args) {
        Map<String, Integer> emps = new HashMap<>();
        emps.put("aa", 650);
        emps.put("bb", 1200);
        emps.put("cc", 2900);

        Set<Map.Entry<String, Integer>> entries = emps.entrySet();
        for (Map.Entry<String, Integer> entry : entries) {
            if (entry.getKey().equals("22")) {
                entry.setValue(2600);
            }

            entry.setValue(entry.getValue() + 100);
            System.out.println(entry);
        }
    }
}

10.3 Homework04

分析下 HashSet 和 TreeSet 分别如何去重？

HashSet 去重：
- 计算哈希值：通过调用元素的 hashCode() 方法计算其哈希值。
- 确定位置：使用哈希值来确定在哈希表（底层的数组）中的索引位置。
- 冲突处理：如果该位置已经有元素存在，则通过 equals() 方法与现有元素逐个比较：
  - 如果 equals() 返回 true（表示找到相等的元素），则不将新元素添加到集合中。
  - 如果 equals() 返回 false（即所有比较都不相等），则根据内部结构（如链表或红黑树）添加新元素以解决哈希冲突。
TreeSet 去重：
- 如果初始化时传入了 Comparator 匿名内部类对象，就使用实现的 compare 方法去重，如果方法返回0，就认为是相同的元素/数据，就不添加
- 如果没有传入 Comparator 匿名对象，则以添加的对象实现的 Compareable 接口的 compareTo 方法去重
Comparable 接口用于定义对象的自然排序方式。类实现此接口以表明其实例具有内在的排序顺序

Comparator 接口用于定义一种外部的、可定制的排序策略。它允许开发者提供自定义的排序顺序

10.4 Homework05

下面代码运行会不会抛出异常，并从源码层面说明原因？［考察读源码＋接口编程＋动态绑定］

TreeSet treeSet =  new TreeSet();
treeSet.add(new Person());

class Person{};

代码在运行时会抛出异常，原因在于 TreeSet 的工作机制要求存储的元素必须具备可比较性，即元素应该实现 Comparable 接口。而 Person 类没有实现 Comparable 接口，当 TreeSet 尝试比较两个 Person 实例来确定其排序位置时，会因为找不到比较方法而抛出 ClassCastException

10.5 Homework06-坑！

分析下面代码的输出：

前提：Person 类重写了基于 id 和 name 的 equals 和 hashCode 方法

HashSet<Person> set = new HashSet<>();

Person p1 = new Person(1001, "AA");
Person p2 = new Person(1002, "BB");

set.add(p1);
set.add(p2);
// [Person{id='1002', name='BB'}, Person{id='1001', name='AA'}]
System.out.println(set);

p1.name = "CC";
// [Person{id='1002', name='BB'}, Person{id='1001', name='CC'}]
System.out.println(set);

set.remove(p1);
// [Person{id='1002', name='BB'}, Person{id='1001', name='CC'}]
System.out.println(set);

set.add(new Person(1001, "CC"));
// [Person{id='1002', name='BB'}, Person{id='1001', name='CC'}, Person{id='1001', name='CC'}]
System.out.println(set);

set.add(new Person(1001, "AA"));
// [Person{id='1002', name='BB'}, Person{id='1001', name='CC'},
// Person{id='1001', name='CC'}, Person{id='1001', name='AA'}]
System.out.println(set);

分析：
- 为什么 remove 没成功？
  - 当 p1 被添加到 HashSet 时，它的哈希值是根据 p1 的 id 和 name 计算得到的。此时，p1 的状态是 id=1001 和 name=AA
  - 修改了 p1 的 name 属性为 "CC"。这改变了 p1 的内部状态，这意味着如果再次计算哈希值，将会得到一个不同的结果
  - 使用 set.remove(p1) 时，HashSet 试图找到 p1 的哈希值对应的桶。但是，由于 p1 的哈希值已经因为内部状态改变而改变，所以 remove 方法可能无法找到正确的桶。如果找到了桶，其内的元素通过 equals 方法比较也可能失败，因为 equals 和 hashCode 都依赖于 name，而这已经被改变了
- 为什么再次添加 1001, "CC" 和 1001, "AA" 都成功了？
  - 由于 p1 的哈希值在其被修改后没有正确地更新（即哈希表中的位置不正确），因此再次添加同样的 id 和修改后的 name ("CC") 时，会产生一个新的哈希值，并被存放在不同的位置。尽管 p1 的当前状态与新对象相同，但新对象会被视为不同的元素并被成功添加
  - 添加一个新的 Person(1001, "AA") 时，由于没有与此状态相同的 Person 对象在 HashSet 中（p1 的状态已经是 1001, "CC"），它同样被添加成功
根本原因：问题的根本原因是对象的可变性与 HashSet 的工作原理不兼容。当 HashSet 中的对象在添加后被修改，它的哈希值可能不再反映其在哈希表中的实际位置