C++ | 哈希表

 前言

💓 个人主页：普通young man-CSDN博客

⏩ 文章专栏：C++_普通young man的博客-CSDN博客

⏩ 本人giee:   普通小青年 (pu-tong-young-man) - Gitee.com

      若有问题 评论区见📝

🎉欢迎大家点赞👍收藏⭐文章
————————————————

---

目录

哈希表的概念

直接定址法

哈希冲突

负载因子

关键字转数字

哈希函数

        除法散列法/除留余数法

处理哈希冲突

开放定址法

线性探测

线性探测代码实现

二次探测

链地址法

扩容

链地址法代码实现

部分代码解释

1. 扩容为什么不再创建一个哈希表直接插入？扩容之后为什么要重新计算原来的位置？

2. 为什么使用头部插入而不使用尾部插入，时间复杂度？

---

哈希表的概念

unordered_map - C++ Reference

unordered_set - C++ Reference

哈希（Hash），也称作散列，是一种用于数据组织和检索的关键技术。它通过特定的哈希函数将输入数据（通常是关键字Key）映射到一个固定范围内的整数值，这个整数值通常用来指示数据存储的位置，即索引位置。这种方法使得数据查找过程变得极为高效，因为它理论上允许直接跳转到包含所需数据的确切位置，而不需要进行逐个比较。

直接定址法

用一道题目来导入：
387. 字符串中的第一个唯一字符 - 力扣（LeetCode）

class Solution {
public:
//计数排序思想int firstUniqChar(string s) {int arr[26] = {0};for(auto ch : s){// a-a = 0  b -a = 1 c-a = 2arr[ ch - 'a']++;}for(size_t i = 0;i < s.size();i++){if (arr[s[i] - 'a'] == 1)return i;}return -1;}
};

这个题如果这个题我们运用一个map做的话，就有点那一把80米的大刀去处理一个蚂蚁，这里可能有点夸张，大家理解意思就好，所以我这里采用了哈希映射的方式直接开一个数组就大大提升了效率，a的ascll是97，大家可以自己算一算。

哈希冲突

举个例子：
如果我们有一个大小为100的数组（M=100），而其中一个数值是4567，哈希函数的作用就是把这个数值转换成0到99之间的某个整数，表示它在数组中的确切位置。这样做的好处是，我们可以迅速存取任何数值，无需遍历整个数组查找特定值。关键点在于设计一个好的哈希函数，以尽量减少冲突（不同数值映射到同一位置的情况），并有效处理不可避免的冲突。

这里关键就是有两个数据会被映射在同一个位置，这里我们就把它称为哈希冲突，所以设计出很好的哈希函数，这样就可以减少哈希冲突，注意是减少，不是避免，哈希冲突是不能避免的。

负载因子

负载因子（Load Factor）是指哈希表中已存储元素数量N与哈希表总容量M的比例，计算公式为 load factor = N / M。这个比例揭示了哈希表的两个关键方面：

• 负载因子越大：意味着哈希表中的元素越多，空间利用率越高，但同时发生哈希冲突的概率也会增加。哈希冲突指的是不同的关键字通过哈希函数映射到了相同的位置。

• 负载因子越小：则表示哈希表中有更多的空闲空间，因此哈希冲突的概率较低，但这也意味着空间没有被充分利用。

例如，如果一个哈希表的容量M是100，当前存储了60个元素（N=60），那么负载因子就是0.6。这意味着该哈希表的空间利用率为60%，同时也存在一定程度的哈希冲突风险。

选择合适的负载因子对于平衡哈希表的性能非常重要。过高的负载因子会导致频繁的冲突，影响查找效率；而过低的负载因子则可能导致内存浪费。通常情况下，合理的负载因子范围是在0.7到0.8之间，但这可以根据具体应用场景进行调整。

关键字转数字

当我们讨论哈希函数时，假设所有关键字都已经转换为整数形式。这是因为哈希函数需要一个固定的、易于处理的输入格式来进行高效的计算和映射。具体来说：

整数关键字：如果关键字本身就是整数，那么我们可以直接使用它作为哈希函数的输入。
非整数关键字：对于非整数类型的关键字（如字符串、浮点数等），我们需要首先将其转换为整数。
字符串：可以通过对字符串中的每个字符编码值进行某种运算（比如累加或更复杂的算法）来生成一个整数值。BKDR哈希这个可以了解一下

哈希表之bkdrhash算法解析及扩展-CSDN博客 差不多就是一种数学的规则
浮点数：可以将其转换为整数表示，或者通过特定的算法提取出其组成部分（如指数和尾数）并转换为整数。

