作为一个老写Java的人我对Map的感情很复杂。前阵子在某个系统里排查一个线上接口偶发超时的问题最后定位到的原因让人哭笑不得——有人在高频访问的热点路径上用了TreeMap做数据缓存明明插入和读取都只是普通的键值命中却要承担红黑树每次O(logN)的旋转和比较开销。换成HashMap之后CPU直接掉了一截。类似这种事在Java集合这个领域里几乎天天都在发生。Map这个接口我们每天写可真正把它吃透的人并不多——HashMap的底层到底怎么存数据扩容的时候发生了什么ConcurrentHashMap靠什么支撑高并发以及为什么有时候自定义对象做key会取不到值。这些如果只停留在“知道API”的层面迟早会在线上给你上一课。这篇内容我会结合自己的实战踩坑经历把Java集合中Map相关的核心原理、选型逻辑和容易翻车的细节彻底讲清楚偏底层原理的部分会用生活化的方式拆开讲保证有Java基础的读者能直接消化。1. HashMap为什么这么快从数组到红黑树的底层进化1.1 哈希桶的定位方式先看hashCode再与运算HashMap在最底层本质上就是一个数组数组的每个位置上通常叫“桶”。你 put 一个键值对进来它第一步做的事不是把数据直接塞进数组而是先算这个key的hashCode再通过位运算找到这个key应该落在哪个桶。这里有个很有意思的细节。JDK8里定位桶下标不是直接用hashCode而是先做一次扰动static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }把高16位与低16位做异或目的是让高位的特征也参与到底层下标计算中。因为数组的默认大小是16计算下标用的是hash (n - 1)如果不做扰动参与运算的实际只有hashCode的低4位容量16时 n-115高位信息完全浪费了。扰动之后即使hashCode的高位分布很好也能被利用起来碰撞概率会明显下降。再说为什么不直接用hash % n而是用hash (n - 1)。原因很简单位运算比取模快而且当n是2的幂时hash (n - 1)与hash % n的结果完全一样。所以HashMap强制要求底层数组的容量必须是2的幂本质上是给这个位运算的捷径创造条件。如果容量是100这样非2的幂数hash 99的分布会非常糟糕某些桶永远不会被使用直接浪费一半空间。1.2 链表过长时会发生什么树化阈值与泊松分布当多个key的hash值定位到同一个桶HashMap的解决方案是用链表挂起来。JDK8里链表有一个往红黑树转换的逻辑当链表长度达到8并且桶数组容量达到64时链表会树化成红黑树。我记得第一次看到这个设计时也犯过嘀咕——为什么阈值偏偏是8不是9也不是6源码注释里给过答案考虑到加载因子0.5用泊松分布计算下来链表中节点数达到8的概率大约只有千万分之六这个概率低到在正常业务里几乎不可能发生。也就是说树化是为了防御极端场景比如hash函数分布异常或者有攻击者故意构造大量hash冲突的数据来拖慢系统。树化不是越早越好。因为红黑树的节点是TreeNode里面多了左右子节点、颜色标记、父节点这些字段光是节点体积就比普通链表节点大很多。如果链表的长度只有三五个节点线性遍历反而比红黑树的左旋右旋快得多。所以这个8的设计本质上是在节点查询效率和额外内存开销之间找平衡。1.3 扩容不是简单的数组加长resize中的高位拆分HashMap的默认加载因子是0.75阈值计算公式是threshold capacity * loadFactor当元素个数超过threshold就会触发扩容容量翻倍。JDK8的扩容有个和JDK7完全不同的细节——旧桶里的节点在扩容之后会被拆成两条链一条留在原来的下标位置另一条挪到原下标 旧容量的位置。为什么能这么拆因为计算下标的掩码从n-1变成了2n-1相当于低位掩码多了一个bit。旧链表里某个节点在新数组中到底留在低位还是挪到高位只取决于多出来的那个bit是0还是1。这个bit通过hash oldCap就能算出来if ((e.hash oldCap) 0) { // 留在原位置 loTail loTail.next; } else { // 移到原位置 oldCap hiTail hiTail.next; }JDK7的扩容采用的是头插入法多线程并发扩容时可能形成环形链表导致get死循环。JDK8改成尾插法之后这个问题基本被消灭了但这不代表HashMap线程安全了并发场景下数据覆盖、size判断错误这些问题依然存在。1.4 容量初始化的反直觉设计threshold才是扩容分界很多人初始化HashMap是这样写的MapString, String map new HashMap(100);看起来是“我能装100个元素”其实这里有个陷阱。initialCapacity这个参数会影响底层数组的容量但HashMap判断要不要扩容不是看数组容量而是看threshold。如果你传了100HashMap会把容量向上取整到最近的2的幂也就是128threshold大约在96。也就是说你以为自己能放100个实际放到96个就会触发一次全量扩容白白损失一段性能。正确做法是按元素数量反推初始容量// 预期存10000个 int expectedSize 10000; int capacity (int) (expectedSize / 0.75f) 1; MapString, Object map new HashMap(capacity);这是实际业务里最让我触动的细节之一。在我维护的某个监控埋点服务里热点key表要预加载几万条配置原先初始化容量拍脑袋写了个几千结果每次启动阶段都会触发三四次大规模resizeCPU飙到60%以上。把容量按上面的公式计算之后启动过程一次性分配到位CPU直接降到个位数。预知容量大小的场景下这个优化几乎是零成本白捡的。2. Map实现不止一种从业务场景反推该选谁2.1 有序性需求LinkedHashMap与TreeMap的分工很多同事写代码时默认Map就是HashMap搞忘了同一个接口下面还有一群各有本事的实现。如果需要按插入顺序遍历或者按访问顺序遍历用LinkedHashMap。它在HashMap的基础上额外维护了一条双向链表串起所有Entry。遍历的时候可以稳定地按插入顺序输出内存开销比HashMap多了一个前驱和后继指针。我见过不少用ArrayList再手动排序实现这个需求的绕了圈子还多花内存。如果需求是按key自然排序或者按某个自定义规则排序用TreeMap。它的底层是一棵红黑树插入和删除都伴随着树的自平衡操作单次操作时间复杂度是O(logN)比HashMap的O(1)明显要慢。但是TreeMap真正厉害的地方在于它天然支持范围查询比如TreeMapLong, String treeMap new TreeMap(); // 取 [100, 200] 范围内的全部数据 SortedMapLong, String range treeMap.subMap(100L, true, 200L, true);这种区间操作在订单按时间排序、积分区间映射、排行榜这类场景里非常顺手。2.2 枚举键的极致优化EnumMap为什么快如果Map的key确定是枚举类型EnumMap可能是性能最好的选择。它的内部不是哈希表而是两个数组一个存key对应的枚举常量一个存value。由于枚举常量的ordinal是确定的连续整数EnumMap直接用这个序号当数组下标连hash都不用算时间和空间都做到了极致。这背后的思路其实很朴素能用数组下标解决的问题没必要绕到哈希。我自己在某状态机引擎里就把一堆MapStatus, Handler换成了EnumMapStatus, Handler代码没什么变化可读性更好性能还往上走了一截。2.3 用LinkedHashMap实现一个简单的LRU缓存这里有一个非常实用的组合技LinkedHashMap的构造函数支持accessOrder参数设为true后就开启访问顺序模式配合重写removeEldestEntry方法可以手写一个简单的LRU缓存。public class LruCacheK, V extends LinkedHashMapK, V { private final int maxCapacity; public LruCache(int maxCapacity) { super(16, 0.75f, true); this.maxCapacity maxCapacity; } Override protected boolean removeEldestEntry(Map.EntryK, V eldest) { return size() maxCapacity; } }单线程环境下这个类就是最精简的LRU实现。如果加了同步控制或者用Collections.synchronizedMap包一层完全可以在某些中小型项目中当本地缓存用很多框架底层早期就是这么干的。2.4 企业级选型流程先回答三个问题再动手我在实际项目里总结了一套特别笨但是特别有效的Map选型思路。动笔写代码之前先回答三个问题第一个问题这个Map会被多线程同时读写吗会直接上ConcurrentHashMap别碰HashMap也别拿Collections.synchronizedMap包装HashMap——虽然它确实是线程安全的但并发度太低所有操作都串行化性能会很难看。第二个问题遍历顺序有没有要求没有要求用HashMap要求插入顺序用LinkedHashMap要求按key排序用TreeMap要求按访问顺序淘汰旧数据用带accessOrder的LinkedHashMap。顺序要求是决定选择的最常见因素。第三个问题key是什么类型是否有明确的取值集合如果是枚举用EnumMap如果是正好落在连续小整数的业务编号用数组可能比Map更直接。这几个问题想清楚Map选型基本不会出大错。3. ConcurrentHashMap的并发进化从分段锁到CASsynchronized3.1 JDK7分段锁为什么慢早期JDK7的ConcurrentHashMap采用的是分段锁设计。底层是一个Segment数组每个Segment继承自ReentrantLock默认并发度是16也就是最多16个Segment。每次put的时候先定位这个key属于哪个Segment然后只需要锁住这个Segment即可。分段锁的优势是可以让16个段并行写入互不干扰。但问题在于如果某个Segment内的hash冲突比较集中或者业务key恰好都落在同一个段里锁竞争就会集中在那一两个段上整体并发能力还是会被拖累。而且定位一次Segment还要进行一次哈希计算效率打了折扣。3.2 JDK8的桶级并发与扩容协作JDK8把整个分段锁方案推倒重来设计思路变成了“锁细化到桶级别”。底层只有一个Node数组put流程大致是这样定位到桶下标后如果这个桶是空的直接用CAS操作把新节点放进去无锁完成写入如果桶非空会synchronized锁住这个桶的头节点然后再进行链表或红黑树的插入如果当前正在进行扩容还会优先协助扩容或者等待迁移完成。这里的synchronized看起来是重量级锁但JDK8之后JVM对synchronized做了大量优化包括偏向锁、轻量级锁、锁升级加上桶内的冲突概率通常都很低实际性能非常可观。真正复杂的部分是它的扩容机制。JDK8支持多线程并发协助扩容迁移桶的任务会被切分成多个小任务其它线程在put时发现桶里的节点是ForwardingNode就知道这个桶已经迁移过了会顺手把还没迁移的那部分任务领走一部分。这种协作式扩容大大缩短了大Map扩容时的停顿时间。3.3 size()统计的折中方案与mappingCount的坑ConcurrentHashMap的size()统计方式和HashMap不太一样。它维护了一个baseCount作为基础计数同时在并发度高的时候会开辟一个CounterCell数组不同线程各自在独立的Cell上累加最后返回时把baseCount和所有Cell的值相加。这个思路跟LongAdder的设计基本一致核心目标就是减少CAS竞争。这里有一个经常被忽略的坑size()返回的是int类型的总和数据量一旦超过int上限结果就会错误溢出。Java官方建议用mappingCount()替代size它返回long类型精度更高。虽然绝大多数业务Map元素数量不会接近21亿但写成map.size()在高并发系统里容易给人一种“这个值是实时精确的”错觉。实际上ConcurrentHashMap的size统计是近似值迭代过程中元素可能还在变化。如果需要绝对精确的快照必须在外层加锁或者配合其它同步手段。3.4 并发场景下HashMap的死亡环游与替代方案很多刚转Java的人会有一个疑问既然JDK8的HashMap扩容改成了尾插法不再死循环了那用HashMap并发写是不是就安全了不是。并发put时可能发生数据覆盖两个线程同时在一个空桶上CAS各自的新节点后写的会覆盖先写的也可能size计数不正确线程A扩容后把线程B刚写入的数据弄丢。更隐蔽的是并发读时HashMap可能查询到不一致的数据。这些都不是异常而是静默的错误往往比抛异常更可怕。所以在并发场景老老实实用ConcurrentHashMap或者用ConcurrentSkipListMap处理需要排序的并发场景。不要抱着侥幸心理拿HashMap当并发容器用这是我看了太多线上事故之后最想强调的一句。4. 遍历、排序与序列化Map使用中最容易翻车的三个细节4.1 遍历时删除元素为什么会抛ConcurrentModificationException在遍历HashMap时直接调用map.remove(key)十有八九会抛ConcurrentModificationException。原因在于HashMap内部维护了一个modCount计数器每一次结构性修改增加、删除键值对都会让modCount自增。迭代器在创建时会记录当时的modCount每次next()都会核对一次发现不一致立即抛出异常。这就是所谓fail-fast策略。设计理念是——与其让遍历在错误数据上继续执行导致不确定的结果不如尽早暴露问题。想一边遍历一边删除有三个办法// 方法1使用迭代器自己的remove IteratorString it map.keySet().iterator(); while (it.hasNext()) { String key it.next(); if (delete.equals(key)) { it.remove(); } } // 方法2Java 8 之后用 removeIf map.keySet().removeIf(key - delete.equals(key)); // 方法3如果要按value删除 map.entrySet().removeIf(entry - entry.getValue() null);顺便提醒一句迭代中替换已有key的value不算结构性修改不会触发异常。新增或删除键值对才是。4.2 按Map的value排序时比较器不能只看value想按value对Map排序因为Map本身没有按value排序的概念通常是把entrySet转成List再排序ListMap.EntryString, Integer list new ArrayList(map.entrySet()); list.sort(Map.Entry.comparingByValue());这里有个非常容易踩的坑如果value本身就是重复的比较器返回0时排序算法通常会认为这两个元素“相等”。在List排序中这没啥大事最多是顺序不稳定但如果这个比较器被放进TreeMap问题就严重了——TreeMap会把比较结果相同的两个key当作同一个键直接覆盖掉之前的键值对数据无提示地丢失。我在某个模拟项目中就遇到过这个问题。当时用TreeMap对若干商品按热度排序热度相同的商品直接被后面的覆盖了排查了很久才意识到比较器需要兜底条件value相同的时候再加上key的比较保证任意两个键比较结果不为0。这个细节按值排序时一定要记得。4.3 HashMap的序列化为什么不用默认机制HashMap实现了Serializable但它的底层桶数组是被transient修饰的。很多人不理解既然要支持序列化数组为什么要搞成transient因为HashMap的存储布局和hash值的计算时点强相关。同一个HashMap在不同版本的JDK里扩容策略可能不同桶下标完全可能不一样。如果用默认序列化直接把数组快照保存下来反序列化时要保证桶布局完全一致才能正常恢复几乎做不到。所以HashMap自己重写了writeObject和readObject序列化时只保存key和value反序列化时通过putVal重新计算hash、重新插入保证恢复后的HashMap跟重新put一遍的结果一致。这个特点在跨环境传输缓存数据时尤其值得注意。比如把HashMap序列化后通过Redis缓存给另一个服务读取两边如果JDK版本差异较大反序列化依然兼容就是因为存储的是键值对本身而不是哈希桶的内部结构。5. 自定义Key引发的血案equals、hashCode与可变字段5.1 new出来的新对象为什么取不到旧值这是HashMap使用中最经典的一个问题。我见过很多次定义一个User类有id和name作为key存进HashMap然后put完了用new User(1, 张三)去get结果为null。原因在于User如果没有重写equals和hashCode默认行为是“对象身份比较”。两次new出来的对象即使内容一模一样hashCode不同落到HashMap里的桶就可能不同即使同桶equals也是false。存进去的是A对象取出来的是B对象B当然找不到。所以自定义对象作为key时必须重写equals和hashCode并且保证equals相等的对象hashCode一定相等。更省事的做法是直接用String、Integer、Long这些不可变类当key这些类本身就严格遵守哈希契约也天然不可变是HashMap最可靠的选择。5.2 可变对象做key之后消息就再也找不回来了就算重写了equals和hashCode自定义对象只要包含可变字段就有潜在风险。比如一个class OrderKey包含一个status字段hashCode依赖status。第一次put时status是“待支付”hashCode计算出来是10放在桶10上。之后业务代码改了status为“已支付”hashCode变成了20再用这个对象去get它去桶20找数据自然找不到。结果就是数据明明在Map里却永远拿不到。这个问题最阴险的地方在于它不是必现的。只有当字段变更导致hashCode变化且变化后落到了不同的桶才会出现。而这个变化往往发生在分布式系统中——对象在多个节点之间流转字段被中间环节顺手改了到了下一个服务调用get时直接打了个空。修复思路很简单但要求设计时就做到作为key的对象必须不可变所有字段在构造时确定之后不再暴露任何修改入口。要么就用String拼接字段作为key这是最无脑也最安全的方式。5.3 一个真实的排查案例和修复链路之前某内部系统有一个本地缓存缓存key是自定义的ConfigKey包含module、name两个字段。系统运行几天后偶尔会出现“配置查不到”的问题查不到之后还会触发全量刷新线上时不时抖一下。排查过程是这样的。先看是不是缓存过期逻辑有误不是。再看是不是内存不够被回收不是。最后把configKey对象打印出来对比发现缓存里有同样的module和name但hashCode和老的key对不上问题锁定在对象某个非业务字段被序列化框架注入后发生了变更。虽然业务字段没变但hashCode里包含了一个动态字段导致桶定位失败。修复方式就是永远不拿可变对象当key。把key统一改成module : name的Stringget全部用String查。改完之后这个系统再也没出现过缓存穿透。5.4 设计中如何规避这些坑基于这些经历现在我写Map代码有一个固定的习惯定义key时优先考虑String、Integer、Long这些不可变基础类型。不得不用对象时类必须设计成不可变所有字段finalremove掉setterequals和hashCode只依赖真正标识业务身份的字段不依赖易变字段。Map的容量如果能预估一定按照之前的公式设置initialCapacity。如果放的是多线程共享的Map第一选择永远是ConcurrentHashMap。如果遍历时删数据一律Iterator.remove或者removeIf。这套习惯说起来简单但每条背后都是线上事故换来的。Map是一个被过度惯用的基础工具真正把它用明白的人往往是在坑里爬出来的人。希望这篇关于Java集合-Map的拆解能让你在爬坑之前就先看清脚下的路。
作为一个老写Java的人我对Map的感情很复杂。前阵子在某个系统里排查一个线上接口偶发超时的问题最后定位到的原因让人哭笑不得——有人在高频访问的热点路径上用了TreeMap做数据缓存明明插入和读取都只是普通的键值命中却要承担红黑树每次O(logN)的旋转和比较开销。换成HashMap之后CPU直接掉了一截。类似这种事在Java集合这个领域里几乎天天都在发生。Map这个接口我们每天写可真正把它吃透的人并不多——HashMap的底层到底怎么存数据扩容的时候发生了什么ConcurrentHashMap靠什么支撑高并发以及为什么有时候自定义对象做key会取不到值。这些如果只停留在“知道API”的层面迟早会在线上给你上一课。这篇内容我会结合自己的实战踩坑经历把Java集合中Map相关的核心原理、选型逻辑和容易翻车的细节彻底讲清楚偏底层原理的部分会用生活化的方式拆开讲保证有Java基础的读者能直接消化。1. HashMap为什么这么快从数组到红黑树的底层进化1.1 哈希桶的定位方式先看hashCode再与运算HashMap在最底层本质上就是一个数组数组的每个位置上通常叫“桶”。你 put 一个键值对进来它第一步做的事不是把数据直接塞进数组而是先算这个key的hashCode再通过位运算找到这个key应该落在哪个桶。这里有个很有意思的细节。JDK8里定位桶下标不是直接用hashCode而是先做一次扰动static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }把高16位与低16位做异或目的是让高位的特征也参与到底层下标计算中。因为数组的默认大小是16计算下标用的是hash (n - 1)如果不做扰动参与运算的实际只有hashCode的低4位容量16时 n-115高位信息完全浪费了。扰动之后即使hashCode的高位分布很好也能被利用起来碰撞概率会明显下降。再说为什么不直接用hash % n而是用hash (n - 1)。原因很简单位运算比取模快而且当n是2的幂时hash (n - 1)与hash % n的结果完全一样。所以HashMap强制要求底层数组的容量必须是2的幂本质上是给这个位运算的捷径创造条件。如果容量是100这样非2的幂数hash 99的分布会非常糟糕某些桶永远不会被使用直接浪费一半空间。1.2 链表过长时会发生什么树化阈值与泊松分布当多个key的hash值定位到同一个桶HashMap的解决方案是用链表挂起来。JDK8里链表有一个往红黑树转换的逻辑当链表长度达到8并且桶数组容量达到64时链表会树化成红黑树。我记得第一次看到这个设计时也犯过嘀咕——为什么阈值偏偏是8不是9也不是6源码注释里给过答案考虑到加载因子0.5用泊松分布计算下来链表中节点数达到8的概率大约只有千万分之六这个概率低到在正常业务里几乎不可能发生。也就是说树化是为了防御极端场景比如hash函数分布异常或者有攻击者故意构造大量hash冲突的数据来拖慢系统。树化不是越早越好。因为红黑树的节点是TreeNode里面多了左右子节点、颜色标记、父节点这些字段光是节点体积就比普通链表节点大很多。如果链表的长度只有三五个节点线性遍历反而比红黑树的左旋右旋快得多。所以这个8的设计本质上是在节点查询效率和额外内存开销之间找平衡。1.3 扩容不是简单的数组加长resize中的高位拆分HashMap的默认加载因子是0.75阈值计算公式是threshold capacity * loadFactor当元素个数超过threshold就会触发扩容容量翻倍。JDK8的扩容有个和JDK7完全不同的细节——旧桶里的节点在扩容之后会被拆成两条链一条留在原来的下标位置另一条挪到原下标 旧容量的位置。为什么能这么拆因为计算下标的掩码从n-1变成了2n-1相当于低位掩码多了一个bit。旧链表里某个节点在新数组中到底留在低位还是挪到高位只取决于多出来的那个bit是0还是1。这个bit通过hash oldCap就能算出来if ((e.hash oldCap) 0) { // 留在原位置 loTail loTail.next; } else { // 移到原位置 oldCap hiTail hiTail.next; }JDK7的扩容采用的是头插入法多线程并发扩容时可能形成环形链表导致get死循环。JDK8改成尾插法之后这个问题基本被消灭了但这不代表HashMap线程安全了并发场景下数据覆盖、size判断错误这些问题依然存在。1.4 容量初始化的反直觉设计threshold才是扩容分界很多人初始化HashMap是这样写的MapString, String map new HashMap(100);看起来是“我能装100个元素”其实这里有个陷阱。initialCapacity这个参数会影响底层数组的容量但HashMap判断要不要扩容不是看数组容量而是看threshold。如果你传了100HashMap会把容量向上取整到最近的2的幂也就是128threshold大约在96。也就是说你以为自己能放100个实际放到96个就会触发一次全量扩容白白损失一段性能。正确做法是按元素数量反推初始容量// 预期存10000个 int expectedSize 10000; int capacity (int) (expectedSize / 0.75f) 1; MapString, Object map new HashMap(capacity);这是实际业务里最让我触动的细节之一。在我维护的某个监控埋点服务里热点key表要预加载几万条配置原先初始化容量拍脑袋写了个几千结果每次启动阶段都会触发三四次大规模resizeCPU飙到60%以上。把容量按上面的公式计算之后启动过程一次性分配到位CPU直接降到个位数。预知容量大小的场景下这个优化几乎是零成本白捡的。2. Map实现不止一种从业务场景反推该选谁2.1 有序性需求LinkedHashMap与TreeMap的分工很多同事写代码时默认Map就是HashMap搞忘了同一个接口下面还有一群各有本事的实现。如果需要按插入顺序遍历或者按访问顺序遍历用LinkedHashMap。它在HashMap的基础上额外维护了一条双向链表串起所有Entry。遍历的时候可以稳定地按插入顺序输出内存开销比HashMap多了一个前驱和后继指针。我见过不少用ArrayList再手动排序实现这个需求的绕了圈子还多花内存。如果需求是按key自然排序或者按某个自定义规则排序用TreeMap。它的底层是一棵红黑树插入和删除都伴随着树的自平衡操作单次操作时间复杂度是O(logN)比HashMap的O(1)明显要慢。但是TreeMap真正厉害的地方在于它天然支持范围查询比如TreeMapLong, String treeMap new TreeMap(); // 取 [100, 200] 范围内的全部数据 SortedMapLong, String range treeMap.subMap(100L, true, 200L, true);这种区间操作在订单按时间排序、积分区间映射、排行榜这类场景里非常顺手。2.2 枚举键的极致优化EnumMap为什么快如果Map的key确定是枚举类型EnumMap可能是性能最好的选择。它的内部不是哈希表而是两个数组一个存key对应的枚举常量一个存value。由于枚举常量的ordinal是确定的连续整数EnumMap直接用这个序号当数组下标连hash都不用算时间和空间都做到了极致。这背后的思路其实很朴素能用数组下标解决的问题没必要绕到哈希。我自己在某状态机引擎里就把一堆MapStatus, Handler换成了EnumMapStatus, Handler代码没什么变化可读性更好性能还往上走了一截。2.3 用LinkedHashMap实现一个简单的LRU缓存这里有一个非常实用的组合技LinkedHashMap的构造函数支持accessOrder参数设为true后就开启访问顺序模式配合重写removeEldestEntry方法可以手写一个简单的LRU缓存。public class LruCacheK, V extends LinkedHashMapK, V { private final int maxCapacity; public LruCache(int maxCapacity) { super(16, 0.75f, true); this.maxCapacity maxCapacity; } Override protected boolean removeEldestEntry(Map.EntryK, V eldest) { return size() maxCapacity; } }单线程环境下这个类就是最精简的LRU实现。如果加了同步控制或者用Collections.synchronizedMap包一层完全可以在某些中小型项目中当本地缓存用很多框架底层早期就是这么干的。2.4 企业级选型流程先回答三个问题再动手我在实际项目里总结了一套特别笨但是特别有效的Map选型思路。动笔写代码之前先回答三个问题第一个问题这个Map会被多线程同时读写吗会直接上ConcurrentHashMap别碰HashMap也别拿Collections.synchronizedMap包装HashMap——虽然它确实是线程安全的但并发度太低所有操作都串行化性能会很难看。第二个问题遍历顺序有没有要求没有要求用HashMap要求插入顺序用LinkedHashMap要求按key排序用TreeMap要求按访问顺序淘汰旧数据用带accessOrder的LinkedHashMap。顺序要求是决定选择的最常见因素。第三个问题key是什么类型是否有明确的取值集合如果是枚举用EnumMap如果是正好落在连续小整数的业务编号用数组可能比Map更直接。这几个问题想清楚Map选型基本不会出大错。3. ConcurrentHashMap的并发进化从分段锁到CASsynchronized3.1 JDK7分段锁为什么慢早期JDK7的ConcurrentHashMap采用的是分段锁设计。底层是一个Segment数组每个Segment继承自ReentrantLock默认并发度是16也就是最多16个Segment。每次put的时候先定位这个key属于哪个Segment然后只需要锁住这个Segment即可。分段锁的优势是可以让16个段并行写入互不干扰。但问题在于如果某个Segment内的hash冲突比较集中或者业务key恰好都落在同一个段里锁竞争就会集中在那一两个段上整体并发能力还是会被拖累。而且定位一次Segment还要进行一次哈希计算效率打了折扣。3.2 JDK8的桶级并发与扩容协作JDK8把整个分段锁方案推倒重来设计思路变成了“锁细化到桶级别”。底层只有一个Node数组put流程大致是这样定位到桶下标后如果这个桶是空的直接用CAS操作把新节点放进去无锁完成写入如果桶非空会synchronized锁住这个桶的头节点然后再进行链表或红黑树的插入如果当前正在进行扩容还会优先协助扩容或者等待迁移完成。这里的synchronized看起来是重量级锁但JDK8之后JVM对synchronized做了大量优化包括偏向锁、轻量级锁、锁升级加上桶内的冲突概率通常都很低实际性能非常可观。真正复杂的部分是它的扩容机制。JDK8支持多线程并发协助扩容迁移桶的任务会被切分成多个小任务其它线程在put时发现桶里的节点是ForwardingNode就知道这个桶已经迁移过了会顺手把还没迁移的那部分任务领走一部分。这种协作式扩容大大缩短了大Map扩容时的停顿时间。3.3 size()统计的折中方案与mappingCount的坑ConcurrentHashMap的size()统计方式和HashMap不太一样。它维护了一个baseCount作为基础计数同时在并发度高的时候会开辟一个CounterCell数组不同线程各自在独立的Cell上累加最后返回时把baseCount和所有Cell的值相加。这个思路跟LongAdder的设计基本一致核心目标就是减少CAS竞争。这里有一个经常被忽略的坑size()返回的是int类型的总和数据量一旦超过int上限结果就会错误溢出。Java官方建议用mappingCount()替代size它返回long类型精度更高。虽然绝大多数业务Map元素数量不会接近21亿但写成map.size()在高并发系统里容易给人一种“这个值是实时精确的”错觉。实际上ConcurrentHashMap的size统计是近似值迭代过程中元素可能还在变化。如果需要绝对精确的快照必须在外层加锁或者配合其它同步手段。3.4 并发场景下HashMap的死亡环游与替代方案很多刚转Java的人会有一个疑问既然JDK8的HashMap扩容改成了尾插法不再死循环了那用HashMap并发写是不是就安全了不是。并发put时可能发生数据覆盖两个线程同时在一个空桶上CAS各自的新节点后写的会覆盖先写的也可能size计数不正确线程A扩容后把线程B刚写入的数据弄丢。更隐蔽的是并发读时HashMap可能查询到不一致的数据。这些都不是异常而是静默的错误往往比抛异常更可怕。所以在并发场景老老实实用ConcurrentHashMap或者用ConcurrentSkipListMap处理需要排序的并发场景。不要抱着侥幸心理拿HashMap当并发容器用这是我看了太多线上事故之后最想强调的一句。4. 遍历、排序与序列化Map使用中最容易翻车的三个细节4.1 遍历时删除元素为什么会抛ConcurrentModificationException在遍历HashMap时直接调用map.remove(key)十有八九会抛ConcurrentModificationException。原因在于HashMap内部维护了一个modCount计数器每一次结构性修改增加、删除键值对都会让modCount自增。迭代器在创建时会记录当时的modCount每次next()都会核对一次发现不一致立即抛出异常。这就是所谓fail-fast策略。设计理念是——与其让遍历在错误数据上继续执行导致不确定的结果不如尽早暴露问题。想一边遍历一边删除有三个办法// 方法1使用迭代器自己的remove IteratorString it map.keySet().iterator(); while (it.hasNext()) { String key it.next(); if (delete.equals(key)) { it.remove(); } } // 方法2Java 8 之后用 removeIf map.keySet().removeIf(key - delete.equals(key)); // 方法3如果要按value删除 map.entrySet().removeIf(entry - entry.getValue() null);顺便提醒一句迭代中替换已有key的value不算结构性修改不会触发异常。新增或删除键值对才是。4.2 按Map的value排序时比较器不能只看value想按value对Map排序因为Map本身没有按value排序的概念通常是把entrySet转成List再排序ListMap.EntryString, Integer list new ArrayList(map.entrySet()); list.sort(Map.Entry.comparingByValue());这里有个非常容易踩的坑如果value本身就是重复的比较器返回0时排序算法通常会认为这两个元素“相等”。在List排序中这没啥大事最多是顺序不稳定但如果这个比较器被放进TreeMap问题就严重了——TreeMap会把比较结果相同的两个key当作同一个键直接覆盖掉之前的键值对数据无提示地丢失。我在某个模拟项目中就遇到过这个问题。当时用TreeMap对若干商品按热度排序热度相同的商品直接被后面的覆盖了排查了很久才意识到比较器需要兜底条件value相同的时候再加上key的比较保证任意两个键比较结果不为0。这个细节按值排序时一定要记得。4.3 HashMap的序列化为什么不用默认机制HashMap实现了Serializable但它的底层桶数组是被transient修饰的。很多人不理解既然要支持序列化数组为什么要搞成transient因为HashMap的存储布局和hash值的计算时点强相关。同一个HashMap在不同版本的JDK里扩容策略可能不同桶下标完全可能不一样。如果用默认序列化直接把数组快照保存下来反序列化时要保证桶布局完全一致才能正常恢复几乎做不到。所以HashMap自己重写了writeObject和readObject序列化时只保存key和value反序列化时通过putVal重新计算hash、重新插入保证恢复后的HashMap跟重新put一遍的结果一致。这个特点在跨环境传输缓存数据时尤其值得注意。比如把HashMap序列化后通过Redis缓存给另一个服务读取两边如果JDK版本差异较大反序列化依然兼容就是因为存储的是键值对本身而不是哈希桶的内部结构。5. 自定义Key引发的血案equals、hashCode与可变字段5.1 new出来的新对象为什么取不到旧值这是HashMap使用中最经典的一个问题。我见过很多次定义一个User类有id和name作为key存进HashMap然后put完了用new User(1, 张三)去get结果为null。原因在于User如果没有重写equals和hashCode默认行为是“对象身份比较”。两次new出来的对象即使内容一模一样hashCode不同落到HashMap里的桶就可能不同即使同桶equals也是false。存进去的是A对象取出来的是B对象B当然找不到。所以自定义对象作为key时必须重写equals和hashCode并且保证equals相等的对象hashCode一定相等。更省事的做法是直接用String、Integer、Long这些不可变类当key这些类本身就严格遵守哈希契约也天然不可变是HashMap最可靠的选择。5.2 可变对象做key之后消息就再也找不回来了就算重写了equals和hashCode自定义对象只要包含可变字段就有潜在风险。比如一个class OrderKey包含一个status字段hashCode依赖status。第一次put时status是“待支付”hashCode计算出来是10放在桶10上。之后业务代码改了status为“已支付”hashCode变成了20再用这个对象去get它去桶20找数据自然找不到。结果就是数据明明在Map里却永远拿不到。这个问题最阴险的地方在于它不是必现的。只有当字段变更导致hashCode变化且变化后落到了不同的桶才会出现。而这个变化往往发生在分布式系统中——对象在多个节点之间流转字段被中间环节顺手改了到了下一个服务调用get时直接打了个空。修复思路很简单但要求设计时就做到作为key的对象必须不可变所有字段在构造时确定之后不再暴露任何修改入口。要么就用String拼接字段作为key这是最无脑也最安全的方式。5.3 一个真实的排查案例和修复链路之前某内部系统有一个本地缓存缓存key是自定义的ConfigKey包含module、name两个字段。系统运行几天后偶尔会出现“配置查不到”的问题查不到之后还会触发全量刷新线上时不时抖一下。排查过程是这样的。先看是不是缓存过期逻辑有误不是。再看是不是内存不够被回收不是。最后把configKey对象打印出来对比发现缓存里有同样的module和name但hashCode和老的key对不上问题锁定在对象某个非业务字段被序列化框架注入后发生了变更。虽然业务字段没变但hashCode里包含了一个动态字段导致桶定位失败。修复方式就是永远不拿可变对象当key。把key统一改成module : name的Stringget全部用String查。改完之后这个系统再也没出现过缓存穿透。5.4 设计中如何规避这些坑基于这些经历现在我写Map代码有一个固定的习惯定义key时优先考虑String、Integer、Long这些不可变基础类型。不得不用对象时类必须设计成不可变所有字段finalremove掉setterequals和hashCode只依赖真正标识业务身份的字段不依赖易变字段。Map的容量如果能预估一定按照之前的公式设置initialCapacity。如果放的是多线程共享的Map第一选择永远是ConcurrentHashMap。如果遍历时删数据一律Iterator.remove或者removeIf。这套习惯说起来简单但每条背后都是线上事故换来的。Map是一个被过度惯用的基础工具真正把它用明白的人往往是在坑里爬出来的人。希望这篇关于Java集合-Map的拆解能让你在爬坑之前就先看清脚下的路。
