【C++】精妙的哈希算法

🕗 发布于 2024-10-18 16:20 c++ 哈希算法 机器学习

🚀个人主页：@小羊 🚀所属专栏：C++ 很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~

动图描述

一、哈希结构

1、哈希概念

AVL树、红黑树等平衡树搜索效率取决于搜索过程中的比较次数，一般时间复杂度为O(logN)，虽然平衡树的搜索效率已经很快，但如果可以不经过任何比较或者常数次的比较后就能搜索到我们要找的元素，会极大的提高效率。

哈希结构，是一种通过特定函数（哈希函数）将关键码映射到表中的一个位置，那么在查找时通过该函数就可以很快的找到该元素。

在这里插入图片描述

但是上述的映射方法存在一个问题，就是不同的元素可能会映射到同一个位置，这时就发生了哈希冲突（也叫哈希碰撞），解决哈希冲突，是实现哈希结构的关键。

2、哈希函数

引起哈希冲突的一个原因可能是：哈希函数设计不合理。
哈希函数的设计要保证高效性和可靠性：

一致性：确保相同的输入总是产生相同的输出哈希值
均匀分布：哈希值应在哈希表的地址空间中尽可能均匀分布，以减少哈希冲突
计算效率：哈希函数应简单且计算快速，以便在实际应用中能够快速执行
冲突最小化：设计哈希函数时应尽量减少哈希冲突的发生，以提高哈希表的性能

| 常见哈希函数：
哈希函数是哈希表的核心，它决定了如何将关键字映射到哈希地址。

直接定制法：取关键字的某个线性函数为散列地址，Hash(Key)=A*Key+B。这种方法简单、均匀，但需要事先知道关键字的分布情况
除留余数法：取一个不大于哈希表地址数m的质数p，按照哈希函数Hash(key)=key%p将关键码转换成哈希地址。这种方法实现简单，且当p选择合理时，哈希冲突的概率较低
平方取中法：对关键字进行平方运算，然后抽取中间的几位作为哈希地址。这种方法适用于不知道关键字分布情况，且位数不是很大的场景
折叠法：将关键字从左到右分割成位数相等的几部分（最后一部分位数可以短些），然后将这几部分叠加求和，并按哈希表表长取后几位作为哈希地址。这种方法适用于关键字位数较多的情况

此外，还有随机数法、数学分析法等哈希函数设计方法，可以根据具体应用场景选择合适的哈希函数。
哈希函数设计的越好，产生哈希冲突的可能性就越低，但是哈希冲突还是无可避免。

3、哈希冲突

解决哈希冲突的两种常见方法是：闭散列（开放定址法）和开散列（链地址法）。

3.1 闭散列

当发生哈希冲突时，如果哈希表中还有空位置，就把key存放到冲突位置的“下一个”空位置去。找下一个空位置，常见的探测方法有线性探测、二次探测和双重散列等。

| 线性探测： 从发生冲突的位置开始，依次向后探测，直到找到下一个空位置为止。

在这里插入图片描述

插入
上图中在插入15前，通过哈希函数得到映射位置为5，但是5位置被占了，就依次向后找，在7位置找到了一个空位置将15插入。
删除
闭散列解决哈希冲突时，不好随便物理删除某个元素，可以考虑标记的方法来伪删除一个元素。

//每个位置都给标记
enum State
{
EXIST,//存在
DELETE,//删除
EMPTY//空
}

| 线性探测实现：

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
{
public:

HashTable()
{
_tables.resize(10);//提前开10个位置
} 

private:
vector<HashData<K, V>> _tables;
size_t _n = 0;//存储元素个数
};

插入

关键码对表的size()取模，不能对capacity()取模，因为哈希表支持[]访问，只能访问下标小于size()的元素。

散列表的载荷因子 = 表中的元素个数 / 表的大小

当载荷因子达到某个临界值，就需要扩容。载荷因子越大，产生冲突的可能性就越大，相反产生冲突的可能性就越小。通常载荷因子应限制在0.7-0.8一下。

不能直接对原表进行扩容，无论是原地扩还是异地扩，都会把原数据拷贝过来。但是扩完容后元素的相对位置可能会发生改变，原本冲突的元素扩完容后就不冲突了，所以直接对原表进行扩容是不行的。

在这里插入图片描述

扩容有两种方法：

