【DS】哈希表，哈希桶的实现
目录
-
哈希概念
-
哈希冲突
-
哈希函数
-
负载因子
-
哈希冲突的解决
-
- 闭散列
- 开散列
-
哈希表闭散列的实现
-
- 哈希表的结构
- 哈希函数
- 构造函数
- 查找
- 插入
- 删除
-
哈希表开散列的实现
-
- 哈希表的结构
- 查找
- 插入
- 删除
-
哈希表的表长建议是素数
在学习平衡二叉树的过程中,我们不仅学习了AVL树的实现方法,并且进行了模拟实验以掌握红黑树的构建.由于其结构设计,查找效率达到了令人惊叹的O(logN)级别.然而,尽管如此,平衡树中进行平衡调整所消耗的时间以及相关的学习成本仍然不菲.因此,今天我们将转向一个同样高效但实现难度较低的数据结构——哈希表（也称为桶）.相比于AVL树和红黑树,哈希表的实际复杂度稍低;而且C++ STL中的unordered系列关联容器正是采用了哈希表作为基础数据结构.值得注意的是,unordered系列关联容器相比inordered系列（如std::map, std::set, std::multimap等）在底层使用了哈希表技术,因此它们的整体性能表现更为优异;这种高效率源于其采用高效的哈希表技术作为核心数据结构.
哈希概念
在顺序结构与平衡二叉树数据结构中，并不存在元素关键码与其存储位置之间的直接关联关系；因此，在进行元素查找操作时，则必须依次进行关键码的多次比较操作。基于此可知，在顺序查找算法中其时间复杂度为O(N)，而平衡二叉树结构中的查找平均时间复杂度则与其树的高度相关约为O(log N)，由此可见，在相同的存储规模下不同数据结构算法的时间性能存在显著差异；而搜索效率这一指标往往与每次查找所需的关键码比较次数呈现正相关性
高效的查找方案 ：无需进行任何比较操作即可直接从数据表中获取目标元素。若设计一种数据结构，并利用hashFunc函数使得各元素与其关键码间可实现一对一映射关系 ，则在查找过程中仅需调用该函数即可迅速定位所需信息。
例如：
-
新插入元素 * 基于被插入元素的关键码，利用函数确定其存储位置，并将其存放在对应的位置上。
-
搜索项 * 对给定的关键码执行相同的计算方式，并将得到的结果作为存储位置索引保存起来；在数据结构中按照该存储位置索引查找对应的元素进行比较操作。如果键值匹配，则完成搜索。
该方案属于哈希（散列）技术，在哈希方法中所采用的核心转换规则被称为哈希（散列）函数。通过这种技术生成的组织结构被称为哈希表（Hash Table），亦可简称为散列表。
- 哈希是一种概念，哈希表（桶）才是数据结构。
如以下例子：
例如以下：数据集{1,7,6,4,5,9}；
哈希函数定义为：hash(key)=key%capacity;其中capacity代表存储元素底层空间的总容量。
该方法在搜索过程中无需对多个关键词进行反复比较，在每一步骤中都实现了精确匹配。从而使得整个搜索过程运行得更加迅速。同样地，在插入操作方面也保持了较高的效率——无需复杂的判断逻辑即可完成数据的添加工作。
既然哈希方法的效率如此高，那么它有什么缺陷吗？
哈希冲突
对于两个不同数据元素的关键字k_i与 k_j满足i ≠ j时，则必定满足它们的值不等性关系：即k_i ≠ k_j。然而其属性关系却表现出其独特的特性：即其属性间存在某种特定的关系性特征：即它们的属性值相等性关系成立：即Hash(k_i) = Hash(k_j)）。这种现象称为Hash冲突或Hash碰撞。而称这些具有不同关键码却具有相同属性值的数据元素为"同义数据元素"。
如：
哈希函数
引起哈希冲突的一个原因可能是：哈希函数设计不够合理。
哈希函数的设计原则：
- 哈希函数所支持的关键字集合应包含所有可能被存储的关键码
- 当允许存在m个散列表地址时，则该哈希函数的输出结果应在整数区间[0, m-1]内
- 该哈希函数能够将输入的关键字映射至整个可用地址空间中的各个位置上具有良好的均匀分布特性
常用哈希函数——除留余数法
设散列表中的允许地址总数为m个，则选择一个不超过m且尽可能接近或等于m的一个质数值p作为除数，并根据以下哈希函数：
\text{Hash}(\text{key}) = \text{key} \mod p \quad (其中\, p \leq m)
来将键值转换为对应的哈希地址。
通常情况下，在这种情况下p与表长一致（即p=m）。
哈希函数设计的核心要素即为最大限度地减少不同输入值经哈希函数处理后被映射到同一哈希地址上，并在此基础上充分考虑人们的认知规律进行优化设计。
- 注意：哈希函数的设计主要能够减少碰撞风险的可能性，并不能完全消除碰撞。通过负载因子的调节来控制住碰撞的发生频率。*
负载因子
定义：负载因子即为哈希表中当前存储元素数量与总容量之间的比率。
计算公式：负载因子λ等于（当前存储元素数量）除以（哈希表总容量）。则表示该哈希表的空间利用程度。
性能影响：
- 当负载因子较低时 ，哈希表相对空闲，有较多的空闲槽位可供使用，这有助于减少哈希冲突，提高查找和插入操作的效率。
- 当负载因子较高时 ，哈希表的槽位大部分被占用，这可能会导致哈希冲突的增加，进而影响哈希表的性能。
空间利用率：
- 当负载因子增加时 ，空间利用率也随之提高 ，但可能会导致一定的性能下降 。
- 当负载因子降低时 ，空间利用率随之降低 ，而性能可能得到提升 。
此外，在哈希表（桶）管理中，负载因子不仅被视为扩容的触发条件之一，并且在各个实现版本中通常会被设定为一个动态调整的指标。
哈希冲突的解决
对于哈希冲突这一问题，常用的解决方案有以下两种。
闭散列
闭散列即为开放定址法，在哈希表发生冲突的情况下若哈希表尚未填满则必然存在可用的空位通过依次寻找后续空闲的位置来解决冲突问题。
那如何寻找下一个空位置呢？
方案一采用线性探测策略，在发生冲突的位置之后依次向后寻找下一个可用存储位置
仍然在之前的情况中，在数据结构中继续操作。现在尝试向数据结构中添加一个值为44的元素。因为哈希表中对应地址4的位置已经被占用，在这种情况下为了避免冲突并寻找可用存储空间。因此系统会采用线性探测策略进行处理：逐步向前检查可用存储空间，并最终找到合适的位置完成插入操作。
- 在开放散列方法中通过负载因子来降低哈希碰撞的发生同时利用负载因子来管理哈希表的增长从而确保每次插入新元素时都会确保哈希表有剩余空间可用因此无需担心哈希冲突导致无法放置新元素的问题
- 对于开放定址技术而言装载率是一个关键指标建议严格控制在07至08的比例区间内当装载率超过这一范围时系统会自动调整哈希表容量以维持最佳的工作性能
采用线性探测来解决哈希冲突的元素实际上是一种得不偿失的行为。别人占了我的位置实际上是占用他人存储空间的行为，在这种情况下会使得自己不得不去争夺他人的资源，并且这种行为从长远来看并不能带来实质性的收益或者效率提升。当这些冲突频繁发生时，在某些特定情况下会导致局部资源出现严重拥堵；这可能会让大量的数据无法有效地利用现有的哈希表空间从而降低了整体系统的性能效率。
不考虑负载因子扩容的情况下：
当自然你可以选择其他的策略来应对哈希冲突的问题时，请注意基于闭散列的方法中核心策略与线性探测具有相同效果。
开散列
主要通过使用线性探测法将一组关键码分配到同一个子集中，并组织起来连接形成一个单向链表；这些单向链表的头结点存放在哈希表中的每个子集对应一个头节点。
通过观察上图中的数据分布情况可以看出，在开散列中每一个存储单元（即桶）都用于存放那些在哈希函数作用下产生相同索引而导致碰撞的元素。由此可见，在开散列技术中所形成的这些存储单元也可被称为哈希桶。
哈希表中的负载因子分析：
在设计和实现哈希表时，默认情况下会假设其容量足够处理预期的数据量。然而，在实际应用中发现随着输入数据量不断增加，“每个哈希桶中的节点数量逐渐增多”。当出现极端情况时（例如某个特定场景下），可能会导致一个哈希桶中的链表节点非常多（即该特定场景下），从而严重影响整个哈希表的性能表现。针对这一问题，在达到一定满载程度时（即当前存储的数据量与可用空间的比例达到某个阈值），为了保证哈希表的有效运行效率，在达到一定满载程度时（即当前存储的数据量与可用空间的比例达到某个阈值），需要对现有的数据结构进行扩展操作以提高其承载能力（即所谓的"增容"操作）。具体而言，在所有已有的数据均能够找到唯一对应的位置且不存在碰撞的情况下（理想情况下，在所有已有的数据均能够找到唯一对应的位置且不存在碰撞的情况下），当出现第一个碰撞事件发生时（即系统首次遇到无法唯一映射到空闲位置的情况），此时应当触发"增容"操作以确保系统的稳定运行和高效性
开散列与闭散列比较
采用链地址法来解决哈希冲突问题，则需要在数据结构中引入额外的指针字段。这必然会导致存储资源的浪费。然而，在实际应用中发现：为了维持较高的搜索效率，在开地址法中必须预留足够的空余空间（如二次探查法则要求装载因子a <= 0.7），而表项占用的空间远高于指针所需的空间）。由此可见，在解决哈希冲突问题时采用链地址法更为高效和经济。
哈希表闭散列的实现
哈希表的结构
随后将对关联式容器的实现方式进行模拟研究。具体而言，在实际操作中会直接采用pair类型来存储数据。值得注意的是，在哈希表使用闭散列策略处理冲突时，默认情况下无法随意物理上移除已存在的键值对。若采取简单地从哈希表中删减键值对的方式，则可能会影响剩余键值对的数据检索效率。例如，在尝试从系统中删减键值对（如ID为4）后发现其不再被有效寻址（如ID为44），这表明，在线性探测机制下进行元素删除时会采用一种特殊的'标记式软删'方法。
因此哈希表的数据类型是类HashData，并且包含一个有序元素对。此外，在该数据结构中定义了一个枚举关键字定义的类State。该枚举关键字定义的类State设有三种状态：分别为为空（EMPTY）、为删除（DELETE）、存在（EXIST）。
enum State
{
EXIST,
EMPTY,
DELETE
};
template<class K,class V>
struct HashData
{
pair<K,V> _kv;
State _state = EMPTY;
};
AI生成项目cpp
哈希表的底层通常采用数组结构，并且在许多编程语言中，默认会直接使用vector类型来实现这一功能。此外，在其他库中的哈希表实现方式也类似，并且为了提高效率，在每个哈希表中增加一个变量用于记录元素数量 _size。
template<class K,class V,class Hash = HashFunc<K>>
class HashTable
{
public:
//function
private:
vector<HashData<K, V>> _table;
size_t _size;
};
AI生成项目cpp
哈希函数
在哈希表实现过程中，其主要难点之一是非整型数据的处理问题。
哈希表的基础结构是数组，在采用除留余数法作为哈希函数时，必须确保K值能够执行模运算（即仅限于整数索引）。
在介绍哈希表结构时，在模板的第三个位置设置一个自定义仿射变换作为哈希函数以处理取整需求。即为此处所需的哈希函数，并且该方法只需将输入类型转换成整数值即可实现。
只要满足K值能够生成有效的哈希地址（返回一个整数值），就可以执行映射插入操作。
例如：经过哈希函数处理后得到的结果仅为整数值部分，在这种情况下虽然无法直接按照K值进行映射（因为浮点数本身并不能被直接映射），但至少可以通过将浮点数值转换为相近的整数值来进行表项存储。
查找时当然会进行对应关系比对，在这种情况下就无需担心是否能够找回对应的K值。
以这样的方式理解的话，在本系统中使用的整型均为无符号类型：由于数组下标不支持负数值的存在。
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& e : key)
{
hash *= 31;
hash += e;
}
return hash;
}
};
AI生成项目cpp
- string 被视为一种常用类型；因此，在此处按照模板进行特殊化处理；当K类型为字符串时会匹配这个字符串类型的哈希函数
该字符串哈希算法的具体实现可参考——字符串哈希算法；而开散列哈希表中所使用的哈希函数也遵循同样的原理。
构造函数
该容器由一个vector和一个预定义好的内置类型组成，默认构造函数已经足够从理论上讲不需要自定义构造函数在这里的目的下我们选择自定义构造函数以节省内存空间因此，在实现过程中可以直接利用数组结构并结合vector的强大特性以提高效率那么哈希表中存储的数据数量是由什么决定？答案是由data的数量决定因为通过索引访问元素时只能访问有效的数据个数即data的数量因此我们通常将这个数量称为data的数量
闭散列中负载因子设为0.7，达到0.7时则进行扩容
HashTable()
{
_table.resize(10);//初始大小为10（是vector的size，不是capacity）
}
AI生成项目cpp查找
查找操作为其他操作的基础，所以还是很重要的；其实现步骤如下：
通过除留余数法确定查找的值所对应的哈希地址。
哈希冲突因素导致哈希地址上的存储项可能不是我们正在查找的那个目标项，
因此需要从哈希地址开始向后依次检查。
首先判断当前_state的状态，
当且仅当标签字段中存在标记为EXIST的值时，
才认为该状态是存在的。
接着通过比较或核验K值得出该状态是否存在的结论：
存在则直接返回该状态对应的哈希地址；
如果所有可能的状态都已经检查完毕仍不存在，
则返回null。
特别注意：采用线性探测的方式解决哈希冲突问题时，默认情况下冲突的值必定落在紧随计算结果哈希地址后的第一个可用空位置。
HashData<K, V>* Find(const K& key)//返回数据类型
{
Hash hs;//哈希函数取K
size_t hashi = hs(key) % _table.size();//计算哈希地址
while (_table[hashi]._state != EMPTY)//闭散列，真正的值可能在后面
{
//如果状态为delete，则不存在
if (_table[hashi]._state == EXIST && _table[hashi]._kv.first == key)
{
return &_table[hashi];
}
++hashi;
hashi %= _table.size();
}
return nullptr;
}
AI生成项目cpp
插入
插入步骤如下：
-
进行去重操作时，请确保不允许存在重复的数据项。
-
判断是否需要扩展存储空间时，请注意将原有数据表的内容按照新的存储结构进行合理分配。
-
通过扩展现有存储空间可能减少哈希碰撞的风险，并在此基础上进行相应数据转移。
-
这种迁移操作与直接插入的操作具有相似性。
-
添加新的元素
-
使用取模运算计算哈希地址
-
检测对应位置的状态是否为EXIST；若当前单元已被占用，则需依次向前移动至可用空位
-
在表中插入对应元素，并将状态标记为EXIST
-
计数器_size被递增以记录插入次数
在实现过程中发现一个巧妙的要点就是在扩容操作中可以直接创建一个已经容量扩展完毕的新表格，在这种情况下，在新旧两张表格之间进行数据转换的方法是通过调用该新表格的插入功能模块来完成数据转移的过程即采用了下面介绍的具体插入操作流程作为基础完成所有操作后可以在两张表格之间进行内容切换即可达到扩容的目的
bool Insert(const pair<K, V>& kv)
{
//去重
if (Find(kv.first))
{
return false;
}
//检查是否需要扩容
if (_size * 10 / _table.size() >= 7)//负载因子设为0.7；
{
//扩容，需要重新映射。
HashTable<K, V> newtable;
newtable._table.resize(_table.size() * 2);//二倍扩
for (const auto& e : _table)//将旧的移到新的。
{
if (e._state == EXIST)
{
newtable.Insert(e._kv);//插入逻辑和下面一致
}
}
_table.swap(newtable._table);//交换新旧两表
}
Hash hs;//取K
size_t hashi = hs(kv.first) % _table.size();//除留余数法算出下标
while (_table[hashi]._state == EXIST)//若对应位置已有，则往后推
{
++hashi;
hashi %= _table.size();
}
_table[hashi]._kv = kv;
_table[hashi]._state = EXIST;
++_size;
return true;
}
AI生成项目cpp
删除
请特别注意以下内容：请确保您了解并遵循以下规定——即在任何情况下都应严格遵守规定
- 执行Find操作，并返回其结果值。
- 如果某个节点存在，则将其_state字段设置为DELETE即可完成删除操作。
- 记得_size- -
开放定址法下的哈希表实现增删查操作时的数据状态处理多为直接修改状态的方式。因此，在实际应用中可以直接通过修改数据状态来实现伪删除以达到删除目的。
bool Erase(const K& key)
{
HashData<K, V>* ret = Find(key);
if (ret)
{
ret->_state = DELETE;
_size--;
return true;
}
return false;
}
AI生成项目cpp
哈希表开散列的实现
开散列的哈希表也有称为哈希桶的
哈希表的结构
在使用开放散列法构建的哈希表中
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 HashBucket
{
typedef HashNode<T> Node;
public:
//function
private:
vector<Node*> _bucket;
size_t _size;
};
AI生成项目cpp
开散列的哈希函数，构造函数和上面闭散列的实现是一致的。
查找
步骤：
经计算确定哈希地址
检查该哈希地址对应的单链表是否为空
若单链表非空，则逐一核对各项数据以比对K值
实现逻辑和闭散列是相同的，由于不需要状态标识符，实现起来更简单。
Node* Find(const K& key)//返回数据类型
{
Hash hs;
size_t hashi = hs(key) % _bucket.size();
Node* cur = _bucket[hashi];
while (cur)//存在则进行比对
{
if (cur->_kv.first == key)
{
return cur;
}
cur = cur->_next;
}
return nullptr;
}
AI生成项目cpp
插入
步骤：
删除重复项，并不允许存在具有相同K值的元素。
判断当前哈希表的空间利用情况后决定是否需要扩容。
采用开放地址法（Open Addressing），当插入元素的数量等于桶的数量时才进行扩容。
在扩容过程中，在新的哈希表中逐个复制这些节点到相应的位置上。
通过这种方法能够显著减少不必要的额外操作，
- 插入新节点，_size记得++
在本模块中插入线性链表时，默认采用头插法或尾插法均可，请根据具体情况决定具体实现方式。其中最为关键的步骤在于，在将旧链表元素重新连接至新链表时，并不涉及旧链表节点的断开操作。这一设计不仅能够避免了频繁开窗或回收节点所带来的额外开销，并且通过直接将原有节点挂接至新位置的方式实现了高效的数据重用。其余的操作均属于单链表的基本维护与管理范畴，请熟悉相关内容的读者参考——单链表的实现
bool Insert(const pair<K, V>& kv)
{
//去重
if (Find(kv.first))
{
return false;
}
//检查是否需要扩容
if (_size == _bucket.size())//负载因子为1；
{
//扩容，需要重新映射。
vector<Node*> newbucket;//此时开的是vector
newbucket.resize(_bucket.size() * 2);//扩容
for (size_t i = 0; i < _bucket.size(); i++)
{
if (_bucket[i])//非空说明有数据
{
Node* cur = _bucket[i];//获取当前节点
Node* next = nullptr;
Hash hs;
size_t newhashi;
while (cur)
{
next = cur->_next;//先记录旧表的下一个节点
newhashi = hs(cur->_kv.first) % newbucket.size();//计算在新表的位置
cur->_next = newbucket[newhashi];//串联新表的下一节点
newbucket[newhashi] = cur;//头插
cur = next;//遍历旧表
}
}
}
_bucket.swap(newbucket);//交换新旧两表
}
//插入过程
Hash hs;
size_t hashi = hs(kv.first) % _bucket.size();
Node* newnode = new Node(kv);
//头插
newnode->_next = _bucket[hashi];
_bucket[hashi] = newnode;
++_size;
return true;
}
AI生成项目cpp
在学习哈希表插入操作后, 人们会了解到, 哈希表不具备确保元素按顺序排列的能力. 这一特点也解释了为何unorderded系列的数据结构不具备有序性, 因为它们以哈希表作为基础数据结构. 此外, 这样的设计使得红黑树等平衡树无法实现严格意义上的有序存储.
删除
步骤：
-
确定哈希地址
-
检查该节点是否位于哈希表的桶首位
- 如果待删除的键值对存储在桶首位置，则必须重新配置相关链表结构
- 否则无需额外操作
-
删除节点，_size- -
bool Erase(const K& key)
{
Hash hs;
size_t hashi = hs(key) % _bucket.size();
Node* prev = nullptr;//前一节点
Node* cur = _bucket[hashi];//当前节点
while (cur)
{
if (cur->_kv.first == key)
{
//需要检测是不是当前桶的头节点
if (prev == nullptr)//为头节点
{
_bucket[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
AI生成项目cpp
哈希表的表长建议是素数
减少冲突概率:
- 均匀分布：使用素数值进行模运算能够使哈希值在哈希表中实现更为均匀的分配 ，从而降低不同键产生相同哈希值的概率（即冲突发生率）。这是因为素数值在模运算过程中具备较少的因式分解可能性。
- 避免周期性：选择素数值作为除法运算基数有助于防止出现周期性规律的现象
如：
表长为8：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 1 | 3 | 5 | 7 | ||||
| 9 | 11 | 13 | 15 |
表长为7：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 7 | 1 | 9 | 3 | 11 | 5 | 13 |
| 15 |
因此，在优化哈希表性能时，在扩容操作中避免简单地将容量翻一番会导致结果是表长不再是素数进而影响哈希函数分布均匀性为了避免这种情况就需要预先准备好一个间隔差距大致为两倍的素数数组例如给出如下一个素质序列每个元素之间的间隔大致是前一个元素的二倍增长
const int PRIMECOUNT = 28;
const size_t primeList[PRIMECOUNT] =
{
53ul, 97ul, 193ul, 389ul, 769ul,
1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
1610612741ul, 3221225473ul, 4294967291ul
};
AI生成项目cpp
将其封为一个函数，等到扩容时再来取
size_t GetNextPrime(size_t prime)
{
//素数序列
const int PRIMECOUNT = 28;
const size_t primeList[PRIMECOUNT] =
{
53ul, 97ul, 193ul, 389ul, 769ul,
1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
1610612741ul, 3221225473ul, 4294967291ul
};
//size_t i = 0;
for (size_t i = 0; i < PRIMECOUNT; i++)
{
if (primeList[i] > prime)
return primeList[i];
}
//return primeList[i];//理论上一定会在循环中有结果
}
AI生成项目cpp
使用时在resize中调用即可。
//newbucket.resize(_bucket.size() * 2);//二倍增长
newbucket.resize(GetNextPrime(_bucket.size()));//素数数组
AI生成项目cpp