你有没有想过手机通讯录里存了几千个联系人为什么你输入一个名字屏幕几乎不卡顿就能把对应的号码翻出来逛电商平台的时候购物车里的商品 ID、库存、价格为什么能瞬间同时返回这背后靠的不是什么“魔法数据库”而是一个非常基础又极其重要的数据结构——哈希表也就是 Hash Table。今天我打算围绕“数据结构——哈希(Hash)和代码实现(详解)”这个主题把哈希表的原理、冲突处理、手写代码、应用场景以及面试常见坑一次性讲透。这篇文章适合几类人看正在复习考研数据结构的学生期末突击哈希章节的同学刷 LeetCode 时总被“哈希表题”卡住的选手以及那些“会用 HashMap 但说不清内部原理”的工程师。我会尽量用大白话把原理讲明白同时给出可以直接复现的 C 语言实现代码不依赖任何第三方库你复制到编译器里就能跑。相信看完之后你对哈希的理解会比“会用 API”再深一两个层次。1. 哈希到底是什么从数组到散列的跳跃1.1 为什么数组查找会“慢”先从一个最基础的问题说起。假设我们要存班级里 50 个学生的学号和姓名最朴素的做法就是一个结构体数组每次查找某个学号时从头到尾遍历一遍。数据量小的时候无所谓但如果是 100 万条记录平均要比较 50 万次才能找到一个学号这个开销在真实系统里是不可接受的。数组最好的能力其实是“按下标访问”只要我知道下标 i就能在 O(1) 时间内拿到 arr[i]。问题在于业务里的 key 通常不是连续整数而是“学号 20240001”“用户名 zhangsan”“手机号 138xxxx”这种乱七八糟的东西。哈希的核心思路就是这个我们能不能设计一个函数把任意形式的 key 映射成一个数组下标然后继续用数组“按下标访问”的绝活这个函数就叫哈希函数也叫散列函数。它做的事情可以用一句话概括把不规则的 key 规整成规则的下标。下标有了存取就回到了数组的老路子上快得离谱。这就是为什么数据结构课里哈希表总被称作“以空间换时间”的典型代表。1.2 哈希表的基本结构和术语哈希表底层的存储结构就是一个连续数组数组的每个槽位叫做“桶”Bucket。当你要插入一个键值对 (key, value) 时先调用哈希函数 h(key) 得到一个整数再用这个整数对桶的数量取模得到最终的存储下标。这样 key 和存储位置之间就建立起了一种“函数关系”查找时不需要遍历直接重算一次下标就能定位。这里引出了几个必须清楚的术语哈希函数把 key 转换成整数的函数、哈希值函数算出来的结果、哈希表存储数据的桶数组、冲突两个不同的 key 算出了同一个下标、负载因子当前元素个数 / 桶总数反映哈希表的“拥挤程度”。负载因子这个概念后面反复要用先记住一个直观结论负载因子越大冲突概率越高性能越差负载因子越小浪费的空间越多。工程上一般控制在 0.5 到 0.75 之间这也是很多语言标准库的默认阈值。1.3 一次哈希操作的完整过程我用一个例子带你走完整流程。假设当前哈希表有 8 个桶哈希函数是 h(key) key % 8。现在要插入一个键值对 (20240001, 张三)。第一步计算哈希值20240001 % 8。算一下20240001 对 8 取模结果是 1那么这个键值对就应该放到下标为 1 的桶里。第二步如果下标 1 的桶是空的直接存进去如果已经有其他元素就发生了冲突需要按预定的冲突处理策略继续找位置或挂链。第三步插入完成后表里元素个数加 1同时判断当前负载因子是否超过阈值如果超过了就触发扩容。查找的时候流程更简单同样计算 20240001 % 8 得到下标 1直接去桶 1 里找。如果元素刚好在查找就结束了整个过程没有任何遍历。你会注意到一个设计良好的哈希表查找时间和表里有多少数据基本无关这是它区别于数组、链表最核心的优势。2. 哈希函数设计怎么把 Key 变成下标2.1 除留余数法最经典也最常用在所有哈希函数里除留余数法是最基础、应用最广的一种。它的公式很简单h(key) key % p其中 p 一般取不大于哈希表长度 m 的最大质数。为什么偏偏要取质数我给你举一个直观的反例。假设哈希表长度 m 8数据本身的特征恰好是“都是 8 的倍数”比如 8、16、24、32。你用 key % 8 算会得到什么全都是 0。也就是说不管数据有多少个最后全挤在同一个桶里哈希表退化成了一条链表查询复杂度直接变成 O(n)。但如果 p 取质数比如 7 或 13它对“周期性数据”的敏感程度会明显降低因为这些数据除以质数后产生的余数分布更均匀。这里面的本质是数论里的“同余类”概念你不需要抠得太深只要记住选质数能在一定程度上对冲数据本身的结构性规律。2.2 其他构造方法直接定址、数字分析、平方取中除留余数法能处理大部分场景但有些特定场景下其他方法更合适。直接定址法最简单适合 key 本身就是连续整数的情况比如员工编号从 1 到 1000直接让 h(key) key 就行零冲突但不适合 key 稀疏或分布极不均匀的情况否则会浪费大量空间。数字分析法适用于 key 是固定位数数字串的场景。比如一批手机号都是 11 位前面几位都是 138、139 这种固定前缀真正能区分数据的是中间几位或后几位那就可以只抽取这几位来构造哈希值。平方取中法先把 key 平方再取中间几位作为哈希值。因为平方运算会让每一位数字都参与到结果中所以能有效“搅匀”数据特征适合事先不了解数据分布、但又需要一个凑合能用哈希函数的情况。这些方法看着多本质上都在做同一件事把 key 的特征尽量均匀地散布到有限的地址空间里。工程中百分之八九十的场景用除留余数法就够剩下的是在分布不均匀的邪门数据下才需要换更复杂的函数。2.3 字符串哈希BKDRHash 实现现实中更常见的是字符串 key比如用户名、URL、订单号。字符串哈希要处理的核心问题是不能直接对字符串取模得先把字符串“编码”成一个整数。最粗暴的做法是把每个字符的 ASCII 码加起来比如 abc 是 979899294。这个方法存在致命缺陷字符顺序完全被忽略abc、bca、cab 的结果一模一样排列组合的字串全部冲突。行业里有个很经典的字符串哈希函数叫 BKDRHash核心思想是把字符串看成一个 k 进制的大整数每一位字符都乘上对应的权重这样顺序不同结果就完全不同。常用种子是 31 或 131和 Java 的 String.hashCode() 用 31 是同一个原理。31 这个数好在哪里一是乘法可以优化成移位运算31 * x 可以写成 (x 5) - x在编译器层面非常快二是它是个“不大不小的质数”不容易产生太多哈希碰撞。unsigned int bkdr_hash(const char *key) { unsigned int seed 131; unsigned int hash 0; while (*key) { hash hash * seed (unsigned char)(*key); } return hash 0x7fffffff; }注意代码里最后一个 0x7fffffff 操作它的作用是把符号位强制变成 0确保返回的是一个非负整数。避免后面% capacity时因为负数取模而得到负下标这是个非常容易踩的坑。3. 哈希冲突处理绕不开的核心问题3.1 冲突是怎么产生的哈希函数把无限多的 key 映射到有限多个桶里根据抽屉原理只要 key 的数量超过桶的数量必然有两个不同的 key 落在同一个桶里。即便哈希函数设计得再均匀也只能减少冲突不可能完全避免。所以冲突处理策略是哈希表设计中真正决定性能上限的部分。冲突处理方案主要分两派开放定址法和链地址法。这两种方案在操作系统、数据库、标准库里都有广泛应用没有绝对好坏只有合不合适。下面分别拆解。3.2 开放定址法线性探测、平方探测与双重散列开放定址法的思路是既然目标桶被占了那就按某种规则继续探测下一个空闲位置直到找到一个空桶放进为止。最朴素的是线性探测从冲突位置 i 开始依次尝试 i1、i2、i3……如果探测到数组末尾就绕回开头继续找相当于把整个数组看成一个环形结构。线性探测实现极其简单但它有个臭名昭著的毛病叫“堆积效应”。一旦某个区域发生了连续冲突后续插入的元素会不断往这个区域挤形成越来越长的占用区导致下一次冲突的探测距离更远恶性循环。测试下来当负载因子超过 0.7 时线性探测的插入性能会断崖式下降。平方探测是对线性探测的改进探测序列变成 i1^2、i2^2、i3^2……也就是 1、4、9、16 这样递增的步长。它能把冲突元素更均匀地散开避免大片连续堆积。不过平方探测有个数学前提只有当表长为形如 4k3 的质数时才能保证探测完所有位置否则可能会出现“明明还有空位却永远探测不到”的假溢出情况。双重散列则是准备两个哈希函数第一个算出初始位置第二个算出探测步长组合复杂度更高但效果也更均匀。3.3 链地址法把冲突元素挂成链表链地址法的思路完全不同下标 i 的桶里不直接存数据而是存一个链表的头指针所有冲突的 key 都挂到这条链表上。查找时先定位到桶再沿着链表逐个比较 key。这样做的最大好处是删除容易找到节点链表摘除即可不需要像开放定址法那样小心翼翼地处理“探测链”的断裂问题。Java 的 HashMap 在 JDK 8 之后做了个重要改进当某条链的长度超过 8 且数组长度超过 64 时链表会转换成红黑树把最坏情况下的查询复杂度从 O(n) 降到 O(log n)。这个设计也说明了一个事实链地址法虽然简单但极端数据下确实会出现某条链特别长的问题。不过对于通用场景链表方案代码简单、思想直观是大多数教材和初学者的首选。3.4 两种冲突处理方案的对比选型直接给结论方便你以后做方案选型对比维度开放定址法链地址法核心原理在数组中继续探测空位冲突元素挂到同一个桶的链表空间利用全部存在同一片连续内存缓存友好每个节点分散分配缓存不友好删除操作不能直接置空容易断链需要特殊标记直接摘除节点简单可靠最坏复杂度O(n)O(n)JDK8 后部分场景 O(log n)适用场景表长固定、数据量可预估、删除少数据量动态变化、删除频繁工程实例Redis 字典的 rehash 过程、开放定址的变体Java HashMap、C STL unordered_map如果你自己手写哈希表我建议先掌握链地址法。理由很简单实现难度低不容易出错而且链表法的几乎所有概念都能平移到后续学习红黑树、跳表等更复杂结构上。开放定址法的坑更多适合在理解链表法之后再慢慢研究。4. 代码实现手写哈希表全流程4.1 结构体定义与哈希函数下面进入重头戏代码实现。我选用 C 语言因为 C 没有现成的哈希表库强制你理解每一步在干什么如果你平时写 Java 或 Python看懂这份代码后再去对照 HashMap 或 dict会发现原理完全一样。#include stdio.h #include stdlib.h #include string.h #define DEFAULT_CAPACITY 16 #define LOAD_FACTOR 0.75f typedef struct Node { char *key; int value; struct Node *next; } Node; typedef struct HashTable { Node **buckets; int size; int capacity; } HashTable;这里我用的是链地址法buckets 是一个指针数组每个元素指向一条链表的头节点。size 是当前元素总数capacity 是桶数量。哈希函数复用上一节的 BKDRHash定位下标时用bkdr_hash(key) % capacity。注意 capacity 是 int 类型BKDRHash 返回值已经保证非负取模结果也是非负的不会出现负数下标。为什么用 char* 做 key因为在真实业务里字符串 key 比整数 key 常见得多。你理解了字符串 key 的实现回去看整数 key 版本就毫无难度了。4.2 插入操作遇到相同 key 要更新void put(HashTable *table, const char *key, int value) { int index bkdr_hash(key) % table-capacity; Node *cur table-buckets[index]; // 如果 key 已存在直接更新 value while (cur) { if (strcmp(cur-key, key) 0) { cur-value value; return; } cur cur-next; } // key 不存在创建新节点挂到链表头部 Node *newNode (Node *)malloc(sizeof(Node)); newNode-key (char *)malloc(strlen(key) 1); strcpy(newNode-key, key); newNode-value value; newNode-next table-buckets[index]; table-buckets[index] newNode; table-size; }插入的第一步永远是“先查重”。很多初学者一上来就创建节点挂链表结果同一个 key 被插入了两次查找时只能取到其中一个 value这是非常隐蔽的 bug。我习惯的插入逻辑是先在当前桶的链表中找 key找到就更新值并 return没找到才执行真正的“插头”操作。新节点挂在链表头部是哈希表里很常见的策略因为刚插入的元素往往很快会被再次访问放头部可以让下一次查找更快命中。这里还有一个内存细节key 是外部传入的字符串常量如果直接让 newNode-key key那么当外部调用者修改或释放这段内存时哈希表里就变成野指针了。所以必须malloc一块新内存用strcpy把内容复制过来。这种“深拷贝”思想在开发真实系统时非常重要。4.3 查找操作算下标再链上找int get(HashTable *table, const char *key, int *out) { int index bkdr_hash(key) % table-capacity; Node *cur table-buckets[index]; while (cur) { if (strcmp(cur-key, key) 0) { *out cur-value; return 1; } cur cur-next; } return 0; }查找函数我用了一个“传出参数 返回值”的组合返回值 1 表示找到了0 表示没找到而真正的 value 通过*out传回给调用者。为什么要多这一步因为哈希表里的 value 很可能本身就是 0、-1、空字符串等“合法值”如果直接用返回值返回 value根本没法区分“value 是 0”和“没找到”。这是很多自己写哈希表的人容易忽略的问题。查找过程的时间复杂度取决于链长哈希函数越均匀每条链越短查找越快。如果所有 key 都落在同一个桶里查找就退化成链表的顺序遍历了。4.4 删除操作链表摘除加内存释放int delete_key(HashTable *table, const char *key) { int index bkdr_hash(key) % table-capacity; Node *cur table-buckets[index]; Node *prev NULL; while (cur) { if (strcmp(cur-key, key) 0) { if (prev NULL) { // 要删的是头节点 table-buckets[index] cur-next; } else { prev-next cur-next; } free(cur-key); free(cur); table-size--; return 1; } prev cur; cur cur-next; } return 0; }删除操作有两种写法一种是用双指针prev和cur保存前驱节点另一种是用“指向指针的指针”Node **p table-buckets[index]来统一处理头节点和中间节点。上面代码选择了第一种理解起来更直观面试说思路也方便。删除时有个关键点你必须养成习惯释放节点内存前先把 next 指针保存好或先做链表指针调整。很多初学 C 的选手直接 free(cur)结果 cur 的内存被回收后还去访问 cur-next轻则读脏数据重则段错误。写代码时我总会提醒自己摘除节点、调整链接、释放内存这三步顺序不能乱。另外链地址法的删除天然不用重新哈希但开放定址法的删除则必须垫一个墓碑标记。这一点我在第六节会再展开。4.5 动态扩容与 rehash为什么不能无脑复制哈希表不能一直往里塞数据。当负载因子过高时冲突率飞速上升性能恶化所以扩容机制是哈希表工程实现的必要组成部分。我的策略是在 put 入口处检查负载因子超过阈值就扩容到原来的 2 倍。void resize(HashTable *table) { if ((float)table-size / table-capacity LOAD_FACTOR) { return; } int oldCapacity table-capacity; Node **oldBuckets table-buckets; table-capacity * 2; table-buckets (Node **)calloc(table-capacity, sizeof(Node *)); table-size 0; for (int i 0; i oldCapacity; i) { Node *cur oldBuckets[i]; while (cur) { Node *next cur-next; int newIndex bkdr_hash(cur-key) % table-capacity; cur-next table-buckets[newIndex]; table-buckets[newIndex] cur; table-size; cur next; } } free(oldBuckets); }这里我要重点解释一个所有初学者都会踩的坑扩容绝对不能直接把旧数组元素搬到新数组的同一下标。因为容量变了key % capacity的结果可能完全不同。比如 key17旧容量是 8hash 值是 1新容量变成 16hash 值就变成 9。不重新计算就搬那查找时按新容量算出来的下标还是 9但数据被放在下标 1永远找不到。所以扩容的真实操作叫rehash也就是“重新哈希”。rehash 的过程要遍历旧表的所有链表每个节点都要重新计算下标再头插到新桶中。这时候最好不要在旧节点上额外 malloc 新内存直接把旧节点的指针挪过来就行效率最高。代码里Node *next cur-next;的作用就是先保存旧链表的下一个节点因为当前节点马上要被换到新表里去不保存的话旧链表就断了。4.6 综合 Demo组装起来跑一遍int main() { HashTable *table (HashTable *)malloc(sizeof(HashTable)); table-capacity DEFAULT_CAPACITY; table-size 0; table-buckets (Node **)calloc(table-capacity, sizeof(Node *)); put(table, apple, 100); put(table, banana, 200); put(table, orange, 300); int val; if (get(table, banana, val)) { printf(banana - %d\n, val); } else { printf(banana not found\n); } delete_key(table, apple); if (get(table, apple, val)) { printf(apple - %d\n, val); } else { printf(apple not found\n); } // 手动触发扩容测试 for (int i 0; i 100; i) { char buf[32]; sprintf(buf, key%d, i); put(table, buf, i); } printf(size %d, capacity %d\n, table-size, table-capacity); return 0; }运行结果应该是先输出banana - 200再输出apple not found最后打印的 size 应该是 103capacity 是 64扩容了两次。这个 Demo 能跑起来说明你已经具备了哈希表的最基本实现能力。下一步可以自己动手加一个遍历函数把所有键值对打印出来观察扩容前后的存储分布差异这能帮你建立更扎实的直觉。5. 复杂度分析、应用场景与延伸5.1 平均 O(1) 是怎么来的教科书上写哈希表平均时间复杂度是 O(1)但这个 O(1) 是有前提条件的哈希函数足够均匀负载因子被限制在一定范围内。你可以这样直觉地理解假设桶有 100 个元素只放了 60 个哈希函数又均匀那么绝大多数桶要么为空要么只有一条极短的链平均查找次数就是一个很小的常数。这个常数和数据总量的增长没有关系所以在复杂度分析中记为 O(1)。最坏情况发生在所有 key 都映射到同一个桶里哈希表退化成单链表插入和查找都变成 O(n)。工程上一般通过两个手段来规避一套精心设计的哈希函数加上自动扩容机制。回到代码里我们虽然用链地址法但每次 put 前检查负载因子保证链长不会失控这就在概率上保住了 O(1) 的性能。空间复杂度方面哈希表需要连续数组加链表节点总空间远大于存储数据本身的大小这也是“空间换时间”说法的来源。如果你特别在意内存可以考虑开放定址法它把数据全部存在数组里不需要额外的链表指针空间但代价是删除、探测逻辑更复杂。5.2 哈希的典型应用场景哈希表在真实系统里简直是“无处不在”。最简单的场景是缓存Redis 里每种数据类型都基于哈希表实现通过 key 直接定位 value所以哪怕存储了几百万个键单次读写的耗时也只是微秒级。编译器的符号表也大量使用哈希编译时遇到变量名、函数名都需要快速查到对应的类型和作用域信息。数据库里的哈希索引也是同理点查询非常快但不适合做范围查询这就是哈希索引和 B 树索引长期并存的原因。再往底层说一点Linux 内核里有很多重要数据结构都依赖哈希思想。比如页表、文件系统的 dentry cache、网络协议栈里的连接跟踪表它们都把“快速查找”当成第一需求用的容器内核自己实现了一套哈希链表也就是hlist感兴趣的同学可以去翻内核源码。理解这份手写哈希表之后再去看内核代码会顺畅很多。另一个有意思的应用是布隆过滤器。它本质上是“一个位数组 多个哈希函数”用来判断一个元素“一定不在集合中”或“可能在集合中”。相比哈希表它占用的空间极小但允许误判。搜索引擎、爬虫去重、数据库防止缓存穿透用的都是这个思路。可以说哈希思想从系统内核一直覆盖到业务系统是程序员必须掌握的基础组件之一。5.3 从哈希表到哈希链区块链里的数据结构热词里经常看到“bitcoin 数据结构哈希链”这里我也顺手讲一讲。哈希链和哈希表是两回事哈希表是一个存储结构而哈希链是一种把数据区块串起来的方式每个区块的头部都保存着前一个区块的哈希值区块里的内容一旦被改动哈希值就会变化后面所有区块都会察觉。这种结构天然具备防篡改的能力。为什么要用哈希而不是加密算法因为哈希函数是单向的正向计算极快反向推原值计算上不可行。哪怕原数据只改一个字母哈希结果也会发生巨大变化这被称为雪崩效应。正是这两个特性让区块链不需要中心化机构背书仅靠数据结构本身就能让对方无法伪装篡改。理解哈希链不需要掌握密码学细节你只需要抓住三个关键词单向性、雪崩效应、环环相扣。5.4 澄清一个误区hash 和 history 不是一回事搜索热词里还有一个高频问题叫“hash 和 history 的区别”。这其实是前端路由的概念和本文的哈希表并不在同一层面。前端路由的 hash 模式指的是 URL 中#号后面的部分比如https://example.com/#/home浏览器监听hashchange事件来切换页面history 模式则利用 HTML5 的 History API。这里的 hash 只是“URL 锚点”的传入方式跟哈希函数、哈希表没有直接关系。我之所以专门提这个误区是因为很多人在学习过程中搜“hash”结果搜出来的资料一半在讲数据结构一半在讲前端路由很容易被绕晕。你要做的其实很简单先分清语境。数据结构里说 hash讨论的是 key 到存储位置的映射前端路由里说 hash讨论的是地址栏里#后面的形态两者只是同名而已。6. 常见问题速查与面试避坑6.1 常见问题速查表我自己写哈希表、教哈希表的过程中整理过一张问题速查表几乎覆盖了初学者最容易翻车的地方问题现象根本原因解决方案插入相同 key表里出现两条记录插入前没有做“查重”先遍历链表找 key存在则更新取模出现负数下标哈希函数返回了带符号整数对哈希结果 0x7fffffff扩容后查询不到老数据直接拷贝数组没有 rehash重新计算每个节点的下标strcmp 比较 key 时崩溃key 没做深拷贝或内存被外部释放malloc strcpy 复制 key开放定址法删除后查询失效删除置空导致探测链断裂用墓碑标记或改用链地址法字符串 abc 和 bca 冲突简单字符求和忽略顺序用 BKDRHash 或 java 的 31 种子负载因子超过 0.75 后变慢哈希表太拥挤冲突增多触发扩容扩容到原来的 2 倍这张表我自己在复习数据结构时贴了好几年推荐你也收藏。排查问题时不要一头扎进代码里先对照这张表看看是不是踩了常见坑。6.2 面试高频问题盘点面试里问哈希基本绕不开这几个问题提前准备好能省不少现场组织语言的时间。第一个为什么重写 equals 必须同时重写 hashCode答案是哈希表存储位置依赖 hashCode如果两个对象 equals 判定相等但 hashCode 不同它们会被分配到不同的桶里从哈希表角度它们就是“两个不同对象”导致使用相等判断的语义出现分裂。反过来hashCode 相同但 equals 不同是允许的那只是哈希冲突。第二个JDK 8 的 HashMap 为什么用红黑树因为当链表过长时查询复杂度退化为 O(n)红黑树能维持 O(log n)避免恶意构造大量相等哈希值的 key 对服务端造成攻击。但红黑树节点开销更大所以只在链表长度超过 8 且数组容量超过 64 时才转换短的链表直接用反而更快。第三个一致性哈希和普通哈希的区别是什么普通哈希在节点数量变化时会导致大量 key 重新分布一致性哈希把哈希值空间组织成环形每个 key 只影响相邻节点适合分布式缓存系统的动态扩缩容。第四个哈希能替代一切查找结构吗不能。哈希在范围查询和有序遍历上是短板因为桶之间的顺序不代表 key 的顺序。需要排序时还得靠跳表、B 树这些结构。这也是很多数据库索引不选哈希而选 B 树的根本原因。6.3 实操中踩过的几个坑最后分享几个我在实际写代码过程中踩过的坑希望能帮你少走弯路。第一个坑是 C 语言的内存管理。实现哈希表时malloc一个节点很容易但忘记free也很容易。我最初写删除逻辑时总忘释放cur-key测试次数少看不出问题一旦长期运行内存泄漏积累起来非常吓人。现在我的习惯是每次malloc都问自己一句“这段内存在哪个分支释放”养成这个习惯后内存管理问题少了一大半。第二个坑是哈希函数的均匀性测试。你以为用了 BKDRHash 就万事大吉不一定。我建议你把插入后的链表长度打印出来或者数一下分布式严重倾斜时肯定有哈希函数之外的问题。记得以前处理过一个场景key 都是微秒级时间戳拼接的字符串最后发现问题出在哈希值对 8 取模时后三位全是 0导致所有 key 都被分到了少数桶里。解决办法简单粗暴换更大的质数容量或者对哈希值做一次“扰动”。第三个坑是扩容阈值的选择。别盲目抄 0.75它适合通用场景但如果你明确知道数据量很小容量设大一点把阈值设成 0.5能大幅降低冲突率如果内存受限阈值设到 0.9 也不是不能用只是性能会明显下降。工程上的所有参数都不是绝对的关键是理解每个参数背后的权衡。我个人在实写哈希表的过程中最大的体会是哈希表不止是背下来的“key-value 集合”更是理解“如何用空间换时间”的最佳教材。强烈建议你亲手把上面的代码跑通然后尝试改成开放定址法、再改成整数 key、再加一个遍历输出函数。每改一次你都能加深一层理解。等你哪天遇到问题能自己瞬间想到“这里用哈希表肯定比链表强”你就真正把它变成肌肉记忆了。