S04-01 集合框架-Map

[TOC]

概述

数组的痛点

~~数组的痛点~~：

虽然数组（Array）是计算机底层最基础、执行效率最高的数据结构之一，但由于它的底层设计过于“硬核”，在实际的业务开发中，纯粹的数组会带来诸多不便。

Java 集合框架之所以诞生，很大程度上就是为了解决数组的以下几大痛点：

长度固定，无法动态扩展：
这是数组最致命的弱点。数组在创建时必须指定长度，且一旦分配，长度不可更改。
- 面临的困境：如果声明小了，数据放不下会报 ArrayIndexOutOfBoundsException；如果声明大了，又会白白浪费内存空间。
- 集合的解决方式：像 ArrayList 这样的集合，底层虽然也是数组，但它自带“动态扩容”机制，数据满了会自动创建一个更大的数组并把数据复制过去，对开发者完全透明。
插入和删除操作效率极低：
数组在内存中是一块连续的内存空间，这意味着元素的物理顺序就是它们的逻辑顺序。
- 面临的困境：如果你想在数组的头部或中间插入/删除一个元素，为了保持内存连续，必须将该位置之后的所有元素集体向前或向后移动。这种操作的时间复杂度是 $O(n)$ ，在大数据量下性能非常糟糕。
缺乏内置的高级操作方法：
数组是非常原始的数据结构，它只提供了通过索引读写元素的能力。
- 面临的困境：数组没有内置诸如 contains()（判断是否存在）、indexOf()（查找位置）、remove()（直接删除某个对象）等常用方法。如果你想做这些操作，必须自己写 for 循环去遍历、比对，代码臃肿且容易出错。
内存要求严苛（连续性）：
因为数组要求内存空间必须是连续的，这在某些极端情况下会导致内存利用率低下。
- 面临的困境：假设系统还剩余 100MB 的总内存，但散落在各个角落（碎片化），没有任何一块连续的内存大于 50MB。此时如果你尝试创建一个 50MB 的数组，系统就会直接抛出 OutOfMemoryError，即便总剩余内存是足够的。而链表（如 LinkedList）则不需要连续空间。
无法直接存储键值对（Map 映射）：
数组只能通过数字索引（0, 1, 2...）来访问元素。
- 面临的困境：在现实业务中，我们经常需要用“名字”找“电话”，用“商品 ID”找“价格”。数组无法直接做到这种 Key-Value 的映射，必须依赖哈希表（Map）结构。

数组就像是毛坯房，地基稳、承重好（通过索引访问速度极快，是 $O(1)$ ），但进去之后发现没水电、没刷墙，什么都要自己动手建；而 Java 集合框架则是精装房，把扩容、增删、排序、去重、映射等功能全部打包做好了，开箱即用。

集合框架组成

Java 集合框架（Java Collection Framework，简称 JCF）是 Java 标准库中最核心的部分之一。它提供了一套设计优雅、性能优良的接口和类，用于存储和操作一组对象。

在没有集合框架之前，Java 程序员主要依赖数组、Vector 和 Hashtable 来存储数据，但它们缺乏统一的接口。集合框架的出现，将数据结构（如链表、树、哈希表）的实现标准化，极大地提高了代码的复用性和开发效率。

Java 集合框架主要由两大核心接口派生而来：Collection 和 Map。

Map 接口

~~Map 接口（双列集合/键值对）~~:

Map 接口用于保存具有映射关系的数据（Key-Value 键值对）。其中，Key 唯一且不可重复，Value 可以重复。可以通过 Key 快速查找对应的 Value。

HashMap
- 底层结构：Java 8 之前是数组+链表，Java 8 及之后引入了红黑树（当链表长度大于 8 且数组长度大于 64 时，链表转为红黑树）。
- 特点：访问速度极快，线程不安全，允许一个 null 键和多个 null 值。
LinkedHashMap
- 底层结构：继承自 HashMap，增加了双向链表来维护键值对的插入顺序或访问顺序。
TreeMap
- 底层结构：红黑树。
- 特点：能够根据 Key 进行自动排序（自然排序或定制排序），Key 不能为 null。
Hashtable
- 特点：古老的线程安全实现，不允许 null 键和 null 值。效率低下，目前已被 ConcurrentHashMap 完全取代。

Collection 接口

~~Collection 接口（单列集合）~~:

Collection 是单列集合的根接口，它有三个主要的子接口：List、Set 和 Queue。

List 接口

~~List 接口：有序、可重复~~:

List 集合中的元素是有序的（存入和取出的顺序一致），并且允许元素重复。每个元素都有对应的索引。

ArrayList
- 底层结构：动态数组。
- 特点：查询和修改非常快（通过索引直接访问， $O(1)$ ），但随机插入和删除较慢（需要移动元素， $O(n)$ ）。
- 适用场景：读多写少的场景。
LinkedList
- 底层结构：双向链表。
- 特点：插入和删除非常快（只需修改指针， $O(1)$ ），但查询较慢（需要从头或尾遍历， $O(n)$ ）。它还实现了 Deque 接口，可以作为栈或队列使用。
- 适用场景：增删频繁、查询较少的场景。
Vector
- 特点：古老的实现类，线程安全（所有方法都加了 synchronized），但效率极低。现在基本被 ArrayList 或并发包中的 CopyOnWriteArrayList 替代。

Set 接口

~~Set 接口：无序、不可重复~~:

Set 集合中的元素是无序的（不能保证存取顺序），且不允许元素重复（最多只能包含一个 null）。

HashSet
- 底层结构：基于 HashMap 实现（元素存放在 HashMap 的 Key 中）。
- 特点：存取速度极快，但不保证元素的顺序。判断重复的标准是同时重写 hashCode() 和 equals() 方法。
LinkedHashSet
- 底层结构：HashSet 的子类，内部使用双向链表维护元素的插入顺序。
- 特点：既有 HashSet 的去重和高效性，又能保证遍历顺序与插入顺序一致。
TreeSet
- 底层结构：红黑树（自平衡的二叉查找树）。
- 特点：元素会自动保持排序（自然排序或通过自定义 Comparator 比较器排序）。元素不能为 null。

Queue/Deque 接口

~~Queue / Deque 接口：队列与双端队列~~:

主要用于在处理之前保存元素的集合，遵循先进先出（FIFO）或其他特定的顺序。

PriorityQueue：优先队列，底层基于堆结构。元素按照自然顺序或指定的比较器进行排序，每次出队都是优先级最高的元素。
ArrayDeque：基于循环数组实现的双端队列，效率高于 LinkedList，常用作栈（Stack）或队列（Queue）的替代品。

集合类对比

~~核心集合对比一览表~~:

接口	实现类	底层数据结构	重复性	有序性	线程安全	性能特征
List	`ArrayList`	动态数组	允许	是 (插入顺序)	否	查询快，增删慢
List	`LinkedList`	双向链表	允许	是 (插入顺序)	否	增删快，查询慢
Set	`HashSet`	哈希表	不允许	否	否	存取快，无序
Set	`LinkedHashSet`	哈希表 + 双向链表	不允许	是 (插入顺序)	否	兼顾去重与顺序
Set	`TreeSet`	红黑树	不允许	是 (大小排序)	否	自动排序，略慢
Map	`HashMap`	哈希表 (+红黑树)	Key 唯一, Value 可重复	否	否	键值对高效存取
Map	`TreeMap`	红黑树	Key 唯一, Value 可重复	是 (Key 排序)	否	键值对自动排序

工具类

~~集合工具类~~:

Java 还提供了两个非常有用的工具类，用于操作集合和数组：

Collections 类：包含大量的静态方法，用于对集合进行排序（sort）、反转（reverse）、查找（binarySearch）、洗牌（shuffle）以及将非线程安全集合转换为线程安全集合（synchronizedList 等）。
Arrays 类：专门用于操作数组的工具类，如数组转列表（asList）、排序（sort）、填充（fill）等。

线程安全与并发集合类

~~线程安全与现代并发集合~~:

标准 JCF 中的绝大多数集合（如 ArrayList, HashMap）都是线程不安全的。如果在多线程环境下使用，需要注意并发修改问题（可能会抛出 ConcurrentModificationException）。

在多线程高并发场景下，推荐使用 java.util.concurrent (JUC) 包下的并发集合：

用 ConcurrentHashMap 代替 HashMap（采用分段锁/CAS，性能极佳）。
用 CopyOnWriteArrayList 代替 ArrayList（读写分离，适合读多写极少的场景）。

你目前是在进行基础架构的设计选型，还是在准备面试？如果有具体的业务场景，我可以帮你分析最适合使用哪种集合。

Iterator~

核心工作原理

~~核心工作原理~~:

~~Iterator~~（迭代器）是 Java 集合框架中的核心接口之一，主要用于遍历集合中的元素。它引入了设计模式中的迭代器模式，将集合的底层数据结构（如链表、数组、树等）与遍历逻辑完全解耦。

迭代器内部维护一个指向集合元素的游标（Cursor）。游标最初位于第一个元素之前，每次调用 next() 方法，游标都会越过当前元素并将其返回，直到 hasNext() 返回 false。如果需要删除刚刚跨过的那个元素，可以调用 remove()。

核心迭代机制示例:

下面是使用 Iterator 遍历 List 并安全删除元素的典型代码：

java

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

public class IteratorExample {
  public static void main(String[] args) {
    // 创建并初始化集合
    List<String> list = new ArrayList<>();
    list.add("Java");
    list.add("Python");
    list.add("C++");
    list.add("Go");

    // 1. 获取迭代器
    Iterator<String> iterator = list.iterator();

    // 2. 循环遍历
    while (iterator.hasNext()) {
      String language = iterator.next();
      System.out.println("当前元素: " + language);

      // 3. 条件删除：删除 "C++"
      if ("C++".equals(language)) {
        iterator.remove(); // ✅ 使用迭代器自带的 remove() 是安全的
        // list.remove("C++"); // ❌ 通过集合的 remove() 删除，会导致快速失败
      }
    }

    System.out.println("删除后的集合: " + list);
  }
}

API：Iterator

基础迭代操作

~~基础迭代操作~~:

boolean hasNext()：()，判断迭代器中是否仍有可迭代的元素。通常作为循环的边界条件。

E next()：()，返回迭代器游标后的下一个元素，并将游标向下移动一位。如果已无元素，抛出 NoSuchElementException。

java

import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

public class BaseIteratorDemo {
  public static void main(String[] args) {
    List<Integer> numbers = Arrays.asList(10, 20, 30);
    Iterator<Integer> iterator = numbers.iterator();

    if (iterator.hasNext()) {
      Integer first = iterator.next();
      System.out.println("首次获取: " + first); // 输出 10
    }

    iterator.next(); // NoSuchElementException
  }
}

迭代修改操作

~~迭代修改操作~~:

void remove()：()，从底层集合中删除迭代器最后一次返回的元素。该方法在每次调用 next() 后只能被调用一次，如果在 next() 调用前或连续调用 remove()，将抛出 IllegalStateException。

java

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

public class RemoveIteratorDemo {
  public static void main(String[] args) {
    List<String> languages = new ArrayList<>();
    languages.add("C++");
    languages.add("Java");
    languages.add("Python");

    Iterator<String> iterator = languages.iterator();
    while (iterator.hasNext()) {
      String lang = iterator.next();
      if ("C++".equals(lang)) {
        iterator.remove(); // 安全移除元素
        // iterator.remove(); // IllegalStateException
      }
    }
    System.out.println("修改后的集合: " + languages); // 输出 [Java, Python]
  }
}

