Java哈希表实现get方法空指针异常及单元测试不通过问题求助

问题根因 #

• 空指针异常直接原因：get方法中直接访问items[i].key，未判断当前槽位items[i]是否为null。数组中存在未填充的空槽，访问null对象的属性必然触发空指针，导致循环异常退出、测试失败。
• 循环逻辑缺陷：当前遍历逻辑没有合理终止条件，若查询不存在的key，会无限循环遍历整个数组，用for循环结构做环形遍历的写法不严谨，容易出现逻辑混乱。
• 额外隐患：put方法的环形遍历边界判断顺序错误，当前测试案例未触发，后续也容易出现问题。

修复后的get方法代码 #

public String get(String key) {
    long targetHash = hashFunction(key);
    int keyStartIndex = (int) (targetHash % items.length);
    // 记录已遍历槽位数量，避免死循环
    int visitedCount = 0;

    for(int i = keyStartIndex; visitedCount < items.length; i++, visitedCount++){
        // 先判断槽位是否为空，无删除逻辑的线性探测下遇到空槽即可终止遍历
        if(items[i] == null){
            break;
        }
        if(items[i].key == targetHash){
            return items[i].item;
        }
        // 到达数组末尾绕回开头
        if(i == items.length-1){
            i = -1; // 配合循环末尾的i++，下次迭代i会从0开始
        }
    }
    return null;
}

put方法同步修复建议 #

public void put(String key, String value) throws TableIsFullException {
    if (size >= items.length-1){
        throw new TableIsFullException();
    }
    long targetHash = hashFunction(key);
    DataItem input = new DataItem(targetHash, value);
    int startIndex = (int) (targetHash % items.length);
    int visitedCount = 0;

    for(int i = startIndex; visitedCount < items.length; i++, visitedCount++){
        if(items[i] == null){
            items[i] = input;
            size++;
            break;
        }
        if(i == items.length-1){
            i = -1;
        }
    }
}

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