- 正确答案：HashMap在JDK 1.8中采用数组+链表+红黑树的结构，当元素数量超过阈值（threshold = capacity × loadFactor）且当前桶位置存在冲突时，会触发扩容；扩容操作将数组长度扩大为原来的2倍（即从n扩容到2n），所有已有元素需重新计算hash值并重新映射到新数组中（rehash）；若原桶中是链表，则遍历链表，根据(e.hash & oldCap) == 0判断元素应留在原索引位置还是迁移到原索引+oldCap位置（利用了2次幂的位运算优化）；若原桶中是红黑树，则先拆分链化再视情况决定是否树化。 - 解答思路：首先明确扩容触发条件（size > threshold），然后理解扩容本质是“重建哈希表”——不仅改变容量，还需保证原有数据在新结构中仍能被正确寻址；关键在于理解JDK 1.8中rehash的位运算优化机制：因容量恒为2的幂，故新索引 = hash & (newCap - 1)，而newCap = 2 × oldCap ⇒ newCap - 1比oldCap - 1多一位高位；因此只需判断hash在oldCap对应bit位是否为1，即可区分新索引是否等于原索引（e.hash & oldCap == 0 → 索引不变；否则索引 = 原索引 + oldCap）。该优化避免了取模或除法运算，也避免了全部元素重新调用hash()方法（因为hash值本身未变，仅需重定位）。 - 深度知识讲解： 1. 底层数据结构：HashMap底层是Node[] table，每个Node是单向链表节点（继承自HashMap.Node），当链表长度≥8且table.length≥64时，链表转为TreeNode（红黑树）；TreeNode继承自LinkedHashMap.Entry，具备红黑树结构字段（parent、left、right、red）和双向链表字段（before、after），支持树化与链表化双向转换。 2. 扩容阈值计算：threshold = table.length × loadFactor，默认loadFactor=0.75，初始容量为16 ⇒ threshold=12。注意：threshold不是硬性限制，而是“下一个触发扩容的size临界值”；put操作中，在插入新节点前先检查size+1 > threshold，满足则先扩容再插入。 3. rehash过程细节： - 不调用对象的hashCode()方法重算hash（hash值已在put时通过hash(Object key)方法预处理：h = key.hashCode()，return h ^ (h >>> 16)，目的是让高位参与低位运算，减少低位碰撞）； - 利用oldCap（旧容量，必为2的幂）进行位与判断：(e.hash & oldCap) == 0。举例：oldCap = 16（二进制10000），若e.hash = 0x10001（17），则17 & 16 = 16 ≠ 0 ⇒ 新索引 = 原索引 + 16；若e.hash = 0x00001（1），则1 & 16 = 0 ⇒ 新索引 = 原索引。 - 该设计使得rehash无需%运算，时间复杂度从O(n)取模降为O(1)位运算，且保证迁移后链表相对顺序不变（JDK 1.8中链表采用尾插法，但迁移时按原链表顺序依次处理，新链表顺序与原链表一致；而JDK 1.7头插法导致多线程下死循环，此为重要演进）。 4. 树化与退化机制： - 树化条件：链表长度≥8 && table.length ≥ 64；否则优先扩容而非树化（避免小表过早树化开销）； - 退化条件：resize时若红黑树节点数≤6，则untreeify为链表；split过程中若某分支节点数<6，也会退化； - TreeNode不直接存储key/value，而是通过tieBreakOrder()等辅助方法解决比较冲突，其红黑树实现基于TreeBin封装，实际操作委托给内部root节点及find()、putTreeVal()等方法。 5. 线程安全性：HashMap非线程安全，扩容过程涉及table引用替换（table = newTab）、节点迁移、next指针重置等，多线程并发put可能造成数据丢失、链表成环（JDK 1.7）、或新表部分桶为空（JDK 1.8虽避免成环但仍存在覆盖丢失）。ConcurrentHashMap通过分段锁（1.7）或CAS+synchronized（1.8）保障扩容安全。 - 伪代码（核心扩容逻辑节选，对应JDK 1.8 HashMap.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 } // ... 初始化newTab 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) // 单节点 newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) // 红黑树 ((TreeNode)e).split(this, newTab, j, oldCap); else { // 链表 Node loHead = null, loTail = null; // low index group Node hiHead = null, hiTail = null; // high index group 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; // 原索引+oldCap } } } } } ```

3.27快手暑期实习后端一面

全站热榜

创作者周榜