哈希函数

        除法散列法/除留余数法

除法散列法（除留余数法） 是一种常用的哈希函数方法，其基本思想是通过将关键字 key 除以哈希表的大小 M 并取其余数来确定存储位置。具体来说，哈希函数可以表示为：
h(key)=key%M
避免特定值的M：
当 M 是2的幂次（如16、32等），则 key % M 实际上相当于保留了 key 的最低几位（取决于 M 的大小）。例如，如果 M=16，那么 key % 16 就是 key 的最后4位二进制数。
同样地，如果 M 是10的幂次，比如 M=100，则 key % 100 相当于保留了 key 的最后两位十进制数字。
选择质数作为M：
为了避免上述问题，通常建议选择一个不太接近2的整数次幂的质数（素数）作为 M。质数能更好地分布关键字，减少冲突的可能性。
举例说明
示例1：M为2的幂次
假设 M=16(2^4)我们来看两个数值 {63, 31} 的哈希值：

对于 63：
63%16=15
二进制表示为 00111111，后4位是 1111，即15。对于 31：
31%16=15
二进制表示为 00011111，后4位也是 1111，即15。

这两个看似无关的值映射到了同一个位置，导致冲突。

示例2：M为10的幂次
假设 M=100，我们来看两个数值 {112, 12312} 的哈希值：

对于 112：
112%100=12对于 12312：
12312%100=12

这两个数值的最后两位都是 12，因此它们也映射到了同一个位置，导致冲突。

示例3：M为质数
假设 M=17（质数），我们来看相同的数值 {63, 31} 的哈希值：
 

对于 63：
63%17=12对于 31：
31%17=14

可以看到，使用质数作为 M 可以有效减少冲突。

---

Java HashMap的具体实现
Java的HashMap使用的是2的整数次幂作为 M，并通过位运算来提高效率。这种方法不是直接取模，而是通过右移操作和异或操作来计算哈希值。
在Java的HashMap中，哈希表的大小 M 是2的幂次，并且通过位运算来提高效率。例如，假设 M=2^16，则可以通过以下方式计算哈希值：

int hash = key.hashCode();
hash = (hash ^ (hash >>> 16)) & (M - 1);

这里的关键步骤是：

取 key 的哈希码。
将哈希码右移16位并与原哈希码进行异或操作，使高位和低位都参与到最终的哈希值计算中。
最后与 (M - 1) 进行按位与操作，确保结果在 [0, M) 范围内。

这边还有几种方法乘法散列法（了解），全域散列法（了解），这些方法可以去其他博客了解一下，本博客不做讲解，因为用的不多。

---

处理哈希冲突

        既然我们不能避免哈希冲突，我们就需要恰当的哈希函数方法来解决，主要有两种两种⽅法，开放定址法和链地址法。

开放定址法

        在开放定址法中所有的元素都放到哈希表⾥，当⼀个关键字key⽤哈希函数计算出的位置冲突了，则按照某种规则找到⼀个没有存储数据的位置进行存储，开放定址法中负载因⼦⼀定是小于的。这⾥的规则有三种：线性探测、⼆次探测、双重探测。

线性探测

基本概念：线性探测是一种开放定址法，用于解决哈希冲突。它通过从冲突发生的位置开始，顺序地检查（“探测”）每一个后续的位置，直到找到一个空闲槽为止。
公式：
初始哈希函数：h(key) = hash0 = key % M，这里 M 是哈希表的大小。
线性探测函数：hc(key, i) = (hash0 + i) % M，其中 i = {1, 2, 3, ..., M-1}。这表示如果初始计算的位置被占用了，则依次检查后续的位置。
负载因子：负载因子是已存入哈希表中的元素数量与哈希表大小的比例。因为负载因子小于1，所以在最坏的情况下，最多需要探测 M-1 次就能找到一个未使用的槽位。
群集/堆积问题：如果连续几个槽都被占用，那么新来的键值对将会争夺这些连续槽之后的第一个空槽，这种现象叫做群集或堆积。随着堆积的加剧，查找操作的效率会降低，因为平均来说，查找一个元素需要遍历更多的槽。

下⾯演示 {19,30,5,36,13,20,21,12} 等这⼀组值映射到M=11的表中。

h(19) = 8，h(30) = 8，h(5) = 5，h(36) = 3，h(13) = 2，h(20) = 9，h(21) = 10，h(12) = 1

线性探测代码实现

这个代码里面的质数，还有关键字转转数字我上面都说过，大家自己悟

