哈希表详解：从哈希函数到冲突解决的 C++ 实现

哈希表是一种通过哈希函数建立关键字与存储位置映射关系的数据结构。它利用哈希函数将 Key 映射为数组下标以实现快速查找。由于哈希冲突不可避免，探讨了除法散列法等哈希函数设计，以及负载因子对冲突概率的影响。核心内容包括开放定址法（线性探测、二次探测、双重散列）和链地址法的原理与对比。最后给出了基于 C++ 的哈希表完整代码实现，涵盖插入、查找、删除及动态扩容逻辑，适合深入学习数据结构底层机制。

无尘发布于 2026/2/24更新于 2026/4/183 浏览

哈希概念

哈希 (hash) 又称散列，是一种组织数据的方式。本质就是通过哈希函数把关键字 Key 跟存储位置建立一个映射关系，查找时通过这个哈希函数计算出 Key 存储的位置，进行快速查找

直接定址法

直接定址法本质上就是用关键字计算出一个绝对位置或者相对位置
直接定址法的缺点非常明显，当关键字的范围比较分散时，就很浪费内存甚至内存不够用

哈希冲突

假设我们只有数据范围是 [0,9999] 的 N 个值，我们要映射到一个 M 个空间的数组中 (一般情况下 M>=N)，那么就要借助哈希函数 (hashfunction) hf，关键字 key 被放到数组的 h(key) 位置，这里要注意的是 h(key) 计算出的值必须在 [0,M) 之间
两个不同的 key 可能会映射到同一个位置去，这种情况叫做哈希冲突，或者哈希碰撞
冲突是不可避免的，但可以设计出优秀的哈希函数，减少冲突的次数并设计出解决冲突的方案

负载因子

假设哈希表中已经映射存储了 N 个值，哈希表的大小为 M，那么负载因子=N/M
负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低；
一般设置最大为 0.7

将关键字转为整数

我们将关键字映射到数组中位置，一般是整数好做映射计算，如果不是整数，我们要想办法转换成整数。

哈希函数

除法散列法/除留余数法

假设哈希表的大小为 M，那么通过 key 除以 M 的余数作为映射位置的下标，也就是哈希函数为：h(key) = key % M。
当使用除法散列法时，要避免 M 为某些值，如 2 的幂，10 的幂等。如果是 2 的幂就相当于保留二进制的后多少位了；10 的幂就是十进制的后多少位。
当使用除法散列法时，建议 M 取不太接近 2 的整数次幂的一个质数 (素数)

乘法散列法、全域散列法

处理哈希冲突

开放定址法

在开放定址法中所有的元素都放到哈希表里，当一个关键字 key 用哈希函数计算出的位置冲突了，则按照某种规则找到一个没有存储数据的位置进行存储，开放定址法中负载因子一定是小于 0.7 的。这里的规则有三种：线性探测、二次探测、双重探测。

线性探测

从发生冲突的位置开始，依次线性向后探测，直到寻找到下一个没有存储数据的位置为止，如果走到哈希表尾，则回绕到哈希表头的位置。
线性探测的问题假设，hash0 位置连续冲突，hash0，hash1，hash2 位置已经存储数据了，后续映射到 hash0，hash1，hash2，hash3 的值都会争夺 hash3 位置，这种现象叫做群集/堆积。
h(key) = hash0 = key % M，hash0 位置冲突了，则线性探测公式为 hc(key,i) = hashi = (hash0+i) % M，i = {1,2,3,…,M −1}

下面演示将 {19，30，5，36，13，20，21，12} 这一组按顺序映射到 M=11 的表中

线性探测举例.png

二次探测

从发生冲突的位置开始，依次左右按二次方跳跃式探测，直到寻找到下一个没有存储数据的位置为止，如果往右走到哈希表尾，则回绕到哈希表头的位置；如果往左走到哈希表头，则回绕到哈希表尾的位置
h(key) = hash0 = key % M , hash0 位置冲突了，则二次探测公式为 hc(key,i) = hashi = (hash0 ± i^2 ) % M，i={ 1,2,3,…，M/2}，当 hashi<0 时，需要 hashi+=M

双重散列

第一个哈希函数计算出的值发生冲突，使用第二个哈希函数计算出一个跟 key 相关的偏移量值，不断往后探测，直到寻找到下一个没有存储数据的位置为止。

相关免费在线工具

加密/解密文本

使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online

Base64 字符串编码/解码

将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online

Base64 文件转换器

将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online

Markdown转HTML

将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。在线工具，Markdown转HTML在线工具，online

HTML转Markdown

将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML转Markdown在线工具，online

JSON 压缩

通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