批量函数式操作

~~批量函数式操作~~:

void forEachRemaining()：(Consumer<? super E> action)，对集合中剩余的所有元素执行指定的消费（遍历）操作，直到所有元素处理完毕或抛出异常。常用于配合 Lambda 表达式进行高效流式处理。

java

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

public class ForEachRemainingDemo {
 public static void main(String[] args) {
     List<String> frameworks = new ArrayList<>();
     frameworks.add("Spring");
     frameworks.add("Hibernate");
     frameworks.add("MyBatis");

     Iterator<String> iterator = frameworks.iterator();
     if (iterator.hasNext()) {
         System.out.println("跳过首元素: " + iterator.next());
     }

     // 消费剩余的所有元素
     iterator.forEachRemaining(element -> System.out.println("剩余元素: " + element));
 }
}

快速失败（Fail-Fast）机制

在使用 Iterator 时，有一个新手极易踩坑的地方：在用迭代器遍历集合的过程中，绝对不能直接使用集合自身的方法（如 list.remove() 或 list.add()）来修改集合。

如果这么做，程序会立刻抛出 ConcurrentModificationException 异常。这就是 Java 的 Fail-Fast 机制。

~~为什么会这样~~:

集合内部维护了一个名为 modCount（修改计数器）的变量，每次集合结构发生改变（增、删），modCount 就会加 1。

当你创建 Iterator 时，迭代器内部会记录当前的这个值（expectedModCount = modCount）。

每次调用 next() 时，迭代器都会检查 modCount 是否还等于 expectedModCount。如果不相等，说明你在迭代的同时，通过其他途径（比如 list.remove()）偷偷改了集合，迭代器就会引发“快速失败”，抛出异常。

~~正确做法：~~:

如果需要在遍历时删除元素，必须使用 iterator.remove()。因为 iterator.remove() 在删除元素后，会自动把更新后的 modCount 重新赋值给 expectedModCount，保持两者的同步。

java

import java.util.ArrayList;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;

public class FailFastDemo {
  public static void main(String[] args) {
    List<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);

    // 演示：错误修改引发异常
    try {
      Iterator<Integer> it = list.iterator();
      while (it.hasNext()) {
        Integer val = it.next();
        if (val == 2) {
          list.remove(val); // 错误：通过集合自身的 API 改变结构
        }
      }
    } catch (ConcurrentModificationException e) {
      System.err.println("成功捕获预期的异常：ConcurrentModificationException");
    }
  }
}

For-Each 循环

你平时一定经常写这样的代码：

java

for (String item : list) {
    System.out.println(item);
}

这被称为 ~~Enhanced for loop（增强型 for 循环/for-each）~~。

实际上，这只是一个语法糖。在编译成字节码后，Java 会自动把它转换成 Iterator 的形式。任何实现了 Iterable 接口的类，都可以使用这种 for-each 语法。

注意：正因为 for-each 底层是 Iterator，所以你不能在 for-each 循环里用 list.remove() 删除元素，否则同样会触发 ConcurrentModificationException。如果需要边遍历边删除，必须退回到显式使用 Iterator 的写法。

ListIterator~

针对 List 集合，Java 还提供了一个功能更强大的子接口：ListIterator。

它们的主要区别如下：

特性	Iterator	ListIterator
适用范围	适用于所有 Collection（List, Set 等）	仅适用于 List 集合
遍历方向	只能单向向后遍历 (`next()`)	支持双向遍历 (`next()` 和 `hasPrevious() / previous()`)
元素修改	只能进行删除操作 (`remove()`)	支持删除、修改 (`set()`) 和添加 (`add()`)
索引获取	无法获取当前元素的索引	可以获取前一个或后一个元素的索引 (`nextIndex() / previousIndex()`)

实战：库存筛选系统

~~综合实战案例~~:

该案例模拟了一个简易的电商库存筛选系统，演示如何利用 Iterator 安全地过滤出不合规的商品数据。

java

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

/**
 * 商品实体类
 */
class Product {
  private String name;
  private int stock;

  public Product(String name, int stock) {
    this.name = name;
    this.stock = stock;
  }

  public String getName() { return name; }
  public int getStock() { return stock; }

  @Override
  public String toString() {
    return "Product{name='" + name + "', stock=" + stock + "}";
  }
}

/**
 * 库存管理系统
 */
public class InventoryManagementSystem {
  public static void main(String[] args) {
    // 1. 初始化商品库存列表
    List<Product> inventory = new ArrayList<>();
    inventory.add(new Product("MacBook Pro", 15));
    inventory.add(new Product("iPhone 15", 0));    // 无库存商品
    inventory.add(new Product("iPad Air", 8));
    inventory.add(new Product("Apple Watch", 0));  // 无库存商品

    System.out.println("清理前的库存列表：");
    System.out.println(inventory);

    // 2. 使用 Iterator 安全移除库存为 0 的商品
    Iterator<Product> iterator = inventory.iterator();
    while (iterator.hasNext()) {
      Product product = iterator.next();
      // 筛选条件：若库存为0，则移出货架
      if (product.getStock() == 0) {
        iterator.remove();
      }
    }

    // 3. 输出清理后的最终结果
    System.out.println("\n清理后的有效库存列表：");
    for (Product product : inventory) {
      System.out.println(product);
    }
  }
}

Map~

~~java.util.Map~~ 和 Collection 接口（包含 List、Set 等）并列为 Java 集合框架的两大基石。

简单来说，Map 用于存储键值对（Key-Value Pairs）。每个键（Key）都是唯一的，通过键可以快速查找到对应的值（Value）。如果你需要建立某种“映射关系”，比如“学号 $\rightarrow$ 学生信息”、“英文单词 $\rightarrow$ 中文翻译”，Map 就是你的不二之选。

核心特性

键的唯一性（Unique Keys）： Map 中不允许存在重复的键。如果强行放入相同的键，新值会覆盖旧值。
值的可重复性（Duplicate Values）：不同的键可以指向相同的值。
无序性（通常情况下）： Map 接口本身并不保证元素的顺序。不过，某些具体的实现类（如 LinkedHashMap、TreeMap）提供了特定的顺序。
不继承 Collection：这是一个常见误区。Map 是独立于 Collection 的接口，两者的设计结构完全不同。

核心原理

Map 接口的设计核心在于通过“键（Key）”实现数据的快速检索。其底层的基本抽象形态是基于哈希散列或树状红黑树结构。Key 决定了数据在内存中的存储位置，而 Value 是与该位置绑定的载体。

java

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

public class MapOverviewDemo {
    public static void main(String[] args) {
        // 初始化一个基于哈希表的 Map 容器
        Map<String, String> configuration = new HashMap<>();

        // 建立映射关系
        configuration.put("protocol", "HTTPS");
        configuration.put("timeout", "3000");

        // 通过 Key 检索 Value
        String protocol = configuration.get("protocol");
        System.out.println("Protocol: " + protocol);
    }
}

核心实现类

Java 提供了多种 Map 的实现，以应对不同的业务场景。最常用的有以下四种：

HashMap（最常用）：
- 底层结构： Java 8 之前是数组 + 链表，Java 8 及以后引入了红黑树（当链表长度大于 8 且数组容量大于 64 时转为红黑树），大大提升了高冲突情况下的查询效率。
- 特点： 查询、插入速度极快（平均时间复杂度为 $O(1)$ ）；无序；允许一个 null 键和多个 null 值；线程不安全。
LinkedHashMap（按顺序访问）：
- 底层结构： 继承自 HashMap，但在其基础上增加了一条双向链表。
- 特点： 保持了元素的插入顺序（也可以配置为按访问顺序）。遍历时的速度与元素数量成正比，而与容量无关。
TreeMap（自动排序）：
- 底层结构： 基于红黑树（Red-Black tree）实现。
- 特点： 元素会按照键的自然顺序或自定义的 Comparator 顺序进行排序。查询、插入的时间复杂度为 $O(\log n)$ ；不允许 null 键，但允许 null 值。
ConcurrentHashMap（高并发必备）：
- 底层结构： Java 8 采用数组 + 链表 + 红黑树，利用 CAS 原子操作和 synchronized 锁住细粒度的节点（Node）。
- 特点： 线程安全，且在高并发环境下性能远优于老旧的 Hashtable 或 Collections.synchronizedMap。不允许 null 键和 null 值。

~~四大实现类对比表~~:

特性	HashMap	LinkedHashMap	TreeMap	ConcurrentHashMap
底层数据结构	数组+链表+红黑树	HashMap+双向链表	红黑树	数组+链表+红黑树
元素是否有序	无序	插入顺序或访问顺序	键的自然/自定义顺序	无序
是否允许 null 键	允许（最多一个）	允许（最多一个）	不允许	不允许
是否允许 null 值	允许（多个）	允许（多个）	允许（多个）	不允许
是否线程安全	否	否	否	是
平均时间复杂度	$O(1)$	$O(1)$	$O(\log n)$	$O(1)$

API：Map

增删改查

V put()：(K key, V value)，写入与更新。将指定的值与此映射中的指定键关联。若键已存在，则替换旧值并返回旧值；若键不存在，则返回 null。
void putAll()：(Map<? extends K, ? extends V> m)，批量写入。将指定 Map 的所有映射关系复制到当前 Map 中。
V remove()：(Object key)，如果存在一个键的映射关系，则将其从此映射中移除，并返回被移除的值。
boolean remove()：(Object key, Object value)，仅当指定键当前映射到指定值时，才移除该键值对。
V get()：(Object key)，读取。返回指定键所映射的值；如果此映射不包含该键的映射关系，则返回 null。
V replace()：(K key, V value)，条件替换。只有当指定键当前映射到某个值时，才替换该键对应的值，并返回旧值。

void clear()：()，从此映射中移除所有映射关系，执行后映射将为空。

java

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

public class MapCrudDemo {
  public static void main(String[] args) {
    Map<String, String> sessionMap = new HashMap<>();

    // 1. 写入与更新 (put)
    sessionMap.put("session_id", "X98231");
    String oldStatus = sessionMap.put("status", "INIT"); // 返回 null
    String updatedStatus = sessionMap.put("status", "ACTIVE"); // 返回 "INIT"

    // 2. 批量写入 (putAll)
    Map<String, String> extraData = new HashMap<>();
    extraData.put("ip", "127.0.0.1");
    extraData.put("device", "Mobile");
    sessionMap.putAll(extraData);

    // 3. 读取 (get)
    String ipAddress = sessionMap.get("ip");

    // 4. 条件替换 (replace)
    sessionMap.replace("device", "Desktop");

    // 5. 条件删除与条件移除 (remove)
    sessionMap.remove("session_id");
    boolean isRemoved = sessionMap.remove("status", "INIT"); // 期望返回 false，因为当前值是 "ACTIVE"

    // 6. 清空容器
    sessionMap.clear();

    System.out.println("IP: " + ipAddress + ", Remove Status: " + isRemoved + ", Map: " + sessionMap);

  }
}

判断与大小

