题解：P11615 【模板】哈希表

zlqwq · 2025-01-28 21:06:50 · 题解

如果大家不会哈希表的话，可以去看一下 oi-wiki。

这里解释一下这个算法。

首先，哈希表大概是在维护一个链表结构，然后抽象到图上大概是一个树。

同时，它也支持插入，查询，删除等操作。

查询：对于一个 x，找到 x 的值，然后顺着链表往下遍历。

插入：通过找出 x 的哈希值，把 x 顺着树往数组里存储。

删除：如果暴力删除的话，时间复杂度就变成了 O(n)，这样就失去了哈希表的优势。我们考虑开一个标记数组，把 x 标记上即可，时间复杂度 O(1)。

维护的操作就是这样，然后不要忘了取模。