← 返回首页 📖 📖 Wiki知识库
📐 学习维度 本篇是 📖 📖 Wiki知识库 🏠 首页 🛤️ 学习路径 📚 全部文章

Java集合框架源码精讲 - 🧠 5 分钟心智模型:停车场 + 智能仓库系统

本文是 Java集合框架源码精讲 的分章阅读版。

🧠 5 分钟心智模型:停车场 + 智能仓库系统

Java 集合不是一堆孤立的类,而是针对不同存取场景优化的容器家族。把它们想象成 5 种不同设计的停车场,每种解决一类问题。

① ArrayList = 连续编号的地面停车场


入口
 ↓
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │  ← capacity = 10
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
  ↑
找第 N 个车位 → 直接开过去 O(1)

中间插一辆车 → 后面所有车都要往后挪 O(n)

② LinkedList = 链式标签的车位


head → [车A|next] → [车B|next] → [车C|next] → null
                ←── [prev]   ←── [prev]

找第 3 个 → 从 head 一个个走过去 O(n)
头部加车 → 改两个标签 O(1)
尾部加车 → 改两个标签 O(1)(有 tail 指针)

③ HashMap = 智能编号车库(key 哈希定位)


车位 = hash(key) & (capacity - 1)

车库布局(数组 + 链表 + 红黑树):
┌────┬────┬────┬────┬────┬────┬────┬────┐
│ 0  │ 1  │ 2  │ 3  │ 4  │ 5  │ 6  │ 7  │  ← table 数组
└─┬──┴────┴─┬──┴────┴─┬──┴────┴────┴────┘
  │        │        │
  ↓        ↓        ↓
[车A]    [车B]    [车D]→[车E]→[车F]→[车G]→[车H]→...≥8 → 红黑树
  │        │
  ↓        ↓
[车C]    [车I]

为什么阈值是 8? 泊松分布概率论:哈希均匀时一个桶有 8 个元素的概率 ≈ 0.00000006,正常情况根本不会触发转树。设 8 是为了让"哈希极度不均匀(攻击)"时仍有 O(log n) 兜底。

④ TreeMap = 排序车库(红黑树自平衡)


              [车M]
            /       \
        [车F]       [车S]
        /   \       /   \
     [车B] [车H] [车O] [车Z]

中序遍历 → B, F, H, M, O, S, Z(字典序)

⑤ ConcurrentHashMap = 多层停车场(每层独立管理员)


JDK 7:分段锁(Segment)
┌─────────┬─────────┬─────────┬─────────┐
│ Lock 1  │ Lock 2  │ Lock 3  │ Lock 4  │  默认 16 段
│ ...     │ ...     │ ...     │ ...     │  最大并发 = 16
└─────────┴─────────┴─────────┴─────────┘

JDK 8+:桶级锁(CAS + synchronized)
┌────┬────┬────┬────┬────┬────┬────┬────┐
│ L  │    │ L  │    │    │ L  │    │    │  ← 每个桶一把锁
└────┴────┴────┴────┴────┴────┴────┴────┘
最大并发 = 桶数(远大于 16)

一句话总结

ArrayList=连续编号 / LinkedList=链式标签 / HashMap=智能编号(哈希)/ TreeMap=排序树 / ConcurrentHashMap=多层独立锁

记住这个画面,下文所有源码、扩容、面试题都是在填充细节——骨架已经在脑子里了。



相关页面