链式哈希表插入相同Key时计数错误问题求助

嘿，我一眼就揪出你代码里的问题啦！你遇到的「总有一个Key没被合并」的情况，根源出在链表遍历的循环条件上。

先看你这段有问题的代码：

while (entry.next!= null){
    if (entry.getKey().equals(key)) {
        entry.setValue(entry.getValue()+1);
        condition = true;
        break;
    }
    entry = entry.next;
}

这个循环的判断条件是entry.next != null，这意味着你只会遍历到链表的倒数第二个节点就停止了——最后一个节点永远不会被检查是否和当前插入的Key匹配。而且如果某个桶里只有一个节点时，这个循环根本不会执行，自然也就不会处理这个节点的Key匹配逻辑，导致这个Key要么被当成新节点插入，要么直接遗漏计数。

修复方案：遍历所有节点 #

把循环条件改成entry != null，这样就能覆盖链表中的每一个节点，包括最后一个：

public void insert (String key, int value){
    int hashValue= generateHashValue(key);
    if(table[hashValue] == null) {
        table[hashValue] = new HashTableLinked(key, value);
    } else{
        HashTableLinked entry = table[hashValue];
        boolean condition = false;
        // 修改循环条件为 entry != null，遍历所有节点
        while (entry != null){
            if (entry.getKey().equals(key)) {
                entry.setValue(entry.getValue()+1);
                condition = true;
                break;
            }
            entry = entry.next;
        }
        // 如果遍历完没找到匹配的Key，就把新节点加到链表末尾
        if (!condition) {
            HashTableLinked tail = table[hashValue];
            while (tail.next != null) {
                tail = tail.next;
            }
            tail.next = new HashTableLinked(key, value);
        }
    }
}

额外优化小建议 #

你可以在第一次遍历的时候同时记录尾节点，这样就不用在没找到Key的时候再遍历一次链表找末尾了，能提升插入效率：

public void insert (String key, int value){
    int hashValue= generateHashValue(key);
    if(table[hashValue] == null) {
        table[hashValue] = new HashTableLinked(key, value);
    } else{
        HashTableLinked entry = table[hashValue];
        HashTableLinked tail = null;
        boolean condition = false;
        while (entry != null){
            if (entry.getKey().equals(key)) {
                entry.setValue(entry.getValue()+1);
                condition = true;
                break;
            }
            tail = entry;
            entry = entry.next;
        }
        if (!condition) {
            tail.next = new HashTableLinked(key, value);
        }
    }
}

这样修改后，所有相同的Key都会被正确计数，再也不会出现单独存在的漏网之鱼啦！

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