int size()：()，获取容量大小。返回此映射中的键值映射关系数。若超过 Integer.MAX_VALUE，则返回 Integer.MAX_VALUE。
boolean isEmpty()：()，判空检查。如果此映射不包含键值映射关系，则返回 true。
boolean containsKey()：(Object key)，键存在性判断。如果此映射包含指定键的映射关系，则返回 true。

boolean containsValue()：(Object value)，值存在性判断。如果此映射将一个或多个键映射到指定值，则返回 true。

java

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

public class MapInspectionDemo {
  public static void main(String[] args) {
    Map<Integer, String> employeeMap = new HashMap<>();
    employeeMap.put(1001, "Alice");
    employeeMap.put(1002, "Bob");

    // 1. 获取容量大小
    int count = employeeMap.size();

    // 2. 判空检查
    boolean hasData = !employeeMap.isEmpty();

    // 3. 键存在性判断 (时间复杂度通常为 O(1))
    boolean hasAlice = employeeMap.containsKey(1001);

    // 4. 值存在性判断 (时间复杂度为 O(n)，需要全表线性扫描)
    boolean hasCharlie = employeeMap.containsValue("Charlie");

    // 5. 清空容器
    employeeMap.clear();
    boolean isClean = employeeMap.isEmpty();

    System.out.println("Count: " + count + ", Has Alice: " + hasAlice + ", Is Clean: " + isClean);
  }
}

集合视图与遍历

Set<K> keySet()：()，返回此映射中包含的键的 Set 视图。对该 Set 的删除操作会同步影响原 Map。
Collection<V> values()：()，返回此映射中包含的值的 Collection 视图。
Set<Map.Entry<K, V>> entrySet()：()，返回此映射中包含的映射关系的 Set 视图。是性能最优的遍历形态。

void forEach()：(BiConsumer<? super K, ? super V> action)，对此映射中的每个条目执行给定的操作，直到所有条目都被处理（Java 8 函数式接口）。

java

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

public class MapViewIterationDemo {
  public static void main(String[] args) {
    Map<String, Double> priceMap = new HashMap<>();
    priceMap.put("Apple", 5.5);
    priceMap.put("Banana", 3.2);

    // 1. 获取键集视图
    Set<String> keys = priceMap.keySet();

    // 2. 获取值集视图
    Collection<Double> values = priceMap.values();

    // 3. 经典的 entrySet 迭代器/for-each 遍历（推荐，效率最高）
    for (Map.Entry<String, Double> entry : priceMap.entrySet()) {
      String product = entry.getKey();
      Double price = entry.getValue();
      System.out.println("Product: " + product + ", Price: " + price);
    }

    // 4. 使用 Lambda 表达式遍历 (forEach)
    priceMap.forEach((product, price) -> {
      System.out.println("Lambda -> " + product + " : " + price);
    });
  }
}

高级与静态工厂操作

<K, V> Map<K, V> Map.of()：(K k1, V v1, K k2, V v2)，静态工厂方法，返回包含指定映射关系的不可变 Map 实例。不允许 null 键或 null 值（Java 9+）。
<K, V> Map<K, V> Map.copyOf()：(Map<? extends K, ? extends V> map)，静态工厂方法，返回一个包含给定 Map 的键值对的不可变 Map 副本（Java 10+）。
V getOrDefault()：(Object key, V defaultValue)，返回指定键映射的值；若此映射不包含该键，则返回指定的默认值。
V putIfAbsent()：(K key, V value)，如果指定的键尚未与值关联（或映射到 null），则将其与给定的值关联并返回 null，否则返回当前值。
V computeIfAbsent()：(K key, Function<? super K, ? extends V> mappingFunction)，若指定键未关联值，则使用映射函数计算新值并放入 Map。常用于多值映射结构的构建。

V merge()：(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction)，若键不存在则直接归纳该值；若键存在，则通过重映射函数将旧值与新值合并。

java

import java.util.HashMap;
import java.util.Map;
import java.util.ArrayList;
import java.util.List;

public class MapAdvancedOperationsDemo {
 public static void main(String[] args) {
     // 1. 静态工厂构建不可变容器 (Map.of)
     Map<String, Integer> immutableRank = Map.of("GradeA", 90, "GradeB", 80);
   Map<String, Object> dynamicMap = new HashMap<>();

   // 2. 兜底安全读取 (getOrDefault)
     Object theme = dynamicMap.getOrDefault("theme", "DARK_MODE");

   // 3. 缺失时初始化写入 (putIfAbsent)
     dynamicMap.putIfAbsent("retry_count", 3);

   // 4. 弹性分支计算初始化 (computeIfAbsent)
     Map<String, List<String>> structureMap = new HashMap<>();
     structureMap.computeIfAbsent("Backend", k -> new ArrayList<>()).add("Java");
     structureMap.computeIfAbsent("Backend", k -> new ArrayList<>()).add("Go");

   // 5. 聚合归纳合并 (merge)
     Map<String, Integer> scoreMap = new HashMap<>();
     scoreMap.put("Player1", 50);
     scoreMap.merge("Player1", 20, Integer::sum); // 结果为 70
     scoreMap.merge("Player2", 10, Integer::sum); // 直接初始化为 10

   System.out.println("Theme: " + theme + ", Structure: " + structureMap + ", Scores: " + scoreMap);
 }
}

遍历方式

在实际开发中，遍历 Map 是家常便饭。以下是三种最常用的遍历方案：

`entrySet()`@

这种方式可以同时拿到 Key 和 Value，且不需要二次查找，效率最高。

java

Map<String, Integer> map = new HashMap<>();
map.put("Apple", 10);
map.put("Banana", 20);

for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}

Lambda 与 `forEach`

代码非常优雅，适合日常编写。

java

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

`keySet()` 加 `get()`

这种方式在每次循环时都要调用 map.get(key)，相当于做了一次额外的哈希查找，性能较差。

java

for (String key : map.keySet()) {
    Integer value = map.get(key); // 效率低，尽量避免
    System.out.println("Key: " + key + ", Value: " + value);
}

选型建议

在实际开发中，你该如何选择？

绝大多数常规场景： 毫不犹豫选择 HashMap。
需要保证元素的插入顺序： 选择 LinkedHashMap（常用于实现 LRU 缓存）。
需要对键进行排序（如按英文字母、数字大小）： 选择 TreeMap。
多线程并发环境： 必须选择 ConcurrentHashMap，千万不要在多线程下盲目使用 HashMap，这可能会导致死循环（Java 7 之前）或数据丢失等诡异 BUG。

Map-HashMap~

~~java.util.HashMap~~ 是 Java Collection Framework 中基于哈希表（Hash Table） 实现的经典 Map 接口实现类。它采用键值对（Key-Value） 形式存储数据，允许使用 null 键和 null 值，且不保证元素的顺序。

底层数据结构

HashMap 的底层结构在 Java 8 迎来了一次重大升级：

Java 7 及以前： 采用 数组 + 单向链表 的结构（通常称为拉链法）。
Java 8 及以后： 采用 数组 + 单向链表 + 红黑树 的结构。

为什么要引入红黑树；

在 Java 7 中，如果发生大量的哈希冲突，很多键值对都会被挂在同一个链表上。当链表过长时，查询一个元素的时间复杂度会从理想的 $O(1)$ 退化为 $O(n)$ 。

为了解决这个性能恶梦，Java 8 引入了红黑树。当满足特定条件时，长链表会自动转换为红黑树，将查询的时间复杂度锁定在 $O(\log n)$ 。

树化与退化阈值；

HashMap 并不是一上来就用红黑树的，而是设计了两个关键的触发机构：

树化（Treeify）机制： 当某条链表的长度大于等于 8，且当前数组的总容量大于等于 64 时，该链表才会转化为红黑树。
退化（Untreeify）机制： 在红黑树进行扩容或删除元素时，如果树中的节点数小于等于 6，红黑树会退化回普通链表（因为在节点较少时，红黑树的维护成本反而比链表高）。

java

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

public class HashMapCoreDemo {
  public static void main(String[] args) {
    // 创建基础 HashMap 实例
    Map<String, String> sessionMap = new HashMap<>();

    // 1. 寻址与写入
    sessionMap.put("userId_1001", "Token_A");
    sessionMap.put("userId_1002", "Token_B");

    // 2. 读取与命中
    String token = sessionMap.get("userId_1001");
    System.out.println("Retrieved Token: " + token);
  }
}

核心参数与概念

在阅读 HashMap 源码时，有几个参数决定了它的性能和内存占用：

参数名称	默认值	作用解释
`DEFAULT_INITIAL_CAPACITY`	`16` ( $2^4$ )	默认初始容量。即底层的 Node 数组长度。
`MAXIMUM_CAPACITY`	$2^{30}$	最大容量。
`DEFAULT_LOAD_FACTOR`	`0.75`	默认加载因子。用来衡量数组填满程度的比例。
`threshold`	容量 $\times$ 加载因子	扩容阈值。当 HashMap 内的键值对数量超过这个值时，就会触发扩容（Resize）。

为什么默认加载因子是 0.75？
这是一个在时间成本和空间成本之间折中的选择。如果设为 0.5，数组利用率低，频繁扩容浪费空间；如果设为 1.0，空间利用率高，但会带来大量的哈希冲突，导致查询效率变低。

工作原理

哈希算法：扰动函数@

当你执行 map.put(key, value) 时，HashMap 首先要计算 Key 的哈希值。它并没有直接使用 key.hashCode()，而是做了一次“扰动”：

java

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

为什么要让高 16 位和低 16 位进行异或（^）运算？

因为后面计算数组下标时，通常只有低位用得上。通过让高位也参与运算，可以有效减少哈希冲突。

寻址算法：定位数组下标@

得到了 hash 值后，系统需要把它映射到数组的某个格子（桶）里。

传统的做法是取模运算 hash % length，但计算机做取模比较慢。HashMap 采用了一个极其优雅的位运算公式：

\text{index} = (\text{length} - 1) \& \text{hash}

核心陷阱：为什么 HashMap 的容量必须是 2 的幂次方？
只有当 length 是 2 的幂次方时（如 16, 32, 64），length - 1 的二进制才全是 1（如 15 的二进制是 1111）。此时进行 &（与）运算，能保证计算出来的 index 均匀分布在 0 到 length-1 之间，并且位运算的执行效率极高。

扩容机制

当 HashMap 中的元素个数超过了 threshold（阈值）时，就会自动进行扩容，通常是将数组长度翻倍（Old Capacity $\times$ 2）。

Java 8 的高性能扩容优化:

在 Java 7 中，扩容后所有元素都需要重新计算哈希和下标（Rehash），非常耗时。

Java 8 做了一个聪明的优化：由于容量是翻倍的（二进制往高位进了一位），原先的元素在扩容后的新数组中，要么还在原位置，要么在“原位置 + 旧容量”的位置。

通过判断 (hash & oldCap) 是 0 还是 1，可以极其快速地把链表拆分成“低位链表”和“高位链表”，直接移到新数组中，免去了复杂的重新计算过程。

java

import java.util.HashMap;

public class HashMapResizeDemo {
    public static void main(String[] args) {
        // 初始化小容量，便于观察扩容行为
        HashMap<Integer, String> dynamicMap = new HashMap<>(4);

        // 触发多次内部扩容
        for (int i = 1; i <= 10; i++) {
            dynamicMap.put(i, "Value_" + i);
        }

        System.out.println("Map 扩容后最终大小: " + dynamicMap.size());
    }
}

