设计简单哈希集合

题目

设计简单哈希集合

信息

• 类型：问答
• 难度：⭐

考点

哈希表原理,冲突解决,基本操作实现

快速回答

实现一个简易哈希集合（HashSet），需支持以下操作：

• add(key)：向集合插入元素
• remove(key)：从集合移除元素
• contains(key)：检查元素是否存在

关键实现要点：

1. 使用固定大小的数组（如长度1000）作为桶
2. 采用链地址法解决冲突（每个桶用链表存储元素）
3. 哈希函数：key % size 确定桶索引

原理说明

哈希表通过哈希函数将键映射到数组索引实现快速查找。本设计采用链地址法解决冲突：当多个键映射到同一索引时，在对应桶的链表中存储所有元素。

代码示例（Python）

class ListNode:
    def __init__(self, key):
        self.key = key
        self.next = None

class MyHashSet:
    def __init__(self):
        self.size = 1000
        self.buckets = [None] * self.size

    def _hash(self, key):
        return key % self.size

    def add(self, key):
        idx = self._hash(key)
        if not self.buckets[idx]:
            self.buckets[idx] = ListNode(key)
            return

        curr = self.buckets[idx]
        while True:
            if curr.key == key:  # 键已存在
                return
            if not curr.next:
                break
            curr = curr.next
        curr.next = ListNode(key)

    def remove(self, key):
        idx = self._hash(key)
        curr = prev = self.buckets[idx]
        if not curr: 
            return

        if curr.key == key:  # 删除头节点
            self.buckets[idx] = curr.next
            return

        curr = curr.next
        while curr:
            if curr.key == key:
                prev.next = curr.next
                return
            prev, curr = curr, curr.next

    def contains(self, key):
        idx = self._hash(key)
        curr = self.buckets[idx]
        while curr:
            if curr.key == key:
                return True
            curr = curr.next
        return False

最佳实践

• 负载因子控制：实际应用中需动态扩容（当元素数/桶数 > 阈值时，重建更大哈希表）
• 哈希函数优化：复杂场景可使用更均匀的哈希函数（如MD5后取模）
• 链表优化：当链表过长时可转换为红黑树（如Java HashMap）

常见错误

• 未处理冲突：直接覆盖桶内元素导致数据丢失
• 删除操作错误：链表删除时未正确更新前驱节点的next指针
• 空指针异常：未检查桶是否为空直接操作链表

扩展知识

• 开放寻址法：冲突时线性探测下一个空桶（需处理聚集问题）
• 再哈希：使用第二个哈希函数解决冲突
• 时间复杂度：理想情况O(1)，最坏情况（所有键冲突）O(n)