02、设计哈希Set
2025/11/10大约 3 分钟数据结构算法算法基地面试哈希表刷题程序厨校招社招
集合只回答“某个键是否存在”,不需要保存额外的业务值。HashSet 与 HashMap 的底层思路相通,但节点内容和接口语义应当分清。
问题与目标
LeetCode 705:设计哈希集合要求不使用内建哈希表,支持 add(key)、contains(key) 和 remove(key)。
重复 add 同一个键,集合大小不增加;remove 不存在的键,集合保持原样。contains 返回布尔值,不用 -1 代替不存在。
拉链法怎样处理冲突
数组下标由哈希函数得到,每个桶保存一条只含 key 的链表。同一桶里的键仍然要逐一比较,不能因为桶非空就返回“键存在”。
例如教学上用 4 个桶,1、5、9 都落在桶 1。删除 5 后应让 1 接到 9,不能删除另外两个不同键。

三个操作共用同一个查找约定
contains 只查目标桶;add 先在目标桶查重,找到就结束,未找到才插入;remove 找到后只删除对应节点。接口简单,但三个操作必须使用相同的桶函数和完整 key 比较。
C++17 实现
这里使用数组与 std::list,没有借助 std::unordered_set 或其他内建哈希容器。
#include <algorithm>
#include <array>
#include <cstddef>
#include <list>
class MyHashSet {
public:
void add(int key) {
auto& bucket = buckets_[bucketIndex(key)];
if (std::find(bucket.begin(), bucket.end(), key) == bucket.end()) {
bucket.push_front(key);
}
}
bool contains(int key) const {
const auto& bucket = buckets_[bucketIndex(key)];
return std::find(bucket.begin(), bucket.end(), key) != bucket.end();
}
void remove(int key) {
auto& bucket = buckets_[bucketIndex(key)];
const auto found = std::find(bucket.begin(), bucket.end(), key);
if (found != bucket.end()) bucket.erase(found);
}
private:
static constexpr int kBucketCount = 1009;
static std::size_t bucketIndex(int key) {
const int remainder = key % kBucketCount;
return static_cast<std::size_t>(remainder < 0 ? remainder + kBucketCount : remainder);
}
std::array<std::list<int>, kBucketCount> buckets_;
};
复杂度与边界
B 个桶、N 个键且分布合理时,每次操作期望 O(1+N/B);最坏冲突情况下 O(N)。本教学版本固定桶数、不做扩容,不能无条件承诺随着 N 增长仍为常数时间。空间 O(B+N)。
桶中的链表由容器释放,删除后不会留下手工分配节点。空集合查找返回 false,删除不存在的键无影响,重复插入后删除一次就应完全移除该键。
常见误区
用“键落在哪个桶”代替“键是否存在”会导致误判;add 不查重会把集合写成可重复容器;直接用大小为整个值域的布尔数组也是一种解法,但那是直接寻址,不是本文展示的冲突处理机制。