API：HashMap

构造方法

HashMap HashMap()：()，构造一个具有默认初始容量 (16) 和默认负载因子 (0.75) 的空 HashMap。
HashMap HashMap()：(int initialCapacity)，构造一个具有指定初始容量和默认负载因子 (0.75) 的空 HashMap。

HashMap HashMap()：(int initialCapacity, float loadFactor)，构造一个具有指定初始容量和指定负载因子的空 HashMap。

java

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

public class HashMapConstructorDemo {
 public static void main(String[] args) {
     // 1. 使用默认参数初始化（容量=16，负载因子=0.75）
     Map<String, Object> defaultMap = new HashMap<>();

     // 2. 指定初始容量初始化，常用于已知元素规模的场景，规避中途扩容性能开销
     Map<String, Object> capacityMap = new HashMap<>(64);

     // 3. 同时指定初始容量及负载因子
     Map<String, Object> customMap = new HashMap<>(32, 0.6f);

     System.out.println("所有 HashMap 实例初始化完毕。");
 }
}

数据操作

V put()：(K key, V value)，向 Map 中关联指定的键与值。若键已存在，替换旧值并返回旧值，否则返回 null。
V get()：(Object key)，返回指定键所映射的值；如果此 Map 不包含该键的映射关系，则返回 null。
V remove()：(Object key)，如果存在一个键的映射关系，则将其从此 Map 中移除，并返回其对应的值。

boolean containsKey()：(Object key)，如果此 Map 包含指定键的映射关系，则返回 true。

java

import java.util.HashMap;

public class HashMapCRUDDemo {
 public static void main(String[] args) {
     HashMap<String, Integer> inventory = new HashMap<>();

     // 1. 增/改操作
     inventory.put("Apple", 50);
     Integer oldVal = inventory.put("Apple", 65); // 覆盖旧值，返回 50

     // 2. 查操作
     if (inventory.containsKey("Apple")) {
         Integer appleCount = inventory.get("Apple");
         System.out.println("Apple 数量: " + appleCount);
     }

     // 3. 删操作
     Integer removedVal = inventory.remove("Apple");
     System.out.println("移除的 Apple 数量: " + removedVal);
 }
}

进阶弹性计算

V computeIfAbsent()：(K key, Function<? super K, ? extends V> mappingFunction)，如果指定的键尚未关联值（或映射为 null），则尝试使用给定的映射函数计算其值，并将其输入到 Map 中。

V merge()：(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction)，如果指定的键尚未关联值或关联为 null，则将其与给定的非空值关联；否则，使用给定的重映射函数替换其值。

java

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

public class HashMapComputeDemo {
 public static void main(String[] args) {
     HashMap<String, List<String>> multiMap = new HashMap<>();

     // 1. computeIfAbsent: 简化按组分类数据的初始化和追加操作
     multiMap.computeIfAbsent("Developer", k -> new ArrayList<>()).add("Alice");
     multiMap.computeIfAbsent("Developer", k -> new ArrayList<>()).add("Bob");

     // 2. merge: 简化计数合并逻辑
     HashMap<String, Integer> scoreMap = new HashMap<>();
     scoreMap.put("TeamA", 10);
     // 如果 TeamA 存在，则将旧值与新值 5 相加
     scoreMap.merge("TeamA", 5, Integer::sum);

     System.out.println("分组结果: " + multiMap);
     System.out.println("得分合并结果: " + scoreMap);
 }
}

注意事项

线程不安全

HashMap 是专为单线程设计的。如果在多线程环境下并发读写，会导致严重的问题：

数据丢失 / 覆盖： 两个线程同时 put 发生冲突，可能会互相覆盖对方的数据。
死循环（Java 7 及以前）： 在多线程扩容时，由于采用头插法，可能会形成环形链表。一旦后续调用 get() 查到这个环，CPU 直接飙到 100% 锁死。虽然 Java 8 改用尾插法解决了死循环问题，但高并发下依然会导致数据错乱。
解决方案： 并发场景下，请直接使用 ConcurrentHashMap。

Key 的不变量要求

如果你用一个自定义的类作为 HashMap 的 Key，强烈建议将它的成员变量设为 final，并重写 equals() 和 hashCode() 方法。

反面教材： 如果你把一个对象存入 Map 后，修改了该对象的属性，导致它的 hashCode() 发生了改变。那么你之后将永远无法通过这个 Key 把 Value 拿出来，它就变成了常驻内存的“僵尸数据”。

实战：高并发网关限流计数器

本实战模拟网关层的用户请求限流（Fixed Window Rate Limiting）。使用 HashMap 记录窗口期内每个 API 接口被调用的次数，当超过阈值时触发拦截。本示例展示了 HashMap 在真实业务中进行高频状态匹配、安全数值合并的底座作用。

java

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

public class GatewayRateLimiter {

    // 内部维护限流计数容器
    private final Map<String, Integer> requestCounters = new HashMap<>();
    private final int maxLimit;

    public GatewayRateLimiter(int maxLimit) {
        this.maxLimit = maxLimit;
    }

    /**
     * 判断当前请求是否允许通过
     * @param apiKey 路由接口标示
     * @return boolean 是否放行
     */
    public synchronized boolean isAllowed(String apiKey) {
        // 使用 merge 方法完成：不存在则初始化为1，存在则执行 Integer::sum 累加 1
        int currentRequestCount = requestCounters.merge(apiKey, 1, Integer::sum);

        if (currentRequestCount > maxLimit) {
            System.out.printf("[警告] 接口 [%s] 触发限流！当前请求数: %d, 限制阈值: %d\n",
                    apiKey, currentRequestCount, maxLimit);
            return false;
        }

        System.out.printf("[正常] 接口 [%s] 放行。当前请求数: %d\n", apiKey, currentRequestCount);
        return true;
    }

    public static void main(String[] args) {
        // 初始化限流器，每个接口在单窗口周期内最多允许调用 3 次
        GatewayRateLimiter limiter = new GatewayRateLimiter(3);

        String orderApi = "/api/v1/order/create";
        String payApi = "/api/v1/pay/execute";

        // 模拟连续的网关网络请求流
        limiter.isAllowed(orderApi);
        limiter.isAllowed(orderApi);
        limiter.isAllowed(payApi);
        limiter.isAllowed(orderApi);

        // 第 4 次调用 orderApi，预期触发限流
        limiter.isAllowed(orderApi);

        // 支付接口仅第 2 次调用，预期正常通过
        limiter.isAllowed(payApi);
    }
}

Map-HashMap-LinkedHashMap~

~~java.util.LinkedHashMap~~ 直接继承自 HashMap。它完美的继承了 HashMap 的高性能，同时通过引入一条双向链表，解决了 HashMap 元素无序的痛点。

底层数据结构

LinkedHashMap 在 HashMap 稳定的哈希表架构（数组 + 链表 + 红黑树）基础上，通过维护一条双向链表（Doubly-Linked List），确立了所有条目（Entry）的迭代顺序。

该类很好地解决了 HashMap 元素无序的问题，并在构建缓存淘汰策略（如 LRU）时提供了关键的基础设施。

继承关系： 它继承了 HashMap，这意味着它底层同样拥有数组、单向链表和红黑树。
双向链表： LinkedHashMap 内部定义了一个特殊的节点 Entry，它继承自 HashMap.Node，并增加了两个指针：before 和 after。
- before：指向当前节点在全局迭代顺序中的前驱节点。
- after：指向当前节点在全局迭代顺序中的后继节点。

通过这两个指针，LinkedHashMap 将散落在各个哈希桶（Bucket）中的节点，串联成了一个独立于哈希寻址之外的全局双向链表。起始节点由 head 指向，末尾节点由 tail 指向。

打个比方：
HashMap 像是一个个散落在大楼各个房间（桶）里的客人，你想找某个人很快，但要把所有客人按到访顺序排个队就很难。
LinkedHashMap 则是在这些客人的腰上系了一根红绳子（双向链表），每个人都记着自己前一个到访的是谁，后一个到访的是谁。这样既能快速在房间找到人，又能顺着绳子把所有人按顺序拉出来。

排序模式

LinkedHashMap 最强大的地方在于，它不仅支持插入顺序，还支持访问顺序。这取决于构造函数中的一个关键参数：accessOrder。

java

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder; // true 为访问顺序，false 为插入顺序（默认）
}

插入顺序（Insertion Order，默认）
当你不断往 Map 里 put 元素时，链表会按照你插入的先后顺序记录。遍历时，先插入的先打印。
访问顺序（Access Order）
这是一个非常高级的特性。当 accessOrder 设置为 true 时，每当你调用 get()、put() 或 replace() 访问某个节点后，这个节点就会被自动移动到双向链表的尾部（Tail）。
这意味着，链表头部（Head）永远是“最久未被访问的元素”，链表尾部（Tail）永远是“最近刚刚访问的元素”。

java

import java.util.LinkedHashMap;
import java.util.Map;

public class LinkedHashMapOrderDemo {
public static void main(String[] args) {
    // 1. 默认模式：保持插入顺序
    Map<String, Integer> insertionOrderMap = new LinkedHashMap<>();
    insertionOrderMap.put("Rank1", 100);
    insertionOrderMap.put("Rank3", 300);
    insertionOrderMap.put("Rank2", 200);

    System.out.println("插入顺序迭代结果: " + insertionOrderMap.keySet());

    // 2. 访问顺序模式：开启 accessOrder
    Map<String, Integer> accessOrderMap = new LinkedHashMap<>(16, 0.75f, true);
    accessOrderMap.put("KeyA", 1);
    accessOrderMap.put("KeyB", 2);
    accessOrderMap.put("KeyC", 3);

    // 触发访问操作，KeyA 将被移动到双向链表的末尾
    accessOrderMap.get("KeyA");

    System.out.println("访问顺序迭代结果 (KeyA 应该在最后): " + accessOrderMap.keySet());
}
}

性能对比 HashMap

很多同学会担心：增加了双向链表，性能会不会拉跨？

基本操作（get/put/remove）： 时间复杂度依然是 $O(1)$ 。虽然每次操作要额外修改 before/after 指针，会有极其微小的性能损耗，但在绝大多数业务场景下可以忽略不计。
遍历操作（Iteration）： LinkedHashMap 的遍历速度通常快于 HashMap。
- HashMap 遍历时需要扫一遍整个数组（包括空的格子）。
- LinkedHashMap 遍历时直接沿着那根双向链表走就行了，遍历时间只和元素数量（size）有关，和数组容量（capacity）无关。
内存消耗： 由于每个节点多了两个指针域，LinkedHashMap 占用的内存会比 HashMap 稍大一些。

API：LinkedHashMap

构造方法

LinkedHashMap LinkedHashMap()：()，构造一个具有默认初始容量 (16) 和默认负载因子 (0.75) 的可变、保持插入顺序的 LinkedHashMap。
LinkedHashMap LinkedHashMap()：(int initialCapacity)，构造一个具有指定初始容量和默认负载因子 (0.75) 的保持插入顺序的 LinkedHashMap。
LinkedHashMap LinkedHashMap()：(int initialCapacity, float loadFactor)，构造一个具有指定初始容量和指定负载因子的保持插入顺序的 LinkedHashMap。

