| C++语法 | 相关知识点 | 可以通过点击 | 以下链接进行学习 | 一起加油！ |
|---|---|---|---|---|
| 命名空间 | 缺省参数与函数重载 | C++相关特性 | 类和对象-上篇 | 类和对象-中篇 |
| 类和对象-下篇 | 日期类 | C/C++内存管理 | 模板初阶 | String使用 |
| String模拟实现 | Vector使用及其模拟实现 | List使用及其模拟实现 | 容器适配器Stack与Queue | Priority Queue与仿函数 |
| 模板进阶-模板特化 | 面向对象三大特性-继承机制 | 面向对象三大特性-多态机制 | STL 树形结构容器 | 二叉搜索树 |
| AVL树 | 红黑树 | 红黑树封装map/set | 哈希-开篇 |
在上一篇《哈希之路：序篇的知识启航》中，我们简要介绍了哈希方法及哈希表的基础概念。本篇将进一步探讨如何利用闭散列技术有效解决哈希冲突，并通过模拟实现哈希表的过程，深入解析这一关键技术。
🌈个人主页：是店小二呀
🌈C语言专栏：C语言
🌈C++专栏： C++
🌈初阶数据结构专栏： 初阶数据结构
🌈高阶数据结构专栏： 高阶数据结构
🌈Linux专栏： Linux
🌈喜欢的诗句:无人扶我青云志 我自踏雪至山巅
文章目录
- 前文
- 一、闭散列
- 1.1 线性探测(采用闭散列其中一种办法)
- 1.1.1 操作方面
- 1.1.2 状态标记
- 二、实现哈希表
- 2.1 哈希基本构架
- 2.2 哈希表插入数据
- 2.3 哈希表扩容逻辑
- 2.4 哈希表扩容需要换表
- 2.5 复用插入逻辑
- 2.6 哈希表查找元素
- 2.7 哈希表删除数据
- 三、除留余数法出现类型问题
- 3.1 类型问题分析
- 3.2 简单类型做key
- 3.3 string类型做key
- 3.3.1 BKDR算法
- 3.3.2 string模板特化
- 3.4 复杂类型做key
- 散列表头文件
前文
1.目前哈希使用方面存在【一些问题】:
- 如果数据很分散，容易导致空间浪费。
- 有些值不好映射：比如string，结构体对象。
2.采取哈希函数为【除留余数法】:
除留余数法去进行空间浪费的问题，除留余数法空间跟值得范围无关。
3.【除留余数法】 ：
散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，
按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址
一、闭散列
闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。
注意:这种方式属于强盗逻辑，如果我的位置没有了，就需要去抢夺别人位置。
1.1 线性探测(采用闭散列其中一种办法)
场景:现在需要插入元素44，先通过哈希函数计算哈希地址，hashAddr为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止
1.1.1 操作方面
【插入】:
- 通过哈希函数获取待插入元素在哈希表中的位置
- 如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素
【删除】：
采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素
1.1.2 状态标记
由于采用闭散列处理哈希冲突，如果直接删除元素会影响其他元素查找，同时在插入数据中我们需要一个状态标识判断该位置是否存在数据，是否可以在该位置进行插入逻辑，同时需要注意删除元素设置状态应该为删除，而不是为空，去满足实际的状态。
enum State{EMPTY,EXSIT,DELETE};
二、实现哈希表
2.1 哈希基本构架
enum State
{
EMPTY,
EXSIT,
DELETE
};
template<class K, class V>
struct HashData
{
pair<K, V> _kv;
State _state = EMPTY;
};
template<class K, class V>
class HashTable
{
public:
private:
vector<HashData<K, V>> _tables;
size_t _n = 0;
};
哈希是通过哈希函数使得元素的存储位置与它的关键码之间能够建立一一映射的关系，需要使用pair<K,V>类型进行存储。采用vector作为底层逻辑，存储元素类型为哈希节点类型HashData<K, V>。
这里不采用size作为哈希表中有效元素个数，考虑到容器中结构的差异性，是由于_ size一般用于序列式容器中表示有效元素个数，在关联式容器中命名约定一般规定_n作为记录有效元素个数。
2.2 哈希表插入数据
bool Insert(const pair<K, V>& kv)
{
size_t hashi = kv.first % _tables.size();
//如何判断是否删除，是否继续查找，通过标记
while (_tables[hashi]._state == EXSIT)
{
hashi++;
hashi %= _tables.size();
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXSIT;
_n++;
return true;
}
在插入过程，元素需要通过除留余数法找到对应位置进行插入，期间可能会出现哈希冲突的问题，我们需要以该位置向后寻找状态标记为空的位置进行插入。
在向后寻找位置途中可能存在越界情况，这里采用处理循环队列方式进行取模操作，保证数据在合法范围进行查找。这里存在一个大前提，空间是充足的，不然找半天都找不到位置。
2.3 哈希表扩容逻辑
由于哈希表特殊的结构，在进行哈希表扩容操作时，并不采用空位置被填满才进行扩容，而是采用载荷因子的概念进行控制，否则用于空间过少，发生哈希冲突问题频繁，导致效率降低。
可以理解为：负载因子越小，冲突率越低，效率就越高，空间利用率就越低
【扩容条件判断的问题】:if (_n / _tables.size() > = 0. 7)
用于这里涉及类型问题，可以采用类型装换或者乘个十
if (（double）_n / _tables.size() > = 0. 7)if (_n * 10 / _tables.size() >= 7)
【问题】:这里n是除以size还是capacity？
如果选择除以capacity空间容量，可能会导致越界访问。当然如果不知道除以size还是capacity，可以在构造函数先为_tables开辟空间，避免了这个问题的发生，同时防止了size出现等于零的风险。
2.4 哈希表扩容需要换表
当哈希表进行扩容逻辑时，导致了散列表长度发生了变换。这也意味着通过哈希函数(开发定址法)得到的位置需要重新安排插入。在哈希进行扩容操作时，整个过程中消耗最大的时候，需要开辟空间和插入数据，重新进行映射到新表中。
2.5 复用插入逻辑
在扩容操作需要插入数据，需要进行哈希函数的处理，但是在插入操作中已经存在哈希函数进行处理的逻辑，如果选择重新书写哈希函数显得有点冗余
bool Insert(const pair<K, V>& kv)
{
//建立在空间充足及其目前不存在该数据基本上
size_t hashi = kv.first % _tables.size();
//扩容逻辑,这里涉及到负载因子拉
if (_n * 10 / _tables.size() >= 7)
{
HashTable<K, V> NewHT;
//插入逻辑，但是这里我们选择复用，不用我们去判断
NewHT._tables.resize(_tables.size() * 2);
}
//如何判断是否删除，是否继续查找，通过标记
while (_tables[hashi]._state == EXSIT)
{
hashi++;
hashi %= _tables.size();
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXSIT;
_n++;
return true;
}
2.6 哈希表查找元素
HashData<K, V>* Find(const K& key)
{
size_t hashi = key % _tables.size();
//这里本身就是一个循环判断语句
while (_tables[hashi]._state == EXSIT)
{
if (key == _tables[hashi]._kv.first && _tables[hashi]._state == EXSIT)
{
return &_tables[hashi];
}
hashi++;
hashi %= _tables.size();
}
return nullptr;
}
关于哈希表进行查找逻辑是比较容易，其中我想分享一个在设计遇到的问题。在设计状态标记时，只考虑了存在EXSIT和空EMPTY两个状态，这导致了当删除某个元素时，查找过程中无法判断找到数据及其是否需要继续前进，需要DELET标记。
2.7 哈希表删除数据
bool Erase(const K& key)
{
HashData<K, V>* ret = Find(key);
if (ret)
{
ret->_state = DELETE;
_n--;
return true;
}
else
{
return false;
}
}
哈希表删除数据是我们遇到最简单的删除逻辑，只需要改变位置状态就可以了。
三、除留余数法出现类型问题
【除留余数法】:size_t hashi = key % _tables.size();
3.1 类型问题分析
对于key进行取模查找，是建立在key属于无符号整型类型来考虑的，但是我们设计属于泛型编程，key需要去适应不同种类型:string类型，自定义类型，负数。
这种场景需要使用仿函数进行解决，key不支持强转整型取模，那么就要自己提供换成整型仿函数
3.2 简单类型做key
3.3 string类型做key
关于string类型转化为整型类型，这里不推荐使用stoi函数，从编码角度上，对于中文字符底层是通过多个字符对应一个编码表里面的汉字，一旦不采用这张表会出现乱码的情况。
虽然拿string首字母转化伪ASCII码值可行，但是很容易发生哈希冲突。
3.3.1 BKDR算法
最初考虑将字符串中所有字符的ASCII码值相加，以优于仅考虑首字母的效果。然而，这种方法存在缺陷：不同字符组合可能具有相同的ASCII码总和。因此，我们将采用BKDR算法进行优化。
3.3.2 string模板特化
由于string作key是很常见的情况，</这里我们可以对string模板特殊化。（模板特化建立在存在模板的情况下）
template<>
struct HashFunc<string>
{
size_t operator()(const string& key)
{
size_t hash = 0;
for(auto ch : key)
{
hash *= 131;
hash += ch;
}
return hash;
}
};
3.4 复杂类型做key
如果出现复杂类型做key，这种情况一般是自定义类型，比如容器类、学生信息，我们都可以考虑将类中成员相加起来或者独特项，出来的数据不太唯一。
struct Person
{
string _name;
int _age;
};
散列表头文件
#pragma once
#include <iostream>
using namespace std;
#include <vector>
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)
{
size_t hash = 0;
for (auto ch : key)
{
hash *= 131;
hash += ch;
}
return hash;
}
};
namespace HashTable
{
enum State
{
EMPTY,
EXSIT,
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:
//这里只能构造成空的容器，等待数据插入。我们需要进入的元素是pair类型，K和V是明面上的
HashTable()
{
//避免size和capacity问题
_tables.resize(10);
}
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first) == nullptr)
{
return false;
}
Hash hs;
//建立在空间充足及其目前不存在该数据基本上
size_t hashi = hs(kv.first) % _tables.size();
//扩容逻辑,这里涉及到负载因子拉
if (_n * 10 / _tables.size() >= 7)
{
HashTable<K, V> NewHT;
//插入逻辑，但是这里我们选择复用，不用我们去判断
NewHT._tables.resize(_tables.size() * 2);
}
//如何判断是否删除，是否继续查找，通过标记
while (_tables[hashi]._state == EXSIT)
{
hashi++;
hashi %= _tables.size();
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXSIT;
_n++;
return true;
}
HashData<K, V>* Find(const K& key)
{
Hash hs;
size_t hashi = hs(key) % _tables.size();
//这里本身就是一个循环判断语句
while (_tables[hashi]._state == EXSIT)
{
if (key == _tables[hashi]._kv.first && _tables[hashi]._state == EXSIT)
{
return &_tables[hashi];
}
hashi++;
hashi %= _tables.size();
}
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;
};
void TestHT1()
{
int a[] = { 10001,11,55,24,19,12,31 };
HashTable<int, int> ht;
for (auto e : a)
{
ht.Insert(make_pair(e, e));
}
cout << ht.Find(55) << endl;
cout << ht.Find(31) << endl;
ht.Erase(55);
cout << ht.Find(55) << endl;
cout << ht.Find(31) << endl;
}
}
以上就是本篇文章的所有内容，在此感谢大家的观看！这里是店小二呀C++笔记，希望对你在学习C++语言旅途中有所帮助！