方法一：新建原表两倍大小的vector，遍历原表的元素重新映射到vector中，再将新建的vector和原表的vector交换。
方法二：因为方法一还需要重写一遍映射过程，所以可以直接新建一个哈希表，遍历原表的元素插入到新建的哈希表中，最后交换两个哈希表的vector，这个方法的好处是新建的哈希表复用了原哈希表的Insert。

方法一我们就不实现了，直接用更好一点的方法二：

bool Insert(const pair<K, V>& kv)
{
if (_n * 10 / _tables.size() >= 7)//载荷因子达到一定的值进行扩容
{
HashTable<K, V> newHT;
newHT._tables.resize(2 * _tables.size());
for (int i = 0; i < _tables.size(); i++)
{
if (_tables[i]._state == EXIST)
{
newHT.Insert(_tables[i]._kv);
}
}
_tables.swap(newHT._tables);
}
size_t hashi = kv.first % _tables.size();//确定映射位置
while (_tables[hashi]._state == EXIST)
{
++hashi;
hashi %= _tables.size();//防止越界
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
++_n;
return true;
}

但是现在还有个问题，在上面的代码中要求我们的key可以取模，也就是key只能是无符号整数，如果是浮点数、字符串等上面的代码就行不通，所以还需要想办法将可能出现的浮点数、字符串等类型的key转换为无符号的整型再做映射。

像浮点数等可以直接强转为无符号整型，可以考虑用仿函数解决。字符串一般不能直接强转为无符号整型，我们可以对字符串特殊处理，也就是模版特化，将字符串中字符的ASCII码值加起来作为映射值。
但是这里还有个问题，将字符串中字符的ASCII码值加起来也可能冲突，比如相同的字符按不同的顺序组合起来的字符串。不过好在有专门的字符串哈希函数（字符串哈希函数有好多种，这里使用其中一种：BKDR Hash函数），这里就不做过多介绍了，有兴趣的同学请百度了解。他给出的解决办法是字符每次相加之前+31（31、131、1313、13131…都行）来尽可能减少冲突。

template<class K>
struct HashFunc //key强转为整型
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};

//对string类型特殊处理
template<>
struct HashFunc<string>
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto e : s)
{
hash = hash * 31 + e;
}
return hash;
}
};

删除

删除指定的元素，只需要找到该元素的位置，将该位置的状态标记为DELETE即可。

bool Erase(const K& key)
{
HashData<K, V>* ret = Find(key);
if (ret == nullptr)
{
return false;
}
else
{
ret->_state = DELETE;
return true;
}
}

查找

查找过程需要注意的是，当在表中找到被查找的元素时还要判断此位置是否被标记为已删除，因为删除操作我们并没有实际物理上的删除某个元素。

HashData<K, V>* Find(const K& key)
{
Hash hs;
size_t hashi = hs(key) % _tables.size();
while (_tables[hashi]._state != EMPTY)
{
if (_tables[hashi]._state != DELETE 
&& _tables[hashi]._kv.first == key)
{
return &_tables[hashi];
}
++hashi;
hashi %= _tables.size();
}
return nullptr;
}

线性探测的优点是简单好理解，缺点是数据容易堆积，查找时可能需要多次比较。
闭散列 / 开放定址法我们就先实现到这里，它是一种零和博弈，和下面将要介绍的开散列 / 链地址法对比还是稍逊一筹。

3.2 开散列

通过哈希函数计算散列地址，具有相同映射地址的元素归于同一子集合，每一个子集合称为一个哈希桶，各个桶中的元素通过一个单链表链接起来，哈希表中存各链表的头节点。开散列每个桶中存放的都是产生哈希冲突的元素。

在这里插入图片描述

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;
}
return hash;
}
};

template<class K, class V>
struct HashNode
{
HashNode(const pair<K, V>& kv)
:_kv(kv)
,_next(nullptr)
{}

pair<K, V> _kv;
HashNode<K, V>* _next;
};

template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
typedef HashNode<K, V> Node;
public:
HashTable()
{
_tables.resize(10, nullptr);
}

~HashTable()
{
for (int i = 0; i < _tables.size(); i++)
{
Node* pcur = _tables[i];
while (pcur)
{
Node* next = pcur->_next;
delete pcur;
pcur = next;
}
_tables[i] = nullptr;
}
}

private:
vector<Node*> _tables;
size_t _n = 0;
};

插入

