01、设计哈希Map
键值映射不要求每个键都有一个独占数组位置。哈希表先把键分配到桶,再在桶里区分完整的键。理解这一点,才能处理冲突、更新和删除,而不是把“取模”当作整个哈希表。
问题与目标
LeetCode 706:设计哈希映射要求不使用内建哈希表,实现 put、get 和 remove。不存在的键返回 -1,题目值域为非负整数,所以这个返回约定不会与合法值混淆。
put 已有键时更新它的值,不新增第二个相同键;remove 不存在的键不产生变化。
桶负责粗定位,链表负责解决冲突
采用拉链法:数组中的每个桶保存一条链表,节点保存 key 和 value。两个键取模结果相同,只说明落到同一个桶,不说明它们是同一个键。
为便于画图,假设有 4 个桶:键 1、5 都落到桶 1,节点必须分别保留 (1,10)、(5,50)。实际代码使用 1009 个桶;这个数量是教学选择,不是正确性的必要条件,也不能保证绝无冲突。

更新和删除都需要比较完整 key
执行 put(5,99),先定位桶,再沿链表比较 key。找到 5 后只将 value 从 50 改为 99。只有遍历完整条链仍未找到时,才插入新节点。

删除同样先找 key,再删除那一个链表节点;删除桶头、中间、桶尾或不存在的键,都不应该清空整个桶。
C++17 实现
std::list 只用于维护桶内链表,不提供哈希查找,符合“不使用内建哈希表”的约束。容器负责释放节点,避免手写链表的资源泄漏。
#include <array>
#include <cstddef>
#include <list>
#include <utility>
class MyHashMap {
public:
void put(int key, int value) {
auto& bucket = buckets_[bucketIndex(key)];
for (auto& entry : bucket) {
if (entry.first == key) {
entry.second = value;
return;
}
}
bucket.emplace_front(key, value);
}
int get(int key) const {
const auto& bucket = buckets_[bucketIndex(key)];
for (const auto& entry : bucket) {
if (entry.first == key) return entry.second;
}
return -1;
}
void remove(int key) {
auto& bucket = buckets_[bucketIndex(key)];
for (auto current = bucket.begin(); current != bucket.end(); ++current) {
if (current->first == key) {
bucket.erase(current);
return;
}
}
}
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<std::pair<int, int>>, kBucketCount> buckets_;
};
取模函数额外规范化了负键,但题目测试仍沿用非负 key、value 的范围;若业务允许 value 等于 -1,应改用 optional 等接口区分缺失,不能沿用本题哨兵返回值。
复杂度要看负载,而不只看取模
设有 B 个桶、N 个键,负载因子 α=N/B。在合理分布下,每次操作期望 O(1+α);若通过扩容使负载受控,才能得到通常所说的平均常数操作。本文固定桶数且不扩容,不能对任意增长的 N 保证平均常数。
最坏情况下所有键落在同一桶,单次操作 O(N)。空间为 O(B+N)。质数桶数在某些取模输入中有帮助,但无法替代好的散列策略或负载控制。
常见误区
同桶不等于同键;更新不等于新增;取模本身是常数,不等于整次查找必为常数。验证时主动构造键 1、1010、2019,比只用不冲突的小键更容易检查桶内操作。
