集合 - 文章目录

up

返回上级

sourcecode/java 上一级目录
md

ArrayDeque

ArrayDeque 是环形数组实现的双端队列,刷题里的双料主力:当栈用替代老古董 Stack,当队列用替代 LinkedList。两头进出都是摊还 $O(1)$,没有链表节点开销,缓存局部性好。核心就三个字段加一对循环移动的下标函数。

#集合
md

ArrayList

ArrayList 用一块连续的 Object[] 解决「既要数组的 O(1) 随机访问,又要能自动变长」的问题:容量不够时按约 1.5 倍申请新数组并整体拷贝,把扩容代价摊还到每次 add 上。代价是中间增删要搬移元素,且完全不做并发防护,只靠 modCount 提供 failfast。

#集合
md

Collection接口

Collection 是集合框架两大根系之一(另一支是 Map),List、Set、Queue 全部从它长出来。 它本身一行算法都没有:全是方法声明加几个 default 方法,价值在于「契约」——规定一个元素容器必须回答哪些问题(多大、有没有、给我遍历器)、允许拒绝哪些操作。 读懂这份契约,ArrayList、HashSet 那些实现类的方法表就不用背了,

#集合
md

ConcurrentHashMap

线程安全哈希表。JDK 8 起放弃分段锁 Segment,改成「空桶 CAS + 非空桶 synchronized 锁头节点」,锁粒度从一段桶缩小到一个桶;读操作全程无锁,计数用 LongAdder 思路分散热点,扩容允许多线程分片协作。

#集合
md

CopyOnWriteArrayList

写时复制(CopyOnWrite)的线程安全 List:读完全无锁,写加锁后把整个底层数组复制一份、改新数组、再用 volatile 写把引用换过去。老数组从不被修改,所以读线程手里的快照永远安全。代价是每次写 O(n) 拷贝,只适合读多写极少的场景(监听器列表、白名单、配置项)。

#集合
md

HashMap

HashMap 用「数组 + 链表 + 红黑树」实现平均 O(1) 的键值存取:[hash](/articles/csfour/datastructures/05hashtable/) 定位桶、冲突挂链、链太长转树兜底,最坏从 O(n) 封顶到 O(log n)。 允许一个 null 键、多个 null 值,非线程安全。

#集合
md

HashSet

HashSet 本身几乎没有算法:它把一个 [HashMap](/articles/sourcecode/java/集合/hashmap/) 包成 Set,元素当 key,value 统一填一个哨兵对象。去重、扩容、哈希扰动、树化全是 HashMap 的事,这个类只负责"把 Map 语义翻译成 Set 语义"。

#集合
md

LinkedHashMap

HashMap 的遍历顺序不可预测,LinkedHashMap 用最小代价补上这一点:每个节点在哈希桶之外再挂进一条贯穿全表的双向链表,查找仍是哈希的 O(1),遍历严格按插入顺序(accessOrder=true 时按访问顺序)。 它自己几乎没有"算法",全部秘密在于 HashMap 预留的三个回调钩子;accessOrder 加上重写 removeEld

#集合
md

LinkedList

双向链表,同时实现 List 和 Deque:两端增删 O(1),按下标访问 O(n),非线程安全。 整个类的核心只有三样东西:first/last 两根裸指针、私有的 Node 节点、一组 link/unlink 原语——所有公开 API(add/get/offer/poll/push/pop)都是这几个原语的薄包装。

#集合
md

PriorityQueue

PriorityQueue 是数组上的小根堆。刷题里 Top K、合并 K 个有序链表、数据流中位数(双堆)全靠它。 整个类没有一个"树节点",完全二叉树被编码进数组下标:queue[k] 的父亲是 queue[(k1)/2],两个孩子是 queue[2k+1] 和 queue[2k+2]。 堆序不变量只有一条:任何父亲不大于它的孩子,所以 queue[0]

#集合
md

TreeMap

TreeMap 解决的问题:既要 keyvalue 映射,又要 key 全局有序、能做范围查询(floor/ceiling/subMap)。 它用一棵红黑树把增删查全部压在稳定 O(log n),代价是 key 必须可比较(实现 Comparable 或传入 Comparator)。 HashMap 里的红黑树只是长链退化的兜底、结构不完整,想吃透红黑树的旋

#集合