LinkedHashMap LinkedHashMap()：(int initialCapacity, float loadFactor, boolean accessOrder)，构造一个具有指定初始容量、负载因子和排序模式（true 表示访问顺序，false 表示插入顺序）的空 LinkedHashMap。

java

import java.util.LinkedHashMap;
import java.util.Map;

public class LinkedHashMapConstructorDemo {
 public static void main(String[] args) {
     // 1. 无参默认构造
     Map<String, String> map1 = new LinkedHashMap<>();

     // 2. 指定容量构造，避免频繁 rehash 开销
     Map<String, String> map2 = new LinkedHashMap<>(32);

     // 3. 全参数配置构造（针对 LRU 场景的典型配置）
     Map<String, String> lruBaseMap = new LinkedHashMap<>(16, 0.7f, true);

     map1.put("Status", "OK");
     System.out.println("LinkedHashMap 各类型实例初始化成功。");
 }
}

驱逐策略与钩子

boolean removeEldestEntry()：(Map.Entry<K,V> eldest)，这是一个受保护的钩子方法。在 put 或 putAll 插入新元素后被系统隐式调用。如果该方法返回 true，则 Map 会自动将双向链表中处于 head 位置的最老条目删除。在 LinkedHashMap 原生类中默认返回 false，需要开发者继承并重写。

java

import java.util.LinkedHashMap;
import java.util.Map;

// 通过继承并重写构造有界固定容量的存储容器
class FixedCapacityMap<K, V> extends LinkedHashMap<K, V> {
 private final int maxCapacity;

 public FixedCapacityMap(int maxCapacity) {
     super(maxCapacity, 0.75f, false); // 保持插入顺序
     this.maxCapacity = maxCapacity;
 }

 @Override
 protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
     // 当元素总数超过设定的物理最大容量时，触发自动驱逐最老写入节点
     return this.size() > maxCapacity;
 }
}

public class LinkedHashMapHookDemo {
 public static void main(String[] args) {
     FixedCapacityMap<Integer, String> cache = new FixedCapacityMap<>(3);
     cache.put(1, "A");
     cache.put(2, "B");
     cache.put(3, "C");

     // 此时到达容量上限，塞入第 4 个元素，导致最老的元素 1 被自动清除
     cache.put(4, "D");

     System.out.println("自动驱逐后的 Cache 剩余内容: " + cache); // 预期输出不含 1=A
 }
}

注意事项

线程非安全性：LinkedHashMap 未做并发同步保护。如果在多线程高并发环境下读写，不仅会导致数据丢失，更严重的是，多线程并发引发的双向链表指针断裂和环形指向，会导致系统陷入死循环或抛出 NullPointerException。并发场景下应当使用 Collections.synchronizedMap(new LinkedHashMap(...)) 进行包裹。
访问顺序模式下的并发修改异常：当 accessOrder = true 时，进行 get() 读操作也是一种结构性修改（Structural Modification），因为它改变了全局双向链表的迭代顺序，从而导致 modCount 递增。因此，在使用 Iterator 或 For-Each 循环遍历该 Map 的过程中，绝对禁止调用 get() 方法，否则会立即触发 ConcurrentModificationException。

java

import java.util.LinkedHashMap;
import java.util.Map;

public class LinkedHashMapExceptionDemo {
  public static void main(String[] args) {
    // 创建一个访问顺序的 LinkedHashMap
    Map<String, String> map = new LinkedHashMap<>(16, 0.75f, true);
    map.put("K1", "V1");
    map.put("K2", "V2");

    try {
      // 危险操作：在迭代过程中执行 get() 隐式触发了链表结构重组
      for (Map.Entry<String, String> entry : map.entrySet()) {
        System.out.println("Reading: " + entry.getKey());
        map.get("K1"); // 抛出 ConcurrentModificationException
      }
    } catch (Exception e) {
      System.err.println("捕获预期异常: " + e.toString());
    }
  }
}

实战：手写 LRU 缓存

基于“访问顺序”的特性，LinkedHashMap 天然适合用来实现 LRU（Least Recently Used，最近最少使用）缓存淘汰算法。

LinkedHashMap 专门提供了一个保护方法 removeEldestEntry（移除最老节点）。默认情况下它返回 false，但如果我们重写它，就能实现自动清理老数据的功能：

java

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
  private final int MAX_CAPACITY;

  // 构造函数：开启访问顺序 (accessOrder = true)
  public LRUCache(int capacity) {
    super(capacity, 0.75f, true);
    this.MAX_CAPACITY = capacity;
  }

  // 重写此方法：当 Map 尺寸超过设定的最大容量时，返回 true，自动删除最老的元素
  @Override
  protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
    return size() > MAX_CAPACITY;
  }

  public static void main(String[] args) {
    LRUCache<String, Integer> cache = new LRUCache<>(3);
    cache.put("A", 1);
    cache.put("B", 2);
    cache.put("C", 3);

    System.out.println("初始缓存: " + cache); // {A=1, B=2, C=3}

    cache.get("A"); // 访问了 A，A 会被移到末尾
    System.out.println("访问 A 后: " + cache); // {B=2, C=3, A=1}

    cache.put("D", 4); // 插入 D，此时容量超限(4>3)，触发移除最老元素 B
    System.out.println("插入 D 后: " + cache); // {C=3, A=1, D=4}
  }
}

Map-TreeMap~

~~java.util.TreeMap~~ 是 Java 集合框架中 NavigableMap 接口的红黑树实现。与基于哈希表的 HashMap 和基于双向链表的 LinkedHashMap 不同，TreeMap 内部利用红黑树结构维持键（Key）的严格全序排列，为键值检索、边界查找以及范围区间遍历提供了 $O(\log n)$ 的时间复杂度保证。

底层数据结构

节点寻址与平衡控制

排序和去重机制

API：TreeMap

构造方法

TreeMap TreeMap()：()，构造一个空的 TreeMap，使用键的自然顺序进行排序。所有插入的键必须实现 Comparable 接口。

TreeMap TreeMap()：(Comparator<? super K> comparator)，构造一个空的 TreeMap，并根据指定的比较器进行排序。

java

import java.util.TreeMap;
import java.util.Comparator;
import java.util.Map;

public class TreeMapConstructorDemo {
  public static void main(String[] args) {
    // 1. 自然排序构造
    Map<Integer, String> naturalMap = new TreeMap<>();

    // 2. 自定义比较器构造：创建一个强行逆序（降序）排列的 TreeMap
    Map<Integer, String> reverseMap = new TreeMap<>(Comparator.reverseOrder());

    reverseMap.put(10, "Low");
    reverseMap.put(50, "High");
    reverseMap.put(30, "Medium");

    System.out.println("逆序排列输出: " + reverseMap.keySet()); // [50, 30, 10]
  }
}

增删查

V put()：(K key, V value)，将指定的键值对插入 Map 中。若键已存在，替换旧值。内部会触发红黑树的自平衡。
V get()：(Object key)，根据指定的键获取对应的值。使用二分查找，时间复杂度为 $O(\log n)$ 。

V remove()：(Object key)，根据指定的键移除对应的节点，并触发红黑树的平衡旋转调整。

java

import java.util.TreeMap;

public class TreeMapCrudDemo {
  public static void main(String[] args) {
    TreeMap<String, String> clusterNodes = new TreeMap<>();

    // 1. 写入操作
    clusterNodes.put("node-3", "192.168.0.3");
    clusterNodes.put("node-1", "192.168.0.1");
    clusterNodes.put("node-2", "192.168.0.2");

    // 2. 读取操作
    String ip = clusterNodes.get("node-2");

    // 3. 删除操作
    clusterNodes.remove("node-1");

    System.out.println("节点2的IP: " + ip + ", 剩余节点: " + clusterNodes.keySet());
  }
}

导航与边界检索

K firstKey()：()，返回当前 Map 中最小（排在最前面）的键。若 Map 为空，抛出 NoSuchElementException。
K lastKey()：()，返回当前 Map 中最大（排在最后面）的键。
Map.Entry<K,V> floorEntry()：(K key)，返回小于或等于指定键的最大键所对应的键值对；若不存在符合条件的键，则返回 null。
Map.Entry<K,V> ceilingEntry()：(K key)，返回大于或等于指定键的最小键所对应的键值对；若不存在则返回 null。

Map.Entry<K,V> higherEntry()：(K key)，严格返回大于指定键的最小键所对应的键值对。

java

import java.util.TreeMap;
import java.util.Map;

public class TreeMapNavigationDemo {
  public static void main(String[] args) {
    TreeMap<Integer, String> timeTicks = new TreeMap<>();
    timeTicks.put(100, "Snapshot_1");
    timeTicks.put(200, "Snapshot_2");
    timeTicks.put(500, "Snapshot_3");

    // 1. 获取两端边界键
    Integer first = timeTicks.firstKey(); // 100
    Integer last = timeTicks.lastKey();   // 500

    // 2. 寻找贴近 250 毫秒的地板节点（小于或等于 250 的最大节点）
    Map.Entry<Integer, String> floor = timeTicks.floorEntry(250); // 返回 200=Snapshot_2

    // 3. 寻找贴近 200 毫秒的天花板节点（大于或等于 200 的最小节点）
    Map.Entry<Integer, String> ceiling = timeTicks.ceilingEntry(200); // 返回 200=Snapshot_2

    // 4. 寻找严格大于 200 的节点
    Map.Entry<Integer, String> higher = timeTicks.higherEntry(200); // 返回 500=Snapshot_3

    System.out.println("Floor: " + floor + ", Ceiling: " + ceiling + ", Higher: " + higher);
  }
}

子集视图

NavigableMap<K,V> subMap()：(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)，返回一个子集视图，区间由 formKey 到 toKey。通过布尔值指定是否包含边界。对子集的修改会直接反向作用于原 Map。
NavigableMap<K,V> headMap()：(K toKey, boolean inclusive)，返回小于（或等于，取决于 inclusive）指定键的子集视图。

NavigableMap<K,V> tailMap()：(K fromKey, boolean inclusive)，返回大于（或等于，取决于 inclusive）指定键的子集视图。

java

import java.util.TreeMap;
import java.util.NavigableMap;

public class TreeMapSubMapDemo {
  public static void main(String[] args) {
    TreeMap<String, Integer> scoreBoard = new TreeMap<>();
    scoreBoard.put("Alice", 85);
    scoreBoard.put("Charles", 92);
    scoreBoard.put("Bob", 78);
    scoreBoard.put("David", 60);

    // 排序顺序: Alice(85) -> Bob(78) -> Charles(92) -> David(60) （因Key是名字String，字典序）
    // 1. 截取名字在 "Bob" 到 "David" 之间的子集视图（包含边界）
    NavigableMap<String, Integer> subView = scoreBoard.subMap("Bob", true, "David", true);
    System.out.println("子视图区间: " + subView); // 包含 Bob 和 Charles、David

    // 2. 截取从头到 "Bob"（不包含）的子集
    NavigableMap<String, Integer> headView = scoreBoard.headMap("Bob", false);
    System.out.println("头部视图区间: " + headView); // 仅有 Alice
  }
}

注意事项

null 键的绝对限制：在默认的自然排序模式下，TreeMap 严禁使用 null 作为 Key。写入 null 键会直接抛出 NullPointerException。这是因为红黑树在插入时必须调用 compareTo() 进行大小物理判定。唯一例外是创建 TreeMap 时传入了能够支持并妥善处理 null 比较的自定义 Comparator。

