使用并行数组实现简易String HashMap：扩容后部分键返回null问题

兄弟，我一眼就瞅出你这问题出在哪了——核心bug是扩容（rehashing）时只处理了引发冲突的当前键值对，完全没管旧数组里已经存在的其他键值对！

问题根源拆解 #

你说触发扩容时，只把引发冲突的键值对存入新数组空位，但扩容后你的Map肯定是切换到用新数组了吧？那旧数组里之前已经存好的那些键值对，就直接被丢弃了啊！举个具体场景：

• 旧数组有2000个bucket，已经存了500个键值对
• 现在put第501个键时发生哈希冲突，触发扩容到4000个bucket
• 你只把第501个键值对放到新数组，旧数组里的500个元素完全没迁移
• 之后调用get时，你是从新数组里找，自然找不到那些旧键，返回null

这就像你换了个新柜子，只把手里刚拿的东西放进去，旧柜子里的所有东西都留在原地不管，回头找旧东西当然找不到啦！

修复方案：扩容时必须迁移所有旧元素 #

扩容的正确姿势应该是把旧数组里的每一个有效键值对都重新哈希，放到新数组对应的位置，参考代码如下：

private void rehash() {
    // 1. 创建新的并行数组，容量扩容（比如翻倍）
    int newBucketCount = nButckets * 2;
    String[] newKeyArray = new String[newBucketCount];
    Object[] newValueArray = new Object[newBucketCount];
    
    // 2. 遍历旧数组，迁移所有非空的键值对
    for (int i = 0; i < nButckets; i++) {
        String oldKey = keyArray[i];
        if (oldKey != null) {
            // 重新计算该键在新数组中的哈希位置
            int newIndex = hash(oldKey, newBucketCount);
            // 存入新数组（这里假设你的哈希冲突处理是首次冲突就扩容，所以新位置不会有冲突）
            newKeyArray[newIndex] = oldKey;
            newValueArray[newIndex] = valueArray[i];
        }
    }
    
    // 3. 切换到新数组，更新容量
    keyArray = newKeyArray;
    valueArray = newValueArray;
    nButckets = newBucketCount;
}

然后在put方法里，触发扩容时先调用这个rehash方法，再把当前要put的键值对存入新数组即可。

额外小提醒 #

另外，你当前“首次冲突就扩容”的策略其实不太高效，一般HashMap是当负载因子（已存元素数/容量）达到阈值（比如0.75）时才扩容。不过先把元素丢失的问题解决了，再优化策略也不迟～

内容的提问来源于stack exchange，提问作者electroiv