哈希(hash)——【C++实现】

在这里插入图片描述

本章gitee代码仓库：Hash

文章目录

💐1. 哈希概念
🌻2. 哈希冲突
🌼3. 哈希函数
🌸3.1 哈希函数设计原则
🌸3.2 常见哈希函数

🪴4. 哈希冲突解决方案
🌱4.1 闭散列——开放定址法
🌿4.11 负载因子
🌿4.12 字符串哈希算法
🌿4.13 代码实现

🌱4.2 开散列——哈希桶
🌿4.21 代码实现

💐1. 哈希概念

我们对元素进行搜索有几种方式：

暴力查找，直接遍历元素，时间复杂度为O(N)
二分查找，时间复杂度为O(logN)
但二分查找有2个弊端：
- 必须为有序
- 增删查改不方便
这两个弊端导致二分查找只是一个理想的查找方式，并不是很现实
平衡搜索树，增删查改的时间复杂度都是O(logN)，总体性能都很不错

这些结构中的元素关键码和存储位置都没有对应的关系，而有一种方法名为哈希（也叫散列），它提供了一种与这些完全不同的存储和查找方式，即将存储的值和存储的位置建立出一个对应的函数关系。

有一种排序名为计数排序，将不同的值映射到对应的位置，这本质上就是哈希

不了解的可以看下这篇文章——非比较排序——计数排序

我们的通讯录，按照名字的首字母进行分类，本质也是哈希

以数组{1,8,6,3}为例，假设hashi = key % 6 ，那则有如下对应关系

这样就能通过取模直接定位到该元素的位置

但是如果进行插入元素，例如插入2，2%6=2，这就会导致和8的位置一样

🌻2. 哈希冲突

不同的关键字通过哈希函数计算出了相同的地址，值和位置出现了多对一的关系，这种线性称之为哈希冲突（哈希碰撞）。

解决方案：

选择合理的哈希函数
拟定冲突方案

🌼3. 哈希函数

出现哈希碰撞的原因之一可能就是哈希函数设计的不合理

🌸3.1 哈希函数设计原则

哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须是[0,m-1]之间
哈希函数计算出来的地址能均匀分布在整个空间中
哈希函数较为简单，能在较短时间内计算出结构

🌸3.2 常见哈希函数

直接定址法（值的范围集中）

取某个线性函数作为散列的地址：Hash(key) = A*key + B
除留余数法（值的范围分散）

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，

按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

🪴4. 哈希冲突解决方案

🌱4.1 闭散列——开放定址法

如果当前位置被占用，按照规则找到下一个位置（占用其他元素的位置）

我们删除元素通常都不是直接删除，而采用覆盖的方式，而这里无法很好的覆盖

例如我们删除元素1，如果挪动后面的数据，这就导致映射关系全部乱了，如果不直接覆盖，那么之后又元素插入进来的时候，1这个位置还是有元素的，无法插入

所有这里采用状态的方式进行标记：

存在——EXIST
空——EMPTY
删除——DELETE

🌿4.11 负载因子

哈希表定义了一个载荷因子：α = 填入表中元素个数 / 哈希表的长度，这个是表示哈希表装满长度的标志因子

如果负载因子设计的大，那么哈希冲突的概率就越大（空间利用率高）

如果负载因子设计的小，那么哈希冲突的概率就越小（空间利用率低）

对于开放定址法，经过测算，负载因子应该控制在0.7 ~ 0.8，下面代码实现采用0.7

🌿4.12 字符串哈希算法

面对字符串的哈希函数，我们采用BKDRHash函数

有兴趣可查看此篇文章——各种字符串Hash函数

🌿4.13 代码实现