等价判定偏离机制：TreeMap 去重和检索完全不看 equals()，只看 compareTo() 或 compare()。如果两个对象通过 compare比较返回0，即使它们的 equals()返回false，TreeMap也会认为它们是同一个 Key 并执行覆盖。这就要求开发者编写自定义类时，必须严格确保(compare(x, y) == 0) == (x.equals(y)) 的一致性契约。

性能开销损耗：由于红黑树在插入、更新和删除节点时，需要频繁执行对象间的比对以及整树的自平衡旋转（变色、左右旋），因此在纯粹的随机读写场景下，其吞吐性能明显逊色于常数时间复杂度 $O(1)$ 的 HashMap。

Map-Hashtable~

~~java.util.Hashtable~~ 诞生于 JDK 1.0，比大家熟知的 HashMap（诞生于 JDK 1.2）还要古老。

虽然在现代 Java 开发中，Hashtable 已经基本被市场淘汰，沦为了“遗留类（Legacy Class）”，但深入了解它，对于理解 Java 集合框架的演进、线程安全以及面试过关依然大有裨益。

核心特性

我们可以用三个词来概括 Hashtable 的特点：线程安全、拒绝 Null、古老。

线程安全（Thread-Safe）： Hashtable 的底层几乎所有修改和查询方法（如 put、get、remove）都加上了 synchronized 关键字。这意味着它是线程安全的，但代价是极其惨重的并发性能瓶颈。
绝对不允许 Null： 无论是键（Key）还是值（Value），只要有任何一个为 null，Hashtable 就会直接抛出 NullPointerException。（HashMap 允许键或值为 null 值）。
不继承 AbstractMap： 现代的 Map 实现类（如 HashMap, TreeMap）都继承自 AbstractMap，而 Hashtable 继承自古老的 Dictionary 类（该类已被废弃）。

在现代 Java 开发中，你几乎没有任何理由在新的代码里使用 Hashtable。

想线程安全？请出门左转找 ConcurrentHashMap。
不需要线程安全？请出门右转找 HashMap。

底层结构与算法

Hashtable 的底层结构依然是 数组 + 链表。

值得注意的是，在 Java 8 中，HashMap 引入了红黑树优化（当链表长度大于 8 时转为红黑树），而 Hashtable 没有享受这个待遇。时至今日，它的底层依然是纯粹的链表，一旦发生严重的哈希冲突，其查询效率会直接退化到 $O(n)$ 。

独特的寻址与扩容机制

默认初始容量： 11（而 HashMap 是 16）。
扩容公式： 新容量 = 旧容量 * 2 + 1（而 HashMap 是直接翻倍）。
计算索引的方式： Hashtable 采用的是传统的取模法：

\text{index} = (\text{hash} \& 0\text{x}7\text{FFFFFFF}) \% \text{length}

由于扩容公式保证了容量通常是奇数或素数，直接取模就能让散列非常均匀，因此它不需要像 HashMap 那样为了性能非要把容量限制为 2 的幂次方。

淘汰原因

致命的“全表锁”导致性能低下：
Hashtable 保证线程安全的方式非常粗暴——锁住整个数组。
当线程 A 在向 Hashtable 写入数据时，线程 B 哪怕只是想读取一个完全不相关的位置的数据，也必须在外面排队等待。在高并发场景下，这里会成为严重的性能死结。
现代替代方案更优秀：
- 单线程或无需考虑线程安全： 用 HashMap，速度极快。
- 多线程高并发： 用 ConcurrentHashMap。它在 Java 8 中利用 CAS 原子操作和颗粒度极小的 synchronized 锁（只锁住链表的头节点），实现了读写并发，性能完爆 Hashtable。

历史遗留：Enumeration

如果你在阅读一些十几年前的老项目源码，可能会看到这样的遍历方式：

java

Hashtable<String, Integer> numbers = new Hashtable<>();
numbers.put("One", 1);

// 古老的迭代器：Enumeration
Enumeration<String> keys = numbers.keys();
while (keys.hasMoreElements()) {
  String key = keys.nextElement();
  System.out.println(key + " = " + numbers.get(key));
}

注意： Enumeration 是 Iterator 的前身。它的缺点是不支持 fail-fast（快速失败）。也就是说，在你用 Enumeration 遍历集合时，如果另一个线程偷偷删除了一个元素，Enumeration 可能不会立即报错，而是引发不可预期的诡异行为。因此，日常开发请一律使用 Iterator 或 forEach。

Map-Hashtable-Properties~

~~java.util.Properties~~ 类是 Java 语言中历史悠久的持久化属性配置集。它继承自 java.util.Hashtable<Object, Object>，用于处理属性文件（通常以 .properties 或 .xml 为后缀）。其核心特征是键（Key）和值（Value）在实际应用中默认均为字符串（String）类型，并且提供了极其便利的流（Stream）持久化读写能力。

核心特性

既然继承自 Hashtable，它自然带有老一辈的基因，但它也有自己独特的规矩：

键值对必须是字符串：尽管它继承了 Hashtable 的 put(Object, Object) 方法，但官方强烈建议只存储 String 类型的 Key 和 Value。
天然支持持久化（Persistence）：它自带将内存中的键值对直接写入文件，或者从文件中加载到内存中的方法（load / store）。
线程安全：由于老爹 Hashtable 的方法都加了锁，Properties 也是线程安全的，但通常我们只在程序启动时读取配置，因此并发性能并不是它的核心瓶颈。

核心原理

Properties 内部采用哈希表结构存储键值对，其行为深度依赖于父类 Hashtable 的同步机制。

默认属性链机制

Properties 在实例化时支持传入另一个 Properties 对象作为其默认兜底数据（defaults）。

当调用 getProperty(key) 检索某项配置时：

系统首先在当前 Properties 实例内部的哈希表中进行检索。
若未命中，且初始化时指定了 defaults 属性集，则会自动递归进入 defaults 属性集中进行二次查找。

这种双层或多层嵌套的设计，构成了 Java 早期配置管理中经典的“全局默认配置 + 局部自定义覆盖”的架构模式。

java

import java.util.Properties;

public class PropertiesCoreDemo {
  public static void main(String[] args) {
    // 1. 创建全局默认配置
    Properties defaultCfg = new Properties();
    defaultCfg.setProperty("server.port", "8080");
    defaultCfg.setProperty("server.servlet.context-path", "/api");

    // 2. 创建用户自定义配置，并将默认配置注入作为兜底
    Properties customCfg = new Properties(defaultCfg);
    // 覆盖默认的端口设置
    customCfg.setProperty("server.port", "9090");

    // 3. 读取检索
    // 命中自定义配置，输出 9090
    System.out.println("Port: " + customCfg.getProperty("server.port"));
    // 未命中自定义配置，触发兜底机制，输出 /api
    System.out.println("Context Path: " + customCfg.getProperty("server.servlet.context-path"));
  }
}

持久化存储规范

Properties 支持通过流操作与物理介质进行数据交换。

标准文本格式：
- 属性以 key=value 或 key:value 的行文本形式存储（=和:左右不要有空格，会有歧义）。
- 每一行代表一个映射。
- # 或 ! 开始的行被视作注释。
XML 格式：支持符合 properties.dtd 规范的 XML 结构定义，便于跨语言或环境进行复杂配置解析。

API：Properties

专用替代方法

因为专门用来处理配置，它提供了一套比普通 Map 更符合语义的方法，请尽量用这套方法代替 put/get：

专有方法	对应 Map 方法	作用解释
`setProperty(String key, String value)`	`put(K, V)`	设置配置项。
`getProperty(String key)`	`get(Object)`	获取配置项。
`getProperty(String key, String defaultValue)`	`getOrDefault`	获取配置项，若不存在则返回默认值（极其常用）。
`load(InputStream/Reader)`	无	从配置文件（输入流）中加载键值对。
`store(OutputStream/Writer, comments)`	无	将内存中的配置保存到文件，并可附带注释。

构造方法

Properties Properties()：()，构造一个没有默认值的空属性列表。

Properties Properties()：(Properties defaults)，构造一个带有指定默认属性列表的空属性列表。常用于多层级配置覆盖及兜底场景。

java

import java.util.Properties;

public class PropertiesConstructorDemo {
  public static void main(String[] args) {
    // 1. 无参构造
    Properties rootConfig = new Properties();
    rootConfig.setProperty("app.name", "CloudGateway");

    // 2. 携带默认属性表的构造
    Properties clusterConfig = new Properties(rootConfig);

    System.out.println("Properties 实例初始化就绪。基于父配置的实例大小: " + clusterConfig.size());
  }
}

读写操作

Object setProperty()：(String key, String value)：设置配置项。调用父类的 put 方法。强制限制键与值必须为 String，返回旧值（若无则返回 null）。
String getProperty()：(String key)：获取配置项。在当前属性列表中搜索指定键。若未命中则自动转向默认属性列表（defaults）检索。
String getProperty()：(String key, String defaultValue)：获取配置项。在属性列表中搜索指定键。若最终未命中，则直接返回指定的默认兜底字符串。

Set<String> stringPropertyNames()：()：返回此属性列表中的键集，包含默认属性列表中的键。返回的 Set 仅包含键值均为字符串的条目。

java

import java.util.Properties;
import java.util.Set;

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

    // 1. 严格的 String 类型写入
    props.setProperty("database.url", "jdbc:mysql://localhost:3306/db");
    props.setProperty("database.username", "root");

    // 2. 基础读取与容错读取
    String url = props.getProperty("database.url");
    String timeout = props.getProperty("database.timeout", "3000"); // 缺失时返回默认值

    // 3. 获取所有显式及隐式继承的 String 键集
    Set<String> keys = props.stringPropertyNames();

    System.out.println("URL: " + url + " | Timeout: " + timeout + " | Keys: " + keys);
  }
}

持久化与流操作

void load()：(InputStream inStream)，从字节输入流中读取键值对属性列表。要求输入流采用 ISO-8859-1 字符编码。
void load()：(Reader reader)，从字符输入流中读取键值对属性列表。允许直接处理包含指定任意字符编码（如 UTF-8） 的文本。
void store()：(OutputStream out, String comments)，将当前实例中的属性列表写入字节输出流。comments 为写入文本头部的说明注释。

void store()：(Writer writer, String comments)，将当前实例中的属性列表通过字符输出流持久化。适合需要明确指定文本编码格式的场景。

java

import java.util.Properties;
import java.io.StringReader;
import java.io.StringWriter;
import java.io.IOException;

public class PropertiesStreamDemo {
  public static void main(String[] args) throws IOException {
    // 模拟外部属性文件的配置文本流
    String fileContent = "service.auth.enabled=true\nservice.auth.jwt-secret=K9821A\n";

    Properties appProps = new Properties();

    // 1. 基于 Reader 字符流加载配置数据
    try (StringReader reader = new StringReader(fileContent)) {
      appProps.load(reader);
    }

    // 打印载入的数据
    System.out.println("载入后配置: " + appProps.getProperty("service.auth.jwt-secret"));

    // 2. 将当前配置重新序列化输出到外部字符流
    StringWriter writer = new StringWriter();
    appProps.store(writer, "Global Security Settings Snapshot");

    System.out.println("\n--- 持久化输出文本如下 ---");
    System.out.println(writer.toString());
  }
}

