- 正确答案：HashMap在Java中（以JDK 8为例）采用数组+链表+红黑树的结构存储键值对。当元素数量超过阈值（threshold = capacity × loadFactor）时触发扩容；扩容操作将底层数组长度翻倍（如从16→32），并重新哈希（rehash）所有已有元素，将其分配到新数组的对应桶中。为提升性能，JDK 8对rehash做了优化：利用节点哈希值的高位bit区分新位置（原索引或原索引+oldCap），避免全部重新计算hash，实现O(n)摊还时间复杂度。 - 解答思路：第一步，明确扩容触发条件：size > threshold（而非数组填满）。threshold初始为16×0.75=12，即第13个put操作可能触发扩容。第二步，理解扩容动作：创建新Node[]数组，容量为oldCap << 1（左移一位，等价于×2），要求容量始终为2的幂次——这是为了用位运算替代取模，提高hash寻址效率（index = (n-1) & hash）。第三步，分析rehash过程：JDK 8不再遍历每个元素调用hash()方法，而是利用原hash值与oldCap做按位与（hash & oldCap），若结果为0，则该节点在新数组中位置不变（low bin）；否则新位置为原索引+oldCap（high bin）。这一设计源于2的幂次容量下，新容量mask比旧mask多1位，而该位恰好由hash & oldCap决定。因此，每个桶内链表可被拆分为两个子链表（loHead/hiHead），再分别挂到新数组的两个位置，无需重复调用hashCode()或equals()。第四步，完成迁移后，更新table引用、threshold（newCap × loadFactor）和modCount（支持fail-fast机制）。 - 深度知识讲解：【底层数据结构】HashMap底层是Node[] table，其中Node是静态内部类，含hash、key、value、next字段；当链表长度≥8且table.length≥64时，链表转为TreeNode（红黑树）；树化前提是桶中节点数达标且数组足够大，防止小数组频繁树化开销。TreeNode继承LinkedHashMap.Entry，具备红黑树节点属性（parent、left、right、red等），并通过treeifyBin()完成链表→树转换。【扩容原理核心：2的幂次与位运算】因capacity恒为2^n，(capacity - 1)的二进制为n个1（如15→1111），故hash & (capacity - 1)等价于hash % capacity，但位运算快一个数量级。扩容后newCap = oldCap << 1 ⇒ newMask = (oldCap << 1) - 1 = (oldCap - 1) | oldCap，即比旧mask多出最高位1。而hash & oldCap的结果，正是这个新增位的值（0或1），直接决定元素去向：0→原索引，1→原索引+oldCap。【线程不安全根源】扩容过程涉及newTable创建、节点迁移、table引用更新三步，若多线程并发执行，可能出现A线程迁移到一半，B线程覆盖了table引用，导致部分节点丢失（JDK 7中甚至引发环形链表死循环，JDK 8因使用尾插法+拆分链表避免了环，但仍存在数据覆盖或丢失）。【阈值设计逻辑】loadFactor=0.75是时间与空间的折中：过小（如0.5）导致频繁扩容，内存利用率低；过大（如1.0）则哈希冲突加剧，链表/树变长，查找退化为O(n)或O(log n)，影响性能。【初始化延迟】HashMap构造时仅记录initialCapacity和loadFactor，真正创建table数组发生在第一次put()调用resize()时，即懒初始化（lazy initialization），避免无谓内存分配。 - 代码示例（JDK 8 resize核心逻辑节选，伪代码化说明）： ``` final Node[] resize() { Node[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node[] newTab = (Node[])new Node[newCap]; table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) // single node, rehash to new index newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode)e).split(this, newTab, j, oldCap); else { // preserve order: split linked list into lo & hi parts Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node next; 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 ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; } ``` 补充说明：上述代码中，关键点在于“e.hash & oldCap”判断——因oldCap是2的幂（如16→10000），其二进制唯一高位为1，该运算实质提取hash值对应这一位的值，从而在O(1)内完成位置分流，避免了传统rehash中对每个元素调用hash(key)和%运算的开销。这是JDK 8 HashMap高性能扩容的核心优化。

字节Agent研发面经 整体不太难

全站热榜

创作者周榜

字节Agent研发面经整体不太难