- 正确答案：HashMap 是基于哈希表实现的键值对存储结构，底层使用数组 + 链表（或红黑树）来解决哈希冲突。初始容量为16，负载因子默认为0.75，当元素数量超过容量 × 负载因子时触发扩容，扩容后容量变为原来的2倍。在 Java 8 中，当链表长度达到8且当前数组长度 ≥ 64 时，链表会转换为红黑树以提高查找效率。 - 解答思路： 1. 理解 HashMap 的基本功能：存储键值对、支持快速插入和查找。 2. 分析其底层数据结构：数组作为主干，每个桶（bucket）可以是一个链表或红黑树节点。 3. 明确哈希函数如何将 key 映射到数组索引：hash(key) & (capacity - 1)，利用位运算提升性能。 4. 掌握哈希冲突的处理方式：拉链法（链地址法）。 5. 理解何时发生扩容以及扩容机制：阈值 = 容量 × 负载因子，扩容后重新散列所有元素。 6. 了解链表转红黑树的条件及其优化目的。 - 深度知识讲解： 1. 底层数据结构： HashMap 内部维护一个 Node[] table 数组，Node 是内部类，包含： - final int hash; - final K key; - V value; - Node next; // 下一个节点引用，用于链表当发生哈希冲突时（不同 key 计算出相同索引），采用链表连接多个 Entry。在 Java 8 引入了红黑树优化： - 当某个桶中链表长度 ≥ 8 且当前数组长度 ≥ 64 时，该链表转换为红黑树（TreeNode）。 - 若删除元素导致树节点数 ≤ 6，则退化回链表。 - 目的是防止哈希冲突严重时链表过长，使 O(n) 查找退化为 O(log n)。 2. 哈希计算过程：并非直接使用 key.hashCode()，而是进行扰动处理： hash = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 这样做的原因是 hashCode 是 int 类型（32位），而数组容量通常是 2 的幂，索引由 (n - 1) & hash 得到，只取低几位。高位参与运算可减少碰撞概率。 3. 索引定位公式： index = hash & (capacity - 1) 因为容量始终是 2 的幂，所以 capacity - 1 的二进制全是 1，与操作等价于取模，但比 % 更高效。 4. 扩容机制（resize）： - 初始容量：DEFAULT_INITIAL_CAPACITY = 1 << 4 = 16 - 负载因子：DEFAULT_LOAD_FACTOR = 0.75f - 阈值 threshold = capacity * loadFactor，初始为 16 * 0.75 = 12 - 当 size > threshold 时触发 resize() 扩容流程： a. 创建新数组，大小为原数组的两倍（左移1位：oldCap << 1） b. 遍历旧数组中的每个桶 c. 对每个元素重新计算在新数组中的位置关键优化：由于容量是 2 的幂，扩容后每个元素的新位置要么在原位置，要么在原位置 + oldCap 处。设 oldCap = 16，则 newCap = 32 判断依据是 hash 值中新增的一位是否为 1： if ((e.hash & oldCap) == 0) → 放在原位置 else → 放在原位置 + oldCap 这样无需重新调用 hash 函数，也不需要重新遍历链表逐个 rehash，提高了迁移效率。同时，在 Java 8 中，对于树形结构也会拆分，必要时可能退化为链表或继续维持红黑树。 5. put 方法执行流程： - 计算 key 的 hash 值 - 根据 hash 找到对应桶的首节点 - 如果桶为空，直接新建节点放入 - 如果桶非空： ① 判断第一个节点是否 equals 当前 key，是则替换 value ② 否则遍历链表或树，找到匹配项替换，否则插入末尾 - 插入后检查是否需转树（链表长度 ≥ 8） - 更新 size，判断是否需要扩容 6. null 键的支持： - 允许一个 null 键，put 时特殊处理：hash=0，index=0 - get(null) 时单独判断 7. 线程安全性： - HashMap 不是线程安全的 - 多线程下并发 put 可能导致环形链表（Java 7 头插法问题）、数据丢失等问题 - 替代方案：ConcurrentHashMap 或 Collections.synchronizedMap() - 扩展知识点： - Java 7 使用头插法，多线程扩容可能导致链表成环，引发死循环 - Java 8 改为尾插法，避免了这个问题 - 初始容量建议设为大于预期元素数 / 0.75，避免频繁扩容 - transient 关键字修饰 table，表示序列化时不保存实际结构，自定义 writeObject/readObject 实现序列化优化 - 伪代码示例（简化版 resize）： ``` function resize() oldTab = table oldCap = oldTab.length if oldTab != null else 0 oldThr = threshold newCap = 0 newThr = 0 if oldCap > 0 if oldCap >= MAXIMUM_CAPACITY threshold = Integer.MAX_VALUE return oldTab else newCap = oldCap << 1 // double the size if newCap < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY newThr = oldThr << 1 // double threshold else if oldThr > 0 newCap = oldThr else newCap = DEFAULT_INITIAL_CAPACITY newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY) if newThr == 0 newThr = (int)(newCap * loadFactor) threshold = newThr newTab = new Node[newCap] table = newTab if oldTab != null for each bin in oldTab if bin != null e = bin if e.next == null // only one element newTab[e.hash & (newCap - 1)] = e else if e instanceof TreeNode ((TreeNode)e).split(this, newTab, e.hash & (newCap - 1), oldCap) else // preserve order during transfer loHead = null, loTail = null hiHead = null, hiTail = null do next = e.next if (e.hash & oldCap) == 0 if loTail == null loHead = e else loTail.next = e loTail = e else if hiTail == null hiHead = e else hiTail.next = e hiTail = e while (next != null) if loTail != null loTail.next = null newTab[j] = loHead if hiTail != null hiTail.next = null newTab[j + oldCap] = hiHead return newTab ``` 总结： HashMap 的设计充分考虑了性能与空间平衡，通过哈希扰动、拉链法、红黑树升级、高效扩容策略等多种手段保障平均 O(1) 的访问性能。理解其底层原理不仅有助于应对面试，也能指导实际开发中合理设置初始容量、避免性能陷阱。

soul 测试开发 二面（40min 已oc）

全站热榜

创作者周榜

soul 测试开发二面（40min 已oc）