历史痛点

作为 JDK 1.0 延续至今的古老设计，Properties 身上有两处经常被后世架构师吐槽的痛点：

继承 Hashtable 是个“设计失误”：
在面向对象设计中，这违反了里氏替换原则（LSP）。因为 Properties 继承了 Hashtable，导致它暴露了 put(Object, Object) 方法。
翻车现场： 如果程序员不小心执行了 prop.put("port", 8080);（传入了 Integer），代码编译不会报错。但在后续调用 prop.store() 保存文件时，代码内部会强转成 String，直接抛出 ClassCastException 导致程序崩溃。
让人头疼的“中文乱码”历史：
- 早期（Java 8 及以前）： Properties 文件默认只能以 ISO-8859-1 编码读取。如果配置文件里写了中文，直接读取就会变成一堆乱码 ãã¹。过去开发者不得不使用 JDK 自带的 native2ascii 工具把中文转成 \u4e2d\u6587 这样的 Unicode 码。
- 现代（Java 9 及以后）： 官方终于修复了这个历史遗留问题，默认改用 UTF-8 编码来读取 .properties 文件，中文乱码的问题在现代 Java 版本中基本绝迹。

现代替代方案

虽然 Properties 在原生的 Java 基础组件（如 Log4j、JDBC、Quartz）中无处不在，但在如今的现代企业级开发（如 Spring Boot、Micronaut）中，它的江湖地位正在逐渐被以下方案取代或包装：

YAML (.yml) / JSON： 结构更清晰，天然支持多层嵌套和列表结构（Properties 只能表达扁平的一层结构）。
Spring 的 @Value 与 @ConfigurationProperties： 虽然底层可能依然基于 .properties 或 .yml，但上层直接实现了自动注入和对象绑定，不再需要开发者手动去写 load() 和 getProperty() 了。

实战：读取与保存配置文件

在实际开发中，我们最常用的就是将它与 IO 流结合，进行配置的读写。

~~一、将配置保存到 .properties 文件~~：

java

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

public class PropertiesWriteDemo {
  public static void main(String[] args) {
    Properties prop = new Properties();

    // 1. 设置配置信息（只能是 String）
    prop.setProperty("database.url", "jdbc:mysql://localhost:3306/mydb");
    prop.setProperty("database.user", "root");
    prop.setProperty("database.password", "secret123");

    // 2. 使用字节输出流保存到文件
    try (FileOutputStream out = new FileOutputStream("config.properties")) {
      // 参数二为注释，会写在文件第一行
      prop.store(out, "Database Connection Settings");
      System.out.println("配置保存成功！");
    } catch (IOException e) {
      e.printStackTrace();
    }
  }
}

生成的 config.properties 文件内容如下：

properties

#Database Connection Settings
#Thu Jun 04 12:32:25 CST 2026
database.password=secret123
database.url=jdbc\:mysql\://localhost\:3306/mydb
database.user=root

~~二、从 .properties 文件读取配置~~：

java

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

public class PropertiesReadDemo {
  public static void main(String[] args) {
    Properties prop = new Properties();

    // 1. 使用字节输入流加载文件
    try (FileInputStream in = new FileInputStream("config.properties")) {
      prop.load(in);

      // 2. 读取配置
      String url = prop.getProperty("database.url");
      String user = prop.getProperty("database.user");
      // 演示带有默认值的读取：如果不存在 "timeout"，则返回 "30"
      String timeout = prop.getProperty("database.timeout", "30");

      System.out.println("URL: " + url);
      System.out.println("User: " + user);
      System.out.println("Timeout: " + timeout);
    } catch (IOException e) {
      e.printStackTrace();
    }
  }
}

Collections~

~~java.util.Collections~~ 是 Java 集合框架中的核心工具类。与操作数组的 java.util.Arrays 类似，它提供了一系列静态方法，用于对集合进行排序、查找、线程安全同步化、并发控制以及类型检查等操作。

java.util.Collections 是一个 final 类，其构造方法被私有化，无法被实例化。它的核心设计思想是装饰器模式（Decorator Pattern）和多态算法。

装饰器设计模式

Collections 提供的 ~~synchronizedXxx()~~ 和 ~~unmodifiableXxx()~~ 系列方法，并没有创建全新的集合对象。它们在底层构建了一个内部包装类（如 SynchronizedList 或 UnmodifiableList），该包装类持有原集合的引用，并通过代理机制扩展或限制原集合的行为：

只读限制：在 Unmodifiable 包装器中，所有修改集合结构的方法（如 add(), remove(), set()）都会直接抛出 UnsupportedOperationException。
互斥同步：在 Synchronized 包装器中，所有包装方法内部都包裹在 synchronized(mutex) 同步块中，从而实现线程安全。

视图与引用的底层关联

无论是同步包装器还是不可变包装器，它们返回的都是原集合的视图（View）。

如果绕过包装器，直接修改底层的原集合，包装器视图中的内容会同步发生改变。这种特性在多线程或安全边界开发中需要格外注意。

java

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

public class CollectionsCorePrinciple {
  public static void main(String[] args) {
    // 1. 创建底层原集合
    List<String> rawList = new ArrayList<>();
    rawList.add("Data1");

    // 2. 生成不可变包装视图
    List<String> unmodifiableView = Collections.unmodifiableList(rawList);
    System.out.println("不可变视图初始内容: " + unmodifiableView);

    // 3. 绕过视图直接修改原集合
    rawList.add("Data2");

    // 4. 视图内容发生了级联改变
    System.out.println("修改原集合后，不可变视图的内容: " + unmodifiableView);
  }
}

`RandomAccess` 二分检索优化

当调用 Collections.binarySearch() 时，算法内部会优先通过 instanceof 检测目标 List 是否实现了 ~~RandomAccess~~ 标记接口（例如 ArrayList）。

索引二分查找：如果支持随机访问，算法采用标准的双指针中位线索引定位，时间复杂度为 $O(\log n)$ 。
迭代器二分查找：如果不支持（如 LinkedList），算法则被迫降级使用 Iterator 移动指针。此时，由于链表寻址的时间复杂度为 $O(n)$ ，即使使用了二分折半逻辑，整体时间复杂度依然会退化至 $O(n)$ 。

Fisher-Yates 洗牌算法

Collections.shuffle() 的底层实现采用了经典的 ~~Fisher-Yates 洗牌算法~~。它从列表的最后一个元素开始，向前遍历，并在每一轮中随机生成一个当前范围内的索引，将当前元素与随机索引处的元素进行原地交换。该算法保证了每一种排列组合生成的概率都是绝对均等的，空间复杂度为 $O(1)$ 。

API：Collections

排序与数据打乱【

本功能组用于对线性集合（List）进行顺序重构、乱序洗牌以及逆序颠倒。

<T extends Comparable<? super T>> void
Collections.sort()：(List<T> list)，对传入的 List 集合按元素的自然顺序执行原地升序排列。
void Collections.shuffle()：(List<?> list)，使用默认的随机源对指定的 List 集合执行洗牌（随机打乱）操作。常用于游戏发牌、随机抽奖场景。
void Collections.reverse()：(List<?> list)，反转指定列表中元素的顺序。
【swap】

注意事项：
Collections.sort() 在 Java 8 之后的底层实现已直接代理给 List.sort() 方法。
Collections.shuffle() 会直接改变原集合的物理顺序。如果原集合是基于 Arrays.asList() 生成的，洗牌操作会级联导致原原生数组的内容被连带打乱。

java

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

public class CollectionsSortPermutationFunctionalGroup {
  public static void main(String[] args) {
    // 示例 1: 初始化扑克牌点数列表
    List<String> cards = new ArrayList<>(Arrays.asList("A", "2", "3", "4", "5"));

    // 1. 洗牌打乱
    Collections.shuffle(cards);
    System.out.println("洗牌后的顺序: " + cards);

    // 2. 自然排序（String 按字母/数字字典序）
    Collections.sort(cards);
    System.out.println("排序后的顺序: " + cards);

    // 3. 元素反转
    Collections.reverse(cards);
    System.out.println("反转后的顺序: " + cards);
  }
}

元素检索【

本功能组用于高效查找集合中的极值、精确定位目标索引。

<T extends Object & Comparable<? super T>> T
Collections.max()
Collections.min()：(Collection<? extends T> coll)，根据元素的自然顺序，返回给定集合的最大/最小元素。
<T> int Collections.binarySearch()：(List<? extends Comparable<? super T>> list, T key)，使用二分搜索算法在已排序的有序 List 中寻找指定键值的索引。
【frequency】

注意事项：
传递给 binarySearch 的列表必须是有序的，否则返回值毫无意义（逻辑与 Arrays.binarySearch 一致）。
Collections.max() 和 Collections.min() 会对整个集合执行一次全量 $O(n)$ 线性遍历。在高频调用且集合规模巨大的场景下，建议在数据写入时通过优先队列（PriorityQueue）动态维护极值，避免重复扫描。

java

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

public class CollectionsSearchReplaceFunctionalGroup {
  public static void main(String[] args) {
    List<Integer> numbers = new ArrayList<>();
    numbers.add(10);
    numbers.add(40);
    numbers.add(30);
    numbers.add(40); // 重复元素

    // 示例 1: 查找全局最大值
    int maxVal = Collections.max(numbers);
    System.out.println("集合中的最大值: " + maxVal);

    // 示例 2: 批量替换指定元素
    Collections.replaceAll(numbers, 40, 99);
    System.out.println("批量替换后的集合: " + numbers);

    // 示例 3: 二分查找（先排序，后查找）
    Collections.sort(numbers); // 排序后：[10, 30, 99, 99]
    int target = 30;
    int index = Collections.binarySearch(numbers, target);
    System.out.println("元素 " + target + " 在排序后集合中的索引为: " + index);
  }
}

复制与替换【

【copy】
<T> boolean Collections.replaceAll()：(List<T> list, T oldVal, T newVal)，使用一个新值替换列表中所有出现的指定旧值。

集合工厂与快捷创建

本功能组用于快速生成特定结构（空、单例、多副本）的轻量级紧凑集合。

<T> List<T> Collections.emptyList()：()，返回一个不可变的空列表。常用于方法返回值兜底，避免产生大量的 null 指针或重复创建空对象。
<T> List<T> Collections.singletonList()：(T o)，返回一个仅包含指定对象的不可变列表。适用于仅需单个元素的 API 适配对接。
<T> List<T> Collections.nCopies()：(int n, T o)，返回由指定对象的 n 个副本组成的不可变列表。其底层并非真正克隆了 n 个独立对象，而是通过计数器实现的高效虚拟视图。

注意事项：
这三个工厂方法返回的集合全部是不可变集合。尝试对它们执行 add 或 remove 会直接引发 UnsupportedOperationException。其中 nCopies 返回的集合中，所有索引指向的都是同一个对象的引用，修改该对象的属性会引发整体连锁反应。

java

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

public class CollectionsFactoryFunctionalGroup {
  public static void main(String[] args) {
    // 示例 1: 安全返回值兜底
    List<String> emptyData = Collections.emptyList();
    System.out.println("空集合工厂实例: " + emptyData + ", 长度: " + emptyData.size());

    // 示例 2: 快速构建单元素列表
    List<String> currentTask = Collections.singletonList("Report-Job");
    System.out.println("单例集合内容: " + currentTask);

    // 示例 3: 虚拟副本集合（低内存占用）
    List<Integer> initialWeights = Collections.nCopies(1000, 1);
    System.out.println("多副本集合长度: " + initialWeights.size() + ", 首元素: " + initialWeights.get(500));
  }
}

