哈希算法题目：设计哈希集合

题目描述
设计一个哈希集合（HashSet），要求实现以下操作：

• add(key)：向集合中插入键 key。
• remove(key)：将键 key 从集合中删除。
• contains(key)：检查集合中是否包含键 key，存在则返回 true，否则返回 false。

要求

• 键的取值范围为 [0, 10^6]。
• 操作调用次数最多为 10^4 次。

解题思路
哈希集合的核心是快速判断元素是否存在。直接使用大数组（如 boolean[1000001]）可满足时间复杂度要求，但空间效率低。更通用的方法是采用链地址法（数组+链表）或开放寻址法。以下以链地址法为例分步讲解。

步骤 1：确定哈希桶的数量

• 为了平衡时间与空间效率，通常选择质数作为桶数量（如 1009），减少哈希冲突。
• 此处取 BASE = 1009，即集合由 1009 个链表（桶）组成。

步骤 2：设计哈希函数

• 哈希函数将键映射到桶的索引：hash(key) = key % BASE。
• 例如：若 key = 2025，则 2025 % 1009 = 1006，该键应放入第 1006 号桶。

步骤 3：定义数据结构
每个桶是一个链表，用于存储同一哈希值的所有键。

class MyHashSet {  
    private static final int BASE = 1009;  
    private LinkedList<Integer>[] buckets;  

    public MyHashSet() {  
        buckets = new LinkedList[BASE];  
        for (int i = 0; i < BASE; i++) {  
            buckets[i] = new LinkedList<>();  
        }  
    }  
}  

步骤 4：实现 add(key)

1. 计算桶索引：index = key % BASE。
2. 若该桶的链表中不存在 key，则将 key 添加到链表末尾（避免重复插入）。

public void add(int key) {  
    int index = key % BASE;  
    if (!buckets[index].contains(key)) {  
        buckets[index].addLast(key);  
    }  
}  

步骤 5：实现 remove(key)

1. 计算桶索引 index。
2. 若链表中存在 key，则删除该节点（需遍历链表查找）。

public void remove(int key) {  
    int index = key % BASE;  
    Iterator<Integer> it = buckets[index].iterator();  
    while (it.hasNext()) {  
        if (it.next() == key) {  
            it.remove();  
            return;  
        }  
    }  
}  

步骤 6：实现 contains(key)

1. 计算桶索引 index。
2. 遍历对应链表，若找到 key 则返回 true，否则返回 false。

public boolean contains(int key) {  
    int index = key % BASE;  
    for (int k : buckets[index]) {  
        if (k == key) return true;  
    }  
    return false;  
}  

复杂度分析

• 时间复杂度：平均 O(1)，最坏 O(n)（当所有键哈希冲突时）。
• 空间复杂度：O(n + BASE)，n 为插入的键数量。

关键点

• 链地址法通过链表处理冲突，确保操作高效。
• 选择质数作为桶数量可减少哈希冲突概率。