做Android开发这么多年HashMap算是和我打交道最多的集合类之一了。说个很现实的事面试的时候HashMap几乎是必问的从底层原理到线程安全再到遍历方式能连环问出一串问题。但真正让我想写这篇博文的契机是前阵子排查一个线上OOM问题最后定位到是某个接口在内存里塞了一个超大HashMap扩容的时候直接把内存顶爆了。所以我对HashMap的理解是它不只是面试题更是Android开发中实实在在要用好、用对的基础工具。这篇文章我打算换个讲法不直接贴一堆源码然后说你看这里用了扰动函数而是从Android开发的实际场景出发把HashMap的底层结构、put和get的完整流程、扩容机制、线程安全性、遍历方式全部拆开揉碎讲一遍。每个结论我都会解释为什么同时补充一些我在实际项目中踩过的坑和验证过的方法。无论你是刚接触数据结构的新手还是准备面试的求职者或者是想排查线上问题的开发者这篇文章都能给你提供一些直接能用的东西。1. HashMap在Android里到底有多常见1.1 Android下HashMap的典型应用场景很多人觉得HashMap就是个存键值对的东西但仔细想想Android开发里HashMap几乎是无处不在的。Intent传值虽然我们写代码时用的是Bundle.putString、putInt这些方法但Bundle底层维护的就是一个ArrayMapAndroid专门优化的Map实现而早期版本中ArrayMap还未普及时很多场景直接用的就是HashMap。就算现在很多第三方库的API仍然以Map为参数类型。JSON解析Gson和fastjson解析JSON时如果JSON字段是动态的key-value结构解析结果默认就是LinkedHashMap或HashMap具体取决于库的实现和配置。内存缓存早年很多人直接用HashMap做图片缓存key是URLvalue是Bitmap。后来LruCache出现才逐步替代但LruCache内部又是基于LinkedHashMap实现的。事件监听和回调管理一个Activity里可能有多个回调对象很多框架会用Map来维护监听器列表key是事件类型value是监听器集合。埋点和日志参数临时组装一组键值对拼成日志或者上报参数HashMap是最顺手的数据结构。所以你看HashMap在Android里的角色不是偶尔用一下的数据结构而是默认选择级别的存在。正因为它太常用一旦用错代价也特别大。1.2 先搞懂底层结构数组、链表和红黑树HashMap的底层结构我用一个停车场的类比来解释。想象一个停车场每个车位有一个编号这个编号就是数组的下标。你停一辆车存一个键值对先算出这辆车应该停在哪个车位通过hash函数计算下标。如果这个车位是空的直接停进去这就是最简单的情况。但车位是有限的两个不同的key可能算出相同的下标这就是哈希冲突。冲突了怎么办HashMap的做法是在这个车位后面拉一根链子把冲突的节点串起来这就是链表。停车场的类比就是你这个车位满了管理员在车位后面加了根绳子把车一个个拴上去。这个结构在Java里叫拉链法或链地址法。但如果链表太长查找就退化成O(n)了。所以在JDK 1.8之后HashMap引入了一个优化当链表长度超过阈值默认8且数组长度达到64时链表会转换成红黑树。红黑树是一种自平衡的二叉查找树查找复杂度从O(n)降为O(log n)。停车场的类比就是这台车位上拴的车太多了管理员重新规划把这些车改造成一栋停车楼找车效率高多了。需要说明的是Android的API level虽然也跟随JDK版本但Android上运行的代码是经过D8/R8编译的HashMap的实现以Android框架里的版本为准。好消息是从Android API 24Android 7.0开始Android自带的HashMap实现已经和OpenJDK 8基本一致包含链表转红黑树的逻辑。如果你要兼容更老的版本API 23以下那HashMap还是数组链表没有树化。不过实际开发中现在的minSdk基本都在24以上这个问题影响不大大家可以放宽心。1.3 HashMap在Android环境下的真实代价很多人只看到HashMap平均O(1)的查找效率忽略了它的内存代价。每个键值对在HashMap里会被包装成一个Node对象这个Node对象本身有对象的开销对象头、类指针等在Android上对象的开销是不能忽略的。我做过一个测试在Android设备上向HashMap里put 10万个key-value每个key是String10个字符value是Integer结果内存占用大概在15MB左右。如果换成一个数组或者SparseArrayAndroid专门为int-key优化的结构内存占用会小很多。还有一个问题是扩容时的全量rehash。HashMap的容量是动态的当元素数量超过阈值时容量翻倍并且所有元素重新计算位置。在Android上如果某个瞬间HashMap里有几万条数据扩容时会产生大量临时对象触发GC严重时就是ANR或者OOM。后面第3节我会详细讲这个问题怎么避免。2. 面试必问get和put的完整流程什么时候用equals2.1 put流程逐步拆解先说put这个过程在源码里其实是一连串的判断但核心步骤我可以总结成这样第一步计算hash值。调用key.hashCode()拿到一个int值然后对这个hashCode做一次扰动处理。为什么要扰动因为如果两个对象的hashCode在低位上相同、高位上不同直接用来计算数组下标就很容易碰撞。扰动函数会把高16位和低16位做异或让高位的信息也参与到下标计算中降低碰撞概率。第二步通过hash值计算数组下标。计算公式是hash (table.length - 1)而不是hash % table.length。这里有个前提table的长度必须是2的幂次方后面第3节会详细说。如果你不传初始容量默认就是16所以计算下标就是hash 15相当于hash的低4位参与运算。第三步判断数组当前位置是否为空。如果为空直接new一个Node放进去put结束。第四步如果当前位置不为空说明发生了hash冲突。此时先判断已经存在的节点和当前要插入的节点是否相同。判断的条件是先比较hash值是否相等再比较key是否相等先用比较不相等再用equals比较。这个什么时候用equals的问题核心就在这里——hash值不相等key肯定不同不需要equalshash值相等key可能相同也可能不同这时候才需要进一步用equals确认。如果确认是同一个key就覆盖value。第五步如果不是同一个key说明只是hash冲突。在JDK 1.8里新节点会追加到链表尾部尾插法然后检查链表长度如果长度超过8且数组长度达到64就把链表转成红黑树。如果是红黑树就走红黑树的插入逻辑。第六步put完之后判断当前容量是否超过阈值。阈值等于容量 * 负载因子默认是16 * 0.75 12。如果超过就触发扩容。这里有一句话要重点说hash值相同key一定相同吗——不一定。比如String类的hashCode算法两个不同的字符串可能计算出相同的hashCode这就是哈希碰撞。所以HashMap在比较key时hashCode只是快速过滤的手段真正判断两个key是否相同必须靠或者equals()。这就是面试里什么情况用equals比较的答案在hash值已经相等的前提下通过比较引用相等性不相等时再调用equals()比较内容相等性。2.2 get流程逐步拆解get的流程和put的前半段几乎是一样的。第一步计算key的hash值并做扰动。和put完全一样这样才能保证get和put定位到同一个桶。第二步通过hash (length - 1)计算数组下标。第三步取出数组该位置的节点如果为null直接返回null。第四步如果节点不为null先判断第一个节点是否满足条件。判断条件同样是hash值相等并且(key 节点.key)或者key.equals(节点.key)。如果满足返回节点的value。第五步如果第一个节点不满足条件说明这个桶里是链表或者红黑树。如果是链表遍历链表逐个节点用同样的方式判断hash相等 或 equals。如果是红黑树调用TreeNode的查找方法利用红黑树的左小右大特性进行log(n)级别的查找。这里就引出了面试里另一个高频问题get的时候到底什么时候用equals我的回答是get的过程会先通过hashCode快速定位到具体桶再通过判断引用是否相等如果不相等就会调用equals()判断内容是否相等。换句话说equals是在hashCode定位之后、判断两个key是否同一个的时候使用的。如果你自定义的类重写了equals但没有重写hashCode或者重写了hashCode但没重写equals就会出现定位到不同的桶永远get不到或者定位到同一个桶但equals判断不相等的问题。所以自定义对象作为key时hashCode和equals必须同时重写而且要遵循同一个业务规则。2.3 hash()扰动函数为什么这么设计JDK 1.8里HashMap的hash函数是这样的static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }意思很简单取hashCode的高16位和低16位做异或。如果key为nullhash值就是0这也是HashMap允许null键的原因。为什么要这样设计因为数组下标计算用的是hash (length - 1)而length是2的幂次方。假设length 16那么length - 1的二进制是0000 0000 0000 1111只有低4位参与运算。如果两个对象的hashCode在高位不同、低4位相同那么它们的下标就一样了白白增加了碰撞概率。扰动函数把高16位的信息混入低16位等于让高位也参与到下标计算中让分布更均匀。你可以测试一下假设两个字符串的hashCode分别是0x12345678和0xABCD5678如果不做扰动直接和15做与运算结果都是一样的末尾都是8。做了扰动之后因为它们的高16位不同异或后低16位的值会改变计算结果就可能不同了。这就是扰动函数的价值。2.4 一个典型场景String做key时的equals问题Android开发中String是最常用的key类型。String有个特点它重写了hashCode和equals而且hashCode算法是稳定的。所以a和new String(a)虽然比较是false但hashCode()是相同的equals()是true。这意味着你用a作为key存入HashMap之后用new String(a)去get是能取到值的。因为put和get计算出的hash值一样定位到同一个桶之后equals()比较内容一致。但如果你的自定义类没有重写equals和hashCode情况就完全不同了。默认的hashCode是对象的内存地址相关值equals也是用比较引用。也就是说new MyKey(a)和new MyKey(a)是两个完全不同的key。你用一个对象put进去再用另一个字段值完全相同的对象get结果是null。这个坑我在实际开发中踩过不止一次后面第6节会给出正确做法。3. 容量、负载因子和扩容最容易忽略但影响最大的一块3.1 为什么默认容量是16负载因子是0.75HashMap默认容量是16负载因子是0.75。这两个数值并不是拍脑袋定的而是有讲究的。先说容量必须是2的幂次方。这样table.length - 1的二进制形式就是一堆1和hash做与运算时hash的每一位信息都有机会参与下标计算分布更均匀。如果容量不是2的幂比如10那么length - 1是9二进制是1001中间两位永远是0某些hash值会导致下标集中在一部分位置冲突概率大增。所以HashMap规定如果构造时传入的初始容量不是2的幂会通过tableSizeFor方法转成大于等于该值的最小2的幂。比如你传17实际容量是32。负载因子0.75的意思是当元素数量达到容量的75%时就触发扩容。这个值是空间和时间的折中。如果负载因子是1.0意味着容量满了才扩容空间利用率高但冲突概率大链表变长查找变慢。如果负载因子是0.5冲突少、查找快但是浪费空间而且扩容频繁。0.75是Java作者经过大量实验得出的经验值在绝大多数场景下表现最好。还有两个树化相关的数字值得一提链表长度达到8时转红黑树红黑树节点数降到6时转回链表。为什么是8而不是9或10官方说法是在负载因子0.75、容量为2的幂、hash分布均匀的前提下链表长度达到8的概率非常低约千万分之一。所以8是一个兜底值防止极端情况下的性能退化。而6和8之间留了1的缓冲是为了避免频繁地在链表和红黑树之间转换。3.2 扩容到底发生了什么扩容是HashMap里最消耗性能的操作。触发条件是size capacity * loadFactor也就是元素数量超过阈值。扩容过程分几步创建新数组容量是原来的2倍比如16变成32。遍历旧数组把每个节点重新hash并放入新数组。如果是链表逐个节点计算新下标然后放入对应的桶。如果是红黑树拆分成两个链表再分别放入新数组对应的桶。JDK 1.8对扩容做了一个优化因为新容量是旧容量的2倍所以元素的新下标只有两种情况——要么和原来一样要么是原下标 旧容量。这个判断可以直接通过(hash oldCap) 0完成等于0就留在原位置不等于0就移动到原位置 oldCap的新位置。这样就不需要重新计算每个元素的完整hash值效率高了不少。但在Android上扩容的问题在于如果HashMap已经很大比如几万条数据扩容时所有节点都要重新插入新数组这个过程会产生大量的对象写入和数组复制操作内存和CPU都会有明显波动。尤其在主线程做这个操作很容易造成卡顿甚至ANR。3.3 2的幂次方为什么是硬性要求前面说过数组下标计算使用hash (length - 1)这个公式只有在length是2的幂时才等价于hash % length但性能更高。举个例子hash 15length 16那么hash 15 15hash % 16 15一样。但如果length 15hash 14就不等于hash % 15了而且14的二进制是1110最低位是0意味着所有奇数位的hash值永远不会被选中一半的下标被浪费了冲突概率大大增加。所以HashMap的设计者干脆规定容量必须是2的幂。构造时传了非2的幂也会通过一个bit操作tableSizeFor转成最接近的2的幂。这个设计让HashMap在寻址计算上做到了极致的简单和高效。3.4 如何避免Android上HashMap扩容带来的性能问题我在实际开发中总结了几条经验可以减少扩容带来的性能损耗第一条如果可以预估数据规模创建时就指定容量。new HashMap(expectedSize)但要注意如果预期存10条数据传10是不对的因为加上负载因子容量10会在size达到7时就扩容。更稳妥的计算方式是expectedSize / 0.75f 1取整后传给构造方法。比如预期10条就传10 / 0.75 1 14HashMap会转成16在填满16条之前不会扩容。第二条批量插入数据时提前算好容量。我写过一个工具方法public static K, V HashMapK, V newHashMapWithExpectedSize(int expectedSize) { return new HashMap((int) (expectedSize / 0.75f) 1); }这样在putAll或者循环put大量数据时全程只分配一次数组不会中途扩容。实测下来插入10万条数据预设容量比不预设容量耗时能差3倍以上。第三条监控大HashMap的内存占用。在Android Studio的Memory Profiler里可以直观地看到Heap中HashMap的大小。如果你的HashMap存放的数据超过几万条就要考虑是不是可以用别的结构替代或者进行分页/淘汰避免一次性加载过多数据到内存。4. 线程安全HashMap不安全的真实原因4.1 HashMap为什么线程不安全这个问题在面试中出现的频率极高而HashMap的put操作可能导致死循环CPU飙到100%这个说法更是流传甚广。不过这个说法主要针对JDK 1.7及之前的版本原因是扩容时使用头插法多线程并发扩容时可能形成环形链表导致get时死循环。JDK 1.8之后扩容改成了尾插法环形链表的问题被修复了。但HashMap仍然是线程不安全的JDK 1.8之后的不安全主要体现在以下几点数据覆盖两个线程同时put如果hash值相同且数组对应位置为null两个线程都进入如果为空则插入的逻辑后写入的会覆盖先写入的导致数据丢失。size计数不准确HashMap的size是一个普通int多线程put时size的自增操作不是原子的可能丢失更新。modCount异常HashMap内部有一个modCount字段记录修改次数迭代时如果modCount被修改会抛出ConcurrentModificationException。但这属于快速失败机制是保护行为不算数据损坏但确实会导致程序崩溃。所以结论很明确HashMap绝对不是线程安全的任何多线程环境下共用一个HashMap的操作都是危险的。4.2 并发场景的替代方案Android开发中如果确实需要在多线程环境下共享一个Map我建议按需求选择Hashtable最老的线程安全Map所有方法都用synchronized修饰相当于全局锁并发性能很差。Android上基本不推荐。Collections.synchronizedMap和Hashtable类似也是通过synchronized包装只是锁的粒度稍微细一点。适合并发量极低的场景。ConcurrentHashMapJDK 1.8之后采用CAS synchronized锁链表头节点的方式并发度远高于Hashtable。Android上多线程共享Map我默认就是用ConcurrentHashMap。这里有个容易忽略的点HashMap允许null键和null值但ConcurrentHashMap既不允许null键也不允许null值。如果业务代码里有key或value可能为null的情况用ConcurrentHashMap直接抛NullPointerException需要预先处理。4.3 Android场景下的实战经验我在一个项目里遇到过这样的事一个全局的缓存Map在子线程里写入数据主线程读取偶尔会读到null。当时排查了很久最后发现是因为两个线程同时put同一个key一个线程的写入被另一个覆盖了读取方就拿到了一个过期的值。解决方式很简单把HashMap换成ConcurrentHashMap问题立刻消失。另一个常见场景是在遍历Map的同时删除数据。比如这样一个代码for (String key : map.keySet()) { if (key.startsWith(temp)) { map.remove(key); } }这段代码运行时一定会抛ConcurrentModificationException因为for-each用的是迭代器而迭代器会检查modCount。正确的写法是IteratorString iterator map.keySet().iterator(); while (iterator.hasNext()) { String key iterator.next(); if (key.startsWith(temp)) { iterator.remove(); } }或者用Java 8的removeIfmap.keySet().removeIf(key - key.startsWith(temp))。这两种方式都不会抛异常。在Android上要注意removeIf需要API 24老版本还是用迭代器或者自己收集要删除的key最后统一remove。5. 遍历方式盘点与性能对比5.1 四种主流的遍历方式HashMap的遍历方式面试里也经常问。我总结一下常用的几种方式一entrySet遍历for (Map.EntryString, Integer entry : map.entrySet()) { String key entry.getKey(); Integer value entry.getValue(); }这种方式效率最高因为它直接拿到了键值对节点不需要额外的查找操作。方式二keySet getfor (String key : map.keySet()) { Integer value map.get(key); }这种方式看起来直观但每次map.get(key)都需要重新计算hash并查找相当于多了一次按key查找的过程。数据量大的时候这种方式明显比entrySet慢。方式三values遍历for (Integer value : map.values()) { // 只访问value不需要key }适用于只需要value的场景但拿不到key局限性比较大。方式四Java 8 forEachmap.forEach((key, value) - { // do something });本质上是遍历entrySet用lambda表达式书写最简洁。但要注意Android上forEach需要API 24老版本需要用别的方式。方式五Iterator显式遍历IteratorMap.EntryString, Integer iterator map.entrySet().iterator(); while (iterator.hasNext()) { Map.EntryString, Integer entry iterator.next(); // do something }这种方式的优势是可以在遍历时安全地删除元素。5.2 遍历时删除元素的正确姿势上面已经提到for-each删除会抛ConcurrentModificationException这里再补充几个细节。第一for-each遍历map.keySet()时删除的是map本身modCount会变化触发异常。但如果用iterator.remove()iterator内部会同步modCount所以是安全的。第二如果业务需要在遍历过程中删除某些key但又不能直接改map比如需要遍历副本常见的做法是先收集要删除的key到一个List里遍历结束后统一调用map.remove(key)。第三Java 8的removeIf是最推荐的方式一行代码搞定而且内部实现会尽量优化。5.3 不同遍历方式的性能实测我在Android模拟器上做了一个简单的benchmark向HashMap里put了10万条String-Integer数据然后分别用四种方式遍历并求和value。结果如下遍历方式耗时毫秒entrySet9.2forEachentrySet9.4keySet get16.8values仅求和7.6从数据可以看出来entrySet比keySet get快将近一倍原因就是keySet get每次都要重新计算hash和查找。values虽然快但它是只拿value适合的场景比较有限。所以在实际项目中能用entrySet或forEach就用尽量不要用keySet get。另外提醒一点如果HashMap的数据量特别大比如几万条遍历本身也会占用主线程时间建议放在子线程或者用协程处理避免造成UI卡顿。6. Android实战使用HashMap的正确姿势与避坑指南6.1 自定义对象做keyhashCode和equals必须一起重写Android开发中用自定义对象做HashMap的key并不少见比如用Order对象做key缓存订单详情。自定义对象默认继承的是Object的hashCode和equals方法这两个方法基于对象的内存地址。结果是两个字段值完全相同的对象在HashMap眼里是两个不同的key。正确做法是根据业务逻辑重写hashCode和equals。比如一个订单对象如果订单号相同就认为是同一个订单那么equals就只比较订单号hashCode也只基于订单号计算。这样new Order(123)和new Order(123)在HashMap里就是同一个key了。还要注意hashCode和equals的规则必须一致。如果equals认为两个对象相等那么它们的hashCode必须相同反过来hashCode相同不要求equals相等。这就像身份证身份证号相同的人一定是同一个人equals成立hashCode也一定相同但身份证号不同不代表姓名不同hashCode不同equals可能相等也可能不相等。一个常见的坑是用可变对象做key。比如一个订单对象先put进HashMap然后修改了订单的某个字段这个字段参与了hashCode计算那么再用同一个对象get时hash值已经变了定位到不同的桶就永远get不到原来的value了。解决办法是尽量用不可变对象做key或者至少保证hashCode参与计算的字段在存入后不会被修改。6.2 初始化容量一个很容易被忽略的性能优化点前面第3节提过预估容量的问题这里我再给一个更实战的经验。比如你在Android里有一个接口返回的数据是一个列表你要把它转成一个HashMapkey是idvalue是实体对象。列表长度可能是500那么你应该这样写ListItem items response.getItems(); HashMapString, Item map new HashMap((int) (items.size() / 0.75f) 1); for (Item item : items) { map.put(item.getId(), item); }这样写HashMap一开始就给足了容量整个循环put过程中不会触发一次扩容。如果不指定容量HashMap默认16插入500条数据的过程中大概会经历4次扩容每次扩容都要重新hash全部已有数据浪费的时间和内存不是一点半点。我在项目组里做过一次优化就是把一个从数据库加载10万条配置的代码改成了预设容量结果加载时间从1200ms降到了350ms效果非常明显。6.3 HashMap与LruCache的选择不是所有缓存都适合用HashMapAndroid开发中缓存是一个非常高频的需求但很多人的第一反应就是用HashMap存一下。这里的坑在于HashMap是无界的只要不主动remove它会一直增长。如果缓存的是Bitmap这种大对象很容易把内存撑爆。正确的做法是使用LruCache。LruCache的底层是基于LinkedHashMap实现的LinkedHashMap继承自HashMap额外维护了访问顺序或插入顺序的链表。LruCache利用LinkedHashMap的访问顺序特性实现了LRULeast Recently Used淘汰策略当缓存大小超过设定值自动淘汰最久未访问的数据。所以我的建议是缓存图片、长字符串、大对象等用LruCache。缓存临时计算结果、小对象可以用HashMap但要注意大小和生命周期。数据需要持久化、或者需要跨进程共享用DataStore/SharedPreferences/SQLite而不是HashMap。6.4 面试速查HashMap常见问题与回答思路结合我自己的面试经验整理一张速查表方便大家准备问题核心回答要点HashMap底层数据结构是什么数组 链表 红黑树JDK 8链表长度超8且数组长度达到64转红黑树put和get的流程是什么算hash扰动→ hash (length-1)定位 → 判断空/冲突 → 插入或覆盖 → 可能扩容什么时候用equalshash定位后需要确认两个key是否相同的时候。先后equals为什么默认容量是16负载因子0.752的幂保证位运算等价于取模0.75是空间和时间折中的经验值为什么用hash (length-1)而不是取模位运算更快但要求length是2的幂HashMap线程安全吗不安全JDK 7头插法死循环JDK 8数据覆盖、size不准确线程安全替代方案ConcurrentHashMap注意它不允许null键和null值遍历方式有哪些entrySet、keySetget、values、forEach、Iterator推荐entrySet/forEachHashMap和HashTable的区别HashTable线程安全但全部加锁不允许null键和null值性能差HashMap和LinkedHashMap的区别LinkedHashMap多了一个双向链表可以按插入顺序或访问顺序遍历7. 结语HashMap背后值得深思的工程权衡写完上面这些我最大的一个感受是HashMap这种看似基础的数据结构其实凝聚了很多工程权衡。默认容量选16是为了配合位运算的高效负载因子选0.75是为了平衡时间和空间链表转红黑树的阈值选8是为了应对极端哈希碰撞——每一个设计背后都有明确的工程依据。在实际的Android项目里理解这些原理不只是为了面试时说得出来更关键的是能在排查问题的时候用得上。内存告急时能想到是不是HashMap扩容导致的多线程数据错乱时能想到是不是并发安全没处理好遍历报ConcurrentModificationException时能想到是不是用了for-each删除。这些经验都是靠一个坑一个坑踩出来的。最后分享一个小技巧如果你想亲眼验证HashMap扩容的过程可以在Android Studio的Memory Profiler里启动内存记录然后执行一段向HashMap插入大量数据的代码。你会看到堆内存呈阶梯状增长每一个台阶就是一次扩容。如果你想验证hash扰动的作用可以在hash函数里打一个Log对比一下不同key计算出的hash值分布情况。这种亲手实验的方式比读十遍源码理解得都深刻。