先找出你的能力在哪里，然后再决定你是谁。
—— 塔拉·韦斯特弗 《你当像鸟飞往你的山》
目录
1. C++ 与哈希表：核心概念与引入
2. 哈希表的底层机制：原理与挑战
2.1 核心功能解析：效率与灵活性的平衡
2.2 哈希冲突的本质：问题与应对策略
2.3 开散列与闭散列：两大解决方案的比较
3. 闭散列的精确实现：从设计到优化
3.1 整体框架设计：面向扩展的架构
3.2 仿函数的灵活性：高效哈希的关键
3.3 插入操作：冲突检测与位置分配
3.4 查找操作：速度与准确的双重保障
3.5 删除操作：标记与重构的细节优化
4. 开散列的灵活实现：从基础到高效
4.1 节点设计：指针与数据的平衡艺术
4.2 整体框架搭建：链表与逻辑的融合
4.3 插入函数：链表拓展与哈希分布
4.4 删除函数：节点清理与空间复用
4.5 查找操作：定位效率的优化实践
4.6 功能测试：多场景验证与性能分析
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;
}
看起来没有问题，调试看看分布：
通过对监视窗口的查看，我们可以验证我们的代码正常运行的！
