设计哈希集合

先想最直白的办法：最直白有两条路：开一个能装下所有可能值的大数组（值当下标）——太费内存；或者用一个列表，每次查找都从头扫一遍——太慢。两头都不理想。

为什么这两条都不好：大数组用值当下标，值一大就要开几百万格，绝大多数空着，浪费。长列表省了空间，但每次查找要从头比到尾，n 个元素就是 O(n)，多了就卡。我们想要又快又省。

关键思路：折中办法：只开少量几个桶（这里用 8 个）。来一个 key，用 key % 8 算出它该放进第几个桶。这个「取模算下标」就是哈希函数，它把任意大的值压进固定几个桶里。

桶里会撞怎么办：麻烦在于：不同的值可能算出同一个桶（叫「哈希冲突」）。比如 5%8=5、13%8=5，都想进 5 号桶。解决办法叫链地址法：同一个桶里挂一条链表，撞进来的值就往链表后面接。

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

add(5) · 先算桶号：add(5)：先用哈希函数算桶号，5 % 8 = 5，所以 5 该进 5 号桶（紫色高亮）。先看看这个桶里现在是空的，可以直接放。

add(5) · 挂进 5 号桶：5 号桶原来是空的，把 5 挂上去（绿色=刚存入）。现在 5 号桶的链表是「5」。整个集合里有了 1 个元素。

add(13) · 算出同一个桶：add(13)：算桶号 13 % 8 = 5，又是 5 号桶！可这个桶里已经有 5 了——这就撞上了哈希冲突。怎么办？挂到链表后面。

add(13) · 冲突 · 接到链表尾：先确认链表里没有 13（只有 5），再把 13 接到 5 的后面。现在 5 号桶是一条链：5 → 13。这就是链地址法处理冲突——撞了不怕，往后挂。

add(8) · 进另一个桶：add(8)：算桶号 8 % 8 = 0，进 0 号桶。它和 5、13 不在一个桶，互不打扰——这正是分桶的好处：把元素摊开。

add(8) · 挂进 0 号桶：0 号桶是空的，直接把 8 放进去（绿色）。现在集合里有 3 个元素，分布在两个桶里：0 号桶「8」、5 号桶「5 → 13」。

add(0) · 又一次冲突：add(0)：算桶号 0 % 8 = 0，进 0 号桶，可里面已经有 8 了——又撞上冲突。老规矩，挂到链表后面。

add(0) · 接到 0 号桶链尾：确认链里没有 0，把它接到 8 的后面。0 号桶现在是「8 → 0」。看到没——只要桶号撞上就往后挂，链表想多长就多长。

add(21) · 第三个挤进 5 号桶：add(21)：算 21 % 8 = 5，第三次进 5 号桶！5 号桶已经是「5 → 13」，21 要再往后挂。

add(21) · 5 号桶变三节链：查链里没有 21，接到 13 后面。5 号桶现在是三节链「5 → 13 → 21」。集合里 5 个元素，全靠两条短链兜着。

contains(5) · 先定位桶：查找 contains(5)：同样先算 5 % 8 = 5，直接跳到 5 号桶，不用碰别的桶。这一步是哈希表快的关键——一步定位到桶。

contains(5) · 沿链表比对：进到 5 号桶，沿着链表「5 → 13 → 21」从头比：第一个就是 5，命中！返回 true。桶里通常没几个元素，所以链表很短，比对很快。

contains(3) · 桶是空的：contains(3)：算 3 % 8 = 3，跳到 3 号桶——它是空的（红色）。链表里啥都没有，直接返回 false。压根不用扫别的桶。

contains(13) · 链表要走第二步：contains(13)：算 13 % 8 = 5，进 5 号桶，沿链「5 → 13 → 21」比：第一个 5 不等，往后走，第二个 13 命中，返回 true。冲突的代价就是链表上多比几下，但链一般很短。

remove(5) · 定位 + 摘链：remove(5)：算 5 % 8 = 5，进 5 号桶，在链「5 → 13 → 21」里找到 5（红色标记，准备摘掉）。删除就是把这个节点从链表里拿走。

remove(5) · 链头被摘掉：把 5 从链上摘掉，13 自动顶到链头。现在 5 号桶剩「13 → 21」，集合里 4 个元素。注意 13、21 没受影响——这就是链表删除的好处，只动目标节点。

contains(5) · 删除后再查：再 contains(5)：还是去 5 号桶，沿链「13 → 21」比一遍，没有 5（红色=查无），返回 false。删除生效了。

remove(8) · 删的是链头：remove(8)：算 8 % 8 = 0，进 0 号桶，链「8 → 0」里 8 正好是链头（红色）。删链头也一样——把它摘掉，后面的顶上来。

remove(8) · 0 号桶只剩 0：8 被摘掉，0 顶到链头。0 号桶现在是「0」。集合剩 3 个元素：0 号桶「0」、5 号桶「13 → 21」。这一连串增删查就是哈希集合的完整生命周期。

为什么这样就快：关键在于：取模让我们一步跳到对的桶，不用扫全部元素；只要桶数量够、哈希够均匀，每个桶里的链表都很短，沿链比对几乎瞬间完成。所以平均下来每次操作接近 O(1)。

落到代码 · 三步走：代码非常短：用「列表的数组」当桶（每个内层列表就是一条链）。add 先查重再追加，remove 找到就删，contains 沿链查。取模那一步是灵魂。

本质金句：哈希表的全部秘密就这两句：取模把海量元素摊进少数桶（一步定位、快），桶里挂链表兜住偶尔的冲突（撞了往后挂、稳）。这套结构是 HashMap / HashSet 的底层骨架。

易错实演 · 桶开太少全挤一起：假如桶数太少（极端情况只有 1 个桶），所有值都算到同一个桶，链表变成「5 → 13 → 8」一长条（红色）。查找又退回从头扫，O(n)——哈希表就白做了。所以桶数和哈希均匀很重要。

边界三连：这三种边界，我们的实现都自然兜住：add 靠查重去重、remove 找不到就跳过、contains 空链直接 false。不用任何特判。

面试追问：「开放寻址 vs 链地址」「链表转红黑树」「负载因子与扩容」是哈希表三大经典追问，答得出来能体现你懂底层。