✨博客主页： https://blog.csdn.net/m0_63815035?type=blog

💗《博客内容》：大数据、AI开发、Java、测试开发、Python、Android、Go、Node、Android前端小程序等相关领域知识
📢博客专栏： https://blog.csdn.net/m0_63815035/category_11954877.html
📢欢迎点赞 👍 收藏 ⭐留言 📝
📢本文为学习笔记资料，如有侵权，请联系我删除，疏漏之处还请指正🙉
📢大厦之成，非一木之材也；大海之阔，非一流之归也✨

本篇文章涵盖 ArrayList/LinkedList 源码细节、HashMap 完整原理（含红黑树、扩容、扰动函数）、Set 底层实现、迭代器 fail-fast 机制、并发容器简介、Comparable/Comparator 深入、Collections 工具类全解、Properties 详解 以及 实际开发建议。所有代码均可直接运行。

---

一、容器概览与设计目的

1.1 为什么需要容器（集合框架）

• 数组的局限：长度固定，只能存储同类型元素，增删操作需要手动移动元素。
• 动态管理：程序运行时无法预知需要存储多少对象（如数据库查询结果）。
• 统一操作：Java 集合框架提供统一的接口和算法，降低学习成本。

1.2 容器框架的核心接口

Iterable (根接口，提供 for-each 支持)
│
└── Collection
     ├── List
     ├── Set
     └── Queue
Map (独立分支)

• Collection：单值存储。
• Map：键值对存储。

---

二、List 接口详解

2.1 ArrayList 源码核心（JDK 1.8）

2.1.1 底层结构

transient Object[] elementData;   // 存储元素的数组
private int size;                 // 实际元素个数

2.1.2 构造方法

// 无参构造：初始为空数组，第一次 add 时扩容到 10
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 指定初始容量
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
    }
}

2.1.3 扩容机制

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5 倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

• 每次扩容为原来的 1.5 倍（oldCapacity + oldCapacity / 2）。
• 使用 Arrays.copyOf 复制原数组，开销较大。
• 建议：如果能预估元素个数，使用 ArrayList(int initialCapacity) 减少扩容。

2.1.4 add 和 remove 的时间复杂度

操作	时间复杂度	说明
尾部添加 add(e)	均摊 O(1)	偶尔扩容 O(n)
指定位置添加 add(i, e)	O(n)	需要移动元素
尾部删除 remove(size-1)	O(1)	直接置 null
指定位置删除 remove(i)	O(n)	移动元素
随机访问 get(i)	O(1)	数组特性

2.2 LinkedList 源码核心

2.2.1 底层双向链表节点

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;
    }
}

2.2.2 关键字段

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

2.2.3 插入与删除效率

• 在头部或尾部插入/删除：O(1)（addFirst、addLast、removeFirst、removeLast）。
• 在指定位置插入/删除：需要先遍历到该位置 O(n)，然后再修改前后指针 O(1)。
• 随机访问 get(index)：O(n)，需要通过循环或二分折半查找。

2.2.4 LinkedList 作为双端队列

实现了 Deque 接口，可当作栈、队列使用。

Deque<String> stack = new LinkedList<>();
stack.push("A");     // 压栈
String top = stack.pop();   // 弹栈

Deque<String> queue = new LinkedList<>();
queue.offer("A");    // 入队
String head = queue.poll(); // 出队

2.3 Vector 与 Stack（不推荐使用）

• Vector 与 ArrayList 类似，但方法使用 synchronized 修饰，线程安全，但性能差。
• Stack 继承 Vector，被 Deque 取代。

---

三、Set 接口详解

3.1 HashSet 底层 —— 实际上是一个 HashMap

public class HashSet<E> extends AbstractSet<E> implements Set<E>, ... {
    private transient HashMap<E,Object> map;
    private static final Object PRESENT = new Object();

    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }
}

• HashSet 的元素作为 HashMap 的 Key，Value 是一个固定的占位对象 PRESENT。
• 因此元素的唯一性完全由 HashMap 的 Key 唯一性保证。