// 质数生成函数：返回大于等于n的最小质数
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};// first 和 last 分别指向质数列表的起始和结束位置const unsigned long* first = __stl_prime_list;const unsigned long* last = __stl_prime_list + __stl_num_primes;// 使用标准库函数 lower_bound 在[first, last)范围内查找第一个不小于 n 的元素const unsigned long* pos = lower_bound(first, last, n);// 如果找到，则返回该元素；否则返回列表中最后一个元素return pos == last ? *(last - 1) : *pos;
}namespace open_address {// 状态枚举，用于标记哈希表中的槽的状态enum State{EXIST,   // 存在数据EMPTY,   // 槽为空DELETE   // 数据已被删除};// 哈希节点结构体，包含键值对和状态template<class k, class v>struct Hashnode{pair<k, v> _kv;   // 键值对State _state = EMPTY; // 默认状态为EMPTY};// 默认哈希函数模板，适用于基本类型template<class k>struct HashFun{size_t operator()(const k& key) {return (size_t)key; // 直接转换为size_t类型的数值}};// 字符串特化的哈希函数，使用BKDR算法计算哈希值template<>struct HashFun<string>{size_t operator()(const string& key) {size_t hash = 0;// 遍历字符串中的每个字符，计算哈希值for (auto it : key) {hash += it;hash *= 131;}return hash;}};// 开放地址法实现的哈希表类template<class k, class v, class Hash = HashFun<k> >class Myhashmap{public:// 构造函数，初始化哈希表Myhashmap() :_tables(__stl_next_prime(0)), // 初始化时调用__stl_next_prime获取合适的质数作为初始容量_n(0) // 初始化元素数量为0{};// 插入键值对bool Insert(const pair<k, v> kv) {if (Find(kv.first)) // 如果键已存在，返回falsereturn false;// 当负载因子达到70%时进行扩容if (_n * 10 / _tables.size() >= 7) { //*10避免小数Myhashmap<k, v, Hash> new_tables;new_tables._tables.resize(__stl_next_prime(_tables.size() + 1));// 将旧表中的数据插入到新表for (auto it : _tables) {if (it._state == EXIST) {new_tables.Insert(it._kv);}}// 交换新旧表（指针级别）_tables.swap(new_tables._tables);}Hash hash;// 计算初始哈希值size_t hashi0 = hash(kv.first) % _tables.size();size_t hashi = hashi0;int i = 1;// 线性探测：如果当前位置已被占用，则继续向后探测while (_tables[hashi]._state == EXIST) {hashi = (hashi0 + i) % _tables.size();i++;}// 找到空位后插入数据_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}// 查找键对应的节点Hashnode<k, v>* Find(const k& key) {Hash hash;// 计算初始哈希值size_t hashi0 = hash(key) % _tables.size();size_t hashi = hashi0;int i = 1;// 线性探测查找节点while (_tables[hashi]._state != EMPTY) {if (_tables[hashi]._kv.first == key && _tables[hashi]._state == EXIST) {return &_tables[hashi];}hashi = (hashi0 + i) % _tables.size();i++;}// 如果没有找到，返回nullptrreturn nullptr;}// 删除键对应的节点bool Erase(const k& key) {Hashnode<k, v>* ret = Find(key);if (ret) {// 标记该位置为DELETE，允许后续插入覆盖ret->_state = DELETE;return true;} else {return false;}}private:vector<Hashnode<k, v>> _tables; // 存储哈希节点的数组size_t _n; // 当前存储的元素数量};
}

---

二次探测

• 初始哈希函数：h(key) = hash0 = key % M
• 二次探测公式：
  • 正向探测：hc(key, i) = (hash0 + i^2) % M
  • 负向探测：hc(key, i) = (hash0 - i^2) % M，如果结果小于0，则需要加上 M 来回绕到哈希表尾部。

简单说二次探测就是在原位按i^2探测知道探测到空位或则删除位

假设我们有一组值 {19, 30, 52, 63, 11, 22}，并且哈希表的大小 M=11M=11。我们将使用二次探测方法将这些值插入哈希表中。

h(19) = 8, h(30) = 8, h(52) = 8, h(63) = 8, h(11) = 0, h(22) = 0

---

链地址法

        链地址法（也称为拉链法或哈希桶）是一种用于解决哈希表中键冲突的方法。其基本思想是通过将所有映射到同一个哈希位置的元素链接在一起，形成一个链表或其他动态数据结构（如平衡树）。这样，即使多个键值映射到了同一个哈希位置，也能有效地存储和检索这些值。

