前言
大家好吖，欢迎来到 YY 滴 数据结构 系列 ，热烈欢迎！ 本章主要内容面向接触过C++的老铁
主要内容含：
欢迎订阅 YY滴C++专栏！更多干货持续更新！以下是传送门！
- YY的《C++》专栏
- YY的《C++11》专栏
- YY的《Linux》专栏
- YY的《数据结构》专栏
- YY的《C语言基础》专栏
- YY的《初学者易错点》专栏
- YY的《小小知识点》专栏
一.哈希（散列）的基本概念
1.哈希（散列）的基本概念
理想的搜索方法：不经过任何比较， 一次 直接从表中得到要搜索的元素。
如果构造一种存储结构， 通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系 ，那么在查找时通过该函数可以很快找到该元素
该方式即为 哈希(散列)方法 ，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称 为哈希表(Hash Table)(或者称散列表)
2.哈希表的简单基本例子
例如：数据集合{1，7，6，4，5，9}； 哈希函数设置为：
hash(key) = key % capacity;
- capacity为存储元素底层空间总的大小
- 用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快
- 但是 当插入44时 ，就会出现问题： 不同值映射到相同位置 ，这就是第二部分要讲的" 哈希冲突问题 "
二.哈希冲突(哈希碰撞)
- 一句话理解哈希冲突: 不同值映射到相同位置
- 官方解释：对于两个数据元素的关键字 k i k_i ki和 k j k_j kj(i != j)，有 k i k_i ki != k j k_j kj，但有：Hash( k i k_i ki) == Hash( k j k_j kj)，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
- 把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。
- 引起哈希冲突的一个原因可能是： 哈希函数设计不够合理 。这就是第二部分要讲的"哈希函数"
三.哈希函数
- 我们先要确定一点：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是 无法避免哈希冲突
1.哈希函数设计原则
- 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
- 哈希函数计算出来的地址能均匀分布在整个空间中
- 哈希函数应该比较简单
2.常用的两种哈希函数
【1】 直接定址法–(常用)
取关键字的某个线性函数为散列地址：
Hash（Key）= A*Key + B
- 优点：简单、均匀
- 缺点：需要事先知道关键字的分布情况
- 使用场景：适合查找比较小且连续的情况
【2】除留余数法–(常用)
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，
按照哈希函数Hash(key) = key% p(p<=m), 将关键码转换成哈希地址
【※】哈希表中的荷载因子
四.解决哈希冲突法一：闭散列-“开放地址法”
- 一句话理解闭散列： 当前位置被占用了，按规则找到下一个位置（占用别人应该在的位置）
- 闭散列：也叫 开放定址法 ，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有
空位置，那么可以把key存放到冲突位置中的 “下一个” 空位置中去 。- 那如何寻找下一个空位置呢？—— 线性探测+二次探测
1. 线性探测＆二次探测
- 一句话理解 线性探测： 从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止 ,示例如下所示：
- 线性探测缺点： 一旦发生 哈希冲突 ，所有的冲突连在一起，容易产生 数据“堆积”
- 即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降
低。如何缓解呢？- 二次探测 是为了避免该问题而生；找下一个空位置的方法为： H i H_i Hi = ( H 0 H_0 H0 + i 2 i^2 i2 )% m, 或者： H i H_i Hi = ( H 0 H_0 H0 - i 2 i^2 i2 )% m。其中： i = 1,2,3…， H 0 H_0 H0是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。示例如下所示：
2.闭散列哈希中的基本状态
每一个元素格子可以分成三种状态：
- EXIST（存在）
- EMPTY（空）
- DELETE（已被删除）
enum STATE
{
EXIST,
EMPTY,
DELETE
};
3.闭散列哈希的基本结构
template<class K, class V>
struct HashData
{
pair<K, V> _kv;
STATE _state = EMPTY;
};
vector<HashData<K, V>> _table;
size_t _n = 0; // 存储有效数据的个数————可用于识别荷载因子
4.线性探测中处理"查找"
代码如下所示：
HashData<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 (HashData<const K, V>*) & _table[hashi];
}
++hashi;
hashi %= _table.size();
}
5.线性探测中处理"插入"
【1】注意闭散列扩容问题
插入过程基本程序设计思路：
- 当荷载因子达到某个临界值
_n * 10 / _table.size() >= 7，进入扩容- 扩容过程： 1.设置新表大小 2.创建新表 3.遍历旧表的数据插入到新表即可 4.交换新表旧表首元素地址
- 正常插入过程遵循线性探测：
1.通过哈希函数找到相应映射的下表（hashi）
2.但遇到当前hashi已经被占据时_table[hashi]._state == EXIST，
进行 二次探测hashi %= _table.size();重新寻找新hashi
3.找到状态为EMPTY的hashi时，存入数据，调整状态_table[hashi]._kv = kv; _table[hashi]._state = EXIST; ++_n;
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
{
return false;
}
// 扩容
//if ((double)_n / (double)_table.size() >= 0.7)
if (_n * 10 / _table.size() >= 7) //荷载因子
{
size_t newSize = _table.size() * 2;
// 遍历旧表，重新映射到新表
HashTable<K, V, HashFunc> 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);
}
// 线性探测
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;
}
6.线性探测中处理"删除"
删除过程基本程序设计思路：
- 利用查找函数find接收返回值
- 将该hashi下表对应的状态设置成DELETE即可
// 按需编译
bool Erase(const K& key)
{
HashData<const K, V>* ret = Find(key);
if (ret)
{
ret->_state = DELETE;
--_n;
return true;
}
return false;
}
7. 闭散列适应多种类型转换————“仿函数”＆“类模板特化”&“仿函数在类模板中充当默认模板实参的应用”
【1】仿函数
- 一句话解释 仿函数 ：用一个类重载
（），让其实现函数的功能
- 仿函数在类模板中的应用传送门：传送门
- 使用仿函数的基本操作：重载（）——operator()
template<class K>
struct DefaultHashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
【2】类模板特化
- 使用仿函数的进阶操作：让闭散列适应多种类型转换
- 场景举例：正常情况下，我们输入int double，他都会通过仿函数重载的（）转换成对应的ASCLL码值，但是当传入的是字符串则会出现问题，因此我们需要把类模板 特化一下————
struct DefaultHashFunc<string>- 特化在类模板中的应用传送门：传送门
template<>
struct DefaultHashFunc<string>
{
size_t operator()(const string& str)
{
// BKDR
size_t hash = 0;
for (auto ch : str)
{
hash *= 131;
hash += ch;
}
return hash;
}
};
【3】仿函数在类模板中充当默认实参的应用
- 仿函数在类模板中充当默认模板实参 传送门：传送门
template<class K, class V, class HashFunc = DefaultHashFunc<K>>
class HashTable
{
//调用时
HashFunc hf;
size_t hashi = hf(kv.first) % _table.size();
...};
8.闭散列哈希完整代码展示
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
size_t hash = 0;
for (auto ch : str)
{
hash *= 131;
hash += ch;
}
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 HashFunc = DefaultHashFunc<K>>
class HashTable
{
public:
HashTable()
{
_table.resize(10);
}
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
{
return false;
}
// 扩容
//if ((double)_n / (double)_table.size() >= 0.7)
if (_n * 10 / _table.size() >= 7)
{
size_t newSize = _table.size() * 2;
// 遍历旧表，重新映射到新表
HashTable<K, V, HashFunc> 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);
}
// 线性探测
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;
}
HashData<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 (HashData<const K, V>*) & _table[hashi];
}
++hashi;
hashi %= _table.size();
}
return nullptr;
}
// 按需编译
bool Erase(const K& key)
{
HashData<const K, V>* ret = Find(key);
if (ret)
{
ret->_state = DELETE;
--_n;
return true;
}
return false;
}
private:
vector<HashData<K, V>> _table;
size_t _n = 0; // 存储有效数据的个数
};
}
9.闭散列缺点
- 发生哈希冲突后，几个位置映射的值会 相互影响
五.解决哈希冲突法二：开散列-“链地址法(开链法)”-“哈希桶”
1. 开散列概念
- 开散列法又叫 链地址法(开链法) ，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合， 每一个子集合称为一个桶 ，各个桶中的元素通过一个 单链表 链接起来，各链表的头结点存储在哈希表中。
- 开散列中每个桶中放的都是发生 哈希冲突 的元素。
2.开散列哈希基本形式
//哈希桶
namespace hash_bucket
{
HashTable...//哈希表
HashNode...//节点
vector<Node*> _table; // 指针数组
size_t _n = 0; // 存储了多少个有效数据
}
//哈希表
template<class K, class V, class HashFunc = DefaultHashFunc<K>>
class HashTable
{
typedef HashNode<K, V> Node;
....};
//节点
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)
{}
};
3.开散列插入
【1】哈希桶基本插入问题
- 采取 头插方式
文章来源：https://www.toymoban.com/news/detail-756509.html
// 头插
Node* newnode = new Node(kv);
newnode->_next = _table[hashi];
_table[hashi] = newnode;
【2】注意闭散列扩容问题
引入：文章来源地址https://www.toymoban.com/news/detail-756509.html
- 如果不扩容，不断插入某些桶越来越长效率得不到保障，负载因子适当放大一些，一般负载因子控制在1，平均下来就是每一个桶一个数据
// 负载因子到1就扩容
if (_n == _table.size())
{
size_t newSize = _table.size()*2;
vector<Node*> newTable;
newTable.resize(newSize, nullptr);
if(...)//剩余操作
}
【3】注意闭散列扩容后的操作
- 注意：这里我们采用 遍历旧表，顺手牵羊，把节点牵下来挂到新表的方式
- 原因：重新开空间开节点，消耗大，效率低
// 遍历旧表，顺手牵羊，把节点牵下来挂到新表
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];//旧表
while (cur)
{
Node* next = cur->_next;//保存下一个地址
//找到新的对应位置
size_t hashi = hf(cur->_kv.first) % newSize; //hf为仿函数，在开散列相关章可以查看
//头插到新表
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
//把旧表置空
_table[i] = nullptr;
}
//最后交换新旧表首元素地址
_table.swap(newTable);
【4】闭散列完整插入操作
bool Insert(const pair<K, V>& kv)
{
if(Find(kv.first))
{
return false;
}
HashFunc hf;
// 负载因子到1就扩容
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 hashi = hf(cur->_kv.first) % newSize;
cur->_next = newTable[hashi];
newTable[hashi] = 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;
}
4. 开散列查找操作
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;
}
5. 开散列哈希完整代码展示
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;
}
}
bool Insert(const pair<K, V>& kv)
{
if(Find(kv.first))
{
return false;
}
HashFunc hf;
// 负载因子到1就扩容
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 hashi = hf(cur->_kv.first) % newSize;
cur->_next = newTable[hashi];
newTable[hashi] = 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;
}
void Print()
{
for (size_t i = 0; i < _table.size(); i++)
{
printf("[%d]->", i);
Node* cur = _table[i];
while (cur)
{
cout << cur->_kv.first <<":"<< cur->_kv.second<< "->";
cur = cur->_next;
}
printf("NULL\n");
}
cout << endl;
}
private:
vector<Node*> _table; // 指针数组
size_t _n = 0; // 存储了多少个有效数据
};
}
六.哈希表的使用
#include"HashTable.h"
int main()
{
HashTable<int, int> ht;
int a[] = { 1,111,4,7,15,25,44,9 };
for (auto e : a)
{
ht.Insert(make_pair(e, e));
}
ht.Erase(15);
auto ret = ht.Find(4);
//ret->_kv.first = 41;
ret->_kv.second = 400;
//HashTable<string, string, StringHashFunc> dict;
HashTable<string, string> dict;
dict.Insert(make_pair("sort", "排序"));
dict.Insert(make_pair("left", "xxx"));
auto dret = dict.Find("left");
//dret->_kv.first = "xx";//不可修改，const
dret->_kv.second = "左边";
string s1("xxx");
string s2("xxx");
DefaultHashFunc<string> hf;
cout << hf(s1) << endl;
cout << hf(s2) << endl;
cout << hf("bacd") << endl;
cout << hf("abcd") << endl;
cout << hf("abbe") << endl;
cout << hf("https://www.baidu.com/s?ie=utf-8&f=8&rsv_bp=1&rsv_idx=1&tn=65081411_1_oem_dg&wd=STATE&fenlei=256&rsv_pq=0xdd48647300054f47&rsv_t=1cd5rO%2BE6TJzo6qf9QKcibznhQ9J3lFwGEzmkc0Goazr3HuQSIIc2zD78Pt0&rqlang=en&rsv_enter=1&rsv_dl=tb&rsv_sug3=2&rsv_n=2&rsv_sug1=1&rsv_sug7=100&rsv_sug2=0&rsv_btype=i&prefixsug=STAT%2526gt%253B&rsp=5&inputT=656&rsv_sug4=796") << endl;
return 0;
}
到了这里，关于【数据结构】万字一文手把手解读哈希————（开/闭散列）解决哈希冲突完整详解（6）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[R语言]手把手教你如何绘图(万字)](https://imgs.yssmx.com/Uploads/2024/02/441311-1.png)