bool Insert(const pair<K, V>& kv)
{
size_t hashi = kv.first % _tables.size();

//负载因子==1就扩容
if (_n == _tables.size())
{
HashTable<K, V> newHT;
newHT._tables.resize(2 * _tables.size(), nullptr);
for (int i = 0; i < _tables.size(); i++)
{
Node* pcur = _tables[i];
while (pcur)
{
newHT.Insert(pcur->_kv);
pcur = pcur->_next;
}
}
_tables.swap(newHT._tables);
}
Node* newnode = new Node(kv);

//头插
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return true;
}

上面的扩容过程虽然可行，但是不够好。假如原表中有很多个节点，新建新表扩容后复用Insert就要new很多个节点再插入，这实际上是很有消耗的。因为原节点和新new的节点并无差别，所以可以直接将原表中的节点拿下来头插到新表中，这样就不用再new新节点。

| 优化：

bool Insert(const pair<K, V>& kv)
{
size_t hashi = hs(kv.first) % _tables.size();

//负载因子==1就扩容
if (_n == _tables.size())
{
vector<Node*> newtables(2 * _tables.size(), nullptr);
for (int i = 0; i < _tables.size(); i++)
{
Node* pcur = _tables[i];
while (pcur)
{
Node* next = pcur->_next;
size_t hashi = pcur->_kv.first % newtables.size();
pcur->_next = newtables[hashi];
newtables[hashi] = pcur;
pcur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
Node* newnode = new Node(kv);

//头插
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return true;
}

删除

学习过链表我们知道，单链表的头删和其他位置的删除需要分开处理，因为其他位置删除节点后要将前后节点链接起来，而单链表的头节点没有前一个节点。

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

4、完整代码

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>
struct HashFunc //key强转为整型
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};

//对string类型特殊处理
template<>
struct HashFunc<string>
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto e : s)
{
hash = hash * 31 + e;
}
return hash;
}
};

template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:

HashTable()
{
_tables.resize(10);//提前开10个位置
}

bool Insert(const pair<K, V>& kv)
{
//去冗余
if (Find(kv.first))
{
return false;
}

if (_n * 10 / _tables.size() >= 7)//载荷因子达到一定的值进行扩容
{
HashTable<K, V, Hash> newHT;
newHT._tables.resize(2 * _tables.size());
for (int i = 0; i < _tables.size(); i++)
{
if (_tables[i]._state == EXIST)
{
newHT.Insert(_tables[i]._kv);
}
}
_tables.swap(newHT._tables);
}

Hash hs;
size_t hashi = hs(kv.first) % _tables.size();//确定映射位置
while (_tables[hashi]._state == EXIST)
{
++hashi;
hashi %= _tables.size();//防止越界
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
++_n;
return true;
}

HashData<K, V>* Find(const K& key)
{
Hash hs;
size_t hashi = hs(key) % _tables.size();
while (_tables[hashi]._state != EMPTY)
{
if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key)
{
return &_tables[hashi];
}
++hashi;
hashi %= _tables.size();
}
return nullptr;
}

bool Erase(const K& key)
{
HashData<K, V>* ret = Find(key);
if (ret == nullptr)
{
return false;
}
else
{
ret->_state = DELETE;
return true;
}
}
private:
vector<HashData<K, V>> _tables;
size_t _n = 0;//存储元素个数
};
}

namespace close_address
{
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;
}
return hash;
}
};

template<class K, class V>
struct HashNode
{
HashNode(const pair<K, V>& kv)
:_kv(kv)
, _next(nullptr)
{}

pair<K, V> _kv;
HashNode<K, V>* _next;
};

template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
typedef HashNode<K, V> Node;
public:
HashTable()
{
_tables.resize(10, nullptr);
}

~HashTable()
{
for (int i = 0; i < _tables.size(); i++)
{
Node* pcur = _tables[i];
while (pcur)
{
Node* next = pcur->_next;
delete pcur;
pcur = next;
}
_tables[i] = nullptr;
}
}

