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

哈希概念与实现C++

news 2025/1/15 6:50:21

1. 概念

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

2. 直接定址法

当关键字的范围比较集中时，直接定址法就是非常简单高效的方法，比如一组关键字都在[i,i+99]之间，那么我们就可以开一个100的数组，每个关键字的值就是存储位置的下标。再比如一组关键字值都在[a,z]的小写字母，那么我们开一个26个数的数组，每个关键字acsii码就是存储位置的下标。也就是说直接定址法本质就是用关键字计算出一个绝对位置或者相对位置。这个方法和我们的计数排序是一样的。

3. 哈希冲突

直接定制法效率很高但是缺点也十分明显，当关键字的范围比较分散时，就很浪费内存甚至内存不够用。如果我们的数据范围是[0,9999]的N个值，我们要映射到M个空间的数组中(一般情况下M>=N，因为数据不可能一定连续)，那么就要借助哈希函数，关键字key被放到数组的Key位置，要注意Key计算出的值必须在[0，M]之间。

两个不同的Key可能会映射到同一个位置去，这种位置我们叫做哈希冲突，或哈希碰撞。理想情况是找出一个好的哈希函数避免冲突，但在实际应用中，冲突是不可避免的，所以我们尽量设计出优秀的哈希函数，减少冲突的次数，同时也要设计出解决冲突的方案。

4. 哈希函数的设计

应该尽量让N个关键字被等概率的均匀的散列分布到哈希表的M个空间中，但是实际中却很难做到，我们尽量要往这个方向去设计

  1. 直接定址法：

    • 原理：取关键字的某个线性函数值为哈希地址，即H(key)=A*key+B，其中A和B为常数。
    • 优点：简单、均匀。
    • 缺点：需要事先知道关键字的分布情况。
    • 适用场景：查找比较小且连续的情况。

  2. 除留余数法：

    • 原理：设散列表中允许的地址数为m，取一个不大于m但最接近或等于m的质数p作为除数，按照哈希函数H(key)=key%p计算哈希地址。
    • 优点：容易实现，能够将关键码归入散列表的下标范围。
    • 缺点：只适用于整数关键码，且对p的选择很重要。
    • 改进：在实际应用中，p通常选择小于散列表长度的最大质数，以减少冲突。

  3. 平方取中法：

    • 原理：先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。
    • 优点：通过平方扩大差别，中间几位与关键字中的每一位都相关，故不同关键字会以较高的概率产生不同的、均匀的哈希地址。
    • 适用场景：不知道关键字的分布，且位数又不是很大的情况。

  4. 折叠法：

    • 原理：将关键字分割成位数相等的几部分（最后一部分可以短一些），然后将这几部分叠加求和，并按散列表表长取后几位作为散列地址。折叠法又可以分成边界叠加法和移位叠加法两种。
    • 优点：不需要事先知道关键字的分布，适合关键字位数比较多的情况。
    • 示例：对于关键字123456，可以将其分为123、456两部分，然后叠加求和得到579，再取后两位79作为哈希地址（实际中可能需要根据表长进行取模运算）。

  5. 伪随机数法：

    • 原理：选择一个伪随机函数，取关键字的随机函数值为它的哈希地址，即H(key)=random(key)，其中random为伪随机函数。
    • 优点：当关键字长度不等时，采用此法构造哈希函数较恰当。
    • 缺点：随机性可能导致哈希地址分布不均匀。

  6. 数字分析法：

    • 原理：假设已经知道哈希表中所有的关键字值，而且关键字值都是数字，则可以取关键字值的若干位数字组成哈希地址。
    • 优点：简单、直观。
    • 适用场景：关键字为数字，且数字的某几位分布近似随机的情况。

  7. 相乘取整法：

    • 原理：先用关键字key乘以某个常数A（0<A<1），并抽取出key*A的小数部分，然后用m乘以该小数后取整作为哈希地址。
    • 优点：m的选取比除留余数法要求更低，可以选择为2的整数次幂。
    • 缺点：对A的选择有一定的要求，某些值效果会更好。

  8. 全域散列法：

    • 原理：使用一组散列函数来处理哈希冲突 ，h(key)=((a*key+b)%P)%M ，P需要选⼀个⾜够⼤的质数，a可以随机选[1,P-1]之间的 任意整数，b可以随机选[0,P-1]之间的任意整数，这些函数构成了⼀个P*(P-1)组全域散列函数组。 假设P=17，M=6，a=3，b=4,h(8)=((3*8+4)%17)%6=5 。
    • 优点：减少冲突，提高安全性
    • 缺点：需要预先知道关键字的取值范围，并选择一个合适的素数p来构造哈希函数集合；同时，随机选择哈希函数也会增加一些额外的计算开销。

