哈希表原理、HashMap 扩容与哈希冲突解决

回到总览：00 基础知识（Foundations）
相关模块：ConcurrentHashMap 原理、Segment 分段锁与 CAS+synchronized 演进

一句话定义

哈希表（Hash Table）是通过哈希函数将 Key 映射到数组索引实现均摊 $O(1)$ 查找的数据结构；Java HashMap 采用了链地址法（拉链法） 解决哈希冲突，并在 JDK 8 引入了红黑树优化大链表场景。Android 端则针对小数据集提供了更省内存的 SparseArray / SparseIntArray / ArrayMap。

代码索引

主题	Lab 说明	源码
Map 并发与容器对照	map-concurrency-compare	MapConcurrencyCompare.java

为什么需要

• 为什么 HashMap 的容量 capacity 必须被强制设计为 2 的幂次方（如 16, 32, 64）？
  • 一句话答：设容量为 $N$（2 的幂），取模运算 hash % N 就能等价优化为按位与运算 hash & (N - 1)；CPU 执行按位与指令的开销远低于取模除法指令，大幅提升了哈希定位性能。
• 为什么 10 年 Android 工程师必须了解 ArrayMap / SparseArray 替代 HashMap？
  • 一句话答：传统 HashMap 需要创建大量 Node 对象，在移动端小数据集（<1000 条）下会带来额外的内存开销与基本类型装箱损耗；Android 专用的 SparseArray（避免 int 装箱）与 ArrayMap（双数组二分查找）大幅节省了物理内存。
• 为什么 hashCode() 相同还不能直接认定是同一个 Key？
  • 一句话答：hashCode() 只能做粗定位，真正判断是不是同一个 Key 还要看 equals()；否则不同对象只要 hash 冲突就会被误判成同一条记录。

底层机制

1. JDK 8 HashMap 结构演进（数组 + 链表 + 红黑树）

Bucket 数组 index = hash & (n - 1)
 [0] ───► null
 [1] ───► Node(k1,v1) ───► Node(k2,v2)  (拉链法解决冲突)
 [2] ───► TreeNode (红黑树根节点，链表长度 >= 8 且容量 >= 64 时转换!)

树化与退化门槛

• 树化阈值：单个 Bucket 链表长度 $\ge 8$ 且数组总容量 $\ge 64$ 时，链表转为红黑树。
• 退化阈值：扩容或删除节点导致红黑树节点数量降为 $\le 6$ 时，红黑树退化回单向链表。

2. 扩容（Resize）与位运算高低位重新分配

HashMap 在元素个数大于 capacity * loadFactor（默认 0.75）时触发 2 倍扩容。

• 在 JDK 8 中，由于容量始终是 2 的幂，元素扩容后的新位置要么在原位置，要么在原位置 + 旧容量（取决于新增的最高 bit 是 0 还是 1），无需重新计算 hashCode()。

3. Android 小数据集容器：SparseArray / SparseIntArray / ArrayMap

这一组容器不是“比 HashMap 更高级”，而是“在 Android 小表场景下更省内存”。核心取舍是：

• HashMap：多用结构对象，换平均更快的查找与更稳的大表性能。
• SparseArray / SparseIntArray / ArrayMap：少造对象、少装箱、数组更紧凑，但插入删除可能要搬移数组。

3.1 SparseArray：int -> object

存储形式

keys   = [10, 21, 35]
values = ["dog", "cat", "egg"]

含义：

• keys[0] = 10 对应 values[0] = "dog"
• keys[1] = 21 对应 values[1] = "cat"
• keys[2] = 35 对应 values[2] = "egg"

它本质是两条并排数组：

• int[] keys
• Object[] values

keys[] 按升序排列，所以查找依赖二分查找，而不是哈希桶。

查找

查 key = 21：

1. 在 keys[] 中二分查找 21。
2. 找到下标 1。
3. 返回 values[1] = "cat"。

插入