下⾯演示 {19,30,5,36,13,20,21,12,24,96} 等这⼀组值映射到M=11的表中：

h(19) = 8，h(30) = 8，h(5) = 5，h(36) = 3，h(13) = 2，h(20) = 9，h(21) = 10，h(12) = 1,h(24) = 2,h(96) = 88

扩容

负载因子（Load Factor）是衡量哈希表中元素填充程度的一个指标，定义为已存储元素数量除以哈希表的容量（桶的数量）。不同的冲突解决方法对负载因子有不同的要求：

• 开放定址法：负载因子必须小于1，因为每个位置只能存储一个元素或标记为空/删除状态。当负载因子接近1时，冲突的概率会显著增加，查找、插入和删除操作的效率也会下降。因此，通常会在负载因子达到某个阈值（如0.7）时进行扩容。

• 链地址法：理论上没有负载因子的限制，因为它可以通过链表或其它动态数据结构来存储多个元素。然而，过高的负载因子会导致链表变长，从而影响查找效率。为了保持较高的性能，实际应用中仍然会对负载因子加以控制，例如将最大负载因子设定为1，并在超过该值时进行扩容。

处理极端场景

即使有良好的负载因子管理和扩容机制，某些情况下仍可能出现单个桶特别长的情况，这会影响查找效率。以下是几种处理这种极端情况的方法：

1. 全域散列法：通过使用一组独立的哈希函数，从一个固定的哈希函数族中随机选择一个函数来计算哈希值。这样可以减少被特定输入“针对”的可能性，降低冲突概率。不过，这种方法并不能完全避免极端情况的发生。

2. 转换为更高效的数据结构：

   • 红黑树：Java 8中的HashMap采用了这一策略。当某个桶中的链表长度超过一定阈值（通常是8）时，将链表转换为红黑树。红黑树是一种自平衡二叉搜索树，能够在O(log n)时间内完成查找、插入和删除操作，相比链表的O(n)时间复杂度有显著提升。

链地址法代码实现