如果将关键字映射到数组中位置的话一般是整数好做映射计算，如果不是整数，我们要想办法转换成整数，对于string我们可以对其进行模板特化处理

5. 处理哈希冲突

实践中哈希表一般还是选择除法散列法作为哈希函数，当然哈希表无论选择什么哈希函数也避免不了冲突，那么插入数据时解决冲突主要有两种方法，开放定址法和链地址法。

5.1 开放定址法

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

规则主要有以下几种

  • 线性探测

从发生冲突的位置开始，依次线性向后探测，直到寻找到下一个没有存储数据的位置为止，如果走到哈希表的尾则回绕到哈希表头的位置。其优点是比较简单且易于实现。缺点是直接寻找后面没有存储数据的位置映射后，后续的插入操作会越来越困难。产生群集/堆积。

  • 二次探测

从发生冲突的位置开始，依次左右按照二次方跳跃式探测，直到寻找到下一个没有存储数据的位置为止，如果往右走到哈希表尾，则回绕到哈希表头的位置；如果往左走到哈希表头，则回绕到哈希表尾的位置；

假如 hash0=key%M，hashi位置冲突了，则二次探测公式为hashi=(hash0±i²)%M，i={1,2，....，M/2}

二次探测当hashi=(hash0-i²)%M时，当hashi<0时，需要hashi+=M

相比线性探测，减少了群集现象，但仍然可能存在一定程度的群集

如下图

我们插入10会发生哈希冲突通过线性探测该元素会插入到2号位置，利用线性探测插入如下

利用二次探测，就会插入到1号位置

负载因子

假设哈希表中已经映射存储了N个值，哈希表的大小为M，那么负载因子=N/M，负载因子有些地方也翻译为载荷因子/装载因子等，英文为load factor。负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低。

开放定址法解决冲突不管使用哪种方法，占用的都是哈希表中的空间，始终存在互相影响的问题。所以开放定址法，所以我们选择简单的线性探测法实现即可

5.2 链地址法

链地址法中所有的数据不再直接存储在哈希表中，哈希表中存储一个指针，没有数据映射这个位置时这个指针为空，有多个数据映射到这个位置时，我们把这些冲突的数据链接成一个链表，挂在哈希表这个位置下面，链地址法也叫做拉链法或者哈希桶。

我们下图演示将{1,3,5,6,9,11,17}这个集合中的所有元素插入一个哈希表中

负载因子

链地址法的负载因子没有限制，可以大于1。负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低；STL中的unordered_set或unordered_map都控制在1，大于1就扩容。

极端场景下：

某个桶特别长，我们可以考虑使用全域散列法，防止被针对。JAVA的HashMap中当桶长度超出一定阈值(8)就会把链表转换为红黑树,这样极端场景下查找效率也保持在O(logN)。

但是一般随着数据增多，就会扩容从而减少哈希冲突的个数，所以可以不进行红黑树优化。

6. 开放定址法实现

6.1 结构

我们用一个枚举类型来标记节点的状态，为了删除数据时不影响查找

enum State
{BLANK,//空白OCCUPY,占用DELETE//用了的节点删除了
};template<class K,class V>
struct HashNode
{State _st = BLANK;pair<K,V> _kv;
};

 我们以数组的方式存储数据，与一个记录有效元素个数的变量_n。

template<class K,class V,class Hash=HashFunc<K>>
class HashTable
{
public://.....
private:vector<HashNode<K,V>> _ht;size_t _n=0;//计算存储数据个数
};
6.2 查找

通过哈希函数计算相应位置，通过线性探测与二次探测进行一一比较，如果对比成功且该元素存在就查找成功，查到空节点就查找失败。

	HashNode<K,V>* Find(const K& k){Hash hs;size_t hashi = hs(k) % _ht.size();while (_ht[hashi]._st != BLANK){if (_ht[hashi]._st == OCCUPY && _ht[hashi]._kv.first == k)return &_ht[hashi];hashi++;hashi %= _ht.size();}return nullptr;}
6.3 插入

