很多人写了多年Java对HashMap的用法烂熟于心但真要问一句“get(key)为什么就能拿到value”不少人会卡壳。面试八股能背出“数组加链表”“哈希冲突”“扩容负载因子”这些词可放到实际代码里遇到自定义对象当key查询不到、遍历时莫名其妙报并发修改异常、初始容量没设好导致性能剧烈波动就只能一脸懵去网上搜答案。这篇文章不打算按教科书顺序讲废话我就围绕“通过key找value”这个核心动作把HashMap从哈希函数、冲突解决、查询链路到日常使用的那些坑一层层拆开给你看希望能帮你真正建立一套可以从原理推导实践的知识框架。1. 键值映射的本质数组索引与哈希函数的分工1.1 数组随机访问带来的O(1)幻觉要理解HashMap先得从最朴素的存储工具——数组说起。数组能够支持按下标随机访问因为它在内存里是一段连续空间给定下标index就可以直接算出元素地址base_addr index * element_size。这个计算是常数时间所以理论上只要能把“key”转换成整型下标就能做到O(1)查找。很多初学者一听这话就觉得HashMap所以快是因为用一个超级大的数组把整个数据集拍进去了。这个想法方向没错但现实没这么简单。如果你的key是字符串“abc”、是某个自定义对象、是负数、是超大整数怎么把它变成一个安全且分布合理的下标直接把hashCode取出来用hashCode可能是个几亿的大数而你数组长度只有16越界了怎么办即便取余负数又怎么处理这一系列问题才是哈希函数和后续位运算存在的意义。1.2 哈希函数任意对象到整数的“指纹变换”Java里每个对象都有hashCode()方法它返回一个int。这个int可以理解为对象的“数字指纹”设计目标是把尽可能多的不同对象映射到不同整数上。但注意hashCode()只能保证生成一个int范围内的值并不能保证一定不重复更不能保证分布均匀。HashMap并不是直接用这个原始hashCode当索引的它内部会在put/get时对hashCode做一次二次加工叫扰动函数。以JDK 1.8为例static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }这行代码干了一件很微妙的事把hashCode的高16位通过无符号右移16位然后和原值做异或让高16位的特征也能参与到底位的计算。为什么要这么做因为后面计算桶下标时只用了低n位容量为2的幂时相当于取模如果原始hashCode的低位分布不均匀哈希冲突会比想象中严重得多。通过高16位混入低16位相当于用“信息折叠”的方式提升低位随机性这是JDK工程师针对实际对象hashCode分布做过的大量统计之后定下的方案。1.3 桶结构一个数组装下所有映射说完了整数再说存储布局。HashMap外面看起来是一个Map内部其实是一个NodeK,V[] table数组每个数组元素叫一个“桶”bucket。每个Node对象里存了四个字段hash、key、value、next。所以桶里面放的并不是裸的value而是一个链表节点。当你要存一个键值对时经历的过程是key算出hashhash再算出桶下标如果这个桶空着直接放进去如果桶里已经有节点就顺着链往下找。取的时候同理先定位到桶再在桶内寻找匹配的key找到后取出value。这个过程中数组下标是“粗定位”链表是“精定位”。很多人只记住了“数组链表”却没意识到真正让查找保持高效的关键是绝大多数桶里只有一个节点——只有出现冲突时才会退化到链表。1.4 为什么HashMap的容量都要设计成2的幂如果你看过HashMap源码会发现初始容量不是随便给的如果构造时指定容量为13实际容量会被设置成16。这是因为计算桶下标时用了这个技巧index (n - 1) hash当n是2的幂时n - 1的二进制就是低位全1比如16的n-1是15二进制是1111此时按位与的结果等价于hash % n但位运算速度远快于取模。更重要的是这样能让桶下标均匀分布在0到n-1之间。如果容量不是2的幂(n - 1) hash就会丢弃一些位导致某些桶永远空着冲突概率大增。这一点在你自定义初始容量时尤其重要千万不要以为HashMap会老实按你给的数字建表。2. 哈希冲突的工程解法从链地址到红黑树的权衡2.1 冲突不可避免只能缓解哈希冲突的数学依据是鸽笼原理如果key的取值空间远大于桶的数量那么必然存在多个key映射到同一个桶。即使你扩容到很大只要数据规模够大冲突还是会出现。那HashMap怎么处理冲突呢用的是链地址法——同一个桶里的多个键值对通过next指针串成一个链表。链地址法的好处是简单、实现容易插入永远都是O(1)级直接往链表头或尾挂删除也方便不需要像开放定址法那样处理一堆迁移问题。但它有个天然软肋一旦某个桶的链表变得很长查询该桶内元素的时间就退化成O(n)。也就是说HashMap最坏情况下的性能其实不怎么样只是平均情况下很好。2.2 链表太长时的转身红黑树化阈值为了缓解极端冲突场景下的性能劣化JDK 1.8引入了一个重要机制当某个桶的链表长度达到8并且整个数组长度达到64时链表会转成红黑树。红黑树的时间复杂度是O(log n)对比链表O(n)那是天壤之别。想象一下一个桶里有1000个节点链表查询要1000次比较红黑树大概需要10次左右——这就是树化的价值。为什么阈值选8官方注释里给了泊松分布的计算依据。简单说在随机hashCode的前提下桶内链表长度达到8的概率已经极其低大约是千万分之六所以8这个阈值既保证正常情况几乎不会触发树化又能在恶意构造冲突时兜住性能底限。同时还给了一个反方向的条件如果扩容后链表长度降到6以下红黑树会退化成链表。这里故意让8和6之间留了一格差异避免频繁在链树之间切换。2.3 树化之前还有一个前提容量64很多人容易忽略树化的前置条件数组长度必须大于等于64。如果table长度还不足64就算某个桶的链表已经很长了也不会树化而是先做一次resize扩容。这是因为在table规模很小时更合理的做法是扩大数组、重新哈希把整体冲突摊薄而不是立刻引入红黑树这种相对复杂的数据结构。这个细节在实际调优中有意义。比如你明确知道数据量可能很大且key的hashCode设计不理想那么正确姿势是设置一个合适的初始容量让HashMap在运行过程中尽量避免扩容和树化。扩容和树化都不是免费的前者要重新计算所有元素的桶位置后者要旋转变色调整树结构两者都是性能杀手。2.4 红黑树节点和链表节点并不是同一种对象理解树化的实现还要知道链表节点类型是NodeK,V而树化之后会变成TreeNodeK,VTreeNode是Node的子类因此可以继续留在数组的桶位里。当从红黑树里取数据时也是先按hash找到桶然后在TreeNode里进行左右子树查找判断key是通过hashCode和equals完成的。这里有个隐藏的“坑”如果你自定义的key对象没有正确重写equals树化后的查找就会基于不正确的相等性判断结果表现为“放了却查不到”。这个问题我后面专门用一节讲属于日常开发中最容易踩的空地。3. 一次get查询的完整旅程从key到value的每一步3.1 put操作数据进来时发生了什么虽然标题重点是“通过key找value”但找的前提是先放进去。我建议你把put和get连起来看。put的大致流程是对key做扰动hash得到哈希值。判断table是否为null或长度为0是则先调用resize()初始化。根据(n - 1) hash定位桶下标。若桶为空直接new一个Node放进去。若桶非空遍历桶内链表/树。如果遇到相同hash且key相等(k p.key) key || (key ! null key.equals(k))则覆盖旧value并返回旧value。如果没有相同key则在链表尾部插入新节点。插入后判断size是否超过阈值threshold capacity * loadFactor超过则扩容。注意第6步的等价条件先比较hash值再比较引用是否相等最后才调equals。这告诉了你一个事实——定位key是否“相同”hash只是粗筛选最终认定权利在equals方法手里。3.2 get操作逆向的精确匹配get的流程浓缩起来就是final NodeK,V getNode(int hash, Object key) { NodeK,V[] tab; NodeK,V first, e; int n; K k; if ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) hash]) ! null) { if (first.hash hash ((k first.key) key || (key ! null key.equals(k)))) return first; if ((e first.next) ! null) { if (first instanceof TreeNode) return ((TreeNodeK,V)first).getTreeNode(hash, key); do { if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) return e; } while ((e e.next) ! null); } } return null; }这段代码浓缩了HashMap查找的三大防线第一道哈希值必须相等不相等直接淘汰hash不相等equals一定不相等可以安全跳过。第二道引用相等直接命中这是最快路径无需调用任何方法。第三道equals相等这才是真正意义上的业务key相等。你可以看到HashMap查值的每个环节都在尽可能先做廉价判断把昂贵操作往后放。这一行行代码背后其实是极致的性能设计。3.3 位运算的妙处为什么不用取模前面已经提到索引计算用的是(n - 1) hash这里再展开说透。如果你用hash % n在n为2的幂时结果一样但位运算的CPU指令效率更高。更重要的是hash % n在hash为负数时结果还是负数要额外处理而按位与直接避开了这个问题。这个细节也解释了为什么HashMap在扩容后元素要么留在原索引要么移动到“原索引 旧容量”的新位置。因为容量翻倍后n - 1的高位多了一个1原来用于确定桶位置的那一位正好是决定老位置还是新位置的“开关”。这种设计让扩容时很多元素不需要完全重新计算位置只需要看新增的位是0还是1性能上做了极大优化。这也是为什么HashMap扩容时不会像某些简单实现那样从头再来。3.4 remove与containsKey里藏着相同逻辑很多人用containsKey觉得它就是个“判断有没有”的方法其实它的实现就是getNode找到了返回true找不到返回false。remove也是先getNode定位到节点然后再在链表或树里做删除操作。它们和get共享同一套“hash定位 逐级匹配”的链路。所以一旦你把key的equals或hashCode搞坏了受影响的绝不仅仅是getcontainsKey、remove、put覆盖等所有依赖key匹配的操作都会一起出问题。4. 负载因子、扩容阈值与性能拐点的取舍4.1 负载因子为什么默认是0.75负载因子load factor是HashMap里最容易被忽略的构造参数。它决定了HashMap“多满才需要扩容”。默认值是0.75——这个数字既不是拍脑袋也不是百分比而是在空间和查询时间之间取得了一个工程平衡。负载因子越小比如0.5意味着还没存多少数据就开始扩容数组空位多、冲突少但内存浪费严重负载因子越大比如1.0意味着数组快满了才扩容桶里链表容易变长查询效率下降。0.75这个值其实来源于一个经验公式。官方文档没有给出精确数学推导但大家公认的是0.75在大多数场景下可以让桶内链表长度达到8的概率变得极低从而避免树化。如果你把负载因子调到1链表变长的概率会显著上升调到0.5内存开销可能增加一倍。所以在没有特殊需求时默认值就是最安全的选择。4.2 扩容的时机和代价扩容触发时机是size threshold其中threshold capacity * loadFactor。比如默认容量16负载因子0.75threshold就是12。当你put插入第13个键值对时就会触发扩容容量从16变成32threshold从12变成24所有元素重新计算桶位置并分配。这个过程叫rehash它的代价是O(n)因为要把每个节点迁移到新数组。对单个操作来说瞬间的耗时可能突然飙高这也是为什么“预先指定容量”在实际开发里是极其重要的性能优化。但要注意指定容量也不是说传多少就多少。如果你知道要存1000条数据计算一下需要 capacity * 0.75 1000所以 capacity至少得是1334向上取2的幂就是2048。如果直接传1000HashMap会扩容到1024但threshold是768还没等你存到1000就已经发生过一次扩容了白白多花一次迁移开销。4.3 初始容量设置的实战计算我经常看到有人这么写new HashMap(10000)以为这样就避免扩容了。实际上一万并不是2的幂HashMap内部会找大于等于一万的2的幂也就是16384而threshold是16384 * 0.75 12288。如果你只插入一万条虽然不会触发扩容但空间有一小半是空闲的。这其实还能接受。真正的坑是插入条数超过threshold下的容量——比如你传的是恰好能装下的数却忽略了threshold capacity * 0.75这个乘法导致预估失误。这里给出一个我的习惯预估数据量n后用capacity n / loadFactor 1计算然后再取大于等于这个值的2的幂。或者更省事一点直接调用Guava的Maps.newHashMapWithExpectedSize之类工具它内部就是做了这个换算。当然如果你不想引入依赖自己算也行公式并不复杂。4.4 一个实测对比设不设初始容量差别有多大以前我用一个模拟项目做过测试往HashMap插入500万条记录一种用默认构造后直接批量put一种先指定容量为1024万通过预估计算结果后者总耗时大约只有前者的70%。原因是默认方案在插入过程中触发了多次扩容和rehash每次都要重新计算并向新数组迁移数据累计起来相当可观。但也不要矫枉过正。容量设得太大初始分配大数组本身就有内存成本而且所有桶位一开始都是null用不到的话就是纯浪费。所以合理策略是“预估数据量再适当放宽”而不是盲目给一个很大的数字。5. 键对象的设计红线equals与hashCode为何必须一起重写5.1 自定义对象当key的典型翻车现场我见过最经典的翻车代码是拿一个自定义类当key只重写了equals没重写hashCode。例如class Person { private String id; public Person(String id) { this.id id; } Override public boolean equals(Object o) { if (this o) return true; if (o null || getClass() ! o.getClass()) return false; Person person (Person) o; return id.equals(person.id); } }然后两个new Person(1)按equals是相等的但hashCode不同因为继承的Object.hashCode()是不同对象返回不同整数通常是内存地址换算。当两个Person对象被放进HashMap后你想用其中一个去get另一个hash定位就落到了不同桶equals连上场机会都没有。表现就是——key“明明内容一样”却查不到值。5.2 两个约定一条都不能破Java规范里对hashCode和equals有三个约定其中两条对HashMap至关重要如果两个对象通过equals比较相等那么它们的hashCode必须相等。如果两个对象的hashCode相等它们并不一定equals相等哈希碰撞情况。第一条是HashMap能够正常工作的前提get时先用hash定位再用equals确定。如果“equals相等但hashCode不等”HashMap把两个相等的key当成了完全不同的人逻辑必然错乱。第二条则告诉我们hashCode相同时还会出现冲突桶所以equals的判断依然不能省略。5.3 写一个可靠的键类可靠键类的基本要求有三个不可变或至少业务关键字不变、重写equals、重写hashCode。比如身份证号、订单号、URL这样的业务主键天然适合做key。实现时你不需要从零发明。如果ID字段是String直接用Objects.hash(id)生成hashCodeequals则用Objects.equals(id, other.id)。如果类有多个业务字段把所有参与业务相等的字段都放进hash计算。注意参与equals判断的字段必须全部参与hashCode计算并且用于hashCode的字段不应该出现“因为是随机生成每次不同”的情况。拿new Date()当key就是一种灾难——每次hashCode都可能不同放入后又查不到。5.4 不可变对象的额外收益用String、Integer这类不可变对象当key时不仅hashCode稳定还天然满足equals对称性、传递性这些要求。我建议能直接用JDK的标准类型当key就别自定义。如果必须自定义也要保证这个类的业务字段在放入Map后永远不会被修改。一旦某个key对象的hashCode在放入后变化了后续get时就会定位到错误桶几乎只能靠遍历整个map才能找到——而且即使找到了也是错的索引位置根本拿不到value。这种bug难以排查所以最好从设计上就堵死。6. 开发中的常见误用与实测经验6.1 HashMap不是线程安全的并发下的三种事故现实中很多人拿HashMap当全局缓存多线程读写然后某天突然CPU飙升或死循环。JDK 1.7的HashMap在并发扩容时可能出现链表环导致get时无限循环。1.8修复了链表环问题但它依然不是线程安全容器多个线程并发put可能导致数据丢失、覆盖、size统计不准等问题。即使在1.8下并发put时两个线程同时看到了相同空白桶都会往里写节点后写的覆盖先写的数据直接丢失。正确的并发姿势是如果需要线程安全的Map要么给外层加锁要么直接用ConcurrentHashMap。注意很多面试题喜欢问“Hashtable为什么慢”因为它的所有方法都是synchronized串行化严重而ConcurrentHashMap用分段锁或CAS并发度要好得多。6.2 null键和null值的容忍度HashMap允许null作为key并且只允许一个。扰动函数里看到key null ? 0null会被固定映射到第0个桶。取的时候get(null)也能正常返回。这在实际业务中方便但也可能让你写下map.get(key)后分不清是“没有这个key”还是“这个key的value就是null”——如果不确定用containsKey判断一下。另外Hashtable和ConcurrentHashMap都不允许null key或null value这点在迁移代码时需要格外小心否则一个简单的put就会抛NullPointerException。6.3 遍历时的结构修改陷阱在遍历HashMap的过程中如果直接调用put或remove修改了map的结构增加或删除键值对会触发快速失败机制抛出ConcurrentModificationException。这是由modCount字段监控的。解决方式有两种用迭代器的remove方法或者先把要删的key收集到一个list遍历结束后再统一remove。在迭代时还要留意一点HashMap的遍历顺序是桶顺序加链表顺序和插入顺序无关。如果你需要按插入顺序遍历可以用LinkedHashMap它在HashMap基础上额外维护了双向链表代价是略微增加内存。6.4 与LinkedHashMap、TreeMap的选择做技术选型时很多人把HashMap奉为唯一真理其实不同Map有不同适用场景HashMap绝大多数场景平均查询最快。LinkedHashMap需要维持插入顺序或访问顺序可做LRU缓存。TreeMap需要按键排序底层红黑树支持范围查询但操作是O(log n)。不要因为HashMap快就哪里都用。比如你需要在有序列表上做范围查询TreeMap更合适需要做LRU缓存LinkedHashMap稍微改造就能用。6.5 两个工具箱里的实用技巧我自己写代码时有两个小习惯推荐给你。第一凡是能预估数据量的地方务必先估算并设置初始容量别依赖自动扩容。第二当map里装的是大value对象时需要判断“是否存在”尽量用containsKey而不是先get null这个前面说过了但实际很多人还是会踩。最后一个值得分享的排查技巧当你发现HashMap“存得进去取不出来”时先检查key对象的equals和hashCode如果你用了自定义类去查这两个方法有没有被正确重写以及key对象的业务字段是否在存进去之后被某个setter改动了。我的经验是90%的HashMap诡异问题都出在这两处剩下的再去怀疑并发和扩容都不迟。HashMap底层没有多深奥但把它吃透需要把“哈希函数、冲突、扩容、equals/hashCode”这几条线串起来。当你真正理解“通过key找value”是建立在“先粗定位、再细匹配”这套机制上时很多问题不用查资料也能自己推断出来。希望这篇基于标题展开的拆解能帮你在实战中少踩几个坑。 
长河君 · 2026/10/21 17:38:06 · 阅读 1.2k 从key到value：HashMap哈希函数、冲突解决与日常踩坑全解析
很多人写了多年Java对HashMap的用法烂熟于心但真要问一句“get(key)为什么就能拿到value”不少人会卡壳。面试八股能背出“数组加链表”“哈希冲突”“扩容负载因子”这些词可放到实际代码里遇到自定义对象当key查询不到、遍历时莫名其妙报并发修改异常、初始容量没设好导致性能剧烈波动就只能一脸懵去网上搜答案。这篇文章不打算按教科书顺序讲废话我就围绕“通过key找value”这个核心动作把HashMap从哈希函数、冲突解决、查询链路到日常使用的那些坑一层层拆开给你看希望能帮你真正建立一套可以从原理推导实践的知识框架。1. 键值映射的本质数组索引与哈希函数的分工1.1 数组随机访问带来的O(1)幻觉要理解HashMap先得从最朴素的存储工具——数组说起。数组能够支持按下标随机访问因为它在内存里是一段连续空间给定下标index就可以直接算出元素地址base_addr index * element_size。这个计算是常数时间所以理论上只要能把“key”转换成整型下标就能做到O(1)查找。很多初学者一听这话就觉得HashMap所以快是因为用一个超级大的数组把整个数据集拍进去了。这个想法方向没错但现实没这么简单。如果你的key是字符串“abc”、是某个自定义对象、是负数、是超大整数怎么把它变成一个安全且分布合理的下标直接把hashCode取出来用hashCode可能是个几亿的大数而你数组长度只有16越界了怎么办即便取余负数又怎么处理这一系列问题才是哈希函数和后续位运算存在的意义。1.2 哈希函数任意对象到整数的“指纹变换”Java里每个对象都有hashCode()方法它返回一个int。这个int可以理解为对象的“数字指纹”设计目标是把尽可能多的不同对象映射到不同整数上。但注意hashCode()只能保证生成一个int范围内的值并不能保证一定不重复更不能保证分布均匀。HashMap并不是直接用这个原始hashCode当索引的它内部会在put/get时对hashCode做一次二次加工叫扰动函数。以JDK 1.8为例static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }这行代码干了一件很微妙的事把hashCode的高16位通过无符号右移16位然后和原值做异或让高16位的特征也能参与到底位的计算。为什么要这么做因为后面计算桶下标时只用了低n位容量为2的幂时相当于取模如果原始hashCode的低位分布不均匀哈希冲突会比想象中严重得多。通过高16位混入低16位相当于用“信息折叠”的方式提升低位随机性这是JDK工程师针对实际对象hashCode分布做过的大量统计之后定下的方案。1.3 桶结构一个数组装下所有映射说完了整数再说存储布局。HashMap外面看起来是一个Map内部其实是一个NodeK,V[] table数组每个数组元素叫一个“桶”bucket。每个Node对象里存了四个字段hash、key、value、next。所以桶里面放的并不是裸的value而是一个链表节点。当你要存一个键值对时经历的过程是key算出hashhash再算出桶下标如果这个桶空着直接放进去如果桶里已经有节点就顺着链往下找。取的时候同理先定位到桶再在桶内寻找匹配的key找到后取出value。这个过程中数组下标是“粗定位”链表是“精定位”。很多人只记住了“数组链表”却没意识到真正让查找保持高效的关键是绝大多数桶里只有一个节点——只有出现冲突时才会退化到链表。1.4 为什么HashMap的容量都要设计成2的幂如果你看过HashMap源码会发现初始容量不是随便给的如果构造时指定容量为13实际容量会被设置成16。这是因为计算桶下标时用了这个技巧index (n - 1) hash当n是2的幂时n - 1的二进制就是低位全1比如16的n-1是15二进制是1111此时按位与的结果等价于hash % n但位运算速度远快于取模。更重要的是这样能让桶下标均匀分布在0到n-1之间。如果容量不是2的幂(n - 1) hash就会丢弃一些位导致某些桶永远空着冲突概率大增。这一点在你自定义初始容量时尤其重要千万不要以为HashMap会老实按你给的数字建表。2. 哈希冲突的工程解法从链地址到红黑树的权衡2.1 冲突不可避免只能缓解哈希冲突的数学依据是鸽笼原理如果key的取值空间远大于桶的数量那么必然存在多个key映射到同一个桶。即使你扩容到很大只要数据规模够大冲突还是会出现。那HashMap怎么处理冲突呢用的是链地址法——同一个桶里的多个键值对通过next指针串成一个链表。链地址法的好处是简单、实现容易插入永远都是O(1)级直接往链表头或尾挂删除也方便不需要像开放定址法那样处理一堆迁移问题。但它有个天然软肋一旦某个桶的链表变得很长查询该桶内元素的时间就退化成O(n)。也就是说HashMap最坏情况下的性能其实不怎么样只是平均情况下很好。2.2 链表太长时的转身红黑树化阈值为了缓解极端冲突场景下的性能劣化JDK 1.8引入了一个重要机制当某个桶的链表长度达到8并且整个数组长度达到64时链表会转成红黑树。红黑树的时间复杂度是O(log n)对比链表O(n)那是天壤之别。想象一下一个桶里有1000个节点链表查询要1000次比较红黑树大概需要10次左右——这就是树化的价值。为什么阈值选8官方注释里给了泊松分布的计算依据。简单说在随机hashCode的前提下桶内链表长度达到8的概率已经极其低大约是千万分之六所以8这个阈值既保证正常情况几乎不会触发树化又能在恶意构造冲突时兜住性能底限。同时还给了一个反方向的条件如果扩容后链表长度降到6以下红黑树会退化成链表。这里故意让8和6之间留了一格差异避免频繁在链树之间切换。2.3 树化之前还有一个前提容量64很多人容易忽略树化的前置条件数组长度必须大于等于64。如果table长度还不足64就算某个桶的链表已经很长了也不会树化而是先做一次resize扩容。这是因为在table规模很小时更合理的做法是扩大数组、重新哈希把整体冲突摊薄而不是立刻引入红黑树这种相对复杂的数据结构。这个细节在实际调优中有意义。比如你明确知道数据量可能很大且key的hashCode设计不理想那么正确姿势是设置一个合适的初始容量让HashMap在运行过程中尽量避免扩容和树化。扩容和树化都不是免费的前者要重新计算所有元素的桶位置后者要旋转变色调整树结构两者都是性能杀手。2.4 红黑树节点和链表节点并不是同一种对象理解树化的实现还要知道链表节点类型是NodeK,V而树化之后会变成TreeNodeK,VTreeNode是Node的子类因此可以继续留在数组的桶位里。当从红黑树里取数据时也是先按hash找到桶然后在TreeNode里进行左右子树查找判断key是通过hashCode和equals完成的。这里有个隐藏的“坑”如果你自定义的key对象没有正确重写equals树化后的查找就会基于不正确的相等性判断结果表现为“放了却查不到”。这个问题我后面专门用一节讲属于日常开发中最容易踩的空地。3. 一次get查询的完整旅程从key到value的每一步3.1 put操作数据进来时发生了什么虽然标题重点是“通过key找value”但找的前提是先放进去。我建议你把put和get连起来看。put的大致流程是对key做扰动hash得到哈希值。判断table是否为null或长度为0是则先调用resize()初始化。根据(n - 1) hash定位桶下标。若桶为空直接new一个Node放进去。若桶非空遍历桶内链表/树。如果遇到相同hash且key相等(k p.key) key || (key ! null key.equals(k))则覆盖旧value并返回旧value。如果没有相同key则在链表尾部插入新节点。插入后判断size是否超过阈值threshold capacity * loadFactor超过则扩容。注意第6步的等价条件先比较hash值再比较引用是否相等最后才调equals。这告诉了你一个事实——定位key是否“相同”hash只是粗筛选最终认定权利在equals方法手里。3.2 get操作逆向的精确匹配get的流程浓缩起来就是final NodeK,V getNode(int hash, Object key) { NodeK,V[] tab; NodeK,V first, e; int n; K k; if ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) hash]) ! null) { if (first.hash hash ((k first.key) key || (key ! null key.equals(k)))) return first; if ((e first.next) ! null) { if (first instanceof TreeNode) return ((TreeNodeK,V)first).getTreeNode(hash, key); do { if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) return e; } while ((e e.next) ! null); } } return null; }这段代码浓缩了HashMap查找的三大防线第一道哈希值必须相等不相等直接淘汰hash不相等equals一定不相等可以安全跳过。第二道引用相等直接命中这是最快路径无需调用任何方法。第三道equals相等这才是真正意义上的业务key相等。你可以看到HashMap查值的每个环节都在尽可能先做廉价判断把昂贵操作往后放。这一行行代码背后其实是极致的性能设计。3.3 位运算的妙处为什么不用取模前面已经提到索引计算用的是(n - 1) hash这里再展开说透。如果你用hash % n在n为2的幂时结果一样但位运算的CPU指令效率更高。更重要的是hash % n在hash为负数时结果还是负数要额外处理而按位与直接避开了这个问题。这个细节也解释了为什么HashMap在扩容后元素要么留在原索引要么移动到“原索引 旧容量”的新位置。因为容量翻倍后n - 1的高位多了一个1原来用于确定桶位置的那一位正好是决定老位置还是新位置的“开关”。这种设计让扩容时很多元素不需要完全重新计算位置只需要看新增的位是0还是1性能上做了极大优化。这也是为什么HashMap扩容时不会像某些简单实现那样从头再来。3.4 remove与containsKey里藏着相同逻辑很多人用containsKey觉得它就是个“判断有没有”的方法其实它的实现就是getNode找到了返回true找不到返回false。remove也是先getNode定位到节点然后再在链表或树里做删除操作。它们和get共享同一套“hash定位 逐级匹配”的链路。所以一旦你把key的equals或hashCode搞坏了受影响的绝不仅仅是getcontainsKey、remove、put覆盖等所有依赖key匹配的操作都会一起出问题。4. 负载因子、扩容阈值与性能拐点的取舍4.1 负载因子为什么默认是0.75负载因子load factor是HashMap里最容易被忽略的构造参数。它决定了HashMap“多满才需要扩容”。默认值是0.75——这个数字既不是拍脑袋也不是百分比而是在空间和查询时间之间取得了一个工程平衡。负载因子越小比如0.5意味着还没存多少数据就开始扩容数组空位多、冲突少但内存浪费严重负载因子越大比如1.0意味着数组快满了才扩容桶里链表容易变长查询效率下降。0.75这个值其实来源于一个经验公式。官方文档没有给出精确数学推导但大家公认的是0.75在大多数场景下可以让桶内链表长度达到8的概率变得极低从而避免树化。如果你把负载因子调到1链表变长的概率会显著上升调到0.5内存开销可能增加一倍。所以在没有特殊需求时默认值就是最安全的选择。4.2 扩容的时机和代价扩容触发时机是size threshold其中threshold capacity * loadFactor。比如默认容量16负载因子0.75threshold就是12。当你put插入第13个键值对时就会触发扩容容量从16变成32threshold从12变成24所有元素重新计算桶位置并分配。这个过程叫rehash它的代价是O(n)因为要把每个节点迁移到新数组。对单个操作来说瞬间的耗时可能突然飙高这也是为什么“预先指定容量”在实际开发里是极其重要的性能优化。但要注意指定容量也不是说传多少就多少。如果你知道要存1000条数据计算一下需要 capacity * 0.75 1000所以 capacity至少得是1334向上取2的幂就是2048。如果直接传1000HashMap会扩容到1024但threshold是768还没等你存到1000就已经发生过一次扩容了白白多花一次迁移开销。4.3 初始容量设置的实战计算我经常看到有人这么写new HashMap(10000)以为这样就避免扩容了。实际上一万并不是2的幂HashMap内部会找大于等于一万的2的幂也就是16384而threshold是16384 * 0.75 12288。如果你只插入一万条虽然不会触发扩容但空间有一小半是空闲的。这其实还能接受。真正的坑是插入条数超过threshold下的容量——比如你传的是恰好能装下的数却忽略了threshold capacity * 0.75这个乘法导致预估失误。这里给出一个我的习惯预估数据量n后用capacity n / loadFactor 1计算然后再取大于等于这个值的2的幂。或者更省事一点直接调用Guava的Maps.newHashMapWithExpectedSize之类工具它内部就是做了这个换算。当然如果你不想引入依赖自己算也行公式并不复杂。4.4 一个实测对比设不设初始容量差别有多大以前我用一个模拟项目做过测试往HashMap插入500万条记录一种用默认构造后直接批量put一种先指定容量为1024万通过预估计算结果后者总耗时大约只有前者的70%。原因是默认方案在插入过程中触发了多次扩容和rehash每次都要重新计算并向新数组迁移数据累计起来相当可观。但也不要矫枉过正。容量设得太大初始分配大数组本身就有内存成本而且所有桶位一开始都是null用不到的话就是纯浪费。所以合理策略是“预估数据量再适当放宽”而不是盲目给一个很大的数字。5. 键对象的设计红线equals与hashCode为何必须一起重写5.1 自定义对象当key的典型翻车现场我见过最经典的翻车代码是拿一个自定义类当key只重写了equals没重写hashCode。例如class Person { private String id; public Person(String id) { this.id id; } Override public boolean equals(Object o) { if (this o) return true; if (o null || getClass() ! o.getClass()) return false; Person person (Person) o; return id.equals(person.id); } }然后两个new Person(1)按equals是相等的但hashCode不同因为继承的Object.hashCode()是不同对象返回不同整数通常是内存地址换算。当两个Person对象被放进HashMap后你想用其中一个去get另一个hash定位就落到了不同桶equals连上场机会都没有。表现就是——key“明明内容一样”却查不到值。5.2 两个约定一条都不能破Java规范里对hashCode和equals有三个约定其中两条对HashMap至关重要如果两个对象通过equals比较相等那么它们的hashCode必须相等。如果两个对象的hashCode相等它们并不一定equals相等哈希碰撞情况。第一条是HashMap能够正常工作的前提get时先用hash定位再用equals确定。如果“equals相等但hashCode不等”HashMap把两个相等的key当成了完全不同的人逻辑必然错乱。第二条则告诉我们hashCode相同时还会出现冲突桶所以equals的判断依然不能省略。5.3 写一个可靠的键类可靠键类的基本要求有三个不可变或至少业务关键字不变、重写equals、重写hashCode。比如身份证号、订单号、URL这样的业务主键天然适合做key。实现时你不需要从零发明。如果ID字段是String直接用Objects.hash(id)生成hashCodeequals则用Objects.equals(id, other.id)。如果类有多个业务字段把所有参与业务相等的字段都放进hash计算。注意参与equals判断的字段必须全部参与hashCode计算并且用于hashCode的字段不应该出现“因为是随机生成每次不同”的情况。拿new Date()当key就是一种灾难——每次hashCode都可能不同放入后又查不到。5.4 不可变对象的额外收益用String、Integer这类不可变对象当key时不仅hashCode稳定还天然满足equals对称性、传递性这些要求。我建议能直接用JDK的标准类型当key就别自定义。如果必须自定义也要保证这个类的业务字段在放入Map后永远不会被修改。一旦某个key对象的hashCode在放入后变化了后续get时就会定位到错误桶几乎只能靠遍历整个map才能找到——而且即使找到了也是错的索引位置根本拿不到value。这种bug难以排查所以最好从设计上就堵死。6. 开发中的常见误用与实测经验6.1 HashMap不是线程安全的并发下的三种事故现实中很多人拿HashMap当全局缓存多线程读写然后某天突然CPU飙升或死循环。JDK 1.7的HashMap在并发扩容时可能出现链表环导致get时无限循环。1.8修复了链表环问题但它依然不是线程安全容器多个线程并发put可能导致数据丢失、覆盖、size统计不准等问题。即使在1.8下并发put时两个线程同时看到了相同空白桶都会往里写节点后写的覆盖先写的数据直接丢失。正确的并发姿势是如果需要线程安全的Map要么给外层加锁要么直接用ConcurrentHashMap。注意很多面试题喜欢问“Hashtable为什么慢”因为它的所有方法都是synchronized串行化严重而ConcurrentHashMap用分段锁或CAS并发度要好得多。6.2 null键和null值的容忍度HashMap允许null作为key并且只允许一个。扰动函数里看到key null ? 0null会被固定映射到第0个桶。取的时候get(null)也能正常返回。这在实际业务中方便但也可能让你写下map.get(key)后分不清是“没有这个key”还是“这个key的value就是null”——如果不确定用containsKey判断一下。另外Hashtable和ConcurrentHashMap都不允许null key或null value这点在迁移代码时需要格外小心否则一个简单的put就会抛NullPointerException。6.3 遍历时的结构修改陷阱在遍历HashMap的过程中如果直接调用put或remove修改了map的结构增加或删除键值对会触发快速失败机制抛出ConcurrentModificationException。这是由modCount字段监控的。解决方式有两种用迭代器的remove方法或者先把要删的key收集到一个list遍历结束后再统一remove。在迭代时还要留意一点HashMap的遍历顺序是桶顺序加链表顺序和插入顺序无关。如果你需要按插入顺序遍历可以用LinkedHashMap它在HashMap基础上额外维护了双向链表代价是略微增加内存。6.4 与LinkedHashMap、TreeMap的选择做技术选型时很多人把HashMap奉为唯一真理其实不同Map有不同适用场景HashMap绝大多数场景平均查询最快。LinkedHashMap需要维持插入顺序或访问顺序可做LRU缓存。TreeMap需要按键排序底层红黑树支持范围查询但操作是O(log n)。不要因为HashMap快就哪里都用。比如你需要在有序列表上做范围查询TreeMap更合适需要做LRU缓存LinkedHashMap稍微改造就能用。6.5 两个工具箱里的实用技巧我自己写代码时有两个小习惯推荐给你。第一凡是能预估数据量的地方务必先估算并设置初始容量别依赖自动扩容。第二当map里装的是大value对象时需要判断“是否存在”尽量用containsKey而不是先get null这个前面说过了但实际很多人还是会踩。最后一个值得分享的排查技巧当你发现HashMap“存得进去取不出来”时先检查key对象的equals和hashCode如果你用了自定义类去查这两个方法有没有被正确重写以及key对象的业务字段是否在存进去之后被某个setter改动了。我的经验是90%的HashMap诡异问题都出在这两处剩下的再去怀疑并发和扩容都不迟。HashMap底层没有多深奥但把它吃透需要把“哈希函数、冲突、扩容、equals/hashCode”这几条线串起来。当你真正理解“通过key找value”是建立在“先粗定位、再细匹配”这套机制上时很多问题不用查资料也能自己推断出来。希望这篇基于标题展开的拆解能帮你在实战中少踩几个坑。