3.2 重写 hashCode 和 equals 的必要性

• HashSet 判断两个对象是否相等：先比较 hashCode()，若相等再比较 equals()。
• 若只重写 equals 而不重写 hashCode，则两个逻辑相等的对象可能被放入不同桶中，导致重复。
• 必须同时重写，且保持一致。

3.3 LinkedHashSet

• 继承 HashSet，底层使用 LinkedHashMap，维护插入顺序的双向链表。
• 遍历顺序与插入顺序一致。

3.4 TreeSet

• 底层是 TreeMap（红黑树），元素可排序。
• 元素必须实现 Comparable 或在构造时传入 Comparator。

Set<String> treeSet = new TreeSet<>();          // 自然排序
Set<String> treeSet2 = new TreeSet<>(Comparator.reverseOrder()); // 倒序

---

四、Map 接口详解（重点）

4.1 HashMap 核心原理（JDK 1.8）

4.1.1 数据结构

• 数组 + 单向链表 + 红黑树。
• 数组的每个元素称为桶（bucket），每个桶可以是链表或红黑树。

4.1.2 重要常量

常量	默认值	说明
DEFAULT_INITIAL_CAPACITY	16	默认初始容量
MAXIMUM_CAPACITY	1 << 30	最大容量
DEFAULT_LOAD_FACTOR	0.75f	默认加载因子
TREEIFY_THRESHOLD	8	链表长度 ≥ 8 且数组长度 ≥ 64 转红黑树
UNTREEIFY_THRESHOLD	6	树节点 ≤ 6 转回链表
MIN_TREEIFY_CAPACITY	64	链表树化最小数组长度

4.1.3 put 方法流程

1. 计算 key 的 hash 值：(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)（扰动函数，使高位参与运算，减少碰撞）。
2. 计算桶索引：(n - 1) & hash（等价于 hash % n，但位运算更快）。
3. 如果该桶为空，直接创建节点放入。
4. 如果桶不为空，判断第一个节点是否与当前 key 相等（hash 相等且 equals），是则覆盖。
5. 否则，如果是树节点，执行红黑树插入。
6. 否则，遍历链表，若找到相同 key 则覆盖，否则在尾部插入新节点。
7. 插入后检查链表长度是否 ≥ TREEIFY_THRESHOLD，是则转为红黑树。
8. 检查 ++size > threshold，是则扩容。

4.1.4 扩容机制

• 触发条件：size > capacity * loadFactor。
• 新容量：oldCap << 1（翻倍）。
• 重哈希：重新计算每个元素的桶位置。由于容量是 2 的幂，元素的新位置要么不变，要么变为 原位置 + oldCap，只需判断原 hash 的第 oldCap 位是否为 1，效率很高。

// 扩容后重新分配元素（简化示意）
if ((e.hash & oldCap) == 0) {
    // 保持原位置
} else {
    // 移动到 oldIndex + oldCap
}

4.1.5 加载因子为什么是 0.75

• 空间利用率 与 冲突率 的折衷。
• 过大（如 1.0）：空间利用率高，但链表变长，查询效率低。
• 过小（如 0.5）：频繁扩容，空间浪费。
• 0.75 是统计学上的经验值。

4.1.6 红黑树的作用

• 当链表过长时，查找时间复杂度从 O(n) 降为 O(log n)。
• 红黑树是一种近似平衡的二叉搜索树，插入删除也保持 O(log n)。

4.2 LinkedHashMap

• 继承 HashMap，内部维护双向链表记录插入顺序或访问顺序（accessOrder）。
• 可用于实现 LRU 缓存。

// 构造 accessOrder=true 表示按访问顺序排序
LinkedHashMap<K,V> lru = new LinkedHashMap<K,V>(16, 0.75f, true);

4.3 TreeMap

• 基于红黑树，Key 可排序。
• 支持 subMap、headMap、tailMap 等范围视图。

4.4 ConcurrentHashMap（简单介绍）

