企业官网建设流程全解析

做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 7（Nougat，API 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到get：hashCode和equals在这条链路里的分工

3.1 put一个key进去，HashMap到底做了几步

put流程是HashMap源码里最值得反复看的部分。我把核心步骤简化成下面这条链路：

1. 拿到key的hashCode()。
2. 做扰动计算，JDK 8里是h = h ^ (h >>> 16)，让高16位参与到低16位的计算中。
3. 用(n - 1) & hash计算桶下标，n是数组长度，容量是2的幂，这个与运算等价于取模，但性能高很多。
4. 如果桶下标处为空，直接放一个Node节点。
5. 如果桶下标不为空，遍历链表或红黑树，比较节点哈希值；如果哈希值相同，再用equals判断key是否相同。相同就覆盖value，不同就追加到链表尾部。
6. 如果是链表节点追加后长度达到8，且容量达到64，执行树化。
7. 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；如果不匹配，在链表或红黑树里继续找，每个节点都先比较hash，hash相同再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，或者i+oldCap这两个位置。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类型的key

SparseArray是Android里另一个“小而美”的容器。它的key是基本类型int，value是Object，好处是省掉了Integer自动装箱的开销。如果你有一个key是int、value是对象的映射，HashMap<Integer, Object>会反复装箱拆箱，性能至少有20%到30%的损耗，而SparseArray直接绕开这个问题。它内部也是两个数组，一个存key一个存value，支持按索引删除，支持稀疏数组（值不是从0开始连续存储）。

还有几个变体：LongSparseArray处理long型key，SparseIntArray的value是int型，SparseBooleanArray处理boolean型value。这种容器在小规模数据上的内存占用比HashMap小很多，尤其在Android的MultiDex优化、资源ID映射这类场景里，用起来非常舒服。

6.3 LruCache底层藏的其实是LinkedHashMap

聊Android缓存就绕不过LruCache。LruCache内部是一个LinkedHashMap，并且启用了accessOrder=true，这意味着每次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 + 消息类型”，可以这样重写hashCode：

@Override 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、C，hashCode里忘了加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也不会再是面试后就被你遗忘的知识点。