Java泛型哈希表如何实现键的添加与存在性比较

以下是你代码中存在的问题及修复方案：

现有问题汇总 #

• add方法相关误区：你误以为add无法存入元素，实际是后续compare方法逻辑错误，导致无法正确判断元素是否存在，add本身的头插逻辑是可以正常把元素存入对应哈希桶的，只是存在泛型类型不匹配的隐患。
• compare方法逻辑完全错误：
  1. 已经计算出key对应的哈希下标hashIndex，不需要遍历整个哈希表的所有桶，只需要遍历该下标对应的单条链表即可，你代码中固定取第一个桶hashArray.get(0)遍历，当然找不到其他桶里的元素
  2. 迭代器遍历逻辑和当前节点current完全脱节，遍历过程中没有切换不同的桶，只会在第一个桶的链表中循环
  3. 用==比较key内容，对于字符串、自定义类等引用类型，==比较的是内存地址而非实际内容，应该用equals方法
• 泛型调用报错问题：
  你定义的哈希表是键值对结构<K,V>，但add方法只接收key参数，内部硬编码把value也设为key，当你实例化时指定的V类型和K不一致时，就会触发类型不匹配的报错，提示需要对应类型的新方法。

修复后代码 #

import java.util.ArrayList;
import java.util.Objects;

class GenericHashNode <K, V> {
    K key;
    V value;
    GenericHashNode<K, V> next;

    public GenericHashNode (K key, V value) {
        this.key = key;
        this.value = value;
        next = null;
    }

    public GenericHashNode() {
        next = null;
    }
}

public class GenericHashTable <K, V> {
    private ArrayList<GenericHashNode<K, V> > hashArray;
    private int tableSize;

    public GenericHashTable(int tableSize)
    {
        hashArray = new ArrayList<>(tableSize);
        this.tableSize = tableSize;
        // 每个桶初始化哑节点，方便头插
        for (int i = 0; i < tableSize; i++) {
            hashArray.add(new GenericHashNode<>());
        }
    }

    private int getTableSize() {
        return tableSize;
    }

    private int createHashCode(K key)
    {
        // 增加null key处理，避免空指针
        if (key == null) return 0;
        int h = key.hashCode();
        // 简化负数处理，直接取绝对值
        h = Math.abs(h % getTableSize());
        return h;
    }

    // 修改add方法，接收key和value两个参数，匹配泛型定义
    public void add(K key, V value) {
        int hashIndex = createHashCode(key);
        GenericHashNode<K, V> head = hashArray.get(hashIndex);
        // 可选逻辑：判断是否已有重复key，存在则直接覆盖value
        GenericHashNode<K, V> cur = head.next;
        while (cur != null) {
            if (Objects.equals(cur.key, key)) {
                cur.value = value;
                return;
            }
            cur = cur.next;
        }
        // 头插新节点
        GenericHashNode<K, V> newNode = new GenericHashNode<>(key, value);
        newNode.next = head.next;
        head.next = newNode;
    }

    // compare方法改名为更语义化的containsKey
    public boolean containsKey(K key) {
        int hashIndex = createHashCode(key);
        // 直接取对应下标的桶
        GenericHashNode<K, V> current = hashArray.get(hashIndex).next;
        // 遍历该桶的链表即可
        while(current != null) {
            // 用Objects.equals比较，避免空指针
            if (Objects.equals(current.key, key)) {
                return true;
            }
            current = current.next;
        }
        return false;
    }
}

测试示例 #

你可以用以下代码测试功能：

public class Main {
    public static void main(String[] args) {
        GenericHashTable<String, Integer> table = new GenericHashTable<>(16);
        table.add("test1", 1);
        table.add("test2", 2);
        System.out.println(table.containsKey("test1")); // 输出true
        System.out.println(table.containsKey("test3")); // 输出false
    }
}

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