• 线程安全的高性能 Map。
• JDK 1.7 使用分段锁（Segment），JDK 1.8 使用 CAS + synchronized 锁头节点，粒度更细。
• 读操作基本无锁，写操作只锁定当前桶。

---

五、迭代器与 fail-fast 机制

5.1 迭代器工作原理

每个集合有一个内部类实现 Iterator 接口，维护以下字段：

• cursor：下一个返回元素的位置。
• lastRet：最后一次返回的索引（用于 remove）。
• expectedModCount：迭代器期望的集合修改次数（初始为 modCount）。

5.2 modCount 与 fail-fast

• modCount 记录集合结构性修改次数（添加、删除、扩容等）。
• 每次迭代器操作都会检查 modCount == expectedModCount，若不相等则抛出 ConcurrentModificationException，防止并发修改。

5.3 避免 ConcurrentModificationException

• 使用迭代器自己的 remove 方法（会同步更新 expectedModCount）。
• 使用 CopyOnWriteArrayList（写时复制，适合读多写少）。
• 使用并发集合（ConcurrentHashMap 等）。

// 正确删除
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().equals("B")) {
        it.remove();
    }
}

// Java 8 推荐的删除方式
list.removeIf(s -> s.equals("B"));

5.4 安全失败（fail-safe）机制

• 并发集合（如 CopyOnWriteArrayList）在迭代时使用的是原集合的快照，不会抛异常，但无法感知迭代过程中的修改。

---

六、Collections 工具类全解

方法	描述	示例
sort(List)	自然排序	Collections.sort(list)
sort(List, Comparator)	定制排序	Collections.sort(list, (a,b)->a-b)
reverse(List)	反转顺序	Collections.reverse(list)
shuffle(List)	随机打乱	Collections.shuffle(deck)
swap(List, i, j)	交换元素	Collections.swap(list,0,1)
rotate(List, distance)	循环移动	Collections.rotate(list, 2)
fill(List, obj)	全部填充	Collections.fill(list, null)
copy(dest, src)	复制	Collections.copy(dest, src)
replaceAll(list, oldVal, newVal)	替换	Collections.replaceAll(list, 0, -1)
binarySearch(List, key)	二分查找	Collections.binarySearch(list, 5)
max(Collection), min(Collection)	最大最小值	Collections.max(set)
frequency(Collection, obj)	出现次数	Collections.frequency(list, "A")
disjoint(c1, c2)	是否无交集	Collections.disjoint(set1, set2)
synchronizedXxx(collection)	转为线程安全	List<String> syncList = Collections.synchronizedList(new ArrayList<>())
unmodifiableXxx(collection)	转为不可修改	List<String> unmod = Collections.unmodifiableList(list)

---

七、Comparable 与 Comparator 深入

7.1 Comparable

• 内置于类，实现 int compareTo(T o)。
• 返回负数（当前对象小于参数）、0（相等）、正数（大于）。
• 一旦定义，就是该类的自然排序顺序。

public class Employee implements Comparable<Employee> {
    private int salary;
    @Override
    public int compareTo(Employee o) {
        return Integer.compare(this.salary, o.salary);
    }
}

7.2 Comparator

• 临时排序策略，实现 int compare(T o1, T o2)。
• 可用于 TreeSet、TreeMap、Collections.sort 等。

Comparator<Employee> byName = (e1, e2) -> e1.getName().compareTo(e2.getName());
Comparator<Employee> bySalaryDesc = (e1, e2) -> Integer.compare(e2.getSalary(), e1.getSalary());
// 链式排序
Comparator<Employee> chain = Comparator.comparing(Employee::getDept)
                                       .thenComparing(Employee::getSalary);

7.3 区别总结

特性	Comparable	Comparator
位置	定义在类内部	定义在外部独立
修改类	需要修改原类	无需修改原类
排序方式	只能一种自然顺序	可多种自定义顺序
方法	compareTo(T o)	compare(T o1, T o2)

---

八、Properties 详解

8.1 加载配置文件

Properties props = new Properties();

