当前位置： 首页 > news >正文

【C++】哈希表原理与实现详解

news 2025/8/8 9:46:18

在这里插入图片描述
各位大佬好，我是落羽！一个坚持不断学习进步的学生。
如果您觉得我的文章还不错，欢迎多多互三分享交流，一起学习进步！
也欢迎关注我的blog主页: 落羽的落羽

文章目录

  • 一、哈希是什么
  • 二、哈希表实现
    • 1. 哈希表相关概念
    • 2. 除法散列法
    • 3. 将关键字转为整数
    • 4. 处理哈希冲突
      • 4.1 开放定址法
      • 4.2 链地址法

一、哈希是什么

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

一个常见的哈希映射例子是，如果要统计一段小写字母文字中各个字母的出现次数，可以开一块大小为26的数组，每个字母的ASCII值 - a的ASCII值就是存储这个字母的次数的数组位置下标。这样经过一次遍历就能统计完了。
上述这种方法，也叫直接定址法。

例题：
387. 字符串中的第一个唯一字符
在这里插入图片描述

在这里插入图片描述

非常简单吧。

二、哈希表实现

1. 哈希表相关概念

  • 哈希函数：直接定址法的缺点也十分明显，当key值的分布范围比较分散时，会导致开的内存空间极大，甚至有很多浪费。假设，我们的数据范围是0~9999的N个值，我们一开始开一块大小为M的空间，我们需要构造一个哈希函数（hash function）hf，关键字key的数据被放在hf(key)的位置上，hf(key)的值必须在[0, M)之间。
  • 哈希冲突：还有一个问题，两个不同的key可能会映射到同一个位置上，这种情况叫哈希冲突，或哈希碰撞。最理想的情况是，设计出一种好的哈希函数避免冲突。但是实际应用中，冲突是不可避免的，我们只能尽可能设计出尽可能优秀的哈希函数，尽可能减少冲突。
  • 负载因子：假设哈希表中已经映射存储了N个值，哈希表的大小为M，那么负载因子 = N/M。负载因子越大，哈希冲突的概率越高，空间利用率也高；负载因子越小，哈希冲突的概率越低，空间利用率也越低。

2. 除法散列法

除了直接定址法，常用的哈希映射方法还有除法散列法，下面我们也使用这种方法实现哈希函数。
除法散列法，也叫除留余数法。假设哈希表的大小为M，那么key除以M的余数作为映射位置的下标，也就是哈希函数为：h(key) = key % M。
使用除法散列法时，要尽量避免使用2的幂次、10的幂次之类的值。因为key%2x相当于留下key的二进制的后x位，key%10x相当于留下key的十进制的后x位，就更容易导致哈希冲突。根据前人的总结，M最好取不接近2的整数次幂的质数。

3. 将关键字转为整数

除留余数法最重要的要求是，key能够取模，因此key的类型必须是整数或能转换为整数。

template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};

key是无法直接强制转换为整型的类型时，如string，就可以对hashFunc进行模板特化，单独写一个方法：字符串转换为整型，可以选择直接把字符的ASCII值相加，但是这样计算类似“abcd”和“acdb”结果是一样的。前人总结出的一个绝佳方法是，上一次计算的结果乘以一个质数，一般是31或131：

// string特化
template<>
struct HashFunc<string>
{size_t operator()(const string& key) const{size_t hash = 0;for (auto ch : key){hash += ch;hash *= 131;}return hash;}
};

4. 处理哈希冲突

哈希冲突是避免不了的，所以需要学会处理哈希冲突。处理方式一般有开放定址法、链地址法。
例如，将一组数据30、19、5、36、13、20、21、12映射到大小为11的表中，则h(key) = key % 11。h(30) = 8，h(19) = 8，h(5) = 5，h(36) = 3，h(13) = 2，h(20) = 9，h(21) = 10，h(12) = 1。哈希函数算出的值即为存储它们的数组下标，注意到h(30) = h(19)，两个数据的存储位置冲突了。