要插入首先先查找，有相同的就不插入了，当负载因子大于0.7就进行扩容(使用一个倍数接近2的素数数组)，我们可以通过类似递归的方法将原哈希表的内容重新通过哈希函数映射到新的哈希表中，原哈希表再与新的哈希表进行交换。

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);//返回大于等于n的第一个位置，找不到返回首元素地址return pos == last ? *(last - 1) : *pos;
}bool Insert(const pair<K,V>& kv){if (Find(kv.first))//如果已经有了就不插入了return false;//计算平衡因子，超过0.7就扩容if (_n*10/_ht.size()>7)//等式两边都×10{HashTable<K,V> newht;newht._ht.resize(__stl_next_prime(_ht.size()));for (size_t i = 0; i < _ht.size(); i++){if (_ht[i]._st == OCCUPY){newht.Insert(_ht[i]._kv);}}_ht.swap(newht._ht);}Hash hs;size_t hashi = hs(kv.first) % hs(_ht.size());//计算要插入的地方while (_ht[hashi]._st==OCCUPY)//为空才插入，存在就往后找{hashi++;hashi = hashi % _ht.size();//防止越界}_ht[hashi]._kv = kv;_ht[hashi]._st = OCCUPY;_n++;return true;}
6.4 删除

先通过查找函数，找到对应元素就将其状态改为DELETE删除否则返回false

	bool Erase(const K& k){HashNode<K, V>* node = Find(k);if (node == nullptr)return false;else{node->_st = DELETE;}return true;}

7. 链地址法

7.1 结构

每个节点存放的都是链表，结构可以按链表来实现。一个数组存储指针，一个变量存储元素个数

	template<class K,class V>struct HashNode{pair<K, V> _kv;HashNode<K, V>* _next;HashNode(const pair<K,V>& kv):_next(nullptr),_kv(kv){}};template<class K,class V,class Hash=HashFunc<K>>class HashTable{public:typedef HashNode<K, V> Node;
// .......private:vector<Node*> _table;size_t _n;//节点个数};
7.2 查找

找到对应插入位置遍历链表即可

		Node* Find(const K& k){Hash hs;size_t hashi = hs(k) % _table.size();Node* cur = _table[hashi];while (cur&&cur->_kv.first != k){cur = cur->_next;}return cur;}
7.3 插入

可以考虑负载因子为1的时候来扩容。可以将原来的哈希表上的节点转移到新的哈希表中，通过遍历旧哈希表对新哈希表进行头插，最后再交换。

		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);//返回大于等于n的第一个位置，找不到返回首元素地址return pos == last ? *(last - 1) : *pos;}bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;Hash hs;if (_n * 10 / _table.size() > 10)//平衡因子{vector<Node*> newht;newht.resize(__stl_next_prime(_table.size()));//将旧表节点头插到新表，更加方便for (size_t i = 0; i < _table.size(); i++){Node* cur = _table[i];while (cur){Node* next = cur->_next;size_t hashi = hs(cur->_kv.first) % _table.size();next->_next = newht[hashi];newht[hashi] = next;cur = next;}_table[i] = nullptr;}_table.swap(newht);}size_t hashi = hs(kv.first) % _table.size();Node* newnode = new Node(kv);newnode->_next = _table[hashi];//头插_table[hashi] = newnode;_n++;return true;}
7.4 删除

我们不可以直接用查找函数进行查找，因为删除节点需要找到该节点的前一个节点，只能通过重新遍历查找，最后链接前后节点再减少_n即存储元素的个数即可。

		bool Erase(const K& k){Hash hs;size_t hashi = hs(k) % _table.size();Node* prev = nullptr;Node* tmp = _table[hashi];while (tmp&&tmp->_kv.first!=k){prev = tmp;tmp = tmp->_next;}if (tmp == nullptr)return false;if (prev){prev->_next = tmp->_next;}else{_table[hashi] = tmp->_next;}delete tmp;tmp = nullptr;_n--;return true;}

 8. 源代码

(1). 开放定址法
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;namespace pc
{enum State
{BLANK,//空白OCCUPY,占用DELETE//用了的节点删除了
};template<class K,class V>
struct HashNode
{State _st = BLANK;pair<K,V> _kv;
};template<class K>
class HashFunc
{
public:size_t operator()(K k){return k;}
};template<class K,class V,class Hash=HashFunc<K>>
class HashTable
{
public:
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);//返回大于等于n的第一个位置，找不到返回首元素地址return pos == last ? *(last - 1) : *pos;
}HashTable(){_ht.resize(__stl_next_prime(_ht.size()));}bool Insert(const pair<K,V>& kv){if (Find(kv.first))//如果已经有了就不插入了return false;//计算平衡因子，超过0.7就扩容if (_n*10/_ht.size()>7)//等式两边都×10{HashTable<K,V> newht;newht._ht.resize(__stl_next_prime(_ht.size()));for (size_t i = 0; i < _ht.size(); i++){if (_ht[i]._st == OCCUPY){newht.Insert(_ht[i]._kv);}}_ht.swap(newht._ht);}Hash hs;size_t hashi = hs(kv.first) % hs(_ht.size());//计算要插入的地方while (_ht[hashi]._st==OCCUPY)//为空才插入，存在就往后找{hashi++;hashi = hashi % _ht.size();//防止越界}_ht[hashi]._kv = kv;_ht[hashi]._st = OCCUPY;_n++;return true;}HashNode<K,V>* Find(const K& k){Hash hs;size_t hashi = hs(k) % _ht.size();while (_ht[hashi]._st != BLANK){if (_ht[hashi]._st == OCCUPY && _ht[hashi]._kv.first == k)return &_ht[hashi];hashi++;hashi %= _ht.size();}return nullptr;}bool Erase(const K& k){HashNode<K, V>* node = Find(k);if (node == nullptr)return false;else{node->_st = DELETE;}return true;}private:vector<HashNode<K,V>> _ht;size_t _n=0;//计算存储数据个数
};
}
(2). 链地址法
#include<iostream>
#include<vector>
using namespace std;namespace pc
{template<class K,class V>struct HashNode{pair<K, V> _kv;HashNode<K, V>* _next;HashNode(const pair<K,V>& kv):_next(nullptr),_kv(kv){}};template<class K>struct HashFunc{size_t operator()(K k){return size_t(k);}};template<class K,class V,class Hash=HashFunc<K>>class HashTable{public:typedef HashNode<K, V> Node;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);//返回大于等于n的第一个位置，找不到返回首元素地址return pos == last ? *(last - 1) : *pos;}HashTable(){_table.resize(__stl_next_prime(_table.size()));}~HashTable(){for (size_t i = 0; i < _table.size(); i++){DestroyList(_table[i]);}}void DestroyList(Node* li){if (li == nullptr)return;Node* cur = li;Node* next = li->_next;while (cur){delete cur;cur = next;if(next)next = next->_next;}li=nullptr;}Node* Find(const K& k){Hash hs;size_t hashi = hs(k) % _table.size();Node* cur = _table[hashi];while (cur&&cur->_kv.first != k){cur = cur->_next;}return cur;}bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;Hash hs;if (_n * 10 / _table.size() > 10)//平衡因子{vector<Node*> newht;newht.resize(__stl_next_prime(_table.size()));//将旧表节点头插到新表，更加方便for (size_t i = 0; i < _table.size(); i++){Node* cur = _table[i];while (cur){Node* next = cur->_next;size_t hashi = hs(cur->_kv.first) % _table.size();next->_next = newht[hashi];newht[hashi] = next;cur = next;}_table[i] = nullptr;}_table.swap(newht);}size_t hashi = hs(kv.first) % _table.size();Node* newnode = new Node(kv);newnode->_next = _table[hashi];//头插_table[hashi] = newnode;_n++;return true;}bool Erase(const K& k){Hash hs;size_t hashi = hs(k) % _table.size();Node* prev = nullptr;Node* tmp = _table[hashi];while (tmp&&tmp->_kv.first!=k){prev = tmp;tmp = tmp->_next;}if (tmp == nullptr)return false;if (prev){prev->_next = tmp->_next;}else{_table[hashi] = tmp->_next;}delete tmp;tmp = nullptr;_n--;return true;}private:vector<Node*> _table;size_t _n;//节点个数};}

这篇就到这里啦   ヾ(￣▽￣)Bye~Bye~

(๑′ᴗ‵๑)Ｉ Lᵒᵛᵉᵧₒᵤ❤


http://www.mrgr.cn/news/61461.html

相关文章：

  • Cesium加载地形
  • 回归预测 | MATLAB实RVM-Adaboost相关向量机集成学习多输入单输出回归预测
  • 实战开发：基于用户反馈筛选与分析系统的实现
  • 小结：路由器和交换机的指令对比
  • 忘记了PDF文件的密码，怎么办？
  • 高性能网络模式：Reactor 和 Proactor
  • 单片机原理及应用笔记：C51流程控制语句与项目实践
  • 基于SSM大学生评优管理系统的设计与实现
  • 推断统计——抽样分布、中心极限定理和置信区间
  • 2025第14届中国(上海)国际高纯金属材料及靶材展览会
  • C++，STL 051（24.10.28）
  • 基于Multisim的数字温度计设计与仿真
  • Android 部署web服务器
  • Hue3.9.0-cdh5.14.0安装
  • C语言中的野指针以及避免野指针的常用方式
  • ORBBEC_calss1_ubuntu20.04安装ros noetic
  • 一次性全讲清楚！Spring Cloud微服务
  • 【大数据学习 | kafka】kafka的shell操作
  • Java学习教程，从入门到精通，Java if...else语句（13）
  • AtCoder DP Contest 题目全讲（上）
  • 5. STM32之TIM实验--输出比较（PWM输出，电机，四轴飞行器，智能车，机器人）--（实验5：PWM驱动直流电机）
  • Hadoop生态圈框架部署（二）- 配置IP地址映射为主机名及免密登录
  • 网络中的一些基本概念
  • Spring SPI、Solon SPI 有点儿像（Maven 与 Gradle）
  • 13.2024.10.29
  • jmeter基础01-1_环境准备-windows系统安装jdk