1. 整体设计与思路拆解为什么非要源码层面抠数据结构数据结构这门课科班出身的人基本都学过但很多人学完就忘工作三五年后连HashMap的扩容阈值都说不清。原因其实很简单——学校教的是抽象的ADT抽象数据类型考的是手写链表反转、二叉树遍历但这些和你每天写的ArrayList.add()、HashMap.get()之间隔着一层“封装的黑盒”。你只知道调用不知道背后发生了什么一旦遇到性能瓶颈、并发问题、内存溢出就抓瞎。这篇内容的核心思路就一句话把数据结构的“课本原理”和“JDK源码实现”拉到同一张桌子上对照着看。原理告诉你“应该是什么”源码告诉你“实际是什么”这两者之间的偏差恰恰是编程功力真正提升的地方。举个例子课本说哈希表冲突用链地址法但JDK 8之后的HashMap在链表长度超过8且数组容量达到64时会把链表转成红黑树——这是课本不会细讲的工程优化而它直接影响你在极端场景下的读写性能。适合谁看两类人。第一类是准备面试的开发者尤其是中高级岗位源码层面的数据结构解析几乎是必考题第二类是日常工作里需要排查性能问题、做技术选型的工程师理解了底层实现你才能说清楚为什么LinkedList在随机访问场景下性能远不如ArrayList为什么TreeMap的get操作是O(log n)而不是O(1)。整篇内容的拆解逻辑分四层先讲每种数据结构的基础原理和适用场景然后深入JDK对应实现类的源码逐行解读关键方法再附上复杂度对比表和实战注意事项最后汇总高频踩坑现场。这样从理论到代码再到实战一条线拉通内容密度够大但节奏是逐步深入的不会一上来就甩一堆源码让人劝退。2. 线性表的工程实现从数组到ArrayList的扩容哲学2.1 数组的底层真相与ArrayList的懒加载机制数组是所有数据结构的地基它最核心的特征是连续内存 固定长度。连续内存意味着可以通过下标直接计算内存地址所以随机访问是O(1)固定长度意味着一旦初始化就不能改变大小越界就抛ArrayIndexOutOfBoundsException。这两个特性是理解ArrayList一切行为的钥匙。JDK里的ArrayList几乎就是“会变长的数组”但它变长的策略非常讲究。看一下源码里的关键字段// ArrayList核心字段JDK 8/11 private static final int DEFAULT_CAPACITY 10; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {}; transient Object[] elementData; private int size;注意两个细节。第一DEFAULT_CAPACITY是10但用无参构造创建ArrayList时elementData指向的是一个空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA也就是说初始容量并不是10而是0。真正扩容到10发生在第一次add的时候这叫懒加载。第二elementData用了transient修饰说明它不参与默认的Java序列化ArrayList自己实现了readObject和writeObject只序列化有数据的部分省空间。add方法的核心逻辑在ensureCapacityInternal里扩容触发条件是size 1 elementData.length。一旦触发就调用grow方法新容量按oldCapacity (oldCapacity 1)计算也就是扩容1.5倍。为什么是1.5倍而不是2倍这是一个典型的空间与时间折中。扩容倍数越大需要扩容的次数越少插入均摊成本越低但浪费的内存越多。1.5倍既保证了均摊O(1)的插入复杂度又避免了2倍扩容可能带来的高达50%的内存浪费因为2倍扩容后新增的那部分容量往往用不满。这个数字不是随意定的实测下来扩容次数的数学期望和内存利用率的平衡点1.5倍在多数业务场景下表现最稳。2.2 ArrayList与LinkedList的适用边界别再凭感觉选型面试里最经典的问题之一就是“ArrayList和LinkedList有什么区别”但很多人背了答案却不理解本质。我直接给结论绝大多数业务场景下选ArrayList都更靠谱。理由藏在两者的底层结构里。LinkedList的底层是双向链表每个节点Node持有prev、next、item三个字段。链表的结构决定了它的优势只在“头部插入/删除”这个场景下是真正的O(1)而在get(int index)这种随机访问场景下它需要从头部或尾部看index离哪边近逐个遍历复杂度是O(n)。更关键的是LinkedList的每个节点都是一个独立的Object存在额外的对象头、指针引用开销内存占用远超ArrayList。我做过一次测试插入100万个元素LinkedList的内存占用比ArrayList高了大约30%到50%。再看ArrayList的add(int index, E element)虽然表面上需要挪动后面的元素是O(n)操作但别忘了它底层是连续内存System.arraycopy是JVM级的内存拷贝效率极高。而且实际开发中中间插入的业务场景远少于尾部追加尾部追加在ArrayList里是均摊O(1)几乎无损。一个实操建议如果确定要用链表结构优先考虑ArrayDeque而不是LinkedList。ArrayDeque底层是循环数组既支持双端操作又避免了链表节点开销在栈和队列场景下性能全面胜出。JDK官方文档甚至明确推荐在需要栈/队列功能时优先使用ArrayDeque。2.3 源码阅读法从add方法看ArrayList的完整生命周期读源码最忌讳从头翻到尾一定要从核心方法切入顺着调用链走。我以add(E e)为例把ArrayList的一次完整插入过程画成文字版流程调用add(E e) - ensureCapacityInternal(size 1) - calculateCapacity(elementData, minCapacity) // 如果elementData是空数组取max(DEFAULT_CAPACITY, minCapacity) // 即首次插入时容量至少为10 - ensureExplicitCapacity(minCapacity) - modCount // 结构化修改计数用于fail-fast - 如果minCapacity - elementData.length 0 - grow(minCapacity) - int newCapacity oldCapacity (oldCapacity 1) - 如果newCapacity - minCapacity 0newCapacity minCapacity - 如果newCapacity - MAX_ARRAY_SIZE 0hugeCapacity - elementData Arrays.copyOf(elementData, newCapacity) - elementData[size] e这个流程里有三个值得敲黑板的点。第一个是modCount。它是AbstractList里的一个计数器每次结构性修改增删元素都会加一。迭代器在遍历时会记录初始的expectedModCount一旦发现两者不一致立刻抛ConcurrentModificationException。这就是为什么在遍历ArrayList时不能直接调用remove方法——你以为只是删一个元素实际上破坏了迭代器的安全预期。第二个是grow方法里的MAX_ARRAY_SIZE限制。MAX_ARRAY_SIZE Integer.MAX_VALUE - 8为什么减8因为部分JVM实现里数组头信息需要占一些内存预留8是为了避免OutOfMemoryError的边界情况。如果你非要往ArrayList里塞超过这个大小的数据会直接抛OutOfMemoryError这是物理限制不是代码逻辑问题。第三个是Arrays.copyOf这一步。扩容本质上就是申请一个新数组把旧数据拷过去。这意味着扩容瞬间的内存峰值是旧容量 新容量的总和。如果预估数据量很大建议构造时直接指定初始容量new ArrayList(100000)避免多次扩容带来的数组拷贝开销。这个优化在批量数据导入场景下性能差距可能超过一个数量级。2.4 线性表场景的避坑清单在实际项目中线性表相关的高频问题集中在几个点我踩过坑也帮别人查过列出来供参考。不要在for循环里用list.size()作为删除条件的动态判断依据删完元素后索引会前移容易跳过元素。倒序遍历或者用迭代器的remove()更安全。subList返回的是原List的视图不是新List。对subList做结构性修改会直接影响原List而且修改原List的结构会导致subList失效并抛ConcurrentModificationException。如果只是想要一份独立子集new ArrayList(list.subList(a, b))才是正确姿势。用Arrays.asList生成的List是定长的不能add也不能remove因为它内部直接使用的就是传入的数组。要可变得new ArrayList(Arrays.asList(...))。频繁在列表头部插入删除的场景考虑LinkedList或者更好用ArrayDeque但记住随机访问仍然是链表软肋业务上要取舍。3. 哈希表的源码级拆解HashMap的容量、冲突与树化3.1 HashMap的底层结构演进从纯链表到链表红黑树HashMap是整个Java集合框架里最复杂也最常用的类没有之一。它的核心设计有两次大版本变化JDK 7用数组 单向链表解决哈希冲突JDK 8开始改成数组 链表 红黑树。这个演进的背后是一次真实存在的生产事故——当哈希函数设计不佳或者大量key发生碰撞时链表会退化成一个超长串get操作从期望的O(1)直接恶化成O(n)。网上曾有大团队在某个业务场景下因为key分布不均HashMap查一次要跑几十毫秒接口全部超时。JDK 8的解决方案是引入TREEIFY_THRESHOLD 8和MIN_TREEIFY_CAPACITY 64两个关键阈值。当某个桶位buckets的链表长度达到8且整个数组容量达到64时该桶位的链表会被转成红黑树树的查找复杂度是O(log n)从根源上遏制了退化风险。为什么阈值是8源码注释里给了一段泊松分布的计算——在随机哈希码下链表长度达到8的概率只有约千万分之六所以8是“安全边界”正常情况下链表形不成规模树化只是兜底策略。红黑树本身是一棵自平衡二叉搜索树它的平衡手段是节点染色红/黑 旋转。相比AVL树那种严格平衡左右子树高度差不超过1红黑树的平衡是“弱平衡”——最长路径不超过最短路径的2倍。这个特性让红黑树的插入删除旋转次数更少适合HashMap这种读写都频繁的场景。AVL树查询稍微快一点但维护成本高所以JDK选了红黑树工程上这是确定性的取舍不是拍脑袋。3.2 容量计算、hash扰动与寻址的完整链路HashMap的容量设计有几个反直觉的细节我把关键源码逻辑抽出来逐行解释。// 计算哈希值高16位与低16位异或降低冲突 static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); } // 容量规整返回大于等于cap的2的幂次 static final int tableSizeFor(int cap) { int n cap - 1; n | n 1; n | n 2; n | n 4; n | n 8; n | n 16; return (n 0) ? 1 : (n MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1; }第一个细节是hash()方法里的h ^ (h 16)。这被称为扰动函数。哈希值是一个32位int低位直接决定桶位下标因为寻址用的是(n - 1) hashn是2的幂所以实际上只用了hash的低log2(n)位。如果两个key的哈希值在高位不同、低位相同直接寻址就会冲突而h 16把高16位的信息混入低16位让低位不再“只看局部”。这个操作极廉价但能显著提升散列均匀度。第二个细节是tableSizeFor它保证HashMap的容量永远是2的幂次。为什么必须是2的幂因为只有容量是2的幂(n - 1) hash才能等价于hash % n而位运算比取模快一个数量级。这就是“用空间换位运算红利”的典型设计。构造时传入的初始容量如果是17实际会变成32你自以为设了一个精确的数字框架却给了幂等规整。第三个细节是扩容的resize()方法JDK 8之后有个非常重要的优化元素迁移时不再像JDK 7那样重新计算每个元素的下标而是通过(e.hash oldCap) 0判断元素是留在原位还是“原下标 oldCap”的新位置。原理是扩容后容量翻倍新下标比旧下标多出的那一位正好取决于hash值在oldCap对应位上是0还是1。这个优化把扩容迁移从O(n)的重新散列降成了O(n)的位判断加移动实际耗时大幅缩短。3.3 树化与反树化的边界控制树化不是毫无代价的。红黑树节点TreeNode相比普通链表节点Node多了parent、left、right、prev、red五个字段内存占用大约是普通节点的两倍以上。所以JDK设置了两个条件必须同时满足才会树化链表长度大于等于8且数组容量大于等于64。如果数组容量还不够64即使链表已经很长也只是做一次扩容——因为扩容会让链表分散到新的桶位长度自然下降。反树化的条件体现在split方法里扩容迁移后如果某个红黑树的节点数量小于等于UNTREEIFY_THRESHOLD 6就退化成链表。注意这里6和8中间隔了一个数这是经典的“滞回”设计——避免在树和链表之间反复横跳。如果阈值只有一个值比如8那么链表长度在8附近波动时会出现频繁树化、反树化的抖振性能会因此受损。用两个错开阈值是工程里处理状态切换的常见手法类似的思路在很多缓存淘汰算法里也能看到。3.4 HashMap实战中的容量预设与线程安全HashMap的默认初始容量是16负载因子是0.75意味着当元素个数达到16 * 0.75 12时就会触发扩容。如果你明确知道会存放1000条数据直接new HashMap(1000)是不够的——它会被tableSizeFor规整成1024而1024 * 0.75 7681000已经超过这个值插入过程中会再扩容一次。正确姿势是传入(预期数据量 / 负载因子) 1即new HashMap(1000 / 0.75f 1)大约1334规整后是2048这样全程零扩容。线程安全是另一个高频考点。HashMap不是线程安全的多线程写场景下有两条风险一是JDK 7及之前的头插法在并发扩容时可能形成环形链表get操作会死循环二是JDK 8改成了尾插法环形链表问题没了但并发put还是会造成数据覆盖、丢失更新。解决方案有三个层级Collections.synchronizedMap(new HashMap())最简单但锁粒度是整表并发量低时够用。Hashtable同样全表锁性能更差基本被淘汰。ConcurrentHashMap真正的并发容器JDK 8之后采用CAS synchronized锁单个桶位锁粒度远小于整表并发读性能接近无锁。实操建议很明确只要确定HashMap会被多线程共享写直接上ConcurrentHashMap不要有任何犹豫。4. 树结构的源码级对照TreeMap与红黑树、PriorityQueue与堆4.1 TreeMap的有序性来源与红黑树实现细节TreeMap是看红黑树源码的最好入口因为它就是一棵完整的红黑树。与HashMap不同TreeMap的key必须是可比较的要么实现Comparable要么构造时传入Comparator因为树的插入位置依赖比较结果来决定左走还是右走。TreeMap的put流程值得走一遍put(K key, V value) - 根节点为空直接作为根 - 从根节点往下遍历 cmp compare(key, t.key) cmp 0 走左子树cmp 0 走右子树cmp 0 覆盖旧值 - 找到合适位置插入新节点默认红色 - fixAfterInsertion(t) // 红黑树自平衡修复插入的新节点默认是红色这是红黑树一个重要的工程约定。红色节点不会增加路径上的黑节点数量所以不会破坏规则五任一节点到其每个叶子节点的所有路径都包含相同数目的黑节点这样插入操作最多只需要处理冲突的两个规则——红节点不能连续、根节点必须是黑。相比默认黑色默认红色可以减少很多不必要的修复操作。fixAfterInsertion里最主要的操作就是左旋和右旋。我举例说明左旋如果当前节点的父节点是红色且叔叔节点是黑色或者不存在而当前节点是右孩子就围绕父节点做一次左旋把父子关系调转再配合变色处理。这个过程最复杂的地方在于有三种情况循环处理源码里是一个while循环配合rotateLeft和rotateRight。读这段源码的时候不要试图背代码关键是通过一个具体插入序列手动推演几次旋转变色理解就到位了。4.2 TreeMap和HashMap怎么选别再纠结实际开发中TreeMap的使用频率远低于HashMap但一旦需要“有序”这个特性HashMap就完全没法替代。我给出选择判断的三条准则需要按键的自然顺序或自定义顺序遍历时选TreeMap。比如按时间戳排列的日志缓存、按分数排序的排行榜虽然更推荐用堆。只需要快速存取、无序遍历时选HashMap。TreeMap的put和get都是O(log n)而HashMap是均摊O(1)。数据量过万后这个差距在循环多次访问时会非常明显。需要范围查询比如找所有key大于某值的条目时TreeMap的subMap、headMap、tailMap是杀手级功能这是HashMap完全做不到的。第三点是被严重低估的能力。比如接口文档里常见的“查询2024年5月之后的全部交易记录”如果用HashMap你得遍历所有条目逐个过滤而TreeMap的tailMap(key, inclusive)是直接从树的某个位置开始中序遍历复杂度近似O(log n k)k是返回条数。这个特性在数据量大的场景里就是数量级的性能差距。4.3 PriorityQueue的堆实现与默认小顶堆的陷阱PriorityQueue底层是一个Object[]数组表示的小顶堆JDK默认使用Comparator.naturalOrder()也就是自然顺序的最小值优先出队。如果你用默认的new PriorityQueue()然后依次add(3, 1, 2)poll出来的是1、2、3——这个行为符合直觉。但这里有一个高频坑只依赖迭代器iterator()遍历PriorityQueue时元素并不是有序的。因为PriorityQueue只保证堆顶数组中下标0的位置是当前最小值其他元素之间没有全序关系。iterator()是按数组存储顺序遍历的你不一定看到排好序的结果。唯一能保证有序出队的方式是循环poll()。如果业务上需要“随时获取当前最大/最小的N个元素”PriorityQueue是非常好的选择但需要注意这个遍历误解。再看扩容逻辑。PriorityQueue的grow方法和ArrayList类似但扩容系数不同oldCapacity 64时翻倍否则扩容50%。这个设计考虑了数组结构和堆操作的特性堆操作上滤swim、下滤sink的复杂度是O(log n)堆的深度小频繁扩容的性能损耗比ArrayList更敏感所以小容量时翻倍快速扩容更合理。堆的核心操作是siftUp和siftDown。add在数组尾部追加元素然后通过siftUp不断与父节点比较、上浮poll先取出堆顶元素把数组最后一个元素移到堆顶再siftDown下沉调整。我用一个生活化类比帮助理解堆就像公司里的值班表每次排班时只看当前最紧急的事堆顶新任务来了就插到末尾然后按优先级往上商量而最紧急的任务被处理后最后一名来接手并重新排序。4.4 堆应用场景TopK问题与延迟队列PriorityQueue最经典的应用有两类。一类是TopK问题在一个大数组里找最大的K个数。经典做法是维护一个大小为K的小顶堆遍历数据堆满了之后只有比堆顶大的元素才替换进来每次替换做一次siftDown最终堆里就是最大的K个。这个方案的时间复杂度是O(n log k)空间复杂度是O(k)。对比直接全排序的O(n log n)数据量大时优势是压倒性的。我在处理一个千万级日志的TopK统计时小顶堆方案耗时不到全排序的五分之一。另一类是延迟队列场景。DelayQueue内部就持有一个PriorityQueue把“到期时间”作为排序键。take()方法会阻塞直到堆顶元素到期。这类场景在做定时任务、订单超时关闭、缓存过期清理时很常用。注意JDK自带的DelayQueue不支持取消操作如果业务上频繁删除未到期的任务考虑自定义或者加一层映射表来记录待取消任务。PriorityQueue还有一个值得说的点它不是线程安全的。并发环境下的优先级队列可以用PriorityBlockingQueue它在put、take等操作上加了锁底层仍然是堆结构。如果你需要的是“支持并发的高性能有界优先队列”java.util.concurrent里没有直接对应的类通常需要自己基于PriorityBlockingQueue封装有界逻辑或者引入第三方的环形缓冲实现但多数业务场景下PriorityBlockingQueue配合offer 手动判断长度就够用了。5. 栈与队列的进阶从ArrayDeque到BlockingQueue家族5.1 ArrayDeque的循环数组设计为什么它比Stack和LinkedList都强Java的Stack类从设计上就背了历史包袱。它继承自Vector所有方法都加了synchronized锁单线程场景下这个锁是纯开销它基于动态数组实现但push、pop操作因为锁的存在性能比ArrayDeque差明显。JDK官方文档早就建议栈用ArrayDeque不要用Stack。ArrayDeque的底层是一个循环数组。所谓循环就是通过head和tail两个指针在数组里“绕圈”当tail走到数组末尾时兜回head前面继续。这样addFirst/addLast、pollFirst/pollLast在绝大多数时候都是O(1)的数组读写只有数组满时才触发扩容翻倍并且一次性把元素顺序整理好。看addFirst的源码细节public void addFirst(E e) { if (e null) throw new NullPointerException(); elements[head (head - 1) (elements.length - 1)] e; if (head tail) doubleCapacity(); }(head - 1) (elements.length - 1)这个表达式就是循环的精髓。因为elements.length始终是2的幂所以length - 1的低位全是1做与运算等价于对length取模。这个位运算的效率极高而且避免了负数取模的问题——head - 1为-1时与运算结果直接变成数组最后一个下标。ArrayDeque和HashMap一样把“容量必须是2的幂”这个约束贯彻到了数组操作的每一个角落。实际开发中ArrayDeque最常见的两个替代场景栈操作push/pop替代Stack双端队列操作替代LinkedList。在需要栈的括号匹配、表达式求值、递归转迭代等算法里用ArrayDeque性能最好而且不用考虑锁开销。5.2 BlockingQueue的七种实现与生产者-消费者模型并发场景的队列核心是BlockingQueue接口。它定义了put满了就阻塞、take空了就阻塞、offer带超时时间的非阻塞入队、poll带超时时间的非阻塞出队等操作。选取实现类时需要对业务场景做匹配实现类底层结构是否支持有界特性与适用场景ArrayBlockingQueue循环数组 单一锁必须指定容量有界、公平性可配适合保证内存上限的稳定型队列LinkedBlockingQueue单向链表 两把锁可选默认Integer.MAX_VALUE吞吐量高适合生产消费速率不完全一致的场景SynchronousQueue无缓冲特殊每个插入必须等待一个移除适合直接交付型任务PriorityBlockingQueue二叉堆无界按优先级出队适合任务排序DelayQueue内部PriorityQueue无界元素到延迟时间后才能取出适合延时任务LinkedTransferQueue链表无界支持transfer直接交付适合高并发流式处理LinkedBlockingDeque双向链表可选双端操作适合工作窃取模型这里多说一句ArrayBlockingQueue和LinkedBlockingQueue的选择。前者只有一个锁生产者和消费者竞争同一把锁后者有两把锁putLock和takeLock生产、消费可以真正并行。所以在多核机器、生产消费者线程数量较多的情况下LinkedBlockingQueue的吞吐量通常会更好。但它是无界队列的话要特别小心默认容量是Integer.MAX_VALUE如果消费端卡住生产端会不停往里塞数据直到内存溢出。任何生产环境里的队列都建议显式设置容量上限并配合offer超时策略做降级处理。5.3 生产环境使用队列的四个关键注意事项队列在业务系统里经常是“隐性瓶颈”以下几个坑我亲眼见人踩过。无界队列在流量突刺时会拖垮整个服务。线程池的LinkedBlockingQueue如果无界任务排队膨胀到千万级别时内存直接打满这是高并发服务宕机的常见原因之一。务必有界并配拒绝策略如CallerRunsPolicy。SynchronousQueue适合任务量小于处理能力的场景如果生产速率大于消费速率put会一直阻塞反而拖住生产线程。用它之前要做压测验证。DelayQueue的take会有空转唤醒损耗任务量大时考虑用时间轮替代但时间轮的实现复杂度远高于DelayQueue一般只有极致性能需求才需要。队列元素如果是自定义对象务必实现合理的equals和hashCode否则remove、contains等操作会退化成全遍历时间复杂度变成O(n)在队列元素很多时非常影响性能。6. 数据结构全景视角从单点到组合的思维升级6.1 为什么ConcurrentHashMap的size()用LongAdder思维讲一个组合思维的案例ConcurrentHashMap的size()方法在JDK 8里没有用整表锁去统计而是维护了一个baseCount加一个CounterCell[]数组。更新时先CAS修改baseCount如果CAS失败就随机选一个CounterCell累加。这个设计的本质是把单一热点的计数器拆成多个分片用空间换并发度。这背后的核心思想其实和数据结构无关但它是由“哈希表的分桶思想”迁移过来的。你看数据结构学到一定程度不再是孤立地记忆每个类的API而是开始理解它的设计模式分片、树化、循环、位运算寻址、空间换时间、时间换空间……这些模式是可以跨类迁移的。你理解了HashMap的分桶就能理解ConcurrentHashMap的分片计数你理解了ArrayDeque的循环数组就能理解Disruptor的环形缓冲为什么快你理解了PriorityQueue的堆化就能理解定时任务的时间轮为什么用堆来管理最近触发的任务。读源码最大的收益之一就在这里——你见过了足够多的“工程解法”遇到新问题时脑子里会自动浮现已知的解法库然后做映射和组合。6.2 常见复杂度速查表面试与选型双参考把最常用的数据结构与JDK实现的核心操作复杂度整理成一张表面试前或者做技术方案时直接查数据结构JDK实现插入/删除查询内存特征适用场景动态数组ArrayList尾部均摊O(1)中间O(n)按下标O(1)连续内存无额外指针随机访问频繁、尾部增删为主双向链表LinkedList已知位置O(1)查找位置O(n)O(n)每节点含前驱/后继指针极少使用头部增删频繁时才考虑哈希表HashMap均摊O(1)O(1)数组节点引用树化时内存翻倍快速存取、无序遍历Key-Value有序哈希表LinkedHashMap均摊O(1)O(1)额外维护双向链表需要保持插入顺序或LRU缓存红黑树TreeMapO(log n)O(log n)节点含5个额外字段内存较大有序遍历、范围查询二叉堆PriorityQueueO(log n)取堆顶O(1)数组存储无指针TopK、任务按优先级出队循环双端队列ArrayDeque两端均摊O(1)按下标O(1)但很少用紧凑数组高性能栈/双端队列并发哈希表ConcurrentHashMap均摊O(1)O(1)与HashMap相似分片计数器多线程共享Key-Value这里面有一个反常识的点LinkedHashMap在内存上比HashMap多了一份维护插入顺序的双向链表但它依然保持O(1)的读写而且通过accessOrder参数可以实现LRU缓存。我自己实现一个本地缓存时就用到了LinkedHashMap加removeEldestEntry覆写几十行代码搞定完全没必要引入重型缓存中间件。6.3 源码阅读的心态与节奏建议读JDK源码最大的障碍不是代码复杂而是心态。很多人打开HashMap源码看到上千行就放弃了这完全没有必要。我个人的建议是分段式阅读第一遍只看字段和构造方法搞清楚类里存了什么第二遍挑一个核心方法比如put走完整条调用链第三遍回头对比“原理课本”和“实现”之间的差异。每一遍只解决一个问题三遍下来整个类的基本面貌就清楚了不需要逐行背代码。遇到看不懂的位运算和旋转逻辑最好的方式不是死磕抽象代码而是自己构造一个小例子用纸笔推演。红黑树插入我推演过不下十遍每次推一个不同形态的序列慢慢就形成了肌肉记忆面试中再被问到完全不慌。另外一个经验读源码时要关注版本差异。JDK 7升级到JDK 8HashMap冲突解决方案完全变了Java 9之后集合类又引入了不可变集合List.of、Map.of。看网上的源码分析文章一定要确认对方贴的版本是哪个JDK否则看完发现细节对不上反而浪费时间。6.4 最后分享一个排障的实战片段有次处理一个线上接口超时问题日志里显示某个方法的耗时从2ms飙升到800ms。排查后发现是一个全局的HashMap里堆积了上百万条数据且key的哈希分布极其不均匀某个桶位上的链表长度达到了几百。触发了树化的条件吗没有——因为数组容量只有16而MIN_TREEIFY_CAPACITY要求64容量不够扩容又因为能存的数据太少负载因子0.7516容量最多12条就该扩容但实际因为很多key落到同一个桶size计数远没到扩容阈值所以这个桶位就死扛着一条超长链表。我当时做的修复把容量预设调大并换了一个更均匀的key生成策略。但关键教训是——当哈希冲突严重时HashMap的“自动优化”是有前提的前提是哈希函数本身要足够均匀。如果业务里的key天生分布有偏再多的扩容和树化都是徒劳。这个排查过程让我彻底明白数据结构不是拿来背的是拿来“信任但验证”的。每次用HashMap承载可能很大的数据量时我都会顺手写个简单的分布测试看看桶位长度是否均匀这已经是我的习惯了。