4.1 开放定址法

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

  • 线性探测：从发生冲突的位置开始，依次线性向后探测，直到找到下一个没有存储数据的位置为止，如果找到哈希表尾，则回到哈希表头的位置。因为负载因子小于1，所以最多探测M-1次，一定能找到一个存储key的位置。
    h(key) = hashi = (hash0+i) % M， i = {1, 2, 3, …, M-1}
    线性探测比较简单而且容易实现，但缺点是如果出现位置的连续冲突，多个数据按照插入顺序的不同可能造成位置混乱，争夺同一个位置，这种现象叫做群集（堆积）。

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

下面我们主要使用线性探测，用开放定址法实现哈希表：
先搭出框子：

namespace open_address
{enum State{EXIST,EMPTY, DELETE};template<class K, class V>struct HashData{pair<K, V> _kv;State _state = EMPTY;};template<class K,class V>class HashTable{private:vector<HashData<K, V>> _tables;// 记录实际存储数据个数size_t _n = 0;};
}

要注意的是，我们需要给每个存储值的位置加一个状态标识，否则删除值时，会影响后面新插入的值无法判断这个位置的状态。

哈希表也需要扩容。
这里我们的哈希表的负载因子可以控制在0.7，当负载因子到0.7时就进行一次扩容。假如还按照2倍的扩容，就不能保证下一个M是质数了。一种解决方法是，SGI版本的哈希表方法，提供了一个质数表：

inline unsigned long __stl_next_prime(unsigned long n)
{// Note: assumes long is at least 32 bits.static const int __stl_num_primes = 28;static const unsigned long __stl_prime_list[__stl_num_primes] ={53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};const unsigned long* first = __stl_prime_list;const unsigned long* last = __stl_prime_list + __stl_num_primes;const unsigned long* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;
}

我们这里也借用这个质数表，每次去这个表里获取哈希表扩容后的下一个大小。

开放定址法的哈希表完整实现：

#include<iostream>
#include<vector>
using namespace std;inline unsigned long __stl_next_prime(unsigned long n)
{// Note: assumes long is at least 32 bits.static const int __stl_num_primes = 28;static const unsigned long __stl_prime_list[__stl_num_primes] ={53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};const unsigned long* first = __stl_prime_list;const unsigned long* last = __stl_prime_list + __stl_num_primes;// >=const unsigned long* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;
}template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};// 特化
template<>
struct HashFunc<string>
{size_t operator()(const string& key) const{size_t hash = 0;for (auto ch : key){hash += ch;hash *= 131;}return hash;}
};namespace open_address
{enum State{EXIST,EMPTY,DELETE};template<class K, class V>struct HashData{pair<K, V> _kv;State _state = EMPTY;};template<class K, class V, class Hash = HashFunc<K>>class HashTable{public:HashTable(size_t n = __stl_next_prime(0)):_tables(n), _n(0){}bool Insert(const pair<K, V>& kv){if (Find(kv.first)){return false;}//负载因子到了0.7就进行扩容if ((double)_n / (double)_tables.size() >= 0.7){HashTable<K, V, Hash> newht(__stl_next_prime(_tables.size() + 1));//遍历旧表，将旧表的数据全部重新映射到新表中for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._state == EXIST){newht.Insert(_tables[i]._kv);}}_tables.swap(newht._tables);}Hash hs;size_t hash0 = hs(kv.first) % _tables.size();size_t hashi = hash0;size_t i = 1;//线性探测while (_tables[hashi]._state == EXIST){			hashi = (hash0 + i) % _tables.size();i++;}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;_n++;return true;}HashData<K, V>* Find(const K& key){Hash hs;size_t hash0 = hs(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();i++;}return nullptr;}bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret){ret->_state == DELETE;_n--;return true;}else{return false;}}private:vector<HashData<K, V>> _tables;//记录表中实际存储数据个数size_t _n = 0;};
}

4.2 链地址法

开放定址法中，所有元素都放在哈希表中。链地址法中所有的数据不再直接存储在哈希表中，而是哈希表中每一个位置存储一个指针，没有数据映射到这个位置时，指针为空，有多个数据映射到这个位置时，把冲突的数据连接成一个链表，“挂在”这个哈希表位置下面。链地址法也叫拉链法或哈希桶。

举个例子：
在这里插入图片描述

开放定址法的负载因子必须小于1，而链地址法的负载因子就没有限制了，可以大于1。负载因子越大，哈希冲突的概率越高，空间利用率也高；负载因子越小，哈希冲突的概率越低，空间利用率也越低。STL中unordered_xxx系列容器的最大负载因子基本控制在1，大于1就扩容，我们下面也使用这个方式。

链地址法的哈希桶完整实现：

#include<iostream>
#include<vector>
using namespace std;inline unsigned long __stl_next_prime(unsigned long n)
{// Note: assumes long is at least 32 bits.static const int __stl_num_primes = 28;static const unsigned long __stl_prime_list[__stl_num_primes] ={53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};const unsigned long* first = __stl_prime_list;const unsigned long* last = __stl_prime_list + __stl_num_primes;// >=const unsigned long* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;
}template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};// 特化
template<>
struct HashFunc<string>
{size_t operator()(const string& key) const{size_t hash = 0;for (auto ch : key){hash += ch;hash *= 131;}return hash;}
};namespace hash_bucket
{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(size_t n = __stl_next_prime(0)):_tables(n),_n(0){ }//涉及结点空间的开辟，因此需要自己写析构函数~HashTable(){for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete next;cur = next;}_tables[i] = nullptr;}}bool Insert(const pair<K, V>& kv){if (Find(kv.first)){return false;}Hash hs;//负载因子到了1，需要扩容if (_n == _tables.size()){vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), nullptr);for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;size_t hashi = hs(cur->_kv.first) % newtables.size();//cur头插到新表cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newtables);}size_t hashi = hs(kv.first) % _tables.size();//头插新结点Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;_n++;return true;}Node* Find(const K& key){Hash hs;size_t hashi = hs(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){Hash hs;size_t hashi = hs(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;}_n--;delete cur;return true;}prev = cur;cur = cur->_next;}return false;}private:vector<Node*> _tables;size_t _n; //记录实际存储数据个数};}

本文完整项目代码已上传至我的gitee仓库，欢迎浏览：
https://gitee.com/zhang-yunkai060524/luoyu-c-language

本篇完，感谢阅读。

http://www.lryc.cn/news/613126.html

相关文章：

  • Numpy科学计算与数据分析：Numpy数学函数入门与实践
  • [激光原理与应用-172]：测量仪器 - 能量（焦耳）与功率（瓦）的图示比较
  • 此芯p1开发板使用OpenHarmony时llama.cpp不同优化速度对比(GPU vs CPU)
  • JavaWeb03——基础标签及样式(表单)（黑马视频笔记）
  • 【运维进阶】NFS 服务器
  • 智慧园区系统：打造未来城市生活新体验
  • 第一性原理科学计算服务器如何选择配置-内存选择篇
  • 软考中级【网络工程师】第6版教材 第2章 数据通信基础（下）
  • Windows下Rust编码实现MP4点播服务器
  • 【算法训练营Day22】回溯算法part4
  • Pytest项目_day07（pytest）
  • npm 与 npx 区别详解。以及mcp中npx加载原理。
  • 《深入理解Java字符串：从基础到高级特性》
  • 贪心+矩阵算法
  • 与页面共舞 —— Content Scripts 的魔法
  • 面向对象之类、继承和多态
  • leafletMap封装使用
  • 动手学深度学习13.11. 全卷积网络 -笔记练习（PyTorch）
  • Linux 中断系统全览解析：从硬件到软件的全路线理解
  • 外部排序总结（考研向）
  • MongoDB数据存储界的瑞士军刀：cpolar内网穿透实验室第513号挑战
  • 数据结构：双向链表（Doubly Linked List）
  • 生成对抗网络(GAN)实战 - 创建逼真人脸图像
  • 电路相量法
  • （易视宝）易视TV is-E4-G-全志A20芯片-安卓4-烧写卡刷工具及教程
  • C++的“模板”
  • day069-Jenkins基础使用与参数化构建
  • golang的面向对象编程，struct的使用
  • 急危重症专科智能体”构建新一代急诊、手术与重症中心的AI医疗方向探析
  • 【深度学习机器学习】构建情绪对话模型：从数据到部署的完整实践