【C++】——精细化哈希表架构：理论与实践的综合分析
先找出你的能力在哪里，然后再决定你是谁。
—— 塔拉·韦斯特弗 《你当像鸟飞往你的山》
目录
1、C++ 与哈希表：核心概念与引入
哈希表（Hash Table）是一种重要的数据结构，它通过哈希函数将键映射到表中的特定位置，从而实现对记录的快速访问，支持高效的插入和查找操作。
哈希表的概念最早由H. P. Luhn于1953年提出，他首次描述了利用哈希函数加速数据检索的过程。自此，这一思想逐步演化并广泛应用于数据库管理系统和编程语言中，成为计算机科学领域的重要基础之一。
随着计算机硬件性能的提升和数据量的爆炸性增长，哈希表的作用愈发凸显。作为一种高效的数据结构，哈希表在软件工程、数据库系统、网络搜索引擎等领域扮演着不可或缺的角色，尤其在处理大规模数据和高频率查询时展现出卓越的性能优势。
在C++中，哈希表的功能主要通过unordered系列关联式容器实现。在C++98标准中，STL提供了一组底层基于红黑树的关联式容器，如map和set。这些容器在最坏情况下的查询复杂度为O(log N)，即需要进行与红黑树高度成比例的比较操作。当树的节点数量庞大时，查询效率可能会受到显著影响。
为了进一步提升查询性能，C++11引入了四种unordered系列的关联式容器，包括unordered_map、unordered_set、unordered_multimap和unordered_multiset。这些容器在使用方式上与传统的红黑树关联式容器相似，但其底层实现基于哈希表。通过哈希函数的高效映射，unordered容器在平均情况下能够实现O(1)的常数级查询复杂度，极大地提高了数据访问速度，尤其适用于对查询性能要求较高的场景。
总之，哈希表及其在C++中的实现，不仅优化了数据存储与检索效率，还推动了现代软件开发在处理大规模数据时的能力边界，成为计算机科学领域中不可或缺的核心技术之一。
2、哈希表的底层机制：原理与挑战
2.1 核心功能解析：效率与灵活性的平衡
在顺序结构和平衡树中，元素的关键码与其存储位置之间并没有直接的对应关系。因此，在查找一个元素时，必须通过多次比较其关键码。在顺序查找中，时间复杂度为 O(N），而在平衡树中，查找时间复杂度为树的高度 O(log2N))，搜索效率取决于查找过程中元素比较的次数。
理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。为此，我们可以构造一种特殊的存储结构，通过一个哈希函数（hashFunc）将元素的存储位置与其关键码（key）建立一一映射关系。在这种结构中：
- 插入元素：通过哈希函数计算待插入元素的存储位置，并将元素存储在该位置。
- 搜索元素：计算元素的关键码对应的存储位置，直接访问该位置。如果该位置的元素关键码与待查找的元素相同，则搜索成功。
2.2 哈希冲突的本质：问题与应对策略
对于两个数据元素的关键字 ，如果其下标不同，对应的元素值也不同。但哈希函数计算结果却是相同，即 Hash（ki）==Hash（kj），简单说两个不同的key可能会映射到同⼀个位置去
这种现象称为哈希冲突或哈希碰撞。
哈希冲突的发生可能是由于哈希函数的设计问题。一个好的哈希函数应该满足以下原则：
- 定义域覆盖所有关键字：哈希函数的定义域必须包含所有需要存储的关键字；如果散列表允许有 m 个地址，则哈希函数的值域应当在 0 到 m-1 之间。
- 均匀分布：哈希函数应能将关键字均匀地映射到整个地址空间中，减少冲突的概率。
- 计算简单：哈希函数应设计得尽可能简单，以提高计算效率。
然而，由于存储空间有限，哈希函数难以完全避免哈希冲突的发生。因此，发生哈希冲突时，系统需要采取适当的处理方法。通常，哈希冲突的解决方案有两种常见方法：闭散列（Open Addressing）和开散列（Chaining）。
在闭散列中，当发生冲突时，寻找一个空位将元素存储在散列表中。这通常通过线性探测、二次探测或双重散列等技术实现。
在开散列中，当发生冲突时，多个元素被存储在同一个地址位置的链表中，通常采用链表或其他数据结构来存储这些“同义词”。
在讨论哈希冲突的处理方法时，另一个重要的概念是负载因子（Load Factor）。负载因子是哈希表中元素个数与表的总容量之间的比值，通常表示为：
负载因子反映了哈希表的“密集程度”。当负载因子较高时，意味着哈希表中存储的元素接近其总容量，发生哈希冲突的概率增大；相反，负载因子较低时，哈希表中的元素较少，冲突的概率较小。
负载因子的应用与影响：
- 影响哈希冲突的概率：负载因子越大，哈希表中的元素越密集，碰撞的概率也越高。为了降低冲突发生的概率，通常在负载因子达到一定阈值时，会进行哈希表的扩容，将哈希表的容量增大，从而降低负载因子并减少冲突。
- 闭散列中的负载因子：在闭散列法中，当负载因子增大时，查找、插入等操作的时间复杂度会增加。因为哈希表的空闲位置减少，冲突发生后需要进行探测，可能导致操作变得低效。为避免这种情况，当负载因子超过一定值（通常为 0.7 或 0.75）时，会触发扩容操作，将哈希表的大小翻倍，并重新计算每个元素的哈希地址。
- 开散列中的负载因子：在开散列法中，负载因子的增大会导致链表的长度增加，进而影响查找效率。当负载因子过高时，链表变长，查找、插入和删除操作的时间复杂度会退化为线性时间 O(n)。因此，在开散列中，通常也会采取相似的策略，监控负载因子的变化，当负载因子超过某个阈值时，进行扩容或重新哈希。
2.3 开散列与闭散列：两大解决方案的比较
哈希（散列）方法是一种高效的数据存储和检索方式，其核心在于哈希函数和哈希表的构建。通过哈希函数将数据映射到数组索引上，可以快速定位元素。然而，当多个数据被映射到相同的索引（即哈希冲突）时，需要采取有效的策略进行处理。根据解决冲突的方式，哈希表分为两种类型：闭散列和开散列。
闭散列（开放定址法）
闭散列的核心思想是将冲突的元素存放到哈希表中的其他空位置。其主要实现方式是线性探测：
- 插入：通过哈希函数计算得到目标位置。如果该位置为空，则直接插入；若发生冲突，则从冲突位置开始，依次向后探测，直到找到空位置为止，再插入元素。例如，若元素
44计算出的哈希地址为4，但位置4已存有元素4，则继续向后探测，找到下一个空位置存放44。 - 删除：采用伪删除标记代替物理删除，以免影响其他元素的搜索路径。例如，若直接删除元素
4，则会导致后续查找44时路径断裂，因此采用标记伪删除的方法。
优点：
- 实现简单，无需额外数据结构支持。
缺点：
- 容易产生数据堆积（又称“聚集”），即多个冲突元素连续占据空位置，导致后续插入和查找的效率显著下降。
- 空间利用率较低，特别是在装载因子较高时，冲突频率增加，性能退化明显。
为缓解上述问题，可以使用二次探测法或其他改进方法优化冲突处理。
开散列（链地址法）
开散列通过为每个哈希地址维护一个链表来解决冲突：
- 插入：计算哈希地址后，将冲突元素添加到对应链表的末尾。
- 删除：直接从链表中删除目标元素，链表结构确保不会影响其他元素的查找。
优点：
- 空间利用率高，能更好地适应高装载因子。
- 冲突处理灵活，不会产生数据堆积，查找效率相对稳定。
缺点：
- 需要额外的链表存储空间。
- 链表操作增加了一定的复杂性。
演示两种方法 {19,30,5,36,13,20,21,12,24,96} 这⼀组值映射到M=11的表中，采用的哈希函数：
除法散列法也叫做除留余数法，顾名思义，假设哈希表的大小为M，那么通过key除以M的余数作为映射位置的下标，也就是哈希函数为：h(key) = key % M。
3、 闭散列的精确实现：从设计到优化
3.1 整体框架设计：面向扩展的架构
首先我们需要进行一个简单的框架搭建：
我们需要一个HashData类，来储存数据HashTable类底层是vector容器因为会有不同类型的key，所以我们需要一个仿函数来将不同类型转换为size_t，这样才支持哈希函数映射因为闭散列的删除不能直接删除节点，否则会导致线性探测失效，所以HashData类里需要记录状态
//版本一 --- 开放地址法（闭散列） #include<utility> #include<iostream> #include<vector> using namespace std; //节点状态 enum status { EXIST, EMPTY, DELETE }; //设计节点 template<class K, class V> struct HashData { //键值对 pair<K, V> _kv; //状态 status _status; }; // kv键值，仿函数解决不同类型key转换为size_t类型的下标 template<class K,class V,class Hash=HashFunc<K>> class HashTable { public: HashTable() { _table.resize(10); } private: //底层是vector容器 vector<HashData K, V>> _table; size_t _n;//有效数据个数 Hash hs；//仿函数 }; 3.2 仿函数的灵活性：高效哈希的关键
仿函数的作用是将不同数据类型的key转换为可以使用的size_t类型，这样可以才能一 一映射过去
对于可以直接显示类型转换的类型直接转换即可。而对于不能直接转换的类型（比如string）就要进行特殊处理了！
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) { // BKDR size_t hash = 0; for (auto ch : s) { hash += ch; hash *= 131; } return hash; } }; 3.3 插入操作：冲突检测与位置分配
- 首先插入之前要先检查是否在哈希表中已经有数据了
- 然后检查该次是否需要进行扩容
- 通过key值选取合适位置进行插入，有效个数++
bool insert(const pair<K, V>&kv) { //插入前先进行一个检查 if (Find(kv.first)) return false; //是否需要扩容 if (_n >= _table.size() * 0.7) { //进行替换 HashTable<K, V> newHT; newHT._table.resize(_table.size() * 2); //进行赋值 for (auto &s : _table) { if (s._status == EXIST) newHT.insert(s._kv); } //进行替换！！！ _table.swap(newHT._table); } //进行插入 //hash地址 size_t hash0 = kv.first % _table.size(); size_t hashi = hash0; size_t i = 1; //寻找合适位置进行插入 // 线性探测 while (_table[hashi].status == EXIST) { hashi = (hash0 + i) % _table.size(); //取模解决回绕问题 ++i; } //找到合适位置了进行插入 _table[hashi]._kv = kv; _table[hashi].status = EXIST; _n++; return true; }3.4 查找操作：速度与准确的双重保障
查找逻辑很简单对Key进行线性探测即可
HashData<K, V>* Find(const K& key) { size_t hash0 = hs(key) % _table.size(); size_t hashi = hash0; size_t i = 1; while (_table[hashi]._state != EMPTY) { if (_table[hashi]._state == EXIST && _table[hashi]._kv.first == key) //这里需要加判断状态语句 我们删除只是该状态 { return &_table[hashi]; } // 线性探测 hashi = (hash0 + i) % _table.size(); ++i; } return nullptr; }3.5 删除操作：标记与重构的细节优化
删除先通过key找到需要删除的数据
然后将状态设置为DELETE , 有效个数- -
//删除 bool Erase(const K& key) { //size_t hash0 = hs(key) % _tables.size(); //size_t hashi = hash0; //size_t i = 1; //while (_table[hashi]._state != EMPTY) //{ // if (_table[hashi]._state == EXIST // && _table[hashi]._kv.first == key) // { // _table[hashi].status = DELETE; // --_n; // return true; // } // // 线性探测 // hashi = (hash0 + i) % _tables.size(); // ++i; //} //return false; //复用 Find HashData<K, V>* ret = Find(key); if (ret == nullptr) { return false; } else { ret->_status = DELETE; --_n; return true; } }这里一开始的空间机制可以优化，我们使用的哈希函数是除法散列法也叫做除留余数法，当使用除法散列法时，建议M取不太接近2的整数次冥的⼀个质数(素数)。这样可以有效避免哈希冲突
优化一下：采用接近2倍扩容的素数表进行开辟空间扩容
class HashTable { public: HashTable() :_tables(__stl_next_prime(0)) , _n(0) {} inline unsigned long __stl_next_prime(unsigned long n) { // Note: assumes long is at least 32 bits. static const int __stl_num_primes = 28; static const unsigned long __stl_prime_list[__stl_num_primes] = { 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 3221225473, 4294967291 }; const unsigned long* first = __stl_prime_list; const unsigned long* last = __stl_prime_list + __stl_num_primes; const unsigned long* pos = lower_bound(first, last, n); return pos == last ? *(last - 1) : *pos; } bool Insert(const pair<K, V>& kv) { if (Find(kv.first)) return 0; //负载因子>=0.7 扩容 if (_n*10 / _tables.size() >= 7) { HashTable<K, V>newht; newht._tables.resize(__stl_next_prime(_tables.size() + 1)); for (auto& data : _tables) { // 旧表的数据映射到新表 if (data._state == EXIST) { newht.Insert(data._kv); } } _tables.swap(newht._tables); } size_t hash0 = kv.first % _tables.size(); size_t hashi = hash0; size_t i = 1; int flag = 1; while (_tables[hashi]._state == EXIST) { // 线性探测 hashi = (hash0 + i) % _tables.size(); ++i; /*hashi = (hash0 + (i*i*flag)) % _tables.size(); if (hashi < _tables.size()) hashi += _tables.size(); if (flag == 1) { flag = -1; } else { ++i; flag = 1; }*/ } _tables[hashi]._kv = kv; _tables[hashi]._state = EXIST; ++_n; return 1; } HashData<K, V>* Find(const K& key) { size_t hash0 = key % _tables.size(); size_t hashi = hash0; size_t i = 1; while (_tables[hashi]._state != EMPTY) { if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key) { return &_tables[hashi]; } // 线性探测 hashi = (hash0 + i) % _tables.size(); ++i; } return nullptr; } bool Erase(const K& key) { HashData<K, V>* ret = Find(key); if (ret == nullptr) return 0; ret->_state = DELETE; return 1; } private: vector<HashData<K, V>> _tables; size_t _n; //标识数据个数 };这样我们就实现了开发地址法（闭散列）的哈希表！！！
4. 开散列的灵活实现：从基础到高效
我们已经实现了闭散列版本的哈希表，今天计划实现另一种哈希表的实现方式——开散列版本（也称哈希桶）。在深入实现之前，让我们先分析所需的工作。
开散列的核心思想是将哈希表设计为一个数组，每个数组元素对应一个映射地址。为了解决哈希冲突，开散列采用链表的形式将冲突的元素链接起来，从而确保高效的查找和插入操作。
由于涉及到链表的使用，我们可以直接利用 STL 库的 list 数据结构。然而，list 本质上是一个双向循环链表，对我们这样简单的场景来说，可能显得有些复杂且不够高效。为了简化实现并节省内存空间，我们可以自行构造一个简单的单向非循环链表，完全可以满足需求，同时节省约一半的空间。
通过这一设计，我们既可以避免闭散列中可能出现的过多探测问题，又能以较低的实现成本构建一个功能完备且高效的哈希表。
4.1 节点设计：指针与数据的平衡艺术
因为我们要实现单链表结构，肯定要来先设计一下节点框架：
//节点设计 template<class K, class V, class Hash = HashFunc<K>> struct HashNode { //储存的数据 pair<K, V> _kv; //下一个节点的指针 HashNode<K, V>* _next; HashNode(const pair<K, V>& kv) :_kv(kv) , _next(nullptr) {} };4.2 整体框架搭建：链表与逻辑的融合
设计完成节点后，就可以着手构建整体框架了。哈希桶的底层结构通常由一个指针数组构成，同时需要引入一个变量用于记录当前有效元素的个数，以便在负载因子过高时及时触发扩容操作。
实现的核心功能包括插入、删除和查找三个基本操作。需要注意的是，不同类型的数据在插入时需要通过哈希函数转换为 size_t 类型，这样才能将数据正确映射到数组中的对应位置。
在实现这些功能时，需要重点关注以下几点：
- 插入操作：根据哈希函数确定目标位置，处理可能的冲突，将新元素插入到对应链表中。
- 删除操作：查找到目标位置的链表节点并删除，同时需要妥善处理链表连接。
- 查找操作：根据哈希函数定位到目标链表，然后顺序查找目标节点。
通过上述基本功能的实现，我们可以构建一个高效的哈希桶结构，为后续功能扩展和优化打下坚实基础。
namespace hash_bucket { //仿函数 转整形 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) { // BKDR size_t hash = 0; for (auto ch : s) { hash += ch; hash *= 131; } return hash; } }; //节点设计 template<class K, class V, class Hash = HashFunc<K>> struct HashNode { //储存的数据 pair<K, V> _kv; //下一个节点的指针 HashNode<K, V>* _next; HashNode(const pair<K, V>& kv) :_kv(kv) , _next(nullptr) {} }; //开散列的哈希表 // key value 仿函数（转换为size_t） template<class K, class V, class Hash = HashFunc<K>> class HashTable { typedef HashNode<K, V> Node; inline unsigned long __stl_next_prime(unsigned long n) { static const int __stl_num_primes = 28; static const unsigned long __stl_prime_list[__stl_num_primes] = { 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 3221225473, 4294967291 }; const unsigned long* first = __stl_prime_list; const unsigned long* last = __stl_prime_list + __stl_num_primes; const unsigned long* pos = lower_bound(first, last, n); return pos == last ? *(last - 1) : *pos; } public: HashTable() :_tables(__stl_next_prime(0)) ,_n(0) {} private: vector<Node*> _tables; // 指针数组 //vector<list<pair<K, V>>> _tables; size_t _n = 0; // 表中存储数据个数 //struct Date //{ // list<pair<K, V>>_list; // map<pair<K, V>>_map; // size_t len; // len <=8 _list >8 存_map 红黑树 //}; //vector<Date>_tables; //size_t n = 0; }; }4.3 插入函数：链表拓展与哈希分布
实现插入函数时，可以按照以下步骤进行：
- 检查键是否存在：在插入新元素之前，首先检查当前键是否已经存在于哈希表中，只有在键不存在时才进行插入操作。
- 检查是否需要扩容：根据当前的负载因子（有效元素数与桶容量的比值），判断是否需要扩容以保证操作的效率。
- 计算哈希值并定位映射位置：利用仿函数计算键的哈希值
hashi，从而确定其在哈希表中的映射位置。 - 创建并插入新节点：构造一个新节点，并采用头插法将其插入到对应位置的链表中。
关于扩容逻辑，需要特别注意优化实现。最直观的方法是遍历原哈希表，将数据重新插入到新的哈希表中，并释放旧节点。然而，这种方式多做了无意义的节点释放与重建操作。实际上，我们可以直接将原有的节点从旧哈希表中迁移到新哈希表中，无需释放和重新分配，既节省了时间也优化了内存使用。
bool Insert(const pair<K, V>& kv) { //先查找，已经有了相同数据插入失败 if (Find(kv.first)) return 0; Hash hash; // 负载因子等于1时候 进行扩容 if (_n==_tables.size()) { //HashTable<K, V>newht; //newht._tables.resize(__stl_next_prime(_tables.size() + 1)); //for (size_t i = 0; i < _tables.size(); i++) //{ // Node* cur = _tables[i]; // while (cur) // { // newht.Insert(cur->_kv); // cur = cur->_next; // } //} //_tables.swap(newht._tables); // // 多次插入 繁琐 // 这⾥如果使⽤上⾯的⽅法，扩容时创建新的结点，后⾯还要使⽤旧结 //点，浪费了 // 下⾯的⽅法，直接移动旧表的结点到新表，效率更好 vector<Node*> newtable(__stl_next_prime(_tables.size() + 1)); for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; // 头插到新链表 size_t hashi = hash(cur->_kv.first) % newtable.size(); cur->_next = newtable[hashi]; newtable[hashi] = cur; cur = next; } _tables[i] = nullptr; } _tables.swap(newtable); } size_t hashi = hash(kv.first) % _tables.size(); // 头插 Node* newnode = new Node(kv); newnode->_next = _tables[hashi]; _tables[hashi] = newnode; ++_n; return 1; }4.4 删除函数：节点清理与空间复用
删除的逻辑是根据key值找到对应的位置，在该位置的链表中检索是否有相等的数值。如果有就进行删除，否则返回false
bool Erase(const K& key) { if (Find(key) == nullptr) return 0; Hash hash; size_t hashi = hash(key) % _tables.size(); Node* cur = _tables[hashi]; Node* prev = nullptr; while (cur) { if (cur->_kv.first == key) { if (prev == nullptr) //只有一个节点 { _tables[hashi] = cur->_next; } else //中间节点 { prev->_next = cur->_next; } delete cur; --_n; return 1; } else { // 在链表里遍历到删除的数据 prev = cur; cur = cur->_next; } } return 0; }4.5 查找操作：定位效率的优化实践
查找的逻辑和删除类似，根据key值找到映射位置，再在该链表中进行检索，找到返回节点指针，反之返回空指针。
Node* Find(const K& key) { Hash hash; size_t hashi = hash(key) % _tables.size(); Node* cur = _tables[hashi]; while (cur) { if (cur->_kv.first == key) { return cur; } cur = cur->_next; } return __nullptr; }4.6 功能测试：多场景验证与性能分析
这里我们分别测试插入删除，插入寻找，字符串的处理：
int main() { int a[] = { 19,30,5,36,13,20,21,12,24,96 }; hash_bucket::HashTable<int, int> ht2; for (auto e : a) { ht2.Insert({ e,e }); } cout << ht2.Find(96) << endl; cout << ht2.Find(30) << endl; cout << ht2.Find(19) << endl << endl; ht2.Erase(96); ht2.Erase(19); ht2.Erase(30); cout << ht2.Find(96) << endl; cout << ht2.Find(30) << endl; cout << ht2.Find(19) << endl << endl; hash_bucket::HashTable<string, string> ht3; const char* a2[] = { "abcd","sort","insert" }; for (auto& e : a2) { ht3.Insert({ e,e }); } cout << ht3.Find("abcd") << endl; cout << ht3.Erase("abcd") << endl; return 0; }
看起来没有问题，调试看看分布：
通过对监视窗口的查看，我们可以验证我们的代码正常运行的！