// 链地址法实现的哈希表命名空间
namespace hash_bucket {// 仿函数模板，用于将键 k 转换为无符号整数（正数）// 这个仿函数的作用是为哈希表提供一个通用的将键转换为可用于哈希计算的值的方法template<class k>struct HashFun{// 重载 () 运算符，使得该结构体的对象可以像函数一样被调用size_t operator()(const k& key) {// 直接将键转换为无符号整数类型return (size_t)key;}};// 针对 string 类型的 HashFun 仿函数的特化版本// 因为 string 类型不能直接转换为无符号整数，所以需要专门的处理template<>struct HashFun<string>{size_t operator()(const string& key) {// 初始化哈希值为 0size_t hash = 0;// 使用 BKDR 哈希算法来计算字符串的哈希值，该算法可以有效减少哈希冲突for (auto it : key){// 将当前字符加入哈希值计算hash += it;// 乘以 131 是 BKDR 算法的一部分，有助于更好地分散哈希值hash *= 131;}return hash;}};// 哈希表节点的结构体模板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 Hash = HashFun<k> >class Myhashmap{// 重命名节点类型，方便后续使用typedef Hashnode<k, v> Node;public:// 构造函数Myhashmap() :// 初始化哈希表数组大小为 11_tables(11),// 初始化存储的元素个数为 0_n(0){};// 析构函数~Myhashmap() {// 遍历哈希表数组的每一个桶for (int i = 0; i < _tables.size(); i++){// 获取当前桶的头节点Node* cur = _tables[i];// 遍历当前桶中的所有节点while (cur){// 存储下一个节点的指针Node* next = cur->_next;// 释放当前节点的内存delete cur;// 将下一个节点赋值给 cur，继续遍历cur = next;}// 将当前桶的指针置为 nullptr_tables[i] = nullptr;}// 将存储的元素个数置为 0_n = 0;}// 拷贝构造函数Myhashmap(const Myhashmap& m1) :// 拷贝元素个数_n(m1._n),// 初始化哈希表数组大小与被拷贝对象相同_tables(m1._tables.size()){// 循环遍历被拷贝对象的每一个桶for (int i = 0; i < m1._tables.size(); i++){// 获取被拷贝对象当前桶的头节点Node* cur = m1._tables[i];// 遍历当前桶中的所有节点while (cur){// 创建一个新节点，拷贝当前节点的键值对Node* newnode = new Node(cur->_kv);// 采用头插法将新节点插入到当前桶中newnode->_next = _tables[i];_tables[i] = newnode;// 移动到被拷贝对象的下一个节点cur = cur->_next;}}}// 赋值运算符重载// 思想：利用拷贝构造函数创建一个临时对象，然后交换当前对象和临时对象的内容Myhashmap& operator=(Myhashmap tmp){// 交换哈希表数组_tables.swap(tmp._tables);// 交换元素个数std::swap(_n, tmp._n);return *this;}// 插入键值对的函数bool Insert(const pair<k, v> kv) {// 判断是否存在相同的键，如果存在则不允许插入if (Find(kv.first))return false;// 创建仿函数对象，用于计算哈希值Hash hash;// 判断是否需要扩容，扩容条件是负载因子（元素个数 / 哈希桶数）等于 1if (_tables.size() == _n){// 创建一个新的哈希表数组，大小为原数组的 2 倍vector<Node*> new_tables(_tables.size()*2);// 遍历旧的哈希表数组for (int i = 0; i < _tables.size(); i++){// 获取旧哈希表当前桶的头节点Node* cur = _tables[i];// 遍历当前桶中的所有节点while (cur){// 计算节点在新哈希表中的哈希值size_t new_hashi = hash(cur->_kv.first) % new_tables.size();// 存储当前节点的下一个节点指针Node* next = cur->_next;// 采用头插法将当前节点插入到新哈希表的对应桶中cur->_next = new_tables[new_hashi];new_tables[new_hashi] = cur;// 移动到下一个节点cur = next;}}// 交换新旧哈希表数组_tables.swap(new_tables);}// 计算新插入节点在当前哈希表中的哈希值size_t hashi = hash(kv.first) % _tables.size();// 创建一个新节点，存储要插入的键值对Node* newnode = new  Node(kv);// 采用头插法将新节点插入到当前哈希表的对应桶中newnode->_next = _tables[hashi];_tables[hashi] = newnode;// 元素个数加 1++_n;return true;}// 查找指定键的节点的函数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;}// 未找到则返回 nullptrreturn nullptr;}// 删除指定键的节点的函数bool Erase(const k& key) {// 创建仿函数对象，用于计算哈希值Hash hash;// 计算要删除节点在哈希表中的哈希值size_t hashi = hash(key) % _tables.size();// 记录前一个节点的指针，初始化为 nullptrNode* prev = nullptr;// 获取对应桶的头节点Node* cur = _tables[hashi];// 遍历当前桶中的所有节点while (cur){// 如果找到匹配的键if (cur->_kv.first == key) {// 如果要删除的是头节点if (prev == nullptr){// 将桶的头指针指向下一个节点_tables[hashi] = cur->_next;}else{// 否则将前一个节点的 next 指针指向下一个节点prev->_next = cur->_next;}// 释放要删除节点的内存delete cur;// 元素个数减 1--_n;return true;}else {// 记录当前节点为前一个节点prev = cur;// 移动到下一个节点cur = cur->_next;}}// 未找到要删除的节点，返回 falsereturn false;}private:// 存储哈希表的指针数组，每个元素是一个指向节点的指针vector<Node*> _tables;// 存储哈希表中元素的个数size_t _n = 0;};}

部分代码解释

1. 扩容为什么不再创建一个哈希表直接插入？扩容之后为什么要重新计算原来的位置？

扩容不直接创建新哈希表插入

这个请你思考一下我们的代码结构vector<Node*>,vector能自动释放，Node*不能，还有就是如果再创一个哈希直接将旧的值插入效率就会很高，如果新创建一个vector<Node*>直接把原来表的哪些桶指针指向这个新的表效率就很高，也解决了释放这个问题

虽然 vector 可以自动管理内存，但 Node* 是指针，指向动态分配的内存。如果直接将旧桶指针指向新表，会造成多个指针指向同一块内存，当析构哈希表时，会多次释放同一块内存，导致未定义行为。

2. 为什么使用头部插入而不使用尾部插入，时间复杂度？

使用头部插入的原因

在链地址法实现的哈希表中，插入元素时通常使用头部插入而不是尾部插入，主要是因为头部插入的时间复杂度较低。

• 头部插入：只需要修改两个指针的指向，即新节点的 next 指针指向原链表的头节点，然后将桶的头指针指向新节点。这个操作的时间复杂度是O(1) ，因为只涉及到常数级别的操作。

• 尾部插入：需要遍历链表找到链表的尾部节点，然后将新节点插入到尾部。在最坏情况下，链表的长度可能达到 （哈希表中元素的总数），因此尾部插入的时间复杂度是O(n) 

Node* newnode = new  Node(kv);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;