bool Insert(const pair<K, V>& kv)
{
Hash hs;
size_t hashi = hs(kv.first) % _tables.size();

负载因子==1就扩容
//if (_n == _tables.size())
//{
//HashTable<K, V> newHT;
//newHT._tables.resize(2 * _tables.size(), nullptr);
//for (int i = 0; i < _tables.size(); i++)
//{
//Node* pcur = _tables[i];
//while (pcur)
//{
//newHT.Insert(pcur->_kv);
//pcur = pcur->_next;
//}
//}
//_tables.swap(newHT._tables);
//}

//负载因子==1就扩容
if (_n == _tables.size())
{
vector<Node*> newtables(2 * _tables.size(), nullptr);
for (int i = 0; i < _tables.size(); i++)
{
Node* pcur = _tables[i];
while (pcur)
{
Node* next = pcur->_next;//记录下一个节点
size_t hashi = hs(pcur->_kv.first) % newtables.size();//映射新表的相对位置
pcur->_next = newtables[hashi];//头插
newtables[hashi] = pcur;
pcur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
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* pcur = _tables[hashi];
while (pcur)
{
if (key == pcur->_kv.first)
{
return pcur;
}
pcur = pcur->_next;
}
return nullptr;
}

bool Erase(const K& key)
{
Hash hs;
size_t hashi = hs(key) % _tables.size();
Node* pcur = _tables[hashi];
Node* prev = nullptr;
while (pcur)
{
if (pcur->_kv.first == key)
{
if (prev == nullptr)
{
_tables[hashi] = pcur->_next;
}
else
{
prev->_next = pcur->_next;
}
delete pcur;
--_n;
return true;
}
prev = pcur;
pcur = pcur->_next;
}
return false;
}
private:
vector<Node*> _tables;
size_t _n = 0;
};
}

本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~

原文地址：https://blog.csdn.net/2301_78843337/article/details/142912056

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：用 Ollama 和 Open WebUI 部署 Llama3 70B
下一篇：代码随想录算法训练营Day28

大数据研究实训室建设方案
大数据项目实训平台作为一个通用的项目实训管理系统，具有高度的灵活性和可扩展性，能够根据学校或机构的特定需求进行定制，内置大数据、云计算和人工智能等领域的实训实战课程资源。实训室将专注于培养学生在大数据
阅读更多2024-10-19
ollama上传本地模型到仓库
一定要添加ollama的密钥，不然上传的时候会报错登录上之后找到设置然后加入你电脑上的ollama的key。
阅读更多2024-10-19
通过PHP与API的结合，开启电商数据集成的新篇章
在数字化转型的浪潮中，电子商务数据的集成对于企业来说变得越来越重要。PHP，作为服务端脚本语言的佼佼者，为开发者提供了强大的工具和库来实现与电商API的无缝对接。通过掌握API调用，PHP开发者可以轻
阅读更多2024-10-19
Java爬虫：API接口数据爬取入门详解及示例代码
API接口数据爬取是Java爬虫技术的一个重要应用领域。通过使用Java的HTTP客户端库和数据解析库，我们可以高效地从API接口获取数据，并进行进一步的分析和应用。掌握这些技能，将使你在数据获取和处
阅读更多2024-10-19
VUE传递字符串显示二维码
1.安装插件npm install vue-qrcode2.使用<script setup lang="ts">import { ref } from
阅读更多2024-10-19
智能指针(3)
我们会发现如果使用的是普通的开辟在栈里面的成员变量或者静态的全局变量都是跟着智能指针走的，但是我们的引用计数计数的是一个空间被多少个智能指针管理着，所以这个计数是肯定要跟着被管理的空间走的，以上两种表
阅读更多2024-10-19
C#两个窗体之间传递参数
C#两个窗体之间传递参数
阅读更多2024-10-19
【C#】使用Visual Studio创建Windows Forms应用程序计算对角线之和
118 Pages（2）课后练习题
阅读更多2024-10-19
DFS算法经典题目： Leetcode 51.N皇后
题目详情如下这道题如果使用暴力解法的话，需要对N个皇后放在每个地方都进行枚举并判断是否可行，时间复杂度非常之高，肯定是过不了的，所以需要使用其他解法。根据题目可以知道每两个皇后之间的位置关系不能是在同
阅读更多2024-10-19
Mybatis多对一查询的配置及两种方法的使用示例对比以及Mybatis一对多查询两种方法使用示例及对比
同多对一的查询一样，mapper.xml配置中使用子查询嵌套的方法在SQL执行的时候会进行多次查询，最终查询次数和取得的行数成正比增加。City(id=0, cityname=北京, areaList
阅读更多2024-10-19

【C++】精妙的哈希算法

目录

一、哈希结构

1、哈希概念

2、哈希函数

3、哈希冲突

3.1 闭散列

3.2 开散列

4、完整代码

相关文章