HashMap 底层原理，是一道“开口容易、讲深难”的题。多数人能背出“数组加链表”，可面试官一旦问“为什么容量要取 2 的幂”“扰动函数到底解决什么”，台面上卡壳的不在少数。这题后面连着扩容、并发、ConcurrentHashMap，是集合框架里承上启下的一题，基础不牢，后面全白搭。
先把结论放在前面：HashMap 底层是“数组 + 链表 + 红黑树”的复合结构。元素通过 key 的哈希定位桶下标，哈希值会先经过一次高 16 位异或低 16 位的扰动，减少低位相同导致的碰撞；单桶内元素超过 8 个且表长达到 64 时，链表转成红黑树把查询从 O(n) 降到 O(log n)；负载因子默认 0.75，元素数超过容量乘 0.75 就触发扩容。这题要答好，得把“怎么定位、怎么存、怎么退化与升级”讲透。
机制拆解
讲清一次 put 的完整链路。先算 hash：h = key.hashCode()，再做扰动 hash = h ^ (h >>> 16)，把高位特征揉进低位；再用 (n - 1) & hash 得到桶下标（这要求 n 是 2 的幂，才能用位与代替取模，且扩容时只需看新增的一位）。桶里若为空直接挂节点；若已有节点，先比 hash 再比 key（equals）决定是覆盖还是追加；追加后若链表长度到 8，且数组长度 ≥ 64，就把该桶树化，否则优先扩容。查询 get 同理：定位桶、比 hash、比 equals。
这些坑的正确绕法
最常见的坑是自定义 key 只重写 equals 不重写 hashCode。两个逻辑相等的对象若 hashCode 不同，会被算到不同桶里，containsKey / get 就再也查不到，集合悄悄“丢数据”。hashCode 与 equals 必须满足契约：相等对象 hashCode 必相等。
其次是把可变对象当 key 却中途改字段。对象进表后 hashCode 随字段变化，再查时算到的桶已经不是当初挂的那个，条目变成幽灵数据——既查不出，也删不掉，还白白占着桶。
还有一个更隐蔽的坑：对 HashMap 做并发写。多线程同时 put 在 JDK 7 及以前可能因扩容时链表反转形成环，导致后续查询 CPU 占满；JDK 8 虽修了反转，但数据覆盖、size 不准、丢失写入仍有。并发场景该用 ConcurrentHashMap。
代码里见真章
看一段能直接跑的代码，把上面的机制落到具体写法上：
// HashMap 原理：数组 + 链表 + 红黑树
Map<String, Integer> m = new HashMap<>();
m.put("k", 1); // hash(key) ^ (h>>>16) 扰动，再 (n-1)&hash 定位桶
// 单桶冲突链长度 >= 8 且表长 >= 64 → 链表转红黑树（查询 O(logN)）
// 扩容阈值 = capacity * loadFactor（默认 0.75）
for (Map.Entry<String, Integer> e : m.entrySet()) {
System.out.println(e.getKey() + "=" + e.getValue());
}
这段代码值得盯三处：第一处，扰动函数把高位信息掺入低位，缓解低位碰撞；第二处，树化有两个前提（链长 8 与表长 64），缺一不可，否则优先扩容；第三处，负载因子 0.75 是空间与时间的折中，到阈值就扩容翻倍并重分布。面试讲到这一层，基本就稳了。
这题在面试里怎么问、怎么答
“请简单介绍一下 HashMap 底层原理，它在 Android 开发中起什么作用？”按“结构 → 定位 → 冲突处理”递进，别超三分钟。HashMap 用数组承载桶，桶内先用链表、过阈值转红黑树，在 Android 里承担大量键值缓存、接口参数映射、轻量字典。如果要把使用约定沉淀成团队规范，建议加一条：自定义 key 需要同时重写 equals 和 hashCode，且 key 尽量用不可变类型。
“HashMap 的底层原理是什么？能不能详细说一下？”从扰动函数讲到桶定位，再到链表与红黑树的升级条件，最后落到负载因子与扩容阈值。强调 (n-1)&hash 依赖 2 的幂容量，这是 HashMap 一系列设计的基石。机制别空讲，配核心代码最稳。
“在使用 HashMap 时遇到过什么问题？”讲真实案例：曾用一个可变的坐标对象做 key，业务中途改了坐标字段，结果缓存命中率骤降、内存稳步上涨；定位后把 key 换成不可变的字符串组合，问题消除。量化的修复效果最加分。
“和相关的替代方案相比，有什么优劣？”与 LinkedHashMap 比，HashMap 不维护顺序但更省内存；与 TreeMap 比，HashMap 靠哈希 O(1)，TreeMap 靠比较 O(log n) 且有序；与 ConcurrentHashMap 比，HashMap 非线程安全。选型就按“要不要顺序、要不要并发、要不要排序”三项来。选型时要把“可变对象做 key 导致幽灵数据”这类代价摆到台面上，再决定是否引入。
再补一个工程上容易忽略的细节：为什么负载因子偏偏是 0.75 而不是 0.5 或 1.0。负载因子越低，哈希冲突越少、查询越快，但空桶多、内存浪费；越高则反之。0.75 是泊松分布下冲突概率与空间占用的一个经验平衡点，官方注释里还给出了桶中元素个数服从泊松分布、链长到 8 的概率极小（约千万分之六）的数学依据。理解这一点，就能解释“为什么树化阈值设在 8”——那是冲突概率已经低到几乎不可能、真出现就说明哈希分布出问题的临界点。另一个点：初始容量若不是 2 的幂，HashMap 会用 tableSizeFor 向上取到最近的 2 的幂，所以传 17 实际是 32，传容量要按“预期元素数 / 0.75 再向上取 2 的幂”来估。
再补三个容易被追问的实现细节。其一是 hashCode 质量与扰动的配合：扰动函数只把高 16 位混入低位，若自定义 key 的 hashCode 本身分布很差（例如恒返回常量），扰动也救不回来，所以覆盖 hashCode 时要选好乘子与位移。其二是树化门槛为何同时要求表长不小于 64：桶数太少时链表转红黑树的收益抵不过重建成本，先扩容把冲突摊开更划算，这个顺序不能颠倒。其三是同族对比：IdentityHashMap 用系统身份哈希而非 equals 契约做键，适合“同一引用才算同一”的场景；WeakHashMap 则从生命周期角度给键加约束，适合缓存类需求。三者放在一起讲，能体现对 Map 家族的整体把握。最后留一条线索：正是“数组 + 链表”这套结构决定了 HashMap 无法做桶级并发控制，这正是后续扩容与并发两题要接着展开的原因，把这条线点出来，面试官会顺势追问，而答案恰好已经准备好。
再补一个容易被追问的实现细节：为什么 HashMap 不直接用 hashCode() 的返回值当下标？两个原因。一是 hashCode 是 32 位整数，值域远大于数组长度，必须先压到 capacity 范围内；二是很多类型的 hashCode 低位信息稀薄（比如字符串按字符算、或用户自定义实现质量不佳），只用低位会加剧碰撞，扰动函数正是把高位信息折下来补充低位质量。理解这一点，就能顺带解释为什么 HashMap 不支持负数下标——它先对 hashCode 做了一次 h ^ (h >>> 16)，结果仍为正数，配合 (n - 1) 的掩码即可保证下标落在 [0, n) 区间内。此外，get 的判等顺序是"先比 hash 再比引用、再比 equals"，引用相等短路这一步也是性能来源，链式调用 key == k || key.equals(k) 的写法值得记住。
给正在准备面试的你
把 HashMap 底层原理画成一张图：顶部一个数组，每个格子里挂着链表或红黑树，旁边标扰动、负载因子、树化阈值。面试中关于 HashMap 的问题，关键在于能够从原理、应用、踩坑三个层面给出有深度的回答。
再补工程案例与踩坑——应用落点是手写一个简化 HashMap（数组加链表），实现 put/get 并演示扩容前后索引变化。
复习时别孤立刷题：HashMap 扩容与 rehash——相邻考点常被一起问，边界提前划清楚。
划两句重点：哈希经高 16 位异或低 16 位扰动后定位桶，单桶超 8 且表长超 64 才树化；负载因子 0.75 是空间与时间的折中，自定义 key 要重写 equals 与 hashCode 且尽量不可变。
下一篇聊 HashMap 扩容与 rehash：为什么容量是 2 的幂——沿着今天这条主线继续往前走。
如果这篇文章对你有帮助，欢迎点赞、在看、转发三连。你的支持就是这个系列持续更新的动力。
「Android软件开发面试·从入门到精通」连载系列
上一篇：LinkedList-与-ArrayList-选型：随机访问与插删的权衡
下一篇预告：HashMap-扩容与-rehash：为什么容量是-2-的幂
有任何问题欢迎在评论区留言交流。