// 从类路径加载
try (InputStream in = Thread.currentThread().getContextClassLoader()
        .getResourceAsStream("config.properties")) {
    props.load(in);
}

// 从文件系统加载
try (FileInputStream fis = new FileInputStream("config.properties")) {
    props.load(fis);
}

// 读取属性，提供默认值
String dbUrl = props.getProperty("db.url", "jdbc:mysql://localhost:3306/test");

8.2 存储属性到文件

props.setProperty("app.name", "MyApp");
try (FileOutputStream out = new FileOutputStream("config.properties")) {
    props.store(out, "Application Configuration");
}

8.3 XML 格式属性文件

// 加载 XML
props.loadFromXML(in);
// 存储为 XML
props.storeToXML(out, "Comment");

---

九、实际开发中的选择建议

场景	推荐集合
存储顺序重要，允许重复	ArrayList
频繁在中间插入删除	LinkedList
去重，不关心顺序	HashSet
去重，需要保持插入顺序	LinkedHashSet
去重，需要自动排序	TreeSet
键值对，快速查找	HashMap
键值对，需要保持插入顺序	LinkedHashMap
键值对，需要按 Key 排序	TreeMap
线程安全的键值对	ConcurrentHashMap
读多写少的列表	CopyOnWriteArrayList
配置文件	Properties

---

十、常见面试题与陷阱

1. ArrayList 和 LinkedList 的区别

   • 底层结构：数组 vs 双向链表。
   • 随机访问：ArrayList O(1)，LinkedList O(n)。
   • 插入删除：ArrayList 尾部 O(1)，中间 O(n)；LinkedList 两端 O(1)，中间 O(n)。
   • 内存占用：ArrayList 可能有数组闲置空间；LinkedList 每个节点存储额外指针。

2. HashMap 容量为什么是 2 的幂

   • 为了使用 (n-1) & hash 代替 % 运算，提高速度。
   • 扩容时元素位置计算简单。

3. 如何保证 HashMap 线程安全

   • Collections.synchronizedMap(new HashMap<>())
   • ConcurrentHashMap（推荐）

4. HashSet 如何保证元素唯一

   • 利用 HashMap 的 Key 唯一性。

5. TreeSet 中元素如何排序

   • 实现 Comparable 或构造时传入 Comparator。

6. 迭代时删除元素为什么不能用 for-each

   • for-each 底层使用迭代器，但调用集合自身的 remove 会修改 modCount，导致迭代器检查失败抛出异常。

---

十一、代码演练

示例 1：使用 Comparator 实现多字段排序

class Person {
    String name;
    int age;
    // 构造器、getter、toString 省略
}

List<Person> persons = Arrays.asList(
    new Person("张三", 20),
    new Person("李四", 18),
    new Person("张三", 22)
);

persons.sort(Comparator.comparing(Person::getName)
                       .thenComparingInt(Person::getAge));

示例 2：使用 HashMap 统计单词频率

String text = "hello world hello java";
Map<String, Integer> freq = new HashMap<>();
for (String word : text.split(" ")) {
    freq.merge(word, 1, Integer::sum);
}
System.out.println(freq);  // {hello=2, world=1, java=1}

示例 3：利用 LinkedHashMap 实现 LRU 缓存

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;
    public LRUCache(int maxSize) {
        super(16, 0.75f, true);
        this.maxSize = maxSize;
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;
    }
}

---

十二、后续进阶

• 掌握 ArrayList、LinkedList、HashMap、HashSet 的底层原理是面试和开发的基础。
• 理解 fail-fast 机制，避免在遍历时修改集合。
• 正确使用 Comparable 和 Comparator，编写灵活的排序逻辑。
• 多线程环境优先使用 ConcurrentHashMap 而非同步包装类。
• 善用 Collections 工具类简化代码。

也可以深入学习 源码分析 和 并发集合，进一步理解 Java 容器的设计精髓。

今天这篇文章就到这里了，大厦之成，非一木之材也；大海之阔，非一流之归也。感谢大家观看本文