template<class K>
struct DefaultHashFunc
{size_t operator()(const K& key){return (size_t)key;}
};
//模板特化
template<>
struct DefaultHashFunc<string>
{size_t operator()(const string& str){//BKDR hashsize_t hash = 0;for (auto ch : str){hash *= 131;hash += ch;}return (size_t)str[0];}
};//开放定址法
namespace open_address
{enum STATE{EXIST,EMPTY,DELETE};template<class K, class V>struct HashDate{pair<K, V> _kv;STATE _state = EMPTY;};template<class K, class V, class HashFunc = DefaultHashFunc<K>>class HashTable{public:HashTable(){_table.resize(10);	//预先开好10个空间}bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;//扩容if (_n * 10 / _table.size() >= 7)	//设负载因子为0.7{size_t newSize = _table.size() * 2;//扩容之后关系改变，需要重新映射HashTable<K, V> newHT;newHT._table.resize(newSize);//旧表数据插入到新标for (size_t i = 0; i < _table.size(); i++){if (_table[i]._state == EXIST){newHT.Insert(_table[i]._kv);}}//新标和旧表交换_table.swap(newHT._table);}//不能取模capacity，虽然空间有，但访问还是要看size的大小，不然会发生越界HashFunc hf;size_t hashi = hf(kv.first) % _table.size();while (_table[hashi]._state == EXIST){//线性探测hashi++;hashi %= _table.size();}_table[hashi]._kv = kv;_table[hashi]._state = EXIST;++_n;return true;}HashDate<const K, V>* Find(const K& key){HashFunc hf;size_t hashi = hf(key) % _table.size();while (_table[hashi]._state != EMPTY){if (_table[hashi]._state == EXIST && _table[hashi]._kv.first == key){return (HashDate<const K, V>*) & _table[hashi];}++hashi;hashi %= _table.size();}return nullptr;}bool Erase(const K& key){HashDate<const K, V>* ret = Find(key);if (ret){ret->_state = DELETE;--_n;return true;}return false;}private:vector<HashDate<K, V>> _table;	//哈希表size_t _n = 0;	//有效元素个数};
}

线性探测会导致一片拥堵，为此还有一种方法为二次探测

例如线性探测是：
hashi = key % n;
//如果有值了 i>=0
hashi+=i;
而二次探测则是：
hashi = key % n;
//如果有值 i>=0
hashi + i^2;
这样就能在一定程度上减少拥堵

🌱4.2 开散列——哈希桶

开放定址法的缺陷就是冲突会相互影响。而哈希桶的做法是，设置一个指针数组，如果发现冲突，则内部消化

这里桶的结构其实就是链式结构，对每个桶的管理就相当于对于链表的管理，下面的代码采用的是单链表

这里也是需要进行扩容，如果不扩容，就会导致在某种情况下，桶越来越长，这样查找数据就变成了对链表数据的查找，时间复杂度为O(N)，所以还是需要进行扩容。

这里的负载因子可以适当放大一点，一般负载因子控制在1，平均下来每个桶都有数据

🌿4.21 代码实现

这里的桶因为是自定义的链式结构，所以需要我们自己写拷贝构造和析构函数

//哈希桶
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 HashFunc = DefaultHashFunc<K>>class HashTable{typedef HashNode<K, V> Node;public:HashTable(){_table.resize(10, nullptr);}~HashTable(){for (size_t i = 0; i <_table.size(); i++){Node* cur = _table[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_table[i] = nullptr;}}//拷贝构造HashTable(const HashTable& ht){_table.resize(ht._table.size(), nullptr);HashFunc hf;for (size_t i = 0; i < ht._table.size(); i++){Node* cur = ht._table[i];while (cur){Node* newNode = new Node(cur->_kv);size_t hashi = hf(cur->_kv.first) % ht._table.size();//头插newNode->_next = _table[hashi];_table[hashi] = newNode;cur = cur->_next;}}_n = ht._n;}void Print(){for (size_t i = 0; i < _table.size(); i++){printf("[%d]->", (int)i);Node* cur = _table[i];while (cur){cout << cur->_kv.first << "->";cur = cur->_next;}cout << "NULL" << endl;}cout << endl;}bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;HashFunc hf;//扩容 -- 扩容的时候会稍微慢一点 ---^(扩容)-----^(扩容)----------^(扩容)-----.....//这里的扩容不能和开放定址法一样采用将旧表元素重新插入新表//因为这里涉及到开节点，新表开新节点，旧表释放旧节点，浪费if (_n == _table.size()){size_t newSize = _table.size() * 2;vector<Node*> newTable;newTable.resize(newSize,nullptr);//遍历旧表，将节点牵过来for (size_t i = 0; i < _table.size(); i++){Node* cur = _table[i];while (cur){Node* next = cur->_next;//头插到新表size_t newHashi = hf(cur->_kv.first) % newSize;cur->_next = newTable[newHashi];newTable[newHashi] = cur;cur = next;}_table[i] = nullptr;}_table.swap(newTable);}size_t hashi = hf(kv.first) % _table.size();//头插Node* newNode = new Node(kv);newNode->_next = _table[hashi];_table[hashi] = newNode;++_n;return true;}Node* Find(const K& key){HashFunc hf;size_t hashi = hf(key) % _table.size();Node* cur = _table[hashi];while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return nullptr;}bool Erase(const K& key){HashFunc hf;size_t hashi = hf(key) % _table.size();Node* prev = nullptr;Node* cur = _table[hashi];while (cur){if (cur->_kv.first == key){//头删if (prev == nullptr){_table[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;return true;}prev = cur;cur = cur->_next;}return false;}private:vector<Node*> _table;	//指针数组size_t _n = 0;	//有效元素};
}