这个问题需要结合具体的哈希表实现来分析，最常见的是Java中的HashMap和Python中的dict。由于题目未指明语言或具体实现，我们以Java 8+的HashMap为默认上下文（因其设计经典、细节丰富、校园招聘高频考察），并补充其他常见实现作为对比。 - **正确答案**：在Java 8+ HashMap中，初始容量为16，负载因子为0.75，当插入第13个元素时触发第一次扩容（16×0.75=12），之后每次扩容为原容量2倍；插入100个key共扩容**5次**（容量依次为16→32→64→128），即扩容发生在达到阈值后插入操作时，实际扩容次数为：从16→32（第13次put）、32→64（第25次put）、64→128（第49次put）、128→256（第97次put）——等等，需严格按扩容触发条件逐轮推演。准确计算如下：初始：capacity = 16，threshold = 12（16 × 0.75）第13次put → size从12→13，触发扩容 → capacity=32，threshold=24 第25次put → size从24→25，触发扩容 → capacity=64，threshold=48 第49次put → size从48→49，触发扩容 → capacity=128，threshold=96 第97次put → size从96→97，触发扩容 → capacity=256，threshold=192 此时已插入97个key时完成第4次扩容；继续插入至第100个key（97、98、99、100），不再触发新扩容（因为96 < 100 < 192）。 ✅ 所以插入100个key共触发**4次扩容**。但注意：若初始容量被显式指定（如new HashMap<>(100)），则可能0次扩容；若使用无参构造器（默认16），且所有key不发生哈希冲突（理想均匀分布），则仅由size驱动扩容，就是上述4次。然而——关键陷阱在于：**扩容次数取决于实际插入过程中是否突破threshold，而threshold = capacity × loadFactor，且capacity始终为2的幂**。HashMap的扩容机制是“懒扩容”：仅在putVal()末尾检查size >= threshold才resize()。因此必须模拟size增长过程：扩容事件发生在以下size值插入后： - size=12 → 插入第13个key时触发（1st resize） - size=24 → 插入第25个key时触发（2nd） - size=48 → 插入第49个key时触发（3rd） - size=96 → 插入第97个key时触发（4th） - 下一次将在size=192时触发（需插入第193个key），故100以内最多4次。 ✅ 最终答案：**4次** - **解答思路**： 1. 明确HashMap默认参数：initialCapacity=16，loadFactor=0.75 → threshold=12； 2. 每次扩容后，capacity翻倍，threshold同步更新为 newCapacity × 0.75（向下取整？注意：threshold在resize中直接设为 table.length * loadFactor，由于length是2的幂，0.75×2^k恒为整数：16×0.75=12，32×0.75=24，64×0.75=48，128×0.75=96，256×0.75=192 —— 全为整数）； 3. 扩容触发条件是：put后++size >= threshold（注意是插入“后”判断）； 4. 因此枚举threshold序列：12→24→48→96→192…，对应插入序号为13, 25, 49, 97 —— 第97次插入引发第4次扩容，第100次插入仍在capacity=256、threshold=192范围内，不再扩容； 5. 结论：4次。 - **深度知识讲解**： ● 底层数据结构：Java 8+ HashMap采用“数组 + 链表 + 红黑树”混合结构。数组table长度恒为2的幂，通过h & (length-1)替代取模实现O(1)寻址（要求length为2^n，故扩容必须2倍）。 ● 扩容本质：新建2倍容量数组，重新hash所有旧节点并rehash到新桶中。每个节点的迁移位置只有两种可能：原索引i 或 i + oldCap（因newCap = oldCap << 1，而hash & (newCap-1) = hash & (oldCap-1) 或 hash & (oldCap-1) + oldCap），该性质使JDK可高效分拆链表（无需重新计算hash，仅看hash & oldCap是否为0）。 ● 为什么必须2的幂？—— 保证 (n - 1) 的二进制全为1，使得 & 运算等价于 mod n，且无取模开销；同时支持上述扩容位运算优化（e.g., if ((e.hash & oldCap) == 0) 放lo链表，否则放hi链表）。 ● 负载因子0.75是时间与空间权衡：过大会增加哈希冲突（链表/红黑树变长，查找退化）；过小则浪费内存。实验表明0.75在随机哈希下平均链表长度≈1，冲突概率低。 ● 注意：扩容是单线程安全的，但HashMap本身非线程安全；并发扩容可能导致环形链表（JDK 7）或数据丢失（JDK 8已修复部分问题，但仍不保证线程安全）。 ● 补充对比：　– Python dict：底层为开放寻址法（open addressing），初始大小64，扩容阈值为2/3（即64×2/3≈42），扩容后大小约为原大小的1.125倍（向上取最近2的幂？实际策略更复杂：min(64, 2*used+1)等），插入100个key约扩容3~4次，但机制完全不同；　– C++ std::unordered_map：标准未规定具体策略，libstdc++默认负载因子1.0，初始桶数11（质数），扩容为下一个质数，故100个key会经历多次质数扩容（11→23→47→97→199），约4~5次，且无统一规律；　– Redis dict：双哈希表渐进式rehash，扩容时维持新旧两个ht，每次操作迁移一个bucket，避免单次阻塞，插入100个key期间可能处于rehash状态，但“扩容次数”概念弱化。 - **伪代码（HashMap put及resize核心逻辑节选）**： ``` final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 首次put触发初始化resize if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { // 处理冲突... } if (++size > threshold) 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; // threshold也翻倍 } else if (oldThr > 0) newCap = oldThr; else { 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) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode)e).split(this, newTab, j, oldCap); else { // preserve order 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; } ``` 总结：插入100个key在Java HashMap默认配置下扩容4次，本质是由threshold序列{12,24,48,96}决定的，根植于其2的幂容量设计、位运算寻址、懒扩容机制及负载因子平衡策略。理解这一过程，需穿透API表象，掌握数组长度约束、哈希分布、rehash位运算优化等底层原理。

27届Java后端 安克一面

全站热榜

创作者周榜

27届Java后端安克一面