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

本文详细介绍了哈希表的基本概念、哈希函数的设计方法以及哈希冲突的解决方案。内容涵盖直接定址法、除法散列法与乘法散列法等哈希函数构建方式，重点讲解了开放定址法（包括线性探测、二次探测、双重散列）和链地址法两种主流冲突解决策略。文章提供了完整的 C++ 代码实现，展示了哈希表的结构定义、插入、查找、删除及扩容逻辑，帮助读者深入理解哈希表的工作原理及其在实际开发中的应用。

二进制发布于 2026/2/60 浏览

哈希概念

哈希（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 的表中

线性探测举例

二次探测

从发生冲突的位置开始，依次左右按二次方跳跃式探测，直到寻找到下一个没有存储数据的位置为止，如果往右走到哈希表尾，则回绕到哈希表头的位置；如果往左走到哈希表头，则回绕到哈希表尾的位置。
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++ 实现

哈希概念

直接定址法

哈希冲突

负载因子

将关键字转为整数

哈希函数

除法散列法/除留余数法

乘法散列法、全域散列法

处理哈希冲突

开放定址法

线性探测

二次探测

双重散列

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

更多推荐文章

相关免费在线工具

开放定址法哈希表结构

链地址法

解决冲突的思路

示例演示

代码实现