enum State { EXIST, //存在 EMPTY, //空 DELETE //被删除 }; template<class K, class V> struct HashData { pair<K, V> _kv; State _state = EMPTY; }; template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; } }; template<> struct HashFunc<string> { size_t operator()(const string& s) { size_t hash = 0; for (auto e : s) { hash = hash * 31 + e; //避免'abc'和'acb'这样的字符串冲突，所以*一个素数 } return hash; } }; template<class K, class V, class Hash = HashFunc<K>> class HashTable { public: HashTable() :_tables(11),_n(0) { } bool Insert(const pair<K, V>& kv) { if (Find(kv.first)) { return false; } //负载因子>=0.7 就扩容 if (_n * 10 / _tables.size() >= 7) { vector<HashData<K, V>> newtables(_tables.size() * 2); HashTable<K, V, Hash> newht; newht._tables.resize(_tables.size() * 2); for (auto data : _tables) { //旧表的顺序映射到新表 if (data._state == EXIST) { newht.Insert(data._kv); //调用 Insert，不用再自己找位置了 } } _tables.swap(newht._tables); } Hash hash; //把要比较的值转为无符号整型 size_t hash0 = hash(kv.first) % _tables.size(); //第一次算出来的位置 size_t hashi = hash0; size_t i = 1; while (_tables[hashi]._state == EXIST) { //线性探测 hashi = (hash0 + i) % _tables.size(); //+1 +2 +3 …… ++i; } _tables[hashi]._kv = kv; _tables[hashi]._state = EXIST; ++_n; return true; } HashData<K, V>* Find(const K& key) { Hash hash; size_t hash0 = hash(key) % _tables.size(); //第一次算出来的位置 size_t hashi = hash0; size_t i = 1; while (_tables[hashi]._state != EMPTY) { if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key) { return &_tables[hashi]; //返回指针 } //线性探测 hashi = (hash0 + i) % _tables.size(); //+1 +2 +3 …… ++i; } return nullptr; } bool Erase(const K& key) { HashData<K, V>* ret = Find(key); if (ret) { ret->_state = DELETE; return true; } else { return false; } } private: vector<HashData<K, V>> _tables; size_t _n = 0; //记录已经存放的数据个数 };

template<class K,class V> struct HashNode { pair<K, V> _kv; HashNode<K, V>* _next; HashNode(const pair<K, V>& kv) :_kv(kv) , _next(nullptr) { } }; template<class K, class V, class Hash = HashFunc<K>> class HashTable { typedef HashNode<K, V> Node; public: HashTable() :_tables(11),_n(0) { } //拷贝构造 HashTable(const HashTable& hashtable) { _tables.resize(hashtable._tables.size()); _n = hashtable._n; for (size_t i = 0; i < hashtable._tables.size(); ++i) { Node* src_cur = hashtable._tables[i]; Node* dst_tail = nullptr; //目标对象链表尾（尾插） while (src_cur) { Node* new_node = new Node(src_cur->_kv); if (_tables[i] == nullptr) { _tables[i] = new_node; } else { dst_tail->_next = new_node; } dst_tail = new_node; //指向尾结点 src_cur = src_cur->_next; } } } ~HashTable() { for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; delete cur; cur = next; } _tables[i] = nullptr; } } bool Insert(const pair<K, V>& kv) { if (Find(kv.first)) { return false; } //负载因子==1 时扩容 if (_n == _tables.size()) { vector<Node*> newTable(_tables.size() * 2); for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; //头插到新表 size_t hashi = cur->_kv.first % newTable.size(); cur->_next = newTable[hashi]; newTable[hashi] = cur; cur = next; } _tables[i] = nullptr; } _tables.swap(newTable); } size_t hashi = kv.first % _tables.size(); //头插 Node* newnode = new Node(kv); newnode->_next = _tables[hashi]; _tables[hashi] = newnode; ++_n; return true; } Node* Find(const K& key) { size_t hashi = key % _tables.size(); Node* cur = _tables[hashi]; while (cur) { if (cur->_kv.first == key) { return cur; } cur = cur->_next; } return nullptr; } bool Erase(const K& key) { size_t hashi = key % _tables.size(); Node* prev = nullptr; Node* cur = _tables[hashi]; while (cur) { if (cur->_kv.first == key) { if (prev == nullptr) { //头节点 _tables[hashi] = cur->_next; } else { //中间节点 prev->_next = cur->_next; } delete cur; return true; } else { prev = cur; cur = cur->_next; } } return false; } private: vector<Node*> _tables; //指针数组 size_t _n = 0; //表中存的数据个数 };

哈希表详解：从哈希函数到冲突解决的 C++ 实现

哈希概念

直接定址法

哈希冲突

负载因子

将关键字转为整数

哈希函数

除法散列法/除留余数法

乘法散列法、全域散列法

处理哈希冲突

开放定址法

线性探测

二次探测

双重散列

更多推荐文章

相关免费在线工具

开放定址法哈希表结构

链地址法

解决冲突的思路

示例演示

代码实现

哈希表详解：从哈希函数到冲突解决的 C++ 实现

哈希概念

直接定址法

哈希冲突

负载因子

将关键字转为整数

哈希函数

除法散列法/除留余数法

乘法散列法、全域散列法

处理哈希冲突

开放定址法

线性探测

二次探测

双重散列

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具

开放定址法哈希表结构

链地址法

解决冲突的思路

示例演示

代码实现