先说个我踩过的坑。去年维护一个广告检索服务平时单次请求稳定在5毫秒某次版本上线之后P99耗时直接从8毫秒飙到800毫秒CPU也一直下不来。用pprof抓热点栈里全是哈希表查找和字符串分配业务代码明明只是查了一个map。排查到最后是新功能里用unordered_map存了一批拼接出来的长字符串当key这些key结构高度相似默认哈希函数对这类数据碰撞极其严重几万条记录全挤在了几个桶上查找复杂度从O(1)退化成了O(n)。哈希表是软件工程里出场率最高的数据结构之一平均O(1)的查找让它在缓存、索引、去重、路由分发里无处不在。但它不像表面看起来那么简单哈希函数怎么写、冲突怎么处理、装载因子怎么设、扩容怎么做每一项都直接影响线上表现。这篇文章不打算讲教科书理论我就按照自己实际用过、调过、踩过坑的顺序把哈希表彻底拆开聊透。不管你是刚接触数据结构的初学者还是写了几年业务想彻底搞懂哈希表的工程师应该都能从中捞出点东西。1. 哈希表到底是种什么结构1.1 从数组说起为什么我们能O(1)查找想要理解哈希表先想明白数组为什么快。数组里存了n个元素你访问arr[i]的时候CPU直接通过基地址加偏移量去内存里取值地址 基地址 i * 元素大小。这个计算是常数时间跟数组多大完全没有关系。所以数组的按下标随机访问是真正的O(1)。问题来了真实业务里我们手里的key往往是字符串、对象、ID而不是天然的整数下标。你手上有一个订单号ORD20240618001想查这个订单的数据你总不能把订单号直接当成数组下标用。哈希函数就是干这个事的它把任意类型的key映射成一个整数再对这个整数做一次取模或者位运算得到一个合法的数组下标。我用个生活化的例子帮大家理解。图书馆里几百万本书管理员如果给每本书一个唯一编号编号取模后落在某个书架上找书的时候先算书架号再去对应书架的小格子里翻这一步就省掉了几百万次比对。哈希表做的就是这样一件事通过设计良好的映射规则把大海捞针变成根据索引直接定位。1.2 哈希函数担任的角色哈希函数是哈希表里最重要的零件。它的职责是接收任意长度的key输出一个固定范围内的整数哈希值然后通过取模或者掩码操作定位到桶的下标。数学上它完成了从大空间到小空间的压缩映射。举个例子一个最简单的哈希函数h(key) key mod 16。假设key是整数17、33、49它们取模16的结果都是1都会落到桶1这就是冲突。哈希表内部就是用一个数组叫桶数组加上每个桶里挂的元素去组织数据桶下标由哈希函数决定。在真实工程里字符串哈希比整数哈希复杂得多。像Java的String.hashCode()用的是多项式滚动哈希C标准库的std::hash在不同实现里用的算法也不同Python的字符串哈希更是用了随机化种子每次启动都可能不一样。哈希函数设计得好不好直接影响哈希表的均不分布程度后面专门有一节讲这个这里先记住一个结论哈希函数是一种压缩映射压缩映射就必然引入冲突冲突是绕不开的。1.3 理想情况下的复杂度分析假设哈希函数足够好每个key都均匀随机地落在各个桶上桶的数量跟元素数量同阶那么每次插入、查找、删除只需要算一次哈希、定位到桶再在桶的局部做常数次比较平均时间复杂度就是O(1)。这里要强调平均两个字。因为有冲突存在最坏情况下所有key都映射到了同一个桶哈希表就会退化成一条链表查找复杂度变成O(n)。所以衡量一个哈希表的好坏很多时候不是在谈论它的平均表现而是在讨论它能不能避免最坏情况、以及在面对恶意输入时会不会崩掉。后面会详细讲工程上怎么通过冲突处理方案、装载因子、扩容策略和哈希函数设计尽量把最坏情况出现的概率压到极低。2. 哈希冲突绕不开的核心问题2.1 冲突为什么无法回避冲突的本质是鸽笼原理如果要把n个key放进m个桶里当n m时必然有至少一个桶装了多个key冲突无法避免。就算n m由于哈希函数是把无限输入空间映射到有限输出空间你也不能保证不会出现两个不同的key具有相同哈希值的情况。我见过不少刚入行的同学问为什么不用一个足够大的数组、让每个key都有唯一下标答案是做不到因为key空间无限内存有限。哈希表本质上是在用有限的空间存储无限的可能输入所以冲突根本不是没有和有的问题而是什么时候发生和发生了怎么处理的问题。两种主流方案链地址法和开放地址法就是两套完全不同的应对思路。2.2 链地址法拉链法链地址法的思路很直接桶数组里的每个元素不再直接存值而是存一个链表的头指针。发生冲突的元素就排在同一个桶对应的链表里。查找的时候先算哈希找到桶再在链表里线性扫描。我最早接触哈希表就是从拉链法入门的因为它逻辑最自然。C的std::unordered_map用的就是拉链法Java 8之后的HashMap也采用了链表红黑树的变体同一个桶里的元素数量小于等于8时用链表超过8且桶数组长度大于等于64时就转成红黑树把最坏情况从O(n)降到O(log n)。拉链法的优点很明显实现简单删除方便查找时只需要遍历很少几个节点插入的时候不需要处理下一个空位在哪的问题。代价是每个节点要额外存储指针内存开销比较大而且链表节点在内存里往往不是连续的访问时可能产生缓存不命中。不过对绝大多数业务场景来说这个开销可以接受。2.3 开放地址法开放地址法走了另一条路不额外挂链表所有元素都存在桶数组本身里。插入时发现位置被占了就按照某种探测序列去找下一个空位置。探测的常见方式有三种。线性探测冲突的时候依次往后找hash(key) 1、hash(key) 2……直到找到空位。优点是实现简单、内存连续、缓存非常友好缺点也很明显连续占用的桶会形成聚集区一旦聚集后续插入会像堵车一样越堵越长。二次探测按平方序列探测hash(key) 1²、hash(key) 2²……能缓解线性探测的聚集问题但可能出现探测不到空槽的情况。双重哈希用第二个哈希函数计算探测步长理论分布最好但计算量翻倍。开放地址法还有个特殊问题删除。如果直接删掉某个桶里的元素会导致探测链断裂后面的元素可能就找不到了。所以工程实现一般用墓碑标记tombstone删除时做一个标记查询时跳过墓碑继续探测插入时允许覆盖墓碑。Python的字典用的就是开放地址法实际是改进后的紧凑稀疏表方案它在内存利用率和缓存友好性上做得很极致。2.4 两种方案怎么选来一张对比表方便大家根据场景做决策对比维度链地址法开放地址法实现复杂度较低稍高删除需要墓碑机制内存占用节点需要额外指针开销大更紧凑内存利用率高缓存友好性链表节点分散访问不连续桶数组连续缓存命中率高最坏情况O(n)可优化为红黑树O(log n)探测链可能很长扩容代价重建所有桶重新分配链表节点重新分配数组并rehash代表实现C unordered_map、Java HashMapPython dict、Redis hash我的个人经验是如果是通用场景、需要频繁删除、代码要便于维护选拉链法如果对内存占用敏感比如要存几千万个键值对或者对缓存局部性要求极高就认真考虑开放地址法。Redis的字典设计得很聪明普通场景用拉链法但它的对象编码里也有紧凑的ziplist和listpack方案本质上都是在不同数据量下做取舍。3. 装载因子、扩容与哈希函数质量3.1 装载因子为什么偏偏是0.75装载因子load factor的定义是当前元素数量 / 桶数组长度。它直接决定了哈希表的拥挤程度。装载因子越高空间利用率越高但冲突概率也越大查询退化风险越高装载因子越低冲突少、性能好但内存浪费严重。这是一个典型的空间换时间问题。Java的HashMap把默认装载因子设在0.75这个数字不是拍脑袋定的它是在时间成本和空间成本之间的经典权衡。按照泊松分布模型在随机哈希函数下当装载因子为0.75时单个桶里元素数量超过8的概率极低大概亿分之几所以Java 8选择把树化阈值定在8既避免链表过长又不会频繁触发红黑树转换。C的std::unordered_map默认max_load_factor是1.0Python的dict装载因子大约是2/3各有各的取舍逻辑。工程上我建议大家不要乱改这个值。有些同学为了省内存把装载因子调到0.9以上结果遇到一次哈希不均匀线上查询直接爆炸。如果确实内存紧张不如换用更紧凑的数值类型或者换数据结构的存储方式而不是拿哈希表的性能去赌。3.2 扩容机制为什么rehash不是复制那么简单当元素数量超过装载因子上限时哈希表就要扩容。最常见的策略是新桶数量 旧桶数量 × 2或者取大于这个数的质数然后把所有已存在的元素重新计算哈希值、重新插入到新数组里。注意是重新计算位置不是简单地把旧数组元素复制到新数组对应位置。因为桶数量变了取模的结果就全变了。扩容是一个很重的操作尤其在存了几百万个元素时rehash过程会瞬间吃掉大量CPU和内存。为了应对这个问题Redis的字典实现了渐进式rehash扩容时不一次性搬完而是在每次增删改查时顺手搬一小部分把耗时的操作分摊到多次访问里。这种做法在需要保证服务稳定性的场景里非常实用我个人在自研缓存组件时也借鉴过这个思路。3.3 哈希函数设计的三个层次哈希函数的质量可以从三个层次来看。第一层是均匀性。好的哈希函数应该让不同key的输出尽可能均匀分布。一个坏例子是把字符串所有字符的ASCII码加起来如果key都是abc、bca这种同字母不同顺序的字符串就全撞一起了。工程常用的字符串哈希有FNV-1a、MurmurHash、CityHash、xxHash等它们都经过大量语料测试分布性有保障。第二层是速度。哈希函数是每次查询都要执行的性能至关重要。FNV-1a实现简单、极快适合短字符串和嵌入式场景MurmurHash质量好、速度快适合通用场景SipHash则在安全和速度之间取得平衡被很多语言用作哈希表的默认哈希函数。选型时要考虑你的实际数据特征没有银弹。第三层是安全性。如果key是用户可控的恶意攻击者可以构造大量碰撞的key让哈希表整个退化成链表这就是Hash DoS攻击。防御手段包括给哈希函数加随机种子、使用SipHash这类带密钥的哈希算法、限制哈希表最大长度。我在做网关鉴权系统时就吃过这个亏后来把所有对外接口的map全部换成了带随机种子的哈希函数。3.4 主流语言哈希表实现差异对比实现冲突方案装载因子/扩容策略备注Java HashMap链表红黑树默认0.75扩容翻倍非线程安全Java ConcurrentHashMap链表红黑树分段锁/CAS优化并发高并发场景首选C std::unordered_map拉链法max_load_factor默认1.0标准库实现性能依赖编译期Python dict开放地址法约2/3扩容约翻倍3.6后保持插入顺序Redis dict拉链法1.0触发扩容渐进式rehash支持缩容我工作里最常用的是Java和C的哈希表这两者设计哲学完全不同。Java的HashMap引入了红黑树来抵抗极端碰撞而C std::unordered_map完全依赖哈希函数的质量所以用C时反而要更小心。Python的dict在小数据量下性能非常惊艳因为它的实现是专门为Python对象优化的。4. 哈希表在真实业务系统里的应用4.1 缓存系统Redis和内存缓存几乎所有缓存系统底层都站着一个哈希表。Redis本身就是一个全局字典每个key通过哈希定位到对应的存储位置所有数据结构都构建在这张大的哈希表之上。同时Redis的哈希对象在元素少时用ziplist编码元素多了转成hashtable编码本质就是在内存效率和访问效率之间切换。我自己做本地缓存时也习惯用哈希表做核心结构key是缓存键value是带过期时间的包装对象。配合LRU淘汰策略时经典做法是哈希表双向链表哈希表负责O(1)定位节点双向链表负责维护访问顺序。这个就是随手写过的LRU Cache也是面试高频题强烈建议每个人都亲手实现一遍。4.2 数据库索引与布隆过滤器哈希表在数据库领域也有一席之地。MySQL的Memory引擎支持哈希索引适合等值查询InnoDB的自适应哈希索引会在热点数据上自动建哈希索引加速主键查找和重复查询。注意哈希索引不支持范围查询因为哈希值本身是无序的这跟B树正好互补。布隆过滤器也是一个很有意思的哈希应用。它用多个哈希函数把元素映射到一个位数组的多个位上判断一个元素肯定不在集合里非常快判断可能存在会有一定的误判率。我做过一个黑名单服务几千万条黑名单记录如果全放Redis key会占用大量内存用布隆过滤器扛在最前面内存占用直接降了两个数量级。4.3 去重、计数与一致性哈希去重和计数是哈希表的传统主场。业务里最常见的需求是给一批用户ID去重、统计每个商品加购数量、记录某台机器的请求计数。哈希表天然支持按key聚合的思维任何需要根据某个标识快速找到对应聚合数据的场景第一反应都应该是哈希表。购物车场景里商品ID到购买数量的映射就是一个典型的HashMap。分布式场景的一致性哈希也值得提。为什么不用普通哈希取模因为节点增减时取模的基数变了绝大部分key都会迁移对缓存系统来说是灾难。一致性哈希把哈希值组织成一个环每个节点负责一段区间节点增减只影响相邻的小范围数据再通过虚拟节点技术解决节点哈希不均匀的问题。这套思想在很多分布式中间件里都有体现。4.4 算法面试中的哈希表套路算法题里哈希表几乎是万能辅助。两数之和用哈希表存值-下标一趟遍历就能解决最长无重复字符子串用哈希表记录每个字符的出现位置配合滑动窗口移动左指针设计LRU结构要靠哈希表定位节点、双向链表调整顺序求数组中出现次数超过一半的元素哈希计数后一次扫描就能找到。准备面试的时候我建议大家把所有哈希表的高频题按场景归类计数类、索引类、去重类、缓存设计类。每类吃透一两道典型题比盲目刷二十道效果要好得多。5. 从零手写一个迷你哈希表C5.1 为什么选拉链法实现为了让大家真正理解哈希表内部原理我写了一个教学版的迷你哈希表用C实现选择拉链法。原因有三实现清晰每个桶就是一条链表指针指向关系一目了然不用处理开放地址法的墓碑删除问题代码更聚焦跟std::unordered_map的结构保持一致方便对照学习。哈希函数我用了FNV-1a它的强度在简单哈希函数里属于第一梯队而且代码只有几行非常适合教学演示。注意这里仅用于演示生产环境建议直接用std::unordered_map或者经过充分测试的第三方哈希表。5.2 核心实现代码#include vector #include list #include string #include utility #include algorithm #include iostream class SimpleHashMap { public: explicit SimpleHashMap(size_t bucketCount 16) : buckets_(bucketCount), size_(0) {} void put(const std::string key, int value) { auto it find(key); if (it ! buckets_.end()) { it-second value; return; } if ((size_ 1) buckets_.size() * 0.75) { rehash(buckets_.size() * 2); } size_t idx hash(key) % buckets_.size(); buckets_[idx].push_back({key, value}); size_; } bool get(const std::string key, int out) const { size_t idx hash(key) % buckets_.size(); for (const auto kv : buckets_[idx]) { if (kv.first key) { out kv.second; return true; } } return false; } bool erase(const std::string key) { size_t idx hash(key) % buckets_.size(); auto bucket buckets_[idx]; auto it std::find_if(bucket.begin(), bucket.end(), [](const std::pairstd::string, int kv) { return kv.first key; }); if (it bucket.end()) { return false; } bucket.erase(it); --size_; return true; } size_t size() const { return size_; } private: size_t hash(const std::string key) const { // FNV-1a 哈希函数 size_t h 14695981039346656037ULL; for (unsigned char c : key) { h ^ c; h * 1099511628211ULL; } return h; } void rehash(size_t newBucketCount) { std::vectorstd::liststd::pairstd::string, int newBuckets(newBucketCount); for (auto bucket : buckets_) { for (auto kv : bucket) { size_t idx hash(kv.first) % newBuckets.size(); newBuckets[idx].push_back(std::move(kv)); } } buckets_.swap(newBuckets); } std::vectorstd::liststd::pairstd::string, int buckets_; size_t size_; };这段代码包含一个哈希表的核心要素哈希函数、桶数组、链表节点、装载因子判断、扩容rehash。查找时先算哈希再在桶的链表里做线性比较删除时找到节点并从链表移除扩容时重新创建桶数组把所有元素重新哈希一遍。5.3 使用示例与进一步优化用起来很简单int main() { SimpleHashMap map; map.put(apple, 3); map.put(banana, 5); int value; if (map.get(apple, value)) { std::cout apple - value std::endl; } map.erase(apple); if (!map.get(apple, value)) { std::cout apple not found std::endl; } std::cout size map.size() std::endl; return 0; }性能优化角度这个教学版本还有不少改进空间链表节点可以用intrusive的方式内嵌在对象里减少一次内存分配桶的数量可以设计成质数并配合更好的取模方式可以加入线程安全控制可以把值类型改成模板支持任意类型。每次扩容翻倍是有代价的如果提前知道数据规模可以在构造函数里指定初始桶数量尽量避免多次扩容。我自己的习惯是凡是能预估规模的哈希表一律提前初始化好容量这个习惯能省不少事。6. 实战踩坑哈希表问题排查手册6.1 典型故障字符串哈希碰撞导致接口变慢回到开头那个广告检索服务的故障。当时我用pprof抓到热点是哈希表查找第一反应是数据量太大了赶紧看bucket分布结果发现上万条记录集中在了极少数几个桶里几乎退化成了链表遍历。再往下查key的构造方式是用户ID 大版本号 小版本号 特征位拼接的长字符串这种字符串前缀高度一致默认哈希函数在处理这种有规律的key时出现了大量碰撞。排查手段其实很有套路先统计每个桶的长度分布然后换哈希函数验证。C的unordered_map提供了bucket_count和bucket_size接口可以很方便地检查桶负载情况size_t maxBucketSize 0; for (size_t i 0; i myMap.bucket_count(); i) { maxBucketSize std::max(maxBucketSize, myMap.bucket_size(i)); } std::cout bucket_count myMap.bucket_count() , max_bucket_size maxBucketSize std::endl;如果最大桶长度明显大于平均值很多基本可以实锤冲突问题。后来我引入了更好的哈希函数并且给key加了随机盐同一个桶里的元素数量从几千降到了个位数接口耗时直接回到5毫秒。这个惨痛经历让我从此养成了一个习惯凡是自定义对象做哈希表的key一定要重写质量过硬的hashCode。6.2 经典翻车Java 7 HashMap并发扩容死循环Java 7的HashMap在高并发下扩容会死循环这是个非常著名的坑。原因在于它的旧链表迁移采用头插法并发扩容时两个线程同时操作同一个桶可能把链表头节点指来指去最后形成环。一旦链表成环之后的get操作会在这个环里无限循环CPU直接打满服务彻底卡死。Java 8改成了尾插法并且引入红黑树这个死循环问题被削弱了但HashMap本身不是线程安全的并发写仍然会丢数据。所以我的建议非常明确并发场景不要用HashMap老老实实用ConcurrentHashMap或者给外部访问加锁。这个建议已经被说过无数次但每个季度总能看到有人在这个坑里翻车。6.3 哈希函数选型的安全红线哈希函数在安全场景里的选型有一个底线任何需要防碰撞、防伪造的场景都不能用MD5和SHA-1。MD5的碰撞攻击在现代硬件上已经非常廉价SHA-1也被证明了理论攻击可行性。比如SSL证书签名算法如果还用这两个弱哈希就会被CVE编号追踪并逐步淘汰。正确做法是使用SHA-256及以上强度的算法或者带密钥的HMAC。业务上的判断标准是这样如果哈希值只用来做数据完整性校验比如下载文件比对MD5能凑合如果哈希值参与安全判断比如签名、令牌、证书必须用高强度算法。每次写这种代码前我都会问自己一句这个哈希值被篡改了会有什么后果这么一想答案就清楚了。6.4 常见问题速查表现象可能原因排查手段解决方向查询慢、CPU占用高哈希冲突严重、装载因子过高统计桶长度分布换哈希函数、调低装载因子并发环境下死循环/数据丢失HashMap并发写加锁或换并发容器改用ConcurrentHashMap/加锁内存占用过高初始桶数量过大、元素分布稀疏查看桶数量和元素数预估容量、适当调高装载因子重启后key全部失效/数据错乱使用了不稳定的哈希值如对象内存地址检查哈希函数实现改用稳定的基于内容的哈希插入大量数据时卡顿频繁触发扩容rehash观察扩容次数提前指定初始容量、选用渐进式rehash方案排查哈希表问题我的经验是先看数据分布再看哈希实现最后看并发模型顺序不要反。很多看起来玄乎的性能问题最后都落在哈希分布不均和并发修改这两个根因上。把这张表贴在工位旁边碰到类似问题能少走不少弯路。最后再分享一个小技巧想深入理解哈希表不要只看文档动手改一版真实哈希表的装载因子、换一种哈希函数再用几百万条真实数据跑一遍对比测试很多知识会自己从数据里长出来。哈希表这个数据结构看起来简单但它串起来的是算法、内存、并发、安全一整条链路把这些想通写代码的感觉完全不一样。
先说个我踩过的坑。去年维护一个广告检索服务平时单次请求稳定在5毫秒某次版本上线之后P99耗时直接从8毫秒飙到800毫秒CPU也一直下不来。用pprof抓热点栈里全是哈希表查找和字符串分配业务代码明明只是查了一个map。排查到最后是新功能里用unordered_map存了一批拼接出来的长字符串当key这些key结构高度相似默认哈希函数对这类数据碰撞极其严重几万条记录全挤在了几个桶上查找复杂度从O(1)退化成了O(n)。哈希表是软件工程里出场率最高的数据结构之一平均O(1)的查找让它在缓存、索引、去重、路由分发里无处不在。但它不像表面看起来那么简单哈希函数怎么写、冲突怎么处理、装载因子怎么设、扩容怎么做每一项都直接影响线上表现。这篇文章不打算讲教科书理论我就按照自己实际用过、调过、踩过坑的顺序把哈希表彻底拆开聊透。不管你是刚接触数据结构的初学者还是写了几年业务想彻底搞懂哈希表的工程师应该都能从中捞出点东西。1. 哈希表到底是种什么结构1.1 从数组说起为什么我们能O(1)查找想要理解哈希表先想明白数组为什么快。数组里存了n个元素你访问arr[i]的时候CPU直接通过基地址加偏移量去内存里取值地址 基地址 i * 元素大小。这个计算是常数时间跟数组多大完全没有关系。所以数组的按下标随机访问是真正的O(1)。问题来了真实业务里我们手里的key往往是字符串、对象、ID而不是天然的整数下标。你手上有一个订单号ORD20240618001想查这个订单的数据你总不能把订单号直接当成数组下标用。哈希函数就是干这个事的它把任意类型的key映射成一个整数再对这个整数做一次取模或者位运算得到一个合法的数组下标。我用个生活化的例子帮大家理解。图书馆里几百万本书管理员如果给每本书一个唯一编号编号取模后落在某个书架上找书的时候先算书架号再去对应书架的小格子里翻这一步就省掉了几百万次比对。哈希表做的就是这样一件事通过设计良好的映射规则把大海捞针变成根据索引直接定位。1.2 哈希函数担任的角色哈希函数是哈希表里最重要的零件。它的职责是接收任意长度的key输出一个固定范围内的整数哈希值然后通过取模或者掩码操作定位到桶的下标。数学上它完成了从大空间到小空间的压缩映射。举个例子一个最简单的哈希函数h(key) key mod 16。假设key是整数17、33、49它们取模16的结果都是1都会落到桶1这就是冲突。哈希表内部就是用一个数组叫桶数组加上每个桶里挂的元素去组织数据桶下标由哈希函数决定。在真实工程里字符串哈希比整数哈希复杂得多。像Java的String.hashCode()用的是多项式滚动哈希C标准库的std::hash在不同实现里用的算法也不同Python的字符串哈希更是用了随机化种子每次启动都可能不一样。哈希函数设计得好不好直接影响哈希表的均不分布程度后面专门有一节讲这个这里先记住一个结论哈希函数是一种压缩映射压缩映射就必然引入冲突冲突是绕不开的。1.3 理想情况下的复杂度分析假设哈希函数足够好每个key都均匀随机地落在各个桶上桶的数量跟元素数量同阶那么每次插入、查找、删除只需要算一次哈希、定位到桶再在桶的局部做常数次比较平均时间复杂度就是O(1)。这里要强调平均两个字。因为有冲突存在最坏情况下所有key都映射到了同一个桶哈希表就会退化成一条链表查找复杂度变成O(n)。所以衡量一个哈希表的好坏很多时候不是在谈论它的平均表现而是在讨论它能不能避免最坏情况、以及在面对恶意输入时会不会崩掉。后面会详细讲工程上怎么通过冲突处理方案、装载因子、扩容策略和哈希函数设计尽量把最坏情况出现的概率压到极低。2. 哈希冲突绕不开的核心问题2.1 冲突为什么无法回避冲突的本质是鸽笼原理如果要把n个key放进m个桶里当n m时必然有至少一个桶装了多个key冲突无法避免。就算n m由于哈希函数是把无限输入空间映射到有限输出空间你也不能保证不会出现两个不同的key具有相同哈希值的情况。我见过不少刚入行的同学问为什么不用一个足够大的数组、让每个key都有唯一下标答案是做不到因为key空间无限内存有限。哈希表本质上是在用有限的空间存储无限的可能输入所以冲突根本不是没有和有的问题而是什么时候发生和发生了怎么处理的问题。两种主流方案链地址法和开放地址法就是两套完全不同的应对思路。2.2 链地址法拉链法链地址法的思路很直接桶数组里的每个元素不再直接存值而是存一个链表的头指针。发生冲突的元素就排在同一个桶对应的链表里。查找的时候先算哈希找到桶再在链表里线性扫描。我最早接触哈希表就是从拉链法入门的因为它逻辑最自然。C的std::unordered_map用的就是拉链法Java 8之后的HashMap也采用了链表红黑树的变体同一个桶里的元素数量小于等于8时用链表超过8且桶数组长度大于等于64时就转成红黑树把最坏情况从O(n)降到O(log n)。拉链法的优点很明显实现简单删除方便查找时只需要遍历很少几个节点插入的时候不需要处理下一个空位在哪的问题。代价是每个节点要额外存储指针内存开销比较大而且链表节点在内存里往往不是连续的访问时可能产生缓存不命中。不过对绝大多数业务场景来说这个开销可以接受。2.3 开放地址法开放地址法走了另一条路不额外挂链表所有元素都存在桶数组本身里。插入时发现位置被占了就按照某种探测序列去找下一个空位置。探测的常见方式有三种。线性探测冲突的时候依次往后找hash(key) 1、hash(key) 2……直到找到空位。优点是实现简单、内存连续、缓存非常友好缺点也很明显连续占用的桶会形成聚集区一旦聚集后续插入会像堵车一样越堵越长。二次探测按平方序列探测hash(key) 1²、hash(key) 2²……能缓解线性探测的聚集问题但可能出现探测不到空槽的情况。双重哈希用第二个哈希函数计算探测步长理论分布最好但计算量翻倍。开放地址法还有个特殊问题删除。如果直接删掉某个桶里的元素会导致探测链断裂后面的元素可能就找不到了。所以工程实现一般用墓碑标记tombstone删除时做一个标记查询时跳过墓碑继续探测插入时允许覆盖墓碑。Python的字典用的就是开放地址法实际是改进后的紧凑稀疏表方案它在内存利用率和缓存友好性上做得很极致。2.4 两种方案怎么选来一张对比表方便大家根据场景做决策对比维度链地址法开放地址法实现复杂度较低稍高删除需要墓碑机制内存占用节点需要额外指针开销大更紧凑内存利用率高缓存友好性链表节点分散访问不连续桶数组连续缓存命中率高最坏情况O(n)可优化为红黑树O(log n)探测链可能很长扩容代价重建所有桶重新分配链表节点重新分配数组并rehash代表实现C unordered_map、Java HashMapPython dict、Redis hash我的个人经验是如果是通用场景、需要频繁删除、代码要便于维护选拉链法如果对内存占用敏感比如要存几千万个键值对或者对缓存局部性要求极高就认真考虑开放地址法。Redis的字典设计得很聪明普通场景用拉链法但它的对象编码里也有紧凑的ziplist和listpack方案本质上都是在不同数据量下做取舍。3. 装载因子、扩容与哈希函数质量3.1 装载因子为什么偏偏是0.75装载因子load factor的定义是当前元素数量 / 桶数组长度。它直接决定了哈希表的拥挤程度。装载因子越高空间利用率越高但冲突概率也越大查询退化风险越高装载因子越低冲突少、性能好但内存浪费严重。这是一个典型的空间换时间问题。Java的HashMap把默认装载因子设在0.75这个数字不是拍脑袋定的它是在时间成本和空间成本之间的经典权衡。按照泊松分布模型在随机哈希函数下当装载因子为0.75时单个桶里元素数量超过8的概率极低大概亿分之几所以Java 8选择把树化阈值定在8既避免链表过长又不会频繁触发红黑树转换。C的std::unordered_map默认max_load_factor是1.0Python的dict装载因子大约是2/3各有各的取舍逻辑。工程上我建议大家不要乱改这个值。有些同学为了省内存把装载因子调到0.9以上结果遇到一次哈希不均匀线上查询直接爆炸。如果确实内存紧张不如换用更紧凑的数值类型或者换数据结构的存储方式而不是拿哈希表的性能去赌。3.2 扩容机制为什么rehash不是复制那么简单当元素数量超过装载因子上限时哈希表就要扩容。最常见的策略是新桶数量 旧桶数量 × 2或者取大于这个数的质数然后把所有已存在的元素重新计算哈希值、重新插入到新数组里。注意是重新计算位置不是简单地把旧数组元素复制到新数组对应位置。因为桶数量变了取模的结果就全变了。扩容是一个很重的操作尤其在存了几百万个元素时rehash过程会瞬间吃掉大量CPU和内存。为了应对这个问题Redis的字典实现了渐进式rehash扩容时不一次性搬完而是在每次增删改查时顺手搬一小部分把耗时的操作分摊到多次访问里。这种做法在需要保证服务稳定性的场景里非常实用我个人在自研缓存组件时也借鉴过这个思路。3.3 哈希函数设计的三个层次哈希函数的质量可以从三个层次来看。第一层是均匀性。好的哈希函数应该让不同key的输出尽可能均匀分布。一个坏例子是把字符串所有字符的ASCII码加起来如果key都是abc、bca这种同字母不同顺序的字符串就全撞一起了。工程常用的字符串哈希有FNV-1a、MurmurHash、CityHash、xxHash等它们都经过大量语料测试分布性有保障。第二层是速度。哈希函数是每次查询都要执行的性能至关重要。FNV-1a实现简单、极快适合短字符串和嵌入式场景MurmurHash质量好、速度快适合通用场景SipHash则在安全和速度之间取得平衡被很多语言用作哈希表的默认哈希函数。选型时要考虑你的实际数据特征没有银弹。第三层是安全性。如果key是用户可控的恶意攻击者可以构造大量碰撞的key让哈希表整个退化成链表这就是Hash DoS攻击。防御手段包括给哈希函数加随机种子、使用SipHash这类带密钥的哈希算法、限制哈希表最大长度。我在做网关鉴权系统时就吃过这个亏后来把所有对外接口的map全部换成了带随机种子的哈希函数。3.4 主流语言哈希表实现差异对比实现冲突方案装载因子/扩容策略备注Java HashMap链表红黑树默认0.75扩容翻倍非线程安全Java ConcurrentHashMap链表红黑树分段锁/CAS优化并发高并发场景首选C std::unordered_map拉链法max_load_factor默认1.0标准库实现性能依赖编译期Python dict开放地址法约2/3扩容约翻倍3.6后保持插入顺序Redis dict拉链法1.0触发扩容渐进式rehash支持缩容我工作里最常用的是Java和C的哈希表这两者设计哲学完全不同。Java的HashMap引入了红黑树来抵抗极端碰撞而C std::unordered_map完全依赖哈希函数的质量所以用C时反而要更小心。Python的dict在小数据量下性能非常惊艳因为它的实现是专门为Python对象优化的。4. 哈希表在真实业务系统里的应用4.1 缓存系统Redis和内存缓存几乎所有缓存系统底层都站着一个哈希表。Redis本身就是一个全局字典每个key通过哈希定位到对应的存储位置所有数据结构都构建在这张大的哈希表之上。同时Redis的哈希对象在元素少时用ziplist编码元素多了转成hashtable编码本质就是在内存效率和访问效率之间切换。我自己做本地缓存时也习惯用哈希表做核心结构key是缓存键value是带过期时间的包装对象。配合LRU淘汰策略时经典做法是哈希表双向链表哈希表负责O(1)定位节点双向链表负责维护访问顺序。这个就是随手写过的LRU Cache也是面试高频题强烈建议每个人都亲手实现一遍。4.2 数据库索引与布隆过滤器哈希表在数据库领域也有一席之地。MySQL的Memory引擎支持哈希索引适合等值查询InnoDB的自适应哈希索引会在热点数据上自动建哈希索引加速主键查找和重复查询。注意哈希索引不支持范围查询因为哈希值本身是无序的这跟B树正好互补。布隆过滤器也是一个很有意思的哈希应用。它用多个哈希函数把元素映射到一个位数组的多个位上判断一个元素肯定不在集合里非常快判断可能存在会有一定的误判率。我做过一个黑名单服务几千万条黑名单记录如果全放Redis key会占用大量内存用布隆过滤器扛在最前面内存占用直接降了两个数量级。4.3 去重、计数与一致性哈希去重和计数是哈希表的传统主场。业务里最常见的需求是给一批用户ID去重、统计每个商品加购数量、记录某台机器的请求计数。哈希表天然支持按key聚合的思维任何需要根据某个标识快速找到对应聚合数据的场景第一反应都应该是哈希表。购物车场景里商品ID到购买数量的映射就是一个典型的HashMap。分布式场景的一致性哈希也值得提。为什么不用普通哈希取模因为节点增减时取模的基数变了绝大部分key都会迁移对缓存系统来说是灾难。一致性哈希把哈希值组织成一个环每个节点负责一段区间节点增减只影响相邻的小范围数据再通过虚拟节点技术解决节点哈希不均匀的问题。这套思想在很多分布式中间件里都有体现。4.4 算法面试中的哈希表套路算法题里哈希表几乎是万能辅助。两数之和用哈希表存值-下标一趟遍历就能解决最长无重复字符子串用哈希表记录每个字符的出现位置配合滑动窗口移动左指针设计LRU结构要靠哈希表定位节点、双向链表调整顺序求数组中出现次数超过一半的元素哈希计数后一次扫描就能找到。准备面试的时候我建议大家把所有哈希表的高频题按场景归类计数类、索引类、去重类、缓存设计类。每类吃透一两道典型题比盲目刷二十道效果要好得多。5. 从零手写一个迷你哈希表C5.1 为什么选拉链法实现为了让大家真正理解哈希表内部原理我写了一个教学版的迷你哈希表用C实现选择拉链法。原因有三实现清晰每个桶就是一条链表指针指向关系一目了然不用处理开放地址法的墓碑删除问题代码更聚焦跟std::unordered_map的结构保持一致方便对照学习。哈希函数我用了FNV-1a它的强度在简单哈希函数里属于第一梯队而且代码只有几行非常适合教学演示。注意这里仅用于演示生产环境建议直接用std::unordered_map或者经过充分测试的第三方哈希表。5.2 核心实现代码#include vector #include list #include string #include utility #include algorithm #include iostream class SimpleHashMap { public: explicit SimpleHashMap(size_t bucketCount 16) : buckets_(bucketCount), size_(0) {} void put(const std::string key, int value) { auto it find(key); if (it ! buckets_.end()) { it-second value; return; } if ((size_ 1) buckets_.size() * 0.75) { rehash(buckets_.size() * 2); } size_t idx hash(key) % buckets_.size(); buckets_[idx].push_back({key, value}); size_; } bool get(const std::string key, int out) const { size_t idx hash(key) % buckets_.size(); for (const auto kv : buckets_[idx]) { if (kv.first key) { out kv.second; return true; } } return false; } bool erase(const std::string key) { size_t idx hash(key) % buckets_.size(); auto bucket buckets_[idx]; auto it std::find_if(bucket.begin(), bucket.end(), [](const std::pairstd::string, int kv) { return kv.first key; }); if (it bucket.end()) { return false; } bucket.erase(it); --size_; return true; } size_t size() const { return size_; } private: size_t hash(const std::string key) const { // FNV-1a 哈希函数 size_t h 14695981039346656037ULL; for (unsigned char c : key) { h ^ c; h * 1099511628211ULL; } return h; } void rehash(size_t newBucketCount) { std::vectorstd::liststd::pairstd::string, int newBuckets(newBucketCount); for (auto bucket : buckets_) { for (auto kv : bucket) { size_t idx hash(kv.first) % newBuckets.size(); newBuckets[idx].push_back(std::move(kv)); } } buckets_.swap(newBuckets); } std::vectorstd::liststd::pairstd::string, int buckets_; size_t size_; };这段代码包含一个哈希表的核心要素哈希函数、桶数组、链表节点、装载因子判断、扩容rehash。查找时先算哈希再在桶的链表里做线性比较删除时找到节点并从链表移除扩容时重新创建桶数组把所有元素重新哈希一遍。5.3 使用示例与进一步优化用起来很简单int main() { SimpleHashMap map; map.put(apple, 3); map.put(banana, 5); int value; if (map.get(apple, value)) { std::cout apple - value std::endl; } map.erase(apple); if (!map.get(apple, value)) { std::cout apple not found std::endl; } std::cout size map.size() std::endl; return 0; }性能优化角度这个教学版本还有不少改进空间链表节点可以用intrusive的方式内嵌在对象里减少一次内存分配桶的数量可以设计成质数并配合更好的取模方式可以加入线程安全控制可以把值类型改成模板支持任意类型。每次扩容翻倍是有代价的如果提前知道数据规模可以在构造函数里指定初始桶数量尽量避免多次扩容。我自己的习惯是凡是能预估规模的哈希表一律提前初始化好容量这个习惯能省不少事。6. 实战踩坑哈希表问题排查手册6.1 典型故障字符串哈希碰撞导致接口变慢回到开头那个广告检索服务的故障。当时我用pprof抓到热点是哈希表查找第一反应是数据量太大了赶紧看bucket分布结果发现上万条记录集中在了极少数几个桶里几乎退化成了链表遍历。再往下查key的构造方式是用户ID 大版本号 小版本号 特征位拼接的长字符串这种字符串前缀高度一致默认哈希函数在处理这种有规律的key时出现了大量碰撞。排查手段其实很有套路先统计每个桶的长度分布然后换哈希函数验证。C的unordered_map提供了bucket_count和bucket_size接口可以很方便地检查桶负载情况size_t maxBucketSize 0; for (size_t i 0; i myMap.bucket_count(); i) { maxBucketSize std::max(maxBucketSize, myMap.bucket_size(i)); } std::cout bucket_count myMap.bucket_count() , max_bucket_size maxBucketSize std::endl;如果最大桶长度明显大于平均值很多基本可以实锤冲突问题。后来我引入了更好的哈希函数并且给key加了随机盐同一个桶里的元素数量从几千降到了个位数接口耗时直接回到5毫秒。这个惨痛经历让我从此养成了一个习惯凡是自定义对象做哈希表的key一定要重写质量过硬的hashCode。6.2 经典翻车Java 7 HashMap并发扩容死循环Java 7的HashMap在高并发下扩容会死循环这是个非常著名的坑。原因在于它的旧链表迁移采用头插法并发扩容时两个线程同时操作同一个桶可能把链表头节点指来指去最后形成环。一旦链表成环之后的get操作会在这个环里无限循环CPU直接打满服务彻底卡死。Java 8改成了尾插法并且引入红黑树这个死循环问题被削弱了但HashMap本身不是线程安全的并发写仍然会丢数据。所以我的建议非常明确并发场景不要用HashMap老老实实用ConcurrentHashMap或者给外部访问加锁。这个建议已经被说过无数次但每个季度总能看到有人在这个坑里翻车。6.3 哈希函数选型的安全红线哈希函数在安全场景里的选型有一个底线任何需要防碰撞、防伪造的场景都不能用MD5和SHA-1。MD5的碰撞攻击在现代硬件上已经非常廉价SHA-1也被证明了理论攻击可行性。比如SSL证书签名算法如果还用这两个弱哈希就会被CVE编号追踪并逐步淘汰。正确做法是使用SHA-256及以上强度的算法或者带密钥的HMAC。业务上的判断标准是这样如果哈希值只用来做数据完整性校验比如下载文件比对MD5能凑合如果哈希值参与安全判断比如签名、令牌、证书必须用高强度算法。每次写这种代码前我都会问自己一句这个哈希值被篡改了会有什么后果这么一想答案就清楚了。6.4 常见问题速查表现象可能原因排查手段解决方向查询慢、CPU占用高哈希冲突严重、装载因子过高统计桶长度分布换哈希函数、调低装载因子并发环境下死循环/数据丢失HashMap并发写加锁或换并发容器改用ConcurrentHashMap/加锁内存占用过高初始桶数量过大、元素分布稀疏查看桶数量和元素数预估容量、适当调高装载因子重启后key全部失效/数据错乱使用了不稳定的哈希值如对象内存地址检查哈希函数实现改用稳定的基于内容的哈希插入大量数据时卡顿频繁触发扩容rehash观察扩容次数提前指定初始容量、选用渐进式rehash方案排查哈希表问题我的经验是先看数据分布再看哈希实现最后看并发模型顺序不要反。很多看起来玄乎的性能问题最后都落在哈希分布不均和并发修改这两个根因上。把这张表贴在工位旁边碰到类似问题能少走不少弯路。最后再分享一个小技巧想深入理解哈希表不要只看文档动手改一版真实哈希表的装载因子、换一种哈希函数再用几百万条真实数据跑一遍对比测试很多知识会自己从数据里长出来。哈希表这个数据结构看起来简单但它串起来的是算法、内存、并发、安全一整条链路把这些想通写代码的感觉完全不一样。
