第二大脑

主题

2026-08-24
784
3m

Java 集合框架技术栈总览 ​

蒸馏自 github-hxq-note/Java/Java util/（6 篇）+ 语雀-Java开发/JavaSE/集合（2 篇），主题高度集中（List + Map + 并发 Map）。本页是集合域全局地图。

一句话机制 ​

Java 集合分两大体系：Collection（List/Set/Queue，存单个元素）和 Map（存键值对）；核心实现围绕「数组 + 链表 + 红黑树」三种底层结构取舍，线程安全靠「互斥（HashTable/Collections.synchronizedXxx）→ 分段锁（CHM1.7）→ CAS + 局部 synchronized（CHM1.8）」逐代演进。

集合体系全景 ​

Collection                       Map
├── List（有序可重复）            ├── HashMap（数组+链表+红黑树）
│   ├── ArrayList（动态数组）     ├── LinkedHashMap（+双向链表保序）
│   └── LinkedList（双向链表）    └── TreeMap（红黑树，有序）
├── Set（无序不可重复）
│   ├── HashSet（基于 HashMap）
│   └── TreeSet（基于 TreeMap）
└── Queue（队列）

三大底层结构的取舍 ​

结构随机访问增删代表
动态数组O(1) 快O(n) 慢（要搬元素）ArrayList
双向链表O(n) 慢O(1) 快（改指针）LinkedList
哈希表（数组+链表+红黑树）O(1)~O(logn)O(1)~O(logn)HashMap

不变量：HashMap 用「数组 + 链表 + 红黑树」解决哈希冲突——冲突少用链表，冲突严重（链表 ≥8 且数组 ≥64）转红黑树，把查询从 O(n) 降到 O(logn)。

线程安全的演进（核心脉络） ​

方案机制问题
HashTable全表 synchronized并发性能极差
Collections.synchronizedMap包装 + 全表锁同样全表锁
ConcurrentHashMap 1.7Segment 分段锁（默认 16 段）分段间可并发，但锁粒度仍粗
ConcurrentHashMap 1.8CAS + 局部 synchronized（锁单个 Node）锁粒度最细 + 红黑树 + 多线程扩容

演进主线一句话：锁粒度从「全表 → 段 → 单个桶（Node）」逐代变细，并发度逐代提升。CHM1.8 的锁粒度是 Node，配合 CAS 无锁读。

关键机制速览 ​

  • HashMap 哈希函数：(h = key.hashCode()) ^ (h >>> 16)（高 16 位参与运算，减少低位冲突），索引 hash & (length - 1)
  • HashMap 扩容：数组长度保持 2 的 n 次方；1.8 扩容后元素位置「要么不变、要么 +旧容量」
  • ArrayList 扩容：无参构造首次 add 扩到 10，之后每次 1.5 倍（oldCapacity + (oldCapacity >> 1)）
  • CHM1.8 计数：counterCells 分散热点（同 LongAdder），避免并发竞争单个 size

常见误解（避坑） ​

  1. ❌ "HashMap 是线程安全的"。→ 1.7 扩容死循环、1.8 并发 put 数据覆盖；并发场景用 CHM 或加锁。
  2. ❌ "链表元素一超过 8 就转红黑树"。→ 还有第二个条件：数组长度 ≥64，否则优先扩容而非树化。
  3. ❌ "ArrayList 一开始就有 10 容量"。→ 无参构造初始是空数组（容量 0），第一次 add 才扩到 10。
  4. ❌ "ConcurrentHashMap 读也要加锁"。→ 1.8 的 get 是无锁的（volatile + Unsafe 保证可见性）。

关联 ​

最近更新