不可变包装器

本功能组用于为现有集合创建只读视图，保护核心数据不被外部恶意或误操作修改。

<T> List<T> Collections.unmodifiableList()：(List<? extends T> list)，返回指定列表的不可变视图。对外屏蔽写操作。
<K,V> Map<K,V> Collections.unmodifiableMap()：(Map<? extends K, ? extends V> m)，返回指定映射的不可变视图。常用于对外暴露配置项。
<T> Set<T> Collections.unmodifiableSet()：(Set<? extends T> s)，返回指定集合的不可变视图。

注意事项：
不可变包装器提供的只是浅不可变性（Shallow Unmodifiability）。如果集合中存储的是可变对象（如自定义的 User 对象），外部虽然无法增删集合元素，但依然可以通过 list.get(0).setName() 修改集合内部对象的属性。

java

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

public class CollectionsUnmodifiableFunctionalGroup {
  public static void main(String[] args) {
    // 示例 1: 建立 Map 的只读全局配置视图
    Map<String, String> configData = new HashMap<>();
    configData.put("endpoint", "https://api.domain.com");
    configData.put("timeout", "5000");

    Map<String, String> readOnlyConfig = Collections.unmodifiableMap(configData);
    System.out.println("全局配置加载成功: " + readOnlyConfig);

    try {
      readOnlyConfig.put("timeout", "3000"); // 尝试修改
    } catch (UnsupportedOperationException e) {
      System.out.println("安全拦截：拒绝修改全局只读配置映射");
    }

    // 示例 2: 浅不可变性证明
    List<StringBuilder> builderList = new ArrayList<>();
    builderList.add(new StringBuilder("Alpha"));

    List<StringBuilder> readOnlyList = Collections.unmodifiableList(builderList);
    // readOnlyList.add(new StringBuilder("Beta")); // 报错

    // 依然可以修改元素内部的状态
    readOnlyList.get(0).append("-Mutated");
    System.out.println("元素内部状态被篡改: " + readOnlyList);
  }
}

同步包装器

本功能组用于将非线程安全的普通集合转化为线程安全的同步集合。

<T> List<T> Collections.synchronizedList()：(List<T> list)，返回由指定列表支持的同步（线程安全）列表。
<K,V> Map<K,V> Collections.synchronizedMap()：(Map<K,V> m)，返回由指定映射支持的同步（线程安全）映射。

注意事项：
迭代器并发陷阱：使用 Collections.synchronizedList() 返回的同步集合在执行单个原子操作（如 add, remove）时是线程安全的。但是，当使用 Iterator、for-each 或者是 Stream 进行组合式遍历操作时，它无法自动保证并发安全。
手动加锁要求：在遍历同步集合时，必须显式地对包装后的集合对象本身进行 synchronized 静态块加锁，否则在多线程高并发下会抛出 ConcurrentModificationException。在要求高性能并发的场景下，推荐引入 CopyOnWriteArrayList 或 ConcurrentHashMap 代替同步包装器。

java

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

public class CollectionsSynchronizedFunctionalGroup {
  public static void main(String[] args) throws InterruptedException {
    // 示例 1: 初始化同步安全列表
    List<Integer> syncList = Collections.synchronizedList(new ArrayList<>());

    // 模拟多线程安全写入
    Thread t1 = new Thread(() -> {
      for (int i = 0; i < 5; i++) syncList.add(i);
    });
    Thread t2 = new Thread(() -> {
      for (int i = 5; i < 10; i++) syncList.add(i);
    });

    t1.start(); t2.start();
    t1.join();  t2.join();
    System.out.println("多线程并发写入后的同步列表长度: " + syncList.size());

    // 示例 2: 并发遍历时的正确加锁姿势
    Thread t3 = new Thread(() -> {
      // 必须对包装后的视图对象 syncList 加锁，锁住整个遍历块
      synchronized (syncList) {
        Iterator<Integer> iterator = syncList.iterator();
        while (iterator.hasNext()) {
          System.out.print(iterator.next() + " ");
        }
        System.out.println();
      }
    });
    t3.start();
    t3.join();
  }
}

实战：洗牌与发牌功能

~~场景说明~~：

模拟一个在线卡牌电竞游戏（如炉石传说、德州扑克）的后端洗牌与发牌核心调度器。

系统需要安全、零资源开销地初始化一套标准的空扑克牌盒。
批量生成一套包含 52 张牌的卡组，并利用 Fisher-Yates 算法进行高效洗牌打乱。
模拟发牌给多位玩家。
检索某一位玩家手中点数最大的一张牌，并快速检索牌堆中是否还残留着特定的“王牌”。

~~完整源码~~：

java

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

public class CardGameDispatcher {

  // 扑克牌标准卡牌类
  static class Card implements Comparable<Card> {
    String suit; // 花色
    int rank;    // 点数大小 (2-14, 14代表A)

    public Card(String suit, int rank) {
      this.suit = suit;
      this.rank = rank;
    }

    @Override
    public int compareTo(Card o) {
      return Integer.compare(this.rank, o.rank); // 按点数大小升序排列
    }

    @Override
    public String toString() {
      String rankStr = switch(rank) {
        case 11 -> "J"; case 12 -> "Q"; case 13 -> "K"; case 14 -> "A";
        default -> String.valueOf(rank);
      };
      return suit + rankStr;
    }
  }

  public static void main(String[] args) {
    // 1. 安全初始化：若游戏未开始，默认发牌列表返回空工厂集合，避免外部产生 null 崩溃
    List<Card> tableCards = Collections.emptyList();
    System.out.println("1. 游戏准备中，桌面中央牌堆状态: " + tableCards);

    // 2. 生成标准牌堆
    List<Card> deck = new ArrayList<>();
    String[] suits = {"♠", "♥", "♣", "♦"};
    for (String suit : suits) {
      for (int rank = 2; rank <= 14; rank++) {
        deck.add(new Card(suit, rank));
      }
    }
    System.out.println("2. 初始牌堆构建完毕，总计张数: " + deck.size());

    // 3. 调用高效洗牌算法打乱卡组
    Collections.shuffle(deck);
    System.out.println("3. 经历 Fisher-Yates 算法洗牌后的前 5 张牌视图: " + deck.subList(0, 5));

    // 4. 模拟发牌给玩家1（分发 3 张牌）
    List<Card> playerHand = new ArrayList<>();
    for (int i = 0; i < 3; i++) {
      playerHand.add(deck.remove(0)); // 从牌堆顶部抽牌
    }
    System.out.println("4. 玩家 1 手牌: " + playerHand);

    // 5. 检索玩家手牌中的最强战力（极值查找）
    Card maxCard = Collections.max(playerHand);
    System.out.println("5. 玩家 1 手中的最大王牌为: " + maxCard);

    // 6. 裁判盲测：对当前剩余牌堆进行排序，并二分查找是否还存在“黑桃A”（花色不计，仅看点数14）
    Collections.sort(deck); // 二分查找前必须排序
    Card targetAce = new Card("♠", 14);
    int searchResult = Collections.binarySearch(deck, targetAce);

    if (searchResult >= 0) {
      System.out.println("6. 战术分析：牌堆中仍残存点数为 A 的底牌，其在剩余牌堆索引为: " + searchResult);
    } else {
      System.out.println("6. 战术分析：所有的 A 已全部被分发完毕。");
    }
  }
}

S04-01 集合框架-Map ​

概述 ​

数组的痛点 ​

集合框架组成 ​

Map 接口 ​

Collection 接口 ​

List 接口 ​

Set 接口 ​

Queue/Deque 接口 ​

集合类对比 ​

工具类 ​

线程安全与并发集合类 ​

Iterator~ ​

核心工作原理 ​

API：Iterator ​

基础迭代操作 ​

迭代修改操作 ​

批量函数式操作 ​

快速失败（Fail-Fast）机制 ​

For-Each 循环 ​

ListIterator~ ​

实战：库存筛选系统 ​

Map~ ​

核心特性 ​

核心原理 ​

核心实现类 ​

API：Map ​

增删改查 ​

判断与大小 ​

集合视图与遍历 ​

高级与静态工厂操作 ​

遍历方式 ​

entrySet()@ ​

Lambda 与 forEach ​

keySet() 加 get() ​

选型建议 ​

Map-HashMap~ ​

底层数据结构 ​

核心参数与概念 ​

工作原理 ​

哈希算法：扰动函数@ ​

寻址算法：定位数组下标@ ​

扩容机制 ​

API：HashMap ​

构造方法 ​

数据操作 ​

进阶弹性计算 ​

注意事项 ​

线程不安全 ​

Key 的不变量要求 ​

实战：高并发网关限流计数器 ​

Map-HashMap-LinkedHashMap~ ​

底层数据结构 ​

排序模式 ​

性能对比 HashMap ​

API：LinkedHashMap ​

构造方法 ​

驱逐策略与钩子 ​

注意事项 ​

实战：手写 LRU 缓存 ​

Map-TreeMap~ ​

底层数据结构 ​

节点寻址与平衡控制 ​

排序和去重机制 ​

API：TreeMap ​

构造方法 ​

增删查 ​

导航与边界检索 ​

子集视图 ​

注意事项 ​

Map-Hashtable~ ​

核心特性 ​

底层结构与算法 ​

独特的寻址与扩容机制 ​

淘汰原因 ​

历史遗留：Enumeration ​

Map-Hashtable-Properties~ ​

核心特性 ​

核心原理 ​

默认属性链机制 ​

S04-01 集合框架-Map

概述

数组的痛点

集合框架组成

Map 接口

Collection 接口

List 接口

Set 接口

Queue/Deque 接口

集合类对比

工具类

线程安全与并发集合类

Iterator~

核心工作原理

API：Iterator

基础迭代操作

迭代修改操作

批量函数式操作

快速失败（Fail-Fast）机制

For-Each 循环

ListIterator~

实战：库存筛选系统

Map~

核心特性

核心原理

核心实现类

API：Map

增删改查

判断与大小

集合视图与遍历

高级与静态工厂操作

遍历方式

`entrySet()`@

Lambda 与 `forEach`

`keySet()` 加 `get()`

选型建议

Map-HashMap~

底层数据结构

核心参数与概念

工作原理

哈希算法：扰动函数@

寻址算法：定位数组下标@

扩容机制

API：HashMap

构造方法

数据操作

进阶弹性计算

注意事项

线程不安全

Key 的不变量要求

实战：高并发网关限流计数器

Map-HashMap-LinkedHashMap~

底层数据结构

排序模式

性能对比 HashMap

API：LinkedHashMap

构造方法

驱逐策略与钩子

注意事项

实战：手写 LRU 缓存

Map-TreeMap~

底层数据结构

节点寻址与平衡控制

排序和去重机制

API：TreeMap

构造方法

增删查

导航与边界检索

子集视图

注意事项

Map-Hashtable~

核心特性

底层结构与算法

独特的寻址与扩容机制

淘汰原因

历史遗留：Enumeration

Map-Hashtable-Properties~

核心特性

核心原理

默认属性链机制