集合源码 001：类关系图（Overview）

容器，就是可以容纳其他 Java 对象的对象。Java Collections Framework（JCF） 为 Java 开发者提供了通用的容器，始于 JDK 1.2。本系列将从整体结构入手，逐个拆解主要实现类的源码。

知识体系结构

容器主要包括 Collection 和 Map 两种：Collection 存储着对象的集合，Map 存储着键值对（两个对象）的映射表。

graph TD
    C[Collection] --> Set["Set（不重复）"]
    C --> List["List（有序可重复）"]
    C --> Queue["Queue（队列）"]
    Set --> HashSet["HashSet<br/>哈希表"]
    Set --> LinkedHashSet["LinkedHashSet<br/>哈希表 + 双向链表维护插入顺序"]
    Set --> TreeSet["TreeSet<br/>红黑树，有序"]
    List --> ArrayList["ArrayList<br/>动态数组，随机访问"]
    List --> Vector["Vector<br/>同步的动态数组（遗留类）"]
    List --> LinkedList1["LinkedList<br/>双向链表"]
    Queue --> LinkedList2["LinkedList<br/>双向队列"]
    Queue --> PriorityQueue["PriorityQueue<br/>堆实现的优先队列"]

    M[Map] --> HashMap["HashMap<br/>哈希表"]
    M --> Hashtable["Hashtable<br/>同步哈希表（遗留类）"]
    M --> LinkedHashMap["LinkedHashMap<br/>哈希表 + 双向链表维护顺序<br/>（插入序 / LRU）"]
    M --> TreeMap["TreeMap<br/>红黑树，按 key 排序"]

Collection 详解

Set

实现类	底层结构	特点
`HashSet`	哈希表	查找 O(1)，不支持有序性操作；失去插入顺序，Iterator 遍历结果不确定
`LinkedHashSet`	哈希表 + 双向链表	具有 HashSet 的查找效率，且维护元素的插入顺序
`TreeSet`	红黑树	支持有序性操作（如范围查找），查找 O(logN)，不如 HashSet 快

List

实现类	底层结构	特点
`ArrayList`	动态数组	支持随机访问
`Vector`	动态数组	和 ArrayList 类似，但线程安全（遗留类）
`LinkedList`	双向链表	只能顺序访问，但可以快速在链表中间插入/删除元素；还可用作栈、队列和双向队列

Queue

LinkedList：可以用它来实现双向队列
PriorityQueue：基于堆结构实现，可以用来实现优先队列

Map 详解

实现类	底层结构	特点
`HashMap`	哈希表	最常用的 Map 实现
`Hashtable`	哈希表	线程安全，但属于遗留类，不应使用；需要线程安全时用 `ConcurrentHashMap`（分段锁，效率更高）
`LinkedHashMap`	哈希表 + 双向链表	维护元素顺序：插入顺序或最近最少使用（LRU）顺序
`TreeMap`	红黑树	按 key 有序，支持范围操作

两点注意

Java 容器里只能放对象。基本类型（int、long、float、double 等）需要包装成对象类型（Integer、Long、Float、Double 等）才能放到容器里。很多时候拆装箱能够自动完成，这虽然带来了额外的性能和空间开销，但简化了设计和编程。
JCF 的价值：降低编程难度、提高程序性能、提高 API 间的互操作性、降低学习难度、降低设计和实现相关 API 的难度、增加程序的重用性。

系列导航

按下面顺序阅读效果最佳：

参考内容

CarpenterLee/JCFInternals —— Java 集合框架源码解析系列，本系列重要参考

CHARLIE SAYS