插入 30 -> "bee"：

插入前
keys   = [10, 21, 35]
values = ["dog", "cat", "egg"]

插入后
keys   = [10, 21, 30, 35]
values = ["dog", "cat", "bee", "egg"]

因为 keys[] 必须保持有序，所以中间插入时后续元素要整体后移。

特点

• 优点：int key 不装箱、无 Node 对象、内存占用很低。
• 缺点：只能做 int -> object；中间插入、删除要搬移数组；大表或频繁写入不如 HashMap。
• 典型场景：viewId -> View、requestCode -> callback、position -> Fragment。

3.2 SparseIntArray：int -> int

存储形式

keys   = [10, 21, 35]
values = [100, 7, 88]

与 SparseArray 思路完全一样，只是 value 也从 Object[] 变成了原生 int[]。

查找与插入

• 查找：同样是对 keys[] 做二分，然后用下标去 values[] 取值。
• 插入：同样要保持 keys[] 有序，必要时搬移数组。

特点

• 优点：key / value 都不装箱，比 SparseArray<Integer> 更轻。
• 缺点：适用面最窄，只适合 int -> int。
• 典型场景：position -> type、id -> count、resourceId -> flag。

3.3 ArrayMap：通用版小表省内存 Map

存储形式

hashes = [5, 8]
array  = ["dog", 20, "cat", 10]

含义：

• hashes[0] = 5 对应第 0 个 entry
  • array[0] = "dog"（key）
  • array[1] = 20（value）
• hashes[1] = 8 对应第 1 个 entry
  • array[2] = "cat"（key）
  • array[3] = 10（value）

映射关系固定为：

• hashes[i]：第 i 个 entry 的 hash
• array[2*i]：第 i 个 entry 的 key
• array[2*i + 1]：第 i 个 entry 的 value

所以它不是“一个 hash 对应一段 value”，而是“一个 hash 对应 array 中一组 key/value entry”。

查找

查 key = "cat"：

1. 先算 hash("cat") = 8。
2. 在 hashes[] 中二分查找 8。
3. 命中 index = 1。
4. 取 array[2*1] = array[2] = "cat" 做 equals() 比较。
5. 命中后返回 array[2*1 + 1] = array[3] = 10。

处理 hash 冲突

如果有多个不同 key 的 hash 一样：

hashes = [5, 8, 8]
array  = ["dog", 20, "cat", 10, "egg", 30]

这里 "cat" 和 "egg" 都在 hash=8 的连续区间里。

查 "egg" 时：

1. 二分先找到某个 8 的位置，比如 index = 1。
2. 检查 array[2] = "cat"，发现不是。
3. 再向后看 index = 2，因为 hashes[2] 仍然是 8。
4. 检查 array[4] = "egg"，命中。
5. 返回 array[5] = 30。

为什么能“向前 / 向后扫描”？因为 hashes[] 是有序的：

• 所有相同 hash 一定连续挨在一起。
• 一旦向前或向后遇到 hash != 目标 hash，就可以立刻停止；外面不可能再有同 hash 项。

所以 ArrayMap 的冲突处理原则是：

• 先用 hashCode() 定位候选区间。
• 再用 equals() 确认是不是同一个 key。

插入

插入 "egg" -> 30，且 hash("egg") = 8：

插入前
hashes = [5, 8]
array  = ["dog", 20, "cat", 10]

插入后
hashes = [5, 8, 8]
array  = ["dog", 20, "cat", 10, "egg", 30]

如果插入位置落在中间，hashes[] 和 array[] 后续元素都要整体后移。

特点

• 优点：通用 K -> V，但比 HashMap 更省内存；小表很划算。
• 缺点：查找不是纯桶直达；hash 冲突时要扫同 hash 区间；插入删除要搬移数组；大表或频繁增删通常不如 HashMap。
• 典型场景：Android framework / UI 层的小型属性表、小型 metadata、小型对象映射。

4. HashMap：默认通用选择

存储形式

table[0] -> null
table[1] -> Node("dog",20) -> Node("egg",30)
table[2] -> null
table[3] -> Node("cat",10)

它的结构不是平铺数组，而是：

• 一个桶数组 table[]
• 每个桶里挂一个或多个 Node
• 冲突严重时，链表还可能树化为红黑树

每个 Node 至少包含：

• hash
• key
• value
• next

查找

查 "cat"：

1. 计算 hash("cat")。
2. 通过 hash & (n - 1) 找到桶下标。
3. 进入对应 bucket。
4. 在 bucket 内逐个比较 hash 和 equals()。
5. 命中则返回 value；若 bucket 已树化，则在树中继续查找。

插入

1. 计算 hash。
2. 找到桶位置。
3. 如果桶为空，直接创建 Node。
4. 如果桶不为空：
   • 找到同 key -> 更新 value
   • 找不到 -> 追加到链表 / 树结构中
5. 如果元素数量超过 capacity * loadFactor，触发扩容。

特点

• 优点：通用性最强，均摊查找快，大表和频繁增删更稳。
• 缺点：每个 entry 都有额外结构对象；int key/value 会装箱；小表在 Android 上常显得偏胖。
• 典型场景：通用业务字典、规模不确定的映射关系、频繁改动的数据结构。

Android / Flutter / Web / Backend 对照

数据结构	适用环境	查找时间复杂度	内存开销特点
HashMap	Java / Kotlin 通用	均摊 $O(1)$	较多对象开销（Node / TreeNode）
SparseArray	Android 移动端	$O(\log N)$（二分查找）	极低（避免 int key 自动装箱）
SparseIntArray	Android 移动端	$O(\log N)$（二分查找）	更低（key / value 都避免装箱）
ArrayMap	Android 移动端	$O(\log N)$ + 同 hash 区间扫描	低（两个扁平数组存储）
LinkedHashMap	Java / Android	均摊 $O(1)$	额外维护双向链表（常用作 LRU）

常见场景与选型

在 Android 端，数据量小于 1000 时常用的经验法则：

1. key 为 int，value 为对象：优先 SparseArray<V>。
2. key 为 int，value 也是 int：优先 SparseIntArray。
3. key 为其他对象，但 map 很小且内存敏感：优先 ArrayMap<K, V>。
4. 规模不确定、增删频繁、偏通用业务：默认 HashMap<K, V>。

4 个容器的并排决策图

先问：key 是不是 int？
├─ 是
│  ├─ value 也是 int？
│  │  ├─ 是 → SparseIntArray
│  │  │       - 最省：key / value 都不装箱
│  │  │       - 适合：position -> type、id -> count
│  │  └─ 否 → SparseArray<V>
│  │          - 很省：只做 int -> object
│  │          - 适合：viewId -> View、requestCode -> callback
│  └─ 若数据会长很大、写入非常频繁 → 再回头评估 HashMap
│
└─ 否
   ├─ map 很小，而且在 Android 内存敏感路径？
   │  ├─ 是 → ArrayMap<K, V>
   │  │       - 通用 key/value，但比 HashMap 更省内存
   │  │       - 适合：小型属性表、metadata、小型对象映射
   │  └─ 否 → HashMap<K, V>
   │          - 默认通用选择，均摊查找快
   │          - 适合：规模不确定、增删频繁、通用业务字典

• 一句话判断 1：先看 key 是否是 int，这是 SparseArray / SparseIntArray 的分水岭。
• 一句话判断 2：再看数据规模和读写模式；小表偏内存优化，大表或频繁增删偏 HashMap。
• 一句话判断 3：ArrayMap 不是 HashMap 的通用升级版，它只是“小型通用 map 的省内存版本”。

常见误配、事故后果与排障

1. 事故：并发写入 HashMap 导致 JDK 7 死循环死锁

• 误配原因：在多线程并发场景下直接使用非线程安全的 HashMap 进行 put() 扩容。
• 后果：JDK 7 的头插法扩容在并发下会导致链表形成环形结构；之后执行 get() 会直接陷入 CPU 100% 死循环。
• 排障与修法：并发场景严禁使用 HashMap，改用 ConcurrentHashMap。

2. 误配：把所有小 Map 都机械替换成 ArrayMap

• 误配原因：只记住了“ArrayMap 更省内存”，却忽略了它插入删除要搬数组、冲突时还要扫同 hash 区间。
• 后果：在频繁写入、规模变大的场景里，CPU 开销反而可能更差。
• 排障与修法：先判断数据规模、读写比例、key 类型；不要把 ArrayMap 当成 HashMap 的通用升级版。

3. 误配：用 HashMap<Integer, Integer> 承载大量小型 Android 热路径映射

• 误配原因：忽略了 Integer 装箱和 Node 对象分配的成本。
• 后果：对象数膨胀、GC 压力变大，尤其在 RecyclerView、View 索引等小表高频路径里更容易放大抖动。
• 排障与修法：int -> object 改 SparseArray，int -> int 改 SparseIntArray。

对应实验

各章节内已嵌入跳转链接；此处汇总全部 Lab：

Lab	说明	源码
map-concurrency-compare	HashMap / Hashtable / ConcurrentHashMap 并发读写与扩容行为对照	MapConcurrencyCompare.java

复习检查题

1. 为什么 HashMap 解决哈希冲突时，链表长度达到 8 后不一定立刻转化为红黑树？ 答：因为树化还需要满足另一个条件：HashMap 的总容量 capacity 必须大等于 64。如果链表长度达到了 8，但总容量小于 64，HashMap 会优先选择触发 resize() 数组扩容。因为扩容能重新打散元素，从根本上降低单个 Bucket 的冲突概率，只有当数组已经足够大时，转换为红黑树才是性价比更高的方案。
2. 为什么 Android 推荐在 key 为整型时使用 SparseArray 替代 HashMap<Integer, V>？ 答：因为 HashMap<Integer, V> 需要将基本类型 int 装箱为 Integer 对象，且每个键值对需要创建一个 Node 对象，带来了明显的对象头开销和 GC 压力。而 SparseArray 内部直接使用 int[] 存 key、Object[] 存 value，避免了自动装箱和额外的 Node 分配，更适合移动端小表。
3. ArrayMap 为什么能“向前 / 向后扫描同 hash 的那一段”来处理冲突？ 答：因为 hashes[] 是有序数组，相同 hash 的条目一定连续挨在一起；二分找到某个命中点后，只要向两边扫描直到 hash != 目标 hash 即可确定整个候选区间。
4. ArrayMap 与 HashMap 处理 hash 冲突的根本共同点是什么？ 答：共同点都是先用 hashCode() 缩小范围，再用 equals() 确认是否真的是同一个 key；区别只在于 HashMap 在桶链 / 树中找，ArrayMap 在同 hash 的连续区间里找。
5. 为什么 SparseIntArray 比 SparseArray<Integer> 更省？ 答：因为 SparseIntArray 的 key 和 value 都使用原生 int[] 存储，连 value 的 Integer 装箱都省掉了；而 SparseArray<Integer> 只避免了 key 装箱，value 仍是对象。

速记

• HashMap：桶数组 + 链表 / 红黑树；默认通用、均摊快，但结构偏胖。
• SparseArray：int -> object 的有序号码簿；二分查找，省内存。
• SparseIntArray：int -> int 的纯数字号码簿；比 SparseArray<Integer> 更省。
• ArrayMap：hashes[] + array[] 的压缩版通用小表；先二分找 hash，再扫同 hash 区间。
• 选型口令：int -> object 用 SparseArray，int -> int 用 SparseIntArray，小型通用 map 用 ArrayMap，规模不确定或频繁增删默认 HashMap。