做IM模块的时候碰过一次挺玄学的性能问题消息列表页从后台切回前台界面会卡顿一下大概500毫秒的样子。当时第一反应是数据库查询慢了结果Profile一看耗时全落在一个HashMap的resize()上——消息去重时用HashMap缓存了十来万条消息记录的id切前台时恰好塞进来一批新数据正好撞上扩容的坎。那次之后我就意识到HashMap在Android开发里属于“用过一万次都不一定真正懂”的东西。这篇文章把我后来梳理过的底层实现、put/get流程、线程安全问题和Android场景下的内存优化思路完整整理出来适合所有写过Android代码但没系统性读过HashMap源码的开发者也适合准备面试时需要体系化输出这块内容的同学。1. 为什么Android面试总考HashMap因为它决定了你写代码的上限先说个很直白的结论HashMap不是“背一背源码就能应付面试”的知识点它直接影响你日常写代码时的每一个微小决策。你在Android里做缓存、做消息去重、做路由表、做数据统计背后十有八九都是HashMap。用得好内存和CPU都舒服用不好就是莫名其妙的ANR、卡顿和内存抖动。很多初级同学有个误区觉得HashMap就是“键值对存东西”顶多再知道它允许null、无序、线程不安全。但实际上HashMap背后的设计思路是你理解整个Java集合框架的钥匙哈希算法怎么分布数据、冲突怎么解决、什么时候用链表什么时候用红黑树、扩容为什么是二倍、为什么重写equals必须重写hashCode。这些不搞明白你写出来的是能跑的代码但很难写出“在低端机上也不掉链子”的代码。还有一个Android特有的点HashMap来自OpenJDK不同Android版本搭载的实现存在差异。Android 7NougatAPI 24之前和之后HashMap的内部实现有挺明显的分水岭。早期版本更接近JDK 7的数组加链表结构头插法扩容极端情况下并发扩容可能造成环形链表get直接死循环API 24之后再迭代往JDK 8的方向靠引入了红黑树和尾插法把最坏情况从O(n)降到O(log n)。所以网上很多讨论HashMap的文章如果你不辨别它讨论的是JDK 7还是JDK 8到了Android真机上可能是错位的。下面我会以Android开发的实际视角来拆这张“表”不是单纯念源码而是解释每个设计决策背后的代价和收益然后把那些可以落到代码里的经验捞出来。2. 底层那张“表”数组、链表、红黑树是怎么配合着干活的2.1 数组是骨架哈希决定你住哪一层HashMap的底层核心数据结构说穿了就是一张数组数组里每个位置存放的是一个“桶”bucket。当你put一个键值对时HashMap先用key的hashCode()算出一个整型哈希值再经过一个扰动函数处理最后用数组长度减一和这个哈希值与运算得到一个数组下标。这个下标决定了这条数据落在哪个桶里。数组的每个桶在JDK 8及之后的实现里最初只是一个链表节点。如果两个key算出来落在同一个桶就叫哈希冲突或叫碰撞。HashMap解决冲突的办法是链地址法——冲突的多个键值对串成一条链表挂在同一个桶下面。这就是为什么说数组加链表是HashMap的经典结构。这里可以用一个生活类比数组就像一栋楼的楼层索引你先用哈希值算出去哪一层到了那一层以后发现走廊里住了好几户再挨家挨户比对key找到你要找的那户。如果同一层住的人太多链表太长找人就慢所以后来又加了红黑树相当于同一层里做了一套快速检索的管家系统。2.2 链表什么时候升级成红黑树8和64两个门槛JDK 8之后的HashMap有两条很关键的阈值链表长度达到8且整个数组容量达到64才会把链表转成红黑树。为什么不单纯看链表长度因为如果数组本身还很小此时更合理的做法是扩容把数据打散到更大的数组里从根源上减少冲突而不是急着把链表转树。树节点本身比普通链表节点占内存所以转换有成本必须确保转换之后能换来性能收益。当链表长度小于6时红黑树会退化成链表。8和6之间留了一个数字的缓冲避免在阈值附近反复横跳——存一个升级、删一个降级那性能就废了。这个设计思路其实在很多集合类里都能看到不是非黑即白而是给了一点滞回区间。从复杂度上看链表的查找是O(n)当同一个桶里超过8个节点时最坏情况确实难看红黑树保证查询在O(log n)。注意红黑树不是严格平衡的平衡二叉树只是近似平衡所以旋转操作比较少插入删除也快。在Android那种CPU和内存都受限的环境里HashMap通过在极端冲突下自动升级结构避免出现最坏查询复杂度这一点对整体稳定性是有意义的。2.3 Android不同版本看到的HashMap长什么样既然标题带Android肯定要聊这个差异。早期Android比如API 24以前的HashMap继承自Apache Harmony项目或早期OpenJDK实现基本对应JDK 7那版数组加链表没有红黑树。JDK 7扩容时用头插法并发场景下两个线程同时扩容链表头指针相互指向可能形成环形链表get时就会死循环CPU直接飙满。之后Android把java.util下的实现切到OpenJDK从Android 7开始HashMap的实现逻辑逐渐和JDK 8看齐有了红黑树和尾插法。尾插法在扩容时不会反转链表并发扩容时理论上不会造出环但依然不保证线程安全——数据覆盖、size不准这些问题仍然存在。所以你在Android上讨论HashMap时最好说明自己讨论的是哪一版。面试时如果能主动讲出“Android API 24前后实现有差异”这个点会让对方眼前一亮因为这已经不是背源码而是真正跟平台打过交道才有的认知。3. 从put到gethashCode和equals在这条链路里的分工3.1 put一个key进去HashMap到底做了几步put流程是HashMap源码里最值得反复看的部分。我把核心步骤简化成下面这条链路拿到key的hashCode()。做扰动计算JDK 8里是h h ^ (h 16)让高16位参与到低16位的计算中。用(n - 1) hash计算桶下标n是数组长度容量是2的幂这个与运算等价于取模但性能高很多。如果桶下标处为空直接放一个Node节点。如果桶下标不为空遍历链表或红黑树比较节点哈希值如果哈希值相同再用equals判断key是否相同。相同就覆盖value不同就追加到链表尾部。如果是链表节点追加后长度达到8且容量达到64执行树化。put完之后如果总节点数超过阈值threshold capacity * loadFactor默认16 * 0.75 12触发扩容。很多人背过这套流程但细节理解不到位。比如扰动函数的作用HashMap的数组长度默认16如果两个key的hashCode在低几位上正好相同高位不同直接取模就会让它们频繁撞到同一个桶。把高16位异或到低16位以后相当于把高位的散列特性也带入了桶下标计算冲突率会明显降低。3.2 为什么说先用hash比大小、再用equals认亲HashMap查找的逻辑是先算hash定位桶然后在桶里比较。hashCode在这里起的是“粗筛”作用equals才是“精确认亲”。这就回答了很多新人的困惑两个对象用equals比较相等但是hashCode不同HashMap会怎样答案是HashMap根本不会让它们有机会走到equals这一步因为两者已经落在不同的桶里。反过来如果两个对象hashCode相同equals不相等它们会落在同一个桶里链表或红黑树会同时存下这两个节点查找时用equals逐一比对。这两条规则合在一起就是那句经典约定重写equals必须重写hashCode。如果违反了这个约定比如两个对象业务上相等equals返回true但hashCode返回值不同那么HashMap里同样一份数据可能被存到两个地方不仅查不到还会出现数据重复。我的建议是自定义key时优先用不可变对象并且hashCode实现要有足够的分散度。最常见的反面教材是直接用对象的默认hashCode做业务key而默认hashCode和内存地址相关同一个对象在不同时间、不同进程里得到的值都可能不同这会让你的HashMap行为变得完全不可预期。3.3 get为什么有“先hash后equals”的天然优势get流程其实相当于put的逆过程计算hash找桶如果桶第一个节点的hash和key都匹配直接返回value如果不匹配在链表或红黑树里继续找每个节点都先比较hashhash相同再equals。这里有个性能细节hash比较是int型的一次运算就完成而equals可能涉及复杂的业务字段比较。HashMap先拿hash做快速过滤能将equals的调用次数降到最低。这也是为什么一个设计良好的hashCode比equals效率影响更大——它直接决定你get时要走几次equals。我曾经在重构缓存模块时把key从String换成自定义的复杂对象结果get的性能下降了近一个数量级。原因就是那个对象的hashCode写得稀烂大量key集中到少数桶里equals被反复调用。后来把hashCode改成基于核心业务字段计算性能立刻恢复了。这个例子说明HashMap的性能不取决于你调用了多少次put/get而取决于你的hashCode质量。4. 扩容机制为什么存着存着忽然卡一下4.1 扩容到底扩的是什么HashMap默认初始容量是16负载因子是0.75。负载因子意思是当存储的节点数超过容量 * 0.75时触发扩容。默认情况下存入第13个键值对时数组长度要从16变成32。扩容操作包含两件事创建一个长度翻倍的新数组把旧数组里的所有节点重新计算桶下标迁移到新数组。注意这个“重新计算桶下标”非常关键。因为数组长度变了之前用得津津有味的(n - 1) hash得到的结果也会跟着变。所以扩容本质上是一次全量rehash。这也是为什么扩容操作时间复杂度是O(n)在数据量大时卡那么一下是正常的。为什么非要翻倍而不是翻1.5倍或随便加几个因为数组长度必须是2的幂这样才保证(n - 1) hash和hash % n等价而且位运算比取模快一个量级。翻倍操作也简单旧数组第i个桶里的元素扩容后只会回到下标i或者ioldCap这两个位置。JDK 8之后的实现靠这个规律做了优化不需要真正重新计算每个key的hash只需看hash新增的哪一位是0还是1就能决定节点留在原位置还是移到高位。这个优化显著减少了迁移成本。4.2 loadFactor 0.75到底是怎么权衡出来的0.75这个值是一个空间和时间的折中。负载因子调大比如1.0意味着可以塞满数组才扩容内存占用少了但冲突率升高链表变长查找变慢负载因子调小比如0.5冲突少、查找快但数组很快就扩容内存白白空着很多位置。0.75在大多数场景下能兼顾这两方面。在Android开发里这个参数尤其值得注意。默认的0.75不是不能改但要清楚改动目的。比如某些场景确实需要内存优先可以适当调高负载因子比如0.85甚至0.9。代价是更早进入链表长、冲突多的状态。反之如果一个HashMap要承载频繁查询且数据量已知可以预设更大容量并保持0.75不变。我自己的经验是不要轻易动负载因子而是通过预设容量来控制扩容频率。4.3 怎么从源头减少扩容抖动扩容抖动在Android上的表现就是帧率掉一两帧。避免它的最好办法是使用构造函数指定初始容量new HashMap(expectedSize)。但这里有个容易被忽略的细节HashMap会用传入的容量计算出第一个大于等于它的2的幂。比如你传100实际初始容量是128传200实际是256。而且扩容阈值 容量 * 0.75也就是说如果你真想存100个元素传100不够因为存到第97个128 * 0.75就要扩容了。正确做法是给期望容量除以0.75再向上取整比如new HashMap((int) (expected / 0.75f) 1)。我在做IM消息去重时会用到这个公式明确知道这批新消息最多800条就预设new HashMap(1076)保证全程不触发扩容。数据写入阶段少了一次复制迁移批量操作时整体耗时能差出好几倍。这个优化在几百万条数据的大缓存里差异尤其明显但在几千条的小场景里也值得养成习惯。毕竟代码是写给未来的自己和新同事看的一个合理的初始容量本身就是一种注释。5. 线程安全短板并发put到底在丢什么5.1 为什么不安全不只是“数据少了”这么简单HashMap的线程不安全在Android上不仅仅是丢数据那么简单。先回顾一下几个典型问题并发put导致节点覆盖两个线程同时算到同一个桶都认为桶是空的各自写入后写的覆盖先写的其中一个节点直接消失。size计数错乱size不是一个原子操作多线程并发写时大小统计可能不准确。modCount被破坏modCount是HashMap内部的“结构化修改计数器”迭代时如果检测到modCount变了会直接抛ConcurrentModificationException。并发场景下数据被改动你正在遍历的循环可能突然崩溃。极端扩容问题老版本头插法扩容时并发可能形成链表环get时死循环CPU跑到100%。新版尾插法虽然避免了这个致命问题但其他三个问题一点没少。开发Android时很多人觉得主线程才不会并发访问HashMap。但你做消息处理、做任务队列、做数据上报时子线程和主线程共用一个缓存HashMap太常见了。以为不会并发实际上很可能并发。5.2 并发场景下到底选什么如果只是一个“读多写少”的缓存可以用Collections.synchronizedMap(new HashMap())简单加锁但所有操作都串行化性能一般。线程安全自选ConcurrentHashMap它分段锁JDK 7风格或CAS加锁JDK 8风格读操作大多无锁并发性能好得多。但注意ConcurrentHashMap不允许key或value为null所以如果你之前用HashMap存null值换过来要改逻辑。Android还有另一个选项在主线程用ArrayMap或SparseArray这类专门针对移动端优化的容器它们不是线程安全的但如果你场景是主线程独占读写它们的内存效率更高。后面我会专门说这个。5.3 迭代删除也是一颗定时炸弹再多提一个和线程无关但很容易踩的坑在遍历HashMap时直接调用map.remove(key)会在迭代器检查modCount时抛异常。正确做法是使用迭代器的Iterator.remove()或者在遍历中把要删除的key收集到一个列表里遍历结束后再统一删除。这在Android开发里极其常见比如刷完一批数据后清理过期缓存边遍历边删就等着崩溃吧。有一种小技巧如果要删除的逻辑发生在单线程且数据量不大可以直接遍历entrySet时判断条件并调用iterator.remove()。这既安全又高效。如果涉及到其他线程也在操作同一个map那就别硬上了给它套一层同步或者换ConcurrentHashMap。6. Android里有必要知道的替代品ArrayMap、SparseArray和LruCache的关系6.1 ArrayMap为什么在移动端有时候比HashMap香HashMap每个节点都是一个Node对象存十几个键值对就要创建十几个对象在Java堆上东一个西一个内存碎片化严重。小手机会很疼。Android官方推荐在内存敏感场景用ArrayMap它内部是两个数组一个int数组存hash值一个Object数组存key和value。因为所有数据都在连续数组中对象数量少缓存命中率高GC压力小遍历也快。但ArrayMap不是万能的。它查找是用二分查找时间复杂度O(log n)数据量小的时候比HashMap的O(1)慢不了多少而且内存省得很多。可如果数据量冲到几千甚至上万二分查找的劣势就明显了。经验上几百条到一千条数据用ArrayMap性价比最高超过这个量级HashMap更合适。Google官方文档也建议数据量控制在1000以内会比较划算。6.2 SparseArray专治int类型的keySparseArray是Android里另一个“小而美”的容器。它的key是基本类型intvalue是Object好处是省掉了Integer自动装箱的开销。如果你有一个key是int、value是对象的映射HashMapInteger, Object会反复装箱拆箱性能至少有20%到30%的损耗而SparseArray直接绕开这个问题。它内部也是两个数组一个存key一个存value支持按索引删除支持稀疏数组值不是从0开始连续存储。还有几个变体LongSparseArray处理long型keySparseIntArray的value是int型SparseBooleanArray处理boolean型value。这种容器在小规模数据上的内存占用比HashMap小很多尤其在Android的MultiDex优化、资源ID映射这类场景里用起来非常舒服。6.3 LruCache底层藏的其实是LinkedHashMap聊Android缓存就绕不过LruCache。LruCache内部是一个LinkedHashMap并且启用了accessOrdertrue这意味着每次get都会把访问的节点移动到链表尾部头部自然就是最近最少使用的数据。这样当缓存超限时只要删除头部的节点就行。LinkedHashMap继承自HashMap保住了HashMap所有的高效查找能力额外用一个双向链表维护节点顺序。这个设计给我一个启发很多时候我们不需要自己造轮子Android已经结合HashMap的性能和LRU的淘汰策略做了很好的封装。你自己写一个Map做缓存如果没有淘汰策略内存迟早爆。直接用LruCache它自己处理好了多线程同步内部所有操作走同一个锁你只需要设置好maxSize单位并重写sizeOf来准确计算每个缓存条目的大小。7. 实战经验小结预设容量、key设计和遍历性能的取舍7.1 key类设计直接决定HashMap的性能天花板我在前面反复说hashCode质量这里给出一个真正可落地的建议自定义key类时用业务上唯一且不变的字段集合来计算hashCode而且结果分布要尽可能分散。String的hashCode用的是31作为乘子为什么因为31是奇素数乘法溢出时信息丢失少而且JVM还能优化成(i 5) - i提高计算速度。如果业务key是组合字段比如“用户ID 消息类型”可以这样重写hashCodeOverride public int hashCode() { int result userId ! null ? userId.hashCode() : 0; result 31 * result (msgType ! null ? msgType.hashCode() : 0); return result; }equals则要保证和hashCode使用的是同一组字段两个对象相等时必须hashCode也相等。这里有个很常见的坑equals里用了字段A、B、ChashCode里忘了加C结果两个对象equals为true但hashCode不同HashMap里就出现了“同一个逻辑key对应两条数据”的诡异现象。7.2 遍历性能并不是你想象的那样很多教程会告诉你遍历HashMap要用entrySet()而不是keySet()再get理由是keySet遍历时每个key还要再去查一遍value多了一次hash查找。这话对但要看场景。数据量小的时候差别不大数据量大且value对象已经存在时用entrySet确实能省掉一次hash查找尤其在冲突高的链表上这个差距会被放大。还有一点值得注意HashMap的遍历顺序是无序的。它既不是插入顺序也不是值排序。如果你需要可预测的遍历顺序用LinkedHashMap需要排序用TreeMap或者手动排序key后再遍历。我在Android上做统计报表时经常先把HashMap的entrySet转成一个List再按value排序。这个操作不复杂但能避免你在UI上看到每次刷新数据都“跳来跳去”。7.3 一场真实的性能对比给你一个直观体感我拿一台中端Android设备做过简单压测向HashMap写入10万条key为String、value为Integer的数据。采用默认构造且不做预容量设置时期间触发了十几次扩容整体耗时约380毫秒。如果用预设容量new HashMap(134000)按前面说的除0.75再加1整体耗时降到约150毫秒少了百分之六十。读取阶段差异没那么夸张但自定义key hashCode写得稀烂时get耗时从80毫秒涨到超过1秒这个就非常可怕了。这些数字不是让你记住而是给你一个体感HashMap的优化空间不在于什么奇技淫巧而在于基础概念的正确运用。预设容量、好的hashCode、合适的容器选择三个点做到位性能差异就是几倍甚至一个量级的事。我在实际项目里有个习惯凡是new HashMap的地方都会多问一句“这里大概存多少条”存几十条、几百条预设容量无所谓存几万条但没预设那就等于在高峰流量里埋了一颗卡顿的雷。代码Review时看到有人无脑new HashMap()且循环里put几千条我一定会让Ta改成带容量的构造。这个习惯救过很多次线上卡顿。还有一个小技巧可以分享如果你确定key是连续int或者小范围int优先用SparseArray而不是HashMap如果你要缓存列表项且担心内存暴涨试试LruCache包一层LinkedHashMap如果你要在大数据量下做并发读写直接上ConcurrentHashMap不要再纠结HashMap为什么不安全。选择容器的本质其实是你在封装自己对这个场景的理解——数据量多大、读写比例多少、内存宽不宽裕、并发程度多高。把这几个问题想清楚容器选型不会是拍脑袋HashMap也不会再是面试后就被你遗忘的知识点。