设计哈希集合 图解题解

这道题到底在问什么

示例

add(5)、add(13)、add(8)

示例

contains(5) → true，contains(3) → false

示例

remove(5) 之后，contains(5) → false

先想最直接的笨办法

先开 8 个桶，编号 0~7，全是空的（「·」表示空链）。左边一列是桶号，右边一列是这个桶里挂的链表。接下来一个一个操作给你看。（动画第 7 步）

最优解：一步一步想明白

1. 3拿一个大数组 / 一个长列表最直白有两条路：开一个能装下所有可能值的大数组（值当下标）——太费内存；或者用一个列表，每次查找都从头扫一遍——太慢。两头都不理想。
2. 4要么费空间，要么费时间大数组用值当下标，值一大就要开几百万格，绝大多数空着，浪费。长列表省了空间，但每次查找要从头比到尾，n 个元素就是 O(n)，多了就卡。我们想要又快又省。
3. 5开少量「桶」，用取模决定进哪个桶折中办法：只开少量几个桶（这里用 8 个）。来一个 key，用 key % 8 算出它该放进第几个桶。这个「取模算下标」就是哈希函数，它把任意大的值压进固定几个桶里。
4. 6同一个桶放多个值 → 挂成链表麻烦在于：不同的值可能算出同一个桶（叫「哈希冲突」）。比如 5%8=5、13%8=5，都想进 5 号桶。解决办法叫链地址法：同一个桶里挂一条链表，撞进来的值就往链表后面接。
5. 7buckets[0..7] 全空先开 8 个桶，编号 0~7，全是空的（「·」表示空链）。左边一列是桶号，右边一列是这个桶里挂的链表。接下来一个一个操作给你看。
6. 85 % 8 = 5 → 进 5 号桶add(5)：先用哈希函数算桶号，5 % 8 = 5，所以 5 该进 5 号桶（紫色高亮）。先看看这个桶里现在是空的，可以直接放。
7. 95 号桶链表：55 号桶原来是空的，把 5 挂上去（绿色=刚存入）。现在 5 号桶的链表是「5」。整个集合里有了 1 个元素。
8. 1013 % 8 = 5 → 又是 5 号桶！add(13)：算桶号 13 % 8 = 5，又是 5 号桶！可这个桶里已经有 5 了——这就撞上了哈希冲突。怎么办？挂到链表后面。
9. 115 号桶链表：5 → 13先确认链表里没有 13（只有 5），再把 13 接到 5 的后面。现在 5 号桶是一条链：5 → 13。这就是链地址法处理冲突——撞了不怕，往后挂。
10. 128 % 8 = 0 → 0 号桶add(8)：算桶号 8 % 8 = 0，进 0 号桶。它和 5、13 不在一个桶，互不打扰——这正是分桶的好处：把元素摊开。
11. 130 号桶链表：80 号桶是空的，直接把 8 放进去（绿色）。现在集合里有 3 个元素，分布在两个桶里：0 号桶「8」、5 号桶「5 → 13」。
12. 140 % 8 = 0 → 0 号桶已有 8add(0)：算桶号 0 % 8 = 0，进 0 号桶，可里面已经有 8 了——又撞上冲突。老规矩，挂到链表后面。
13. 150 号桶链表：8 → 0确认链里没有 0，把它接到 8 的后面。0 号桶现在是「8 → 0」。看到没——只要桶号撞上就往后挂，链表想多长就多长。
14. 1621 % 8 = 5 → 又是 5 号桶add(21)：算 21 % 8 = 5，第三次进 5 号桶！5 号桶已经是「5 → 13」，21 要再往后挂。
15. 175 号桶链表：5 → 13 → 21查链里没有 21，接到 13 后面。5 号桶现在是三节链「5 → 13 → 21」。集合里 5 个元素，全靠两条短链兜着。
16. 185 % 8 = 5 → 去 5 号桶找查找 contains(5)：同样先算 5 % 8 = 5，直接跳到 5 号桶，不用碰别的桶。这一步是哈希表快的关键——一步定位到桶。
17. 19链头就是 5 → 命中！进到 5 号桶，沿着链表「5 → 13 → 21」从头比：第一个就是 5，命中！返回 true。桶里通常没几个元素，所以链表很短，比对很快。
18. 203 % 8 = 3 → 3 号桶空contains(3)：算 3 % 8 = 3，跳到 3 号桶——它是空的（红色）。链表里啥都没有，直接返回 false。压根不用扫别的桶。
19. 2113 % 8 = 5 → 沿链找到第 2 个contains(13)：算 13 % 8 = 5，进 5 号桶，沿链「5 → 13 → 21」比：第一个 5 不等，往后走，第二个 13 命中，返回 true。冲突的代价就是链表上多比几下，但链一般很短。
20. 225 % 8 = 5 → 从链里摘掉 5remove(5)：算 5 % 8 = 5，进 5 号桶，在链「5 → 13 → 21」里找到 5（红色标记，准备摘掉）。删除就是把这个节点从链表里拿走。
21. 235 号桶链表：13 → 21把 5 从链上摘掉，13 自动顶到链头。现在 5 号桶剩「13 → 21」，集合里 4 个元素。注意 13、21 没受影响——这就是链表删除的好处，只动目标节点。
22. 245 号桶里已没有 5 → false再 contains(5)：还是去 5 号桶，沿链「13 → 21」比一遍，没有 5（红色=查无），返回 false。删除生效了。
23. 258 % 8 = 0 → 摘掉 0 号桶链头 8remove(8)：算 8 % 8 = 0，进 0 号桶，链「8 → 0」里 8 正好是链头（红色）。删链头也一样——把它摘掉，后面的顶上来。
24. 260 号桶链表：08 被摘掉，0 顶到链头。0 号桶现在是「0」。集合剩 3 个元素：0 号桶「0」、5 号桶「13 → 21」。这一连串增删查就是哈希集合的完整生命周期。
25. 27桶把 n 个元素摊薄关键在于：取模让我们一步跳到对的桶，不用扫全部元素；只要桶数量够、哈希够均匀，每个桶里的链表都很短，沿链比对几乎瞬间完成。所以平均下来每次操作接近 O(1)。
26. 28桶数组 + 取模 + 链表增删查代码非常短：用「列表的数组」当桶（每个内层列表就是一条链）。add 先查重再追加，remove 找到就删，contains 沿链查。取模那一步是灵魂。
27. 31记住这一句哈希表的全部秘密就这两句：取模把海量元素摊进少数桶（一步定位、快），桶里挂链表兜住偶尔的冲突（撞了往后挂、稳）。这套结构是 HashMap / HashSet 的底层骨架。
28. 33若只开 1 个桶 → 退化成长链假如桶数太少（极端情况只有 1 个桶），所有值都算到同一个桶，链表变成「5 → 13 → 8」一长条（红色）。查找又退回从头扫，O(n)——哈希表就白做了。所以桶数和哈希均匀很重要。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class MyHashSet:
    def __init__(self):
        self.size = 8
        self.buckets = [[] for _ in range(self.size)]
    def _hash(self, key):
        return key % self.size
    def add(self, key):
        b = self.buckets[self._hash(key)]
        if key not in b:
            b.append(key)
    def remove(self, key):
        b = self.buckets[self._hash(key)]
        if key in b:
            b.remove(key)
    def contains(self, key):
        return key in self.buckets[self._hash(key)]

class MyHashSet {
    int size = 8;
    vector<list<int>> buckets;
    int hash(int key) { return key % size; }
public:
    MyHashSet() : buckets(size) {}
    void add(int key) {
        list<int>& b = buckets[hash(key)];
        for (int x : b) if (x == key) return;
        b.push_back(key);
    }
    void remove(int key) {
        buckets[hash(key)].remove(key);
    }
    bool contains(int key) {
        list<int>& b = buckets[hash(key)];
        for (int x : b) if (x == key) return true;
        return false;
    }
};

class MyHashSet {
    private int size = 8;
    private LinkedList<Integer>[] buckets;
    private int hash(int key) { return key % size; }
    @SuppressWarnings("unchecked")
    public MyHashSet() {
        buckets = new LinkedList[size];
        for (int i = 0; i < size; i++) buckets[i] = new LinkedList<Integer>();
    }
    public void add(int key) {
        LinkedList<Integer> b = buckets[hash(key)];
        if (!b.contains(key)) b.add(key);
    }
    public void remove(int key) {
        buckets[hash(key)].remove(Integer.valueOf(key));
    }
    public boolean contains(int key) {
        return buckets[hash(key)].contains(key);
    }
}

复杂度

面试官可能追问