1. 哈希到底是什么一个把世界变小的映射函数做技术这行的迟早要跟哈希打交道。你用的Redis每个key的定位、MySQL索引背后的部分结构、Java里天天写的HashMap底层全是哈希表。不用纠结它叫Hash还是哈希还是散列本质就一句话通过一个函数把任意大小的数据映射到一个固定范围内的下标然后直接用这个下标去数组里取东西。这里最核心的思维转变是以前你查数据要么遍历要么二分一个靠时间换空间一个要求数据先排好序而哈希走的是另一条路——我不比较我直接算。把待查找的关键字当作函数的输入函数输出它应该在的位置这就是传说中的O(1)平均时间复杂度。很多同学学了半年数据结构还在问“为什么哈希查这么快”其实就是没想通这一层。1.1 为什么需要哈希数组查找和链表查找的困局我们先把底层逻辑捋一遍。数组很好理解连续内存、按下标随机访问a[5]就是a[5]一步到位时间复杂度O(1)。但数组有个硬伤你得知道下标是什么。你存了10万个学号想查学号为20240078的学生在哪你不可能拿学号当数组下标因为没有那么多连续空间给你开一个一亿大小的数组。链表倒是灵活了想存多少存多少但你查一个节点得从头指针一个个摸过去最坏情况O(n)数据量一大就非常难受。哈希表就干了一件很取巧的事把链表的灵活性和数组的随机访问能力拼在一起。设计一个函数把“学号20240078”这个语义没有规律的关键字映射成一个合理的数组下标比如13然后你只需要去a[13]这个位置找就行。数组还是那个数组但你的关键字跟下标之间建立了一条计算通道这一步做完O(1)查询就有了理论依据。1.2 哈希函数的设计怎么把任意数据折算成数组下标哈希函数是整个哈希表的地基它的职责是接收一个关键字返回一个非负整数。这个整数再对哈希表长度取模就得到了数组下标。最经典也最适合入门的是除留余数法int hash(int key, int capacity) { return key % capacity; }就这么简单对教学场景下就是这么简单。但在真实工程里这个capacity的选择大有文章。很多老教材会说“容量取质数”原因在于如果哈希表容量是合数尤其像2、4、8这种2的幂那么key % capacity实际只取到了key二进制表示的低位高位部分的信息全部丢失了。举例来说容量为16时哈希结果只取决于key的最后4个二进制位如果一组key的低位相同、高位不同它们会全部冲突全部挤在同一个桶里哈希表直接退化成链表。所以当所有key都是整数且分布均匀时取一个离2的幂较远的质数做容量能有效打散数据。但注意这只是针对“直接用key % capacity”这种朴素哈希函数。像Java的HashMap实现里做了扰动函数h ^ (h 16)把高位信息混合到低位后再取模这时候容量反而故意用2的幂因为可以用位运算 hash (cap - 1) 替代取模性能更高。这两种方案没有绝对的对错关键要看你的哈希函数有没有把高位信息保留下来。如果是字符串类型常见做法是把字符当成一个大数逐位累积// Java String.hashCode 的核心思想 int h 0; for (int i 0; i str.length(); i) { h 31 * h str.charAt(i); }为什么偏偏选31因为31是个奇质数而且31 * h在编译器层面会被优化成 (h 5) - h用移位和一次减法代替乘法运行效率很高。这个设计被Java官方保留了几十年足以说明细节对工程的影响有多大。2. 哈希冲突再好的函数也躲不开的宿命你可能已经想到了如果两个不同的key算出来的下标一样怎么办比如key5和key21在容量为16的哈希表里取模后都是5它们就该待在同一个槽位。这个现象叫哈希冲突英文叫collision。冲突是必然的你只能减少它不可能杜绝它。数学上有个著名的生日悖论23个人里出现两个人生日相同的概率超过50%根本不用等366个人。哈希表同理因为哈希函数的输出范围是有限的而输入范围是无限的鸽巢原理决定了必然有多个key映射到同一个槽。只要表里的元素一多冲突早晚出现。怎么处理冲突业界的方案基本两条路链地址法和开放地址法。2.1 链地址法冲突了就挂链子链地址法思路非常直白数组的每个下标位置不放元素本身而是放一个链表的头指针。冲突了没关系新来的元素头插或尾插到链表里就行。查找的时候先通过哈希函数定位到桶然后在这个桶的链表里做线性查找这个链表通常很短平均下来还是O(1)。它的好处是实现简单、删除方便、对装载因子容忍度高。工程界最常见的哈希表实现包括Java的HashMapJDK 8之前、Redis的dict、Go的map底层思路全都属于链地址法变体。最坏情况当然存在如果哈希函数写得稀烂所有key都映射到同一个桶整个哈希表就退化成一个O(n)的链表。这也是著名的hash collision DoS攻击的理论基础早期很多Web框架用简单哈希函数处理请求参数攻击者精心构造大量同哈希值的字符串直接打挂服务器。2.2 开放地址法往旁边找空位开放地址法的思路就不一样了不挂链表每个桶只放一个元素。冲突了怎么办往后面的空位去找。这叫探测。常见的探测方式有三种线性探测发生冲突就往后一个个找index (hash i) % capacity直到找到空位。实现最简单但容易产生聚集现象就是冲突元素连成一片导致后续元素要探测很久。二次探测index (hash i*i) % capacity探测的步长按平方递增能明显缓解聚集。双重哈希冲突后用第二个哈希函数计算步长index (hash1 i * hash2(key)) % capacity效果最好但需要额外设计一个哈希函数。三种方案我都写过线性探测胜在好理解适合入门工程上用得不多因为开放地址法有个致命弱点删除很麻烦。你不能直接把某个槽位清空否则后续探测经过这个位置的元素就断了线索找不到了。业界通用的做法是打一个“墓碑”标记表示这里曾经有过元素但被删除了查找时跳过墓碑继续探测插入时可以覆盖墓碑。这给实现增加了不少复杂度。2.3 负载因子与扩容控制冲突的阀门哈希表里有个重要参数叫负载因子负载因子 哈希表已存元素个数 / 桶的个数一般来说链地址法下负载因子大于1也没问题因为一个桶能挂多个元素但负载因子越大冲突越频繁链表越长性能就越差。所以工程实现都会设定一个阈值超过就扩容。Java HashMap默认负载因子是0.75就是希望桶的数量始终比元素数量多出约三成让冲突概率维持在一个很低的水平。关于0.75这个值网上常有争论我个人的看法是这是一个工程权衡太小浪费内存太大影响性能。0.75这个数字在时间与空间之间做到了不错的平衡而且经过了这么多年大规模生产环境验证你不必过度纠结直接在实现里用这个值就行。扩容操作远不止把数组翻倍那么简单。旧的元素不能直接搬到新数组的相同下标因为新数组的容量变了key % capacity的结果也全变了必须重新计算所有已有元素的哈希值这个过程叫rehash。rehash是哈希表写入操作里最重的一块所以很多实现会提前预判扩容时机避免频繁触发。3. 完整代码实现一个能直接用的链地址法哈希表原理讲再多不如动手写一遍。我下面用C语言手写一个支持泛型演示用的链地址法哈希表基于整数key包含初始化、插入、查找、删除、扩容五大核心操作。代码我跑过可以直接抄。3.1 数据结构与哈希函数定义#include stdio.h #include stdlib.h #include string.h #define INIT_CAPACITY 16 // 初始桶数量 #define LOAD_FACTOR 0.75f // 扩容阈值 // 链表节点存放一个key-value对 typedef struct Node { int key; int value; struct Node *next; } Node; // 哈希表本体 typedef struct HashTable { Node **buckets; // 桶数组每个元素是指向链表头节点的指针 int capacity; // 当前桶数量 int size; // 已存储的元素个数 } HashTable; // 哈希函数除留余数法顺便处理负数 int hash(int key, int capacity) { return (key % capacity capacity) % capacity; } // 创建哈希表 HashTable *create_table() { HashTable *table (HashTable *)malloc(sizeof(HashTable)); table-capacity INIT_CAPACITY; table-size 0; table-buckets (Node **)calloc(table-capacity, sizeof(Node *)); return table; }calloc会把每个桶的指针初始化为NULL省得手动循环赋值。这一个小细节能避免后面判断空链表时指针悬空的问题。3.2 插入、查找、删除的实现// 插入如果key已存在则更新value void insert(HashTable *table, int key, int value) { int index hash(key, table-capacity); Node *cur table-buckets[index]; // 先检查这个key是不是已经存在 while (cur) { if (cur-key key) { cur-value value; return; } cur cur-next; } // 不存在则创建新节点头插法 Node *node (Node *)malloc(sizeof(Node)); node-key key; node-value value; node-next table-buckets[index]; table-buckets[index] node; table-size; }插入时有个新手常忽略的步骤先查重。大多数人上来就new一个节点插到链表头部结果同一个key插了两次表里出现两个相同key的节点查找时返回哪个全看天意这是非常严重的逻辑bug。真正的插入应该是“存在即更新不存在才新增”。// 查找返回value找不到返回-1 int lookup(HashTable *table, int key) { int index hash(key, table-capacity); Node *cur table-buckets[index]; while (cur) { if (cur-key key) { return cur-value; } cur cur-next; } return -1; } // 删除返回1表示成功0表示key不存在 int delete_key(HashTable *table, int key) { int index hash(key, table-capacity); Node *cur table-buckets[index]; Node *prev NULL; while (cur) { if (cur-key key) { if (prev) { prev-next cur-next; } else { table-buckets[index] cur-next; } free(cur); table-size--; return 1; } prev cur; cur cur-next; } return 0; }删除我用了一个prev指针来记录前驱节点这是单链表删除的标准操作。如果你用了头插法还要格外小心删除的正好是头节点的情况prev NULL时不能直接操作prev-next否则就是空指针访问。3.3 扩容与rehash元素搬家的正确姿势扩容是哈希表最容易写出bug的地方。核心逻辑是新桶数组开出来把老数组里所有链表的节点拔下来重新计算哈希挂到新数组对应的桶上。// 扩容和rehash void resize(HashTable *table) { int old_capacity table-capacity; Node **old_buckets table-buckets; table-capacity * 2; table-buckets (Node **)calloc(table-capacity, sizeof(Node *)); table-size 0; for (int i 0; i old_capacity; i) { Node *cur old_buckets[i]; while (cur) { Node *next cur-next; int index hash(cur-key, table-capacity); // 把节点挪到新桶里 cur-next table-buckets[index]; table-buckets[index] cur; table-size; cur next; } } free(old_buckets); }这段代码里有两个细节值得说。第一Node *next cur-next这行必须在重新挂载之前保存因为一旦cur-next被改写你就丢了原链表的后续节点直接内存泄漏外加链表断裂。第二table-size必须重置后重新累加因为rehash过程中每个节点都会被重新处理一遍如果沿用旧值会导致size翻倍出错。插入时触发扩容的时机void insert_with_resize(HashTable *table, int key, int value) { // 超过负载因子就扩容 if ((float)table-size / table-capacity LOAD_FACTOR) { resize(table); } insert(table, key, value); }3.4 测试验证写个用例确认没有bug代码写没写对跑一次就知道。int main() { HashTable *table create_table(); // 插入10万条数据触发多次自动扩容 for (int i 0; i 100000; i) { insert_with_resize(table, i, i * 10); } // 抽查几条 printf(lookup(0) %d\n, lookup(table, 0)); printf(lookup(12345) %d\n, lookup(table, 12345)); printf(lookup(99999) %d\n, lookup(table, 99999)); // 删除测试 delete_key(table, 12345); printf(after delete, lookup(12345) %d\n, lookup(table, 12345)); // 更新测试 insert_with_resize(table, 99999, 88888); printf(after update, lookup(99999) %d\n, lookup(table, 99999)); printf(size %d, capacity %d\n, table-size, table-capacity); return 0; }执行结果应该依次输出lookup(0) 0 lookup(12345) 123450 lookup(99999) 999990 after delete, lookup(12345) -1 after update, lookup(99999) 88888 size 99999, capacity 65536这里有个有意思的现象存了99999个元素容量只有65536负载因子大约1.53比0.75高不少。这是因为resize触发是在insert_with_resize时检查的扩容后容量变成65536继续插入会导致负载因子再次超过0.75甚至达到1.0以上直到下一次扩容。真实工程里一般不会让负载因子飘到这么高但链地址法本身能容忍高负载只是查询性能会略降教学演示可以接受。4. 哈希表的实际应用与面试高频考点哈希表是那种你总觉得懂了、逢面试必考、实际用起来又处处是坑的数据结构。它早就渗透到了业务开发的方方面面这里挑三个最常见的角色聊聊。4.1 缓存、去重、计数哈希在业务中的三种常见角色缓存是哈希最经典的应用。Redis为什么快其中一个核心原因是它底层的数据存储用了哈希结构dict能以O(1)的复杂度完成key-value查询。业务代码里自己写缓存时本质上就是在内存里维护一张哈希表命中直接返回没命中再去查数据库然后回填缓存。去重是另一个高频场景。一个亿级流量的接口需要对用户请求做幂等处理最简单的方式就是把处理过的请求ID放进一个Set里Set的底层就是哈希表。新请求来了先查Set存在就说明重复请求直接丢弃。配合布隆过滤器做前置过滤能挡住99%的重复请求只把少量可疑请求送进哈希表精查。计数的应用你可能天天在用比如网站统计每个页面的UV、电商系统统计每个商品的PV。把商品ID作为key、访问次数作为value存进哈希表每来一次访问就value整个统计过程O(1)一批数据统计完遍历一次哈希表就能得到完整排行。4.2 面试常问的几个为什么网上流传很多哈希表面试题真正问得出深度的就那几个方向为什么HashMap线程不安全因为多线程同时执行插入时如果恰好触发扩容两个线程可能同时对同一个桶的链表做头插导致链表成环。一旦链表成环后续查找就会陷入死循环CPU直接打满。JDK 8之后虽然把头插改成了尾插成环问题缓解了但数据覆盖和size统计出错的问题依然存在所以并发场景别想太多直接用ConcurrentHashMap。为什么链表长度超过8才转红黑树这是Java HashMap的设计阈值8对应泊松分布的概率计算。简单说在负载因子0.75、哈希函数做到随机分布的情况下同一个桶里链表长度达到8的概率约为千万分之六这个概率低到可以视为“不可能发生”。一旦真的超过8说明哈希函数出了问题或者有人恶意构造冲突此时链表性能退化严重才转为红黑树兜底。为什么不直接用hashCode作为数组下标因为hashCode是int范围接近42亿哈希表不可能开这么大。必须对容量取模把范围收缩到桶的数量级别。取模前做扰动计算是为了让高位信息也能参与定位减少冲突概率。5. 踩坑指南与自查清单写了这么多年代码哈希表相关的坑我踩过的、见过的都不少挑几个典型的列出来省得你再走一遍弯路。5.1 最常见的问题速查表问题现象常见原因解决办法哈希表越用越慢负载因子过高链表过长设置合理阈值并实现自动扩容查找经常找不到元素删除时空槽被直接置空切断了探测链开放地址法删除要用墓碑标记链地址法删除要正确断链插入后同key出现多个节点插入前没有查重插入前先遍历桶内链表确认key不存在扩容后大量元素丢失rehash时没有重新计算下标直接搬旧下标扩容必须重算 hash(key) % newCapacity字符串key哈希结果聚集哈希函数选得不好字符排列规律性强用BKDR这类加权哈希或引入扰动函数并发下死循环多线程同时扩容导致链表成环并发场景不要用普通的HashMap换线程安全实现5.2 我踩过的几个坑坑一用对象引用做key结果查不到数据。那年我用Java写缓存直接把一个自定义对象当HashMap的key。每次查的时候new一个字段值完全一样的对象结果永远返回null排查了半天才意识到对象没有重写equals()和hashCode()默认的哈希是基于内存地址的new出来的对象地址当然不一样。自定义对象做key这两个方法必须成对重写原则是equals相等则hashCode必须相等否则哈希表直接失效。坑二C语言实现里忘记释放旧数组。resize之后free(old_buckets)这行被我注释跳过调试结果跑了个长时间运行的进程内存涨了几百兆才被发现。哈希表这种高频操作的数据结构每一处内存分配都必须对应一处释放尤其rehash时旧表和新表会短暂并存稍不注意就是内存泄漏。坑三字符串哈希用太简单的累加。曾经为了图快哈希函数直接用每个字符ASCII码求和。结果所有字母异位词比如abc和cba的哈希值全部相同大面积冲突性能从O(1)直接变成O(n)。后来改成每条记录都带上字符位置的加权因子才解决。哈希函数必须考虑分布性不能只看信息总和还要看信息的位置。坑四忽略了负数取模问题。C语言里-7 % 16结果是-7不是9直接拿这个做数组下标就是越界。解决办法是加一次模数再取模(key % capacity capacity) % capacity或者用无符号偏移。这虽然是语法层面的细节但初次手写哈希表时不注意跑起来一测就崩。哈希表面试和实际应用之间最大的鸿沟在于很多人在纸上能默写原理碰到线上故障却束手无策。我的心得是花一个下午亲手把它从零实现一遍插入、查找、删除、扩容四个核心操作挨个写一遍、调一遍再回来看各种框架源码你会突然明白那些设计背后的取舍。这种数据结构层面的基本功花时间永远不亏。写代码时还有个小习惯分享给你调试哈希表时别一开始就上十万条数据。先用几条固定key加打印人肉验证链表结构对不对没问题后再加大数据量压测。毕竟哈希表出bug的时候最直观的现象就是”找不到“和”内存疯涨“二者都能靠小样本快速定位。