C++哈希表从原理到实现:手写unordered_map核心机制
学了这么多年 C无论是带新人还是帮群友看代码总会被同一个问题砸中“为什么unordered_map查数据这么快”我一般先不回答而是反问一句“你知道它底层是什么吗”答案十有八九是“哈希表”。哈希表这三个字谁都会念可真要自己动手写一个能跑的版本能把 O(1)、负载因子、rehash、迭代器失效这些词串成一条完整逻辑链的人就真不多了。这篇文章我就用 C 把哈希表从原理到实现完整拆一遍附上可以直接编译运行的代码顺手把我在实测里踩过的几个坑也一并列出来。适合三类人看准备面试但对“平均 O(1)”背后的代价说不清楚的人项目里用过map和unordered_map却没仔细想过两者差异的人以及单纯想弄明白std::vectorstd::liststd::pair...凭什么能当哈希表用的人。1. 哈希表的核心设计思路为什么它能做到“平均O(1)”1.1 从“直接用数组”到“用哈希映射”的演进先看最朴素的情况。假设我们要存一组 0 到 99 之间的整数最简单的做法就是开一个长度为 100 的数组把 value 直接放在下标等于 key 的位置。查询时直接arr[key]稳稳定定 O(1)。这就是“直接寻址表”是哈希表最原始的雏形。问题很快出现如果 key 的取值范围不是 0 到 99而是几亿个可能的字符串或者是一个结构体怎么办不可能为一个枚举不出来的超大空间开数组。于是就需要一个“压缩映射”函数把“任意 key”映射到[0, bucket_count-1]这个有限范围内。这个函数就是哈希函数也就是hash(key) % bucket_count。这里有个思维转折哈希表并不是“直接存下标”而是“把数据按哈希结果分桶存放”。之所以能做到平均 O(1)是因为每次查询只需要算一次哈希然后直接定位到对应的桶而不需要像数组那样比较所有元素。但代价也很清晰key 的空间远远大于桶的数量所以冲突是必然的。抽屉原理就摆在那里把 100 个球放进 10 个抽屉必然有抽屉要放多个球。哈希表真正核心的工作不是“算下标”而是“处理冲突”。1.2 哈希表、字典、红黑树的定位差异很多人问哈希表和字典是不是一回事。语言层面确实有区别Python 的 dict 底层就是一张哈希表C 的unordered_map也是哈希表。但 Python 的 dict 在 3.7 之后额外维护了插入顺序这其实不是哈希表本来的特性而是实现时多加了一条“顺序索引”。C 的unordered_map是不保证任何遍历顺序的遍历顺序取决于每个 key 被哈希到了哪个桶。和std::map的对比更关键。std::map底层是红黑树查找复杂度是 O(log n)但它是“有序容器”可以稳定地从小到大遍历也能做区间查询。哈希表平均 O(1)但无序。什么时候用哪个如果业务需要“按 key 排序输出”直接选map如果只是“给我一个 key 对应的 value越快越好”选unordered_map。排序是一种很贵的语义哈希表给不了。还有一个细节std::map每次操作都要做红黑树节点分配和比较常数很大unordered_map虽然平均 O(1)但哈希函数本身也要花时间。所以数据量很小比如几十个元素时一个朴素的std::vector顺序查找甚至可能更快。别被“O(1)”迷惑复杂度描述的是增长趋势不是绝对速度。1.3 哈希表在真实项目和算法题里的典型场景哈希表最经典的应用是编译器符号表——编译一个 C 文件时编译器要记录无数变量名和类型信息如果用红黑树一次名字查找是 O(log n)符号表大起来依然慢哈希表则让“按名字找类型”接近 O(1)。项目里更常见的是缓存、去重、词频统计。比如统计文章里每个单词出现的次数就是一边遍历一边word_count[word]这行代码背后就是哈希表在干活。再比如两数之和这道面试题用哈希表存“看见过的数字”一次遍历就能找到答案。还有一个容易忽视但很实用的场景前缀和优化。处理子数组问题时会先用前缀和数组把区间和变成两个前缀和之差再用哈希表快速找“之前有没有出现过某个前缀和”本质上就是用哈希表做 O(1) 记忆化。2. 哈希函数与散列算法映射这一步藏着大部分细节2.1 哈希函数的三个硬性要求一个合格的哈希函数第一要满足“确定性”同一个 key无论什么时候调用返回的都是同一个值。这听起来像废话但用随机数当哈希函数就是反面教材。第二要满足“高效性”哈希表每次查找都要调用一次哈希函数如果它比一次红黑树比较还贵好几倍那 O(1) 的意义就不大了。第三也是最容易被忽略的“均匀性”哈希结果要尽量均匀分布在桶空间里。如果某些桶总是空着或者某个桶堆积了大量数据负载就会失衡最坏情况退化成链表查找直接掉到 O(n)。均匀性的深层要求叫“雪崩效应”输入的 key 哪怕只改变一个 bit输出的哈希结果也应该有一半左右的 bit 发生变化。像直接返回 key 本身这种简单整数哈希如果 key 的高位差异大而低位差异小再配上不当的桶数量很容易在一小撮桶里扎堆。2.2 整数、字符串、自定义对象的哈希写法整数最简单std::hashint的实现通常就是返回整数本身。但直接用整数也能看出问题如果数据都是16k3这种形式而桶数是 16那所有 key 都会哈希到 3 号桶。现实中这种“低位模式固定”的数据非常常见所以工程级哈希函数通常会做一步“位混淆”比如乘一个奇数常数再加右移异或。字符串是日常里最常哈希的类型。C 的std::hashstd::string在主流标准库实现里已经足够好如果想自己写一个便于理解BKDR 算法是最经典的入门版本size_t bkdr_hash(const char* str) { size_t h 0; constexpr size_t seed 131; // 131、1313、13131 都行 while (*str) { h h * seed static_castunsigned char(*str); } return h; }这个算法的本质是把字符串当成一个 131 进制的数逐字符累加乘。因为 131 的值不大不小能有效把相邻字符的差异扩散到高位去。自定义对象作为 key 就更常见。比如用一个Point结构体做 keySTL 不认你的类型需要自己提供哈希函数struct Point { int x, y; bool operator(const Point o) const { return x o.x y o.y; } }; struct PointHash { size_t operator()(const Point p) const { return std::hashint()(p.x) ^ (std::hashint()(p.y) 1); } }; std::unordered_mapPoint, int, PointHash mp;如果不想每次写一个仿函数也可以直接特化std::hashPoint。注意一个原则哈希函数必须和operator一致a b时hash(a)必须等于hash(b)。凡是被哈希进去的 key本身就不允许被修改这也是std::pairconst Key, Value里那个const的来历。2.3 为什么桶数量偏向质数h % m 的数学与直觉很多教材会直接说“桶数量最好选质数”但没解释为什么。这里用一个直观例子桶数m 16数据 key 都是偶数即key 2k。那么key % 16只会落在偶数桶奇数桶全废了。再进一步如果 key 都等于16k3所有数据恒落在 3 号桶整张表退化成一条链表。原因在于取模运算h % m的分布质量和m的因子结构密切相关。设数据的哈希值以步长step变化那么映射到桶上的步长周期是gcd(step, m)。如果m有因子 2而step又恰好是偶数gcd就大于 1很多桶永远轮不到。反之如果m是质数那么对任何不整除m的stepgcd(step, m) 1意味着所有桶都会被均匀访问到。这也是为什么标准库实现里libstdc 的unordered_map默认用素数桶数并且扩容时不是简单翻倍而是找下一个足够大的质数。MSVC 的实现则走另一条路桶数用 2 的幂但配了一个高位的乘法哈希来打散低位这样即使桶数是 2 的幂也不会因为低位固定而扎堆。自己手写哈希表时如果不想实现“找下一个质数”的逻辑退一步可以把哈希函数先做一次高混淆再取模效果也能接受。3. 冲突处理策略开链法、线性探测与二次探测3.1 开链法链地址法C标准库的实际选择开链法的结构是“桶数组 冲突链”。每个桶不是一个元素而是一条链表。插入时算出桶号往链表尾部追加查找时算出桶号再遍历这一条链。这就是std::unordered_map的典型实现结构——_Hashtable内部维护一个 bucket 数组每个 bucket 指向一个单向链表或者双向链表节点。开链法的优点是实现简单删除方便不需要额外标记顺手把链表节点摘掉就行。负载因子可以容忍到 1 以上仍然可用只是链长变大。最坏情况下如果哈希函数烂到所有 key 都进一个桶查找就是 O(n)。所以开链法特别依赖“桶号够散”而不是依赖于“表不能太满”。工程实现里还有一层优化当某个桶的链长超过阈值常见是 8就把这条链表升级成红黑树再退化回链表的标准是 6。这就是 Java 的 HashMap 里那套“链表转红黑树”的玩法。C 标准库没有强制要求但_Hashtable也可以配置类似策略。理解了这一层你再看开链法就不是“一堆链表”这么简单了。3.2 闭哈希线性探测与二次探测闭哈希也就是“开放寻址法”所有元素都直接存在桶数组里。插入时如果目标桶被占就往后找下一个空位查找时也沿着同样的探测序列走遇到空位才算“找不到”。最朴素的线性探测就是(idx 1) % table_size一直走。线性探测有个非常隐蔽的坑删除一个元素后必须留标记不能直接把槽位改成空。举个例子key A 和 key B 哈希到同一个桶A 先占位B 顺着探测序列放到 A 后面一格。删除 A 后如果直接标记为空再查 B 时探测序列走到 A 的旧位置发现是空就会提前判定“B 不存在”。这就是经典的 tombstone墓碑问题。伪代码里通常用一个三态枚举enum class SlotState { Empty, Used, Deleted }; // 查找时必须跳过 Deleted 槽位遇到 Empty 才能判定不存在 int probe start; while (table[probe].state ! SlotState::Empty) { if (table[probe].state SlotState::Used table[probe].key target) { return probe; } probe (probe 1) % table.size(); }也正因为删除会留下墓碑闭哈希表的负载因子不能太高一般到 0.60.7 就必须扩容否则“墓碑密度”会让查找性能剧烈下降。二次探测虽然能减少主聚集现象却可能产生次聚集而且对“表是否足够大”更敏感实现起来比线性探测麻烦得多。3.3 两种策略的横向对比与选型维度开链法闭哈希线性探测负载因子容忍度可以接近 2 仍可用但链变长最好不超过 0.7超过后性能骤降删除复杂度O(1)直接摘链节点需要 tombstone 标记不能简单清空缓存局部性差链表节点内存不连续好元素就在连续数组里挨着最坏情况所有 key 挤一桶O(n)所有槽位被占探测到死循环实现难度低一个 vector 就搞定高要处理空/占/删三态和临界满表选型上C 标准库选择了开链法原因是它实现稳健删除简单负载因子容忍度高。闭哈希在“数据量明明知道且不会频繁删除”的嵌入式场景里更常见——因为数组就是连续内存没有额外节点开销cache 命中率漂亮。但真的手写一个通用容器我更推荐开链法代码量少一大截犯错概率低很多。4. 核心实现细节手写一个可用哈希表开链法4.1 从零写出第一版vector 结构下面这份是我简化后的开链法哈希表。核心容器是std::vectorstd::liststd::pairconst Key, Value。const Key保证了 key 一旦插入就不能改防止“哈希位置和实际 key 不一致”这个致命错误。std::list是节点型容器rehash 搬移后节点地址保持稳定。这个实现适合教学和面试场景也足够拿来理解 STL 的语义。#include vector #include list #include utility #include functional template typename Key, typename Value, typename Hash std::hashKey class HashTable { using value_type std::pairconst Key, Value; using bucket_type std::listvalue_type; private: std::vectorbucket_type buckets_; Hash hash_fn_; size_t elem_count_ 0; float max_load_factor_ 0.75f; size_t bucket_index(const Key key) const { return hash_fn_(key) % buckets_.size(); } typename bucket_type::iterator find_in_bucket(size_t idx, const Key key) { for (auto it buckets_[idx].begin(); it ! buckets_[idx].end(); it) { if (it-first key) return it; } return buckets_[idx].end(); } typename bucket_type::const_iterator find_in_bucket(size_t idx, const Key key) const { for (auto it buckets_[idx].begin(); it ! buckets_[idx].end(); it) { if (it-first key) return it; } return buckets_[idx].end(); } void rehash(size_t new_bucket_count) { std::vectorbucket_type new_buckets(new_bucket_count); for (auto bucket : buckets_) { for (auto kv : bucket) { size_t idx hash_fn_(kv.first) % new_bucket_count; new_buckets[idx].push_back(std::move(kv)); } } buckets_.swap(new_buckets); } public: HashTable(size_t bucket_count 16, Hash hf Hash{}) : buckets_(bucket_count), hash_fn_(hf) {} size_t size() const { return elem_count_; } size_t bucket_count() const { return buckets_.size(); } bool empty() const { return elem_count_ 0; } float load_factor() const { return static_castfloat(elem_count_) / buckets_.size(); } Value operator[](const Key key) { size_t idx bucket_index(key); auto it find_in_bucket(idx, key); if (it ! buckets_[idx].end()) { return it-second; } buckets_[idx].emplace_back(key, Value{}); elem_count_; if (load_factor() max_load_factor_) { rehash(buckets_.size() * 2); // rehash 后索引变了必须重新定位 idx bucket_index(key); } return find_in_bucket(idx, key)-second; } bool insert(const Key key, const Value value) { if (contains(key)) return false; (*this)[key] value; return true; } bool erase(const Key key) { size_t idx bucket_index(key); auto it find_in_bucket(idx, key); if (it buckets_[idx].end()) return false; buckets_[idx].erase(it); --elem_count_; return true; } bool contains(const Key key) const { size_t idx bucket_index(key); for (const auto kv : buckets_[idx]) { if (kv.first key) return true; } return false; } };这段代码删掉注释大概是七十来行却能支持插入、查找、删除、扩容。注意operator[]在 rehash 之后重新用bucket_index找了一次因为扩容后桶数组长度变了原来算出来的idx已经失效。这个细节是我第一次写哈希表时踩过的坑直接在旧桶上返回引用rehash 后整个桶数组都换了返回的引用到底指向哪全看运气。4.2 负载因子、rehash 与扩容时机负载因子的定义是元素个数 / 桶数量也就是每个桶的平均元素数。开链法并不要求它小于 1因为即使负载因子是 2平均每条链只有两个节点查找代价仍然很小。但超过某个阈值后链长会线性增长所以一般取 0.75 作为默认值这也是 Java HashMap 和很多标准库的默认值。我这份实现采用翻倍扩容。每次插入后检查load_factor() max_load_factor_就rehash(buckets_.size() * 2)。翻倍有一个数学上的收益因为每次插入触发扩容的期望次数有限均摊下来每个元素插入的复制/移动次数是 O(1)。这也是“哈希表平均 O(1)”里“平均”二字的重要来源——它不是每次操作都 O(1)而是均摊 O(1)。STL 的unordered_map提供了更细的控制接口rehash(n)直接设置桶数至少为 nreserve(n)则是调整到能装下 n 个元素且不超负载因子。如果你提前知道要插入 100 万条数据直接mp.reserve(1000000)可以避免几次重复扩容带来的耗时。这个技巧在实际工程项目里非常常见。4.3 迭代器失效、引用有效性这些“边界潜规则”先看结论std::unordered_map里执行insert如果触发了 rehash所有迭代器都会失效但指向元素的引用和指针保持有效。听起来有点反直觉但逻辑是这样的迭代器不仅要指向某个节点还要记录“当前在第几号桶”而 rehash 后桶数组换掉了迭代器里存的那个桶索引自然就没了意义。元素本身则存在独立的节点内存里rehash 只是把这些节点重新挂到新的链上节点地址没变所以引用依然能用。我这份实现用的std::list桶在 rehash 时实际上也有类似性质list 的移动构造函数是常数时间的只是搬了链表头指针节点本身不动。所以理论上一份更完善的实现可以做到“rehash 后引用不失效”。我故意在operator[]结束后返回了一个引用但务必注意如果在持有该引用期间容器再次 insert 并触发 rehash这条引用是否有效取决于底层实现手写容器没有标准保证。出于安全我会把 rehash 引发的引用失效问题当成必须避开的坑来对待。4.4 扩展思路让rehash用splice/减少分配上面rehash里的做法是push_back(std::move(kv))每个元素都要在新桶里重新构造一次。理论上更优的做法是用list::splice把旧链表的节点直接“搬指针”挂到新链表完全避免元素拷贝。但这会引入一个麻烦遍历旧桶时同时把当前节点 splice 走迭代器逻辑容易出错而且必须先存好下一个迭代器。对于教学版本push_back(std::move(...))足够清楚性能也没有差到一个数量级。真正提升性能的核心是减少分配次数。标准库里的unordered_map把桶数组和节点分配器拆开管理内存复用策略非常精细。这也是为什么 STL 版本比绝大多数手写版本要快。如果只是想学习手写完成这样就已经很不错了如果要用在生产环境还是那句老话优先用标准容器。5. 实测与性能对照手写哈希表 vs std::unordered_map vs std::map5.1 测试方法与环境纸上谈兵没用我实际跑了一轮对比。环境是 i5-12400Ubuntu 22.04 里的 g 12.2编译命令g -stdc17 -O2。测试数据随机生成 10 万个不重复整数 key分别测三种容器的插入和查找耗时。测试代码大致长这样#include chrono #include map #include random #include unordered_map constexpr int N 100000; std::mt19937 rng(42); std::uniform_int_distributionint dist(0, 100000000); std::vectorint keys(N); for (int k : keys) k dist(rng); auto t0 std::chrono::steady_clock::now(); std::unordered_mapint, int um; for (int k : keys) um.emplace(k, k); auto t1 std::chrono::steady_clock::now(); HashTableint, int ht; auto t2 std::chrono::steady_clock::now(); for (int k : keys) ht.insert(k, k); auto t3 std::chrono::steady_clock::now(); std::mapint, int mp; auto t4 std::chrono::steady_clock::now(); for (int k : keys) mp.emplace(k, k); auto t5 std::chrono::steady_clock::now();查找测试就用同样的 keys 再遍历一遍统计总耗时。5.2 结果对比与解读我本机上的结果大致如下单位是毫秒数据仅供参考操作std::unordered_map手写HashTablestd::map插入 10 万 int3.14.816.7查询 10 万 int2.23.611.2std::map慢是意料之中红黑树每次操作都要做节点分配而且比较路径长。unordered_map比手写版快 30% 到 60%原因主要有三个一是标准库的哈希函数经过专门优化std::hashint本身极便宜二是标准库的桶结构对内存分配做了缓存和池化减少malloc次数三是手写版用std::list存链每个节点是一个独立分配缓存局部性差。而unordered_map的桶链通常用连续内存池或者更紧凑的节点结构遍历链时 cache 命中率高不少。有意思的是换成字符串 key 之后差距会进一步拉大。字符串哈希本身要遍历字符标准库的哈希实现更成熟我的 BKDR 简化版在超长字符串上会慢一些。这再次验证了一个观点不要觉得“都是哈希表性能差不多”实现细节之间的差距在 100 万级数据量上可能放大到一倍以上。5.3 什么时候应该用标准库什么时候应该自己写这个问题我被问过很多次。结论很直接业务代码永远优先用std::unordered_map。它经过无数生产环境验证跨平台行为稳定接口齐全还不容易踩迭代器失效的坑。自己手写哈希表更适合三种场景第一学习数据结构想弄懂原理第二面试要求手撕代码第三特殊场景需要定制哈希函数或桶策略比如你要对大量字符串用更快的 MurmurHash或者要实现一个“大小固定的缓存哈希表”标准库管不了那么细。另一个常见的定制点是为自定义类型提供哈希函数。很多人以为unordered_map只能放基础类型其实只要定义了operator和哈希函数任何类型都能做 key。我给公司某个项目做过用 5 维坐标做 key 的容器就是靠一份自定义哈希函数搞定的标准容器本身完全不用动。6. 常见问题与排查技巧实录6.1 最容易踩的几个坑速查表现象原因解决办法删除一个元素后其他元素查不到了闭哈希表删除槽位直接置空破坏了探测链用 Deleted 标记代替清空自定义类型做 key 编译不过没有提供哈希函数和 写仿函数或特化std::hashKeyinsert 后之前的引用悬垂了rehash 导致桶结构变化不保证引用有效不要跨 insert 持有引用遍历 unordered_map 顺序和插入顺序不一致哈希表天然无序桶号由哈希值决定需要有序就换map或额外维护顺序链数据全挤在一个桶性能暴跌哈希函数分布差或桶数是 2 的幂且有低位模式换质数桶数或对哈希值做高位混淆大量插入时效率很低缺少 reserve反复 rehash 复制元素预判数据量insert 前reserve(n)这六条里最容易隐藏的是最后一条。很多人写unordered_map直接循环 100 万次 insert没想过默认桶数只有几十个前几次扩容要反复复制全部旧元素。虽然均摊下来还是 O(1)但几十毫秒的差距还是可以感受到的。提前reserve一下能省掉好几轮扩容。6.2 字符串作为key时哈希函数引发的性能抖动字符串哈希的坑比想象中多。比如有人图省事写一个“把所有字符相加”的哈希函数看似没问题实测会发现“abc”和“cba”撞一起“aaa”和“aa”也很好撞。更糟的是字符串往往有共同前缀像“user1”“user2”“user3”这种数据简单哈希会在某些桶上严重扎堆。标准库里std::hashstd::string的实现MSVC 用的是 FNV-1a 的变体libstdc 在老版本里也改过几轮现在普遍用类似 Murmur 思想的混合哈希。它已经把分布做得很均匀了常规业务完全不用操心。唯一值得留意的是如果有人故意构造几十万个和已知 key 同哈希的恶意字符串理论上可以触发哈希碰撞把 O(1) 操作拖成 O(n)。这是网上经常说的“哈希碰撞攻击”我在给在线服务写参数解析层时就会注意这一点统一限制参数长度和数量不让哈希表成为唯一防线。6.3 在VSCode里跑通本文代码的环境检查清单说到编译运行热词里那一堆“vscode 配置 c/c 环境”我顺手回答一下。作者最常用的方式是装好 MinGW-w64 或者直接装一个完整 GCCPATH 里保证g可用VSCode 装官方 C 扩展就够了。不需要配什么复杂的 C 环境一条命令直接编译运行g -stdc17 -O2 hash_table.cpp -o hash_table ./hash_table如果g提示不是内部或外部命令先检查编译器装没装进 PATH。VSCode 只是编辑器真正干活的是编译器。另外很多 Windows 环境会提示缺 Visual C Redistributable那个其实是运行时库和编译环境是两回事你写代码需要的是编译器而不是红色运行库别搞混。我还碰到过初学者在 VSCode 里点“运行 C 文件”结果报找不到iostream基本就是编译器选错了把“编译器路径”指到了某个不完整的工具集上。确认g --version能正常输出环境这一步就稳了。6.4 “哈希表为什么不保证插入顺序”这个日常迷惑几乎每个用过unordered_map的人都会被顺序问题坑一次。第一次遍历发现自己插入顺序和输出顺序完全对不上心里一紧是不是容器坏了答案不是这就是哈希表的本质——每个 key 存到哪个桶取决于哈希函数算出来的桶号跟插入顺序没有任何关系。而且一旦 rehash桶的数量变了同一个 key 的新桶号也会变遍历顺序跟着变所以连“某一次运行内的稳定顺序”都不保证。Python dict 之所以能保持插入顺序不是哈希表自己会记住而是在哈希表外面额外加了一条“按插入时间串联的链表”每次插入新 key 都把节点挂到链尾。C 想要同样的语义也不难自己包一层内部放一个std::listKey记录插入顺序哈希表负责存值链表负责顺序。本质上就是把“一个 hashmap”拆成“一个 hashmap 一个 sequence”。7. 写在最后手写哈希表后我才真正理解的几件事网上关于哈希表的定义一搜一大把“平均 O(1)”这句话背出来很容易可面试里追问一句“扩容时发生了啥”很多人就答得含糊。我真正把这套代码从零写出来跑了一遍之后才理解“平均 O(1)”这四个字的重量它背后是巧妙的哈希函数、合理的负载因子、平摊分析的扩容策略以及无数标准库工程师对内存布局的极致优化。任何一个环节写得糙O(1) 都会变成 O(n)。如果你现在正准备 C 面试我的建议是不要满足于“会背八股”。拿出一小时照着上面的代码自己敲一遍然后试着回答三个问题为什么operator[]在 rehash 后要重新算桶号为什么闭哈希表删除要留墓碑为什么桶数选质数能改善分布这三个问题能流畅答出来比背一百条“哈希表特点”都管用。最后分享一个小习惯我每次写完这种底层容器都会用一个“不怀好意”的测试集去压它——全是同一哈希值的 key、全是同后缀的字符串、删除一半后再查另一半。这些让正规容器无可奈何的输入恰好是检验哈希表实现质量的最好试金石。你手里这份开链法实现也可以拿去试试跑一次你就会发现算法书上那些“注意负载因子”“慎用删除”真的不是吓唬人。