哈希表的理解和实现

目录

1. 哈希的概念 (是什么)

2. 实现哈希的两种方式 (哈希函数)

2.1. 直接定址法

2.2. 除留余数法

2.2.1. 哈希冲突

3. 补充知识

3.1. 负载因子

3.2. 线性探测和二次探测

4. 闭散列实现哈希表 (开放定址法)

4.1. 开放定址法的实现框架

4.2. Xq::hash_table::insert 的实现

4.3. Xq::hash_table::find 的实现

4.4. Xq::hash_table::erase 的实现

4.5. 开放定址法实现哈希表的完整代码

5. 开散列实现哈希表 (拉链法)

5.1. 拉链法的实现框架

5.2. 哈希表扩容问题 (表的大小的设计问题)

5.3. Xq::hash_table::insert 的实现

5.4. Xq::hash_table::find 的实现

5.5. Xq::hash_table::erase 的实现

5.6. 拉链法的完整实现 (初始版本)

5.7. 解决取模操作的限制 

5.8. 拉链法的完整实现 (更新版本)

1. 哈希的概念 (是什么)

哈希也叫做散列，本质是一种映射关系，key 和存储位置建立映射（关联）关系，哈希or散列是一种思想(映射)。

2. 实现哈希的两种方式 (哈希函数)

哈希函数（Hash Function）是一种将任意长度的输入数据（也称为消息、键或原始数据）转换为固定长度的输出（哈希值或摘要）的算法。

常见的哈希函数有两种：

  • 直接定址法；
  • 除留余数法。

2.1. 直接定址法

直接定址法（Direct Addressing）也被称为确定性哈希函数（Deterministic Hash Function）。

具体来说，直接定址法会将键直接映射到索引值上，不需要进行任何复杂的计算或处理。

比如下面这个例子：

我们要将 a 数组中的元素全部映射到这张表中， 比如，你是2，我就映射到下标为2的空间中；如果你是0，我就映射到下标为0的地址空间中。

可以看到， 直接定址法的基本思想就是，将键的某个属性或组合 (比如这里键自身的值) 作为索引来直接访问哈希表的特定位置。这样一来，每个键都会与唯一的索引位置相对应，即映射关系是唯一的。

直接定址法的优点：

  • 插入和查找操作的时间复杂度为 O(1)；
  • 不存在哈希冲突 (因为映射关系是唯一的)。

但是直接定址法在某些场景下会暴露它的缺点，比如，如下场景：

可以看到，我要映射的数据不过寥寥几个，但由于数据波动范围非常大，同时，直接定址法要求映射关系唯一，换言之，此时映射的这张表的空间就需要非常大，但由于数据非常少，导致空间利用率极低。

因此，我们对直接定址法的总结：

  • 直接定址法，简单高效，查找和插入的时间复杂度为 O(1)；
  • 因为直接定址法要求映射关系唯一，故不存在哈希冲突；
  • 也正因为直接定址法要求映射关系唯一，对于波动范围比较大的数据，可能会导致空间消耗过大，且空间利用率低；

因此直接定址法的应用场景是非常局限的：只适用于关键字的波动范围比较小的场景，对于波动范围比较大的场景，直接定址法不适用，因此人们提出了除留余数法。

2.2. 除留余数法

除留余数法（Division Method）是一种常见的哈希函数处理方法，用于将输入键映射到哈希表中的索引位置。

除留余数法的基本思想是，将输入键模 (%) 一个特定的数（通常是哈希表的大小），得到余数作为最终的哈希值或索引位置。

具体来说，除留余数法的步骤如下：

  • 1. 选择一个用于取模的常数，通常为一个较大的素数，例如哈希表的大小；
  • 2. 对于给定的键，使用取模 (%) 运算将其除以选择的常数；
  • 3. 得到的余数作为最终的哈希值或索引位置。

例如，下面这种情况，现在有一个数组 {23, 45, 11, 57, 36}，同时，哈希表的大小为10。

按照除留余数法的步骤：

  1. 选择一个用于取模的常数，在这里就是 10；
  2. Hash(key) = key % 10；
  3. Hash(Key) 作为最终的哈希值。

具体如下：

我们发现，上面的数据都可以对应到一个独特的位置，因此查找的时候，我们可以根据同样的方式查找这个数是不是存在。

但是，如果我现在还要继续插入25这个元素，会发生什么问题呢？

我们发现，Hash(25) % 10 = 5，可是 5 这个位置已经被占用了啊，那该怎么办呢？

首先，我们将这种情况称之为哈希冲突/哈希碰撞，即不同的关键字映射到了哈希表的同一个位置。

2.2.1. 哈希冲突

哈希冲突（Hash Collision）或者称之为哈希碰撞，它是指不同的键（Key）被哈希函数映射到相同的哈希值（Hash Value）或哈希表（Hash Table）的同一个位置的情况。

在哈希结构中，哈希函数将键映射到固定长度的哈希值或索引位置。由于哈希函数的输出空间通常要比键的输入空间小得多，因此不同的键可能会产生相同的哈希值。

解决哈希冲突的常见方法包括：

  • 1. 开放寻址法（Open Addressing）：开放寻址法也称之为闭散列 ，在哈希表的冲突位置寻找下一个可用的空槽来存储键值对。常见的开放寻址方法包括线性探测、二次探索等；
  • 2. 拉链法(哈希桶)：拉链法也称之为开散列，在哈希表的每个索引位置上维护一个单链表，将具有相同哈希值的键值对存储在链表中。在插入、查找或删除时，根据哈希值找到对应的链表，然后在链表中进行操作；
  • 3. 增加哈希函数的复杂度：通过改变哈希函数的设计，可以尽量减少哈希冲突的发生。例如，使用更复杂的哈希函数算法、增加哈希表的大小等。

接下来，我们就要以除留余数法为基本思想实现哈希表 (直接定址法实现哈希表价值不大)，由于除留余数法的映射关系并不唯一，因此会有哈希冲突，而我们为了解决哈希冲突，选择两个方案解决，分别是：

  • 闭散列，即开放定址法；
  • 开散列，即拉链法。 

3. 补充知识

3.1. 负载因子

负载因子（load factor）是指哈希表中已经存储的有效元素数量与哈希表总大小之间的比率。它可以用来衡量哈希表的装填程度或密度。

一般情况下，负载因子的计算公式：

  • 负载因子 = 已存储的有效元素个数 / 哈希表大小；

在哈希表中，负载因子的数值范围通常为 0 到 1 之间：

  • 负载因子越接近 1，表示哈希表中存储的有效元素越多，装填程度越高，哈希冲突的概率也就越高，空间利用率高；
  • 负载因子越接近 0，表示哈希表中存储的有效元素较少，装填程度较低，哈希冲突的概率也就越低，空间利用率低。

从这里应该可以看出，负载因子不可太大，也不可太小，而应该适中。

一般来说，负载因子会有一个阈值（例如 0.7 或 0.8）时，我们通常会考虑对哈希表进行扩容操作，以保持合理的负载因子。

总而言之，较低的负载因子可以提供较好的性能，但会占用更多的内存空间；较高的负载因子则可以节省内存空间，但可能会带来更多的哈希冲突和性能下降。

3.2. 线性探测和二次探测

线性探测（Linear Probing）是一种常见的解决哈希冲突的方法，用于处理哈希表中的元素冲突问题。

当发生哈希冲突时，线性探测会尝试在哈希表中找到下一个可用的位置来存储冲突的元素。具体的操作是，如果哈希表中的某个槽位已经被占用，则线性探测会依次检查下一个槽位，直到找到一个空闲的槽位，然后将元素存储在该位置。

当需要查找或删除特定元素时，也需要使用线性探测来定位目标元素所在的位置。如果目标元素不在哈希表的初始位置上，线性探测会按照相同的方式，依次检查下一个槽位，直到找到目标元素或遇到空槽位。

线性探测的优点是实现简单，不需要维护额外的数据结构。然而，线性探测也有一些限制。当装填因子较高时，线性探测容易引发聚集现象，即一些相邻聚集位置连续冲突，可能形成 "踩踏" ，导致哈希表的性能下降。此外，线性探测也可能导致元素的聚集在表的一侧，造成不均匀的分布。

为了克服线性探测的缺点，还有其他的解决冲突方法，如二次探测等，二次探测，缓解线性探测的 "踩踏" ，在实际运用中，可以根据具体的场景和需求选择适合的解决方案。

  • 线性探测：pos++；
  • 二次探测：pos + i ^ 2； 

4. 闭散列实现哈希表 (开放定址法)

4.1. 开放定址法的实现框架

在实现闭散列之前，我们需要讨论一个问题：

如何判定一个位置是否有值呢？ 当某个位置存在值的同时，如何判定这个值是否有效呢？

因为，除留余数法的映射关系并不唯一，存在哈希冲突，而闭散列解决哈希冲突，是通过线性探测或者二次探测，而探测是需要找一个空位置，此时就需要判定，某个位置是否有值，  且这个值是否有效。

事实上，对于一个位置无非就三种情况：

  • 存在有效值；
  • 存在无效值 (该位置的值已被删除)；
  • 不存在值 (该位置没有被赋值过)；

我们的解决方案是，通过枚举解决，如下：

enum state
{EXIST, // (存在有效值)EMPTY, // 存在无效值 (该位置的值已被删除)DELETE // 不存在值 (该位置没有被赋值过)；
};

正因为要区分位置的状态，而哈希表有存储相应的值，故哈希表的数据应该是一个自定义类型，将状态和值封装起来，如下：

template<class K, class V>
struct hash_data
{std::pair<K, V> _kv;state _st;hash_data(const std::pair<K, V>& kv = std::pair<K, V>()):_kv(kv), _st(EMPTY){}
};

同时，为了获得负载因子，我们需要保存有效元素的个数。

有了上面，我们的哈希表的框架如下：

namespace Xq
{template<class K, class V>class hash_table{private:typedef hash_data<K, V> Node;public:bool insert(const std::pair<K, V>& kv) {}bool find(const K& key) {}bool erase(const K& key) {}private:std::vector<Node> _table;size_t _size;   // 有效元素个数};
}

4.2. Xq::hash_table::insert 的实现

首先，暂不考虑扩容和去重问题，如何实现 insert 呢？

bool insert(const std::pair<K, V>& kv)
{// 除留余数法, 计算位置// 注意：这里不能模capacity, 因为 vector 的 operator[] 会强制见检查 pos < size()// 因此实际中, 最好让 size == capacity, 即开空间 or 扩容用 resize 即可.size_t pos = kv.first % _table.size();// 如果这个位置已经有值了, 说明出现了哈希冲突, 在这里采用线性探测// 线性探测: 当发生哈希冲突的位置开始，依次向后探测，直到寻找到下一个空位置(没有被占用的位置)while (_table[pos]._st == EXIST){++pos;// 如果 pos 走到了表的结尾, 让 pos 回到表的开始 if (pos == _table.size())pos = 0;}_table[pos]._kv = kv;_table[pos]._st = EXIST;++_size;return true;
}

当处理完上面的逻辑后，我们需要考虑扩容问题：

void broaden_capacity(size_t new_size)
{// 在这里重新构造一个哈希表，复用inserthash_table<K, V> new_table;new_table._table.resize(new_size);for (size_t i = 0; i < _table.size(); ++i){if (_table[i]._st == EXIST){new_table.insert(_table[i]._kv);}}//更新完数据后,交换新表和旧表std::swap(new_table._table, _table);// 新表出了函数作用域, 自动调用析构, 释放资源. 
}bool insert(const std::pair<K, V>& kv)
{// 去重if (find(kv.first))  return false;// 处理扩容// 空表或者负载因子大于等于0.7进行扩容// 扩容不可以将数据直接拷贝下来, 因为扩容后, 原来的映射关系会受到影响 (表的大小改变)// 此时需要重新映射, 将旧表的数据重新映射到新表, 因此, // 哈希表的扩容代价是很大的，比 vector 的扩容代价还大if (_table.size() == 0 || _size * 10 / _table.size() >= 7){size_t new_size = _table.size() == 0 ? 10 : 2 * _table.size();broaden_capacity(new_size);}// 插入数据逻辑, 在这里省略. 
}

当处理完这个问题，此时我们还需要考虑去重问题，解决方案很简单，写一个 find， 如果这个 Key 已经存在，不插入即可，如下：

bool insert(const std::pair<K, V>& kv)
{// 去重if (find(kv.first))  return false;// 处理扩容逻辑, 省略// 插入数据逻辑, 省略.return true;
}

4.3. Xq::hash_table::find 的实现

find 的处理逻辑很简单：

  1. 如果表为空，直接返回fasle；
  2. 如果表不为空：
    1. 计算这个 key 的初始位置；
    2. 如果当前位置没有，线性探测下一个位置；
    3. 如果在线性探测过程中，某个位置的状态为 EMPTY，说明没有这个值，返回 false；
    4. 如果走到表的结尾，回到表的开始；
    5. 如果走到了初始位置，代表没有这个值，返回 false。

实现如下：

bool find(const K& key)
{// 如果没有数据,直接返回falseif (_size == 0) return false;size_t pos = key % _table.size();size_t start = pos;// 如果走到空,说明没有这个值while (_table[pos]._st != EMPTY){if (_table[pos]._kv.first == key){return true;}++pos;if (pos == _table.size())pos = 0;// 遍历了一圈也没找到,说明不存在,避免死循环if (pos == start)return false;}return false;
}

4.4. Xq::hash_table::erase 的实现

由于我们对哈希表的每个位置都设置了状态，因此，删除就很简单了，只需要将某个位置的状态设置为 DELETE 即可，实现如下：

bool erase(const K& key)
{// 如果目标 key 不存在, 返回false即可if (_size == 0 || !find(key)) return false;// 如果目标 key 存在, 只需要将目标位置的状态置为DELETE即可size_t pos = key % _table.size();// 由于存储元素是线性探测的方式存储的, 因此删除也需要按照线性探测的方式查找while (_table[pos]._kv.first != key){++pos;if (pos == _table.size())pos = 0;}// 将目标 key 所在的位置的状态置为 DELETE_table[pos]._st = DELETE;// 并--有效元素的个数--_size;return true;
}

4.5. 开放定址法实现哈希表的完整代码

namespace Xq
{// 用三种状态标记哈希表的每个空间的情况enum state{EXIST, // (存在有效值)EMPTY, // 存在无效值 (该位置的值已被删除)DELETE // 不存在值 (该位置没有被赋值过)；};template<class K, class V>struct hash_data{std::pair<K, V> _kv;state _st;hash_data(const std::pair<K, V>& kv = std::pair<K, V>()):_kv(kv), _st(EMPTY){}};template<class K, class V>class hash_table{private:typedef hash_data<K, V> Node;public:hash_table() :_size(0){}void broaden_capacity(size_t new_size){// 在这里重新构造一个哈希表，复用inserthash_table<K, V> new_table;new_table._table.resize(new_size);for (size_t i = 0; i < _table.size(); ++i){if (_table[i]._st == EXIST){new_table.insert(_table[i]._kv);}}//更新完数据后,交换新表和旧表std::swap(new_table._table, _table);// 新表出了函数作用域, 自动调用析构, 释放资源. }bool insert(const std::pair<K, V>& kv){// 去重if (find(kv.first))  return false;// 处理扩容// 空表或者负载因子大于等于0.7进行扩容// 扩容不可以将数据直接拷贝下来, 因为扩容后, 原来的映射关系会受到影响 (表的大小改变)// 此时需要重新映射, 将旧表的数据重新映射到新表, 因此, // 哈希表的扩容代价是很大的，比 vector 的扩容代价还大if (_table.size() == 0 || _size * 10 / _table.size() >= 7){size_t new_size = _table.size() == 0 ? 10 : 2 * _table.size();broaden_capacity(new_size);}// 除留余数法, 计算位置// 注意：这里不能模capacity, 因为 vector 的 operator[] 会强制见检查 pos < size()// 因此实际中, 最好让 size == capacity, 即开空间 or 扩容用 resize 即可.size_t pos = kv.first % _table.size();// 如果这个位置已经有值了, 说明出现了哈希冲突, 在这里采用线性探测// 线性探测: 当发生哈希冲突的位置开始，依次向后探测，直到寻找到下一个空位置(没有被占用的位置)while (_table[pos]._st == EXIST){++pos;// 如果 pos 走到了表的结尾, 让 pos 回到表的开始 if (pos == _table.size())pos = 0;}_table[pos]._kv = kv;_table[pos]._st = EXIST;++_size;return true;}bool find(const K& key){// 如果没有数据,直接返回falseif (_size == 0) return false;size_t pos = key % _table.size();size_t start = pos;// 如果走到空,说明没有这个值while (_table[pos]._st != EMPTY){if (_table[pos]._kv.first == key){return true;}++pos;if (pos == _table.size())pos = 0;// 遍历了一圈也没找到,说明不存在,避免死循环if (pos == start)return false;}return false;}bool erase(const K& key){// 如果目标 key 不存在, 返回false即可if (_size == 0 || !find(key)) return false;// 如果目标 key 存在, 只需要将目标位置的状态置为DELETE即可size_t pos = key % _table.size();// 由于存储元素是线性探测的方式存储的, 因此删除也需要按照线性探测的方式查找while (_table[pos]._kv.first != key){++pos;if (pos == _table.size())pos = 0;}// 将目标 key 所在的位置的状态置为 DELETE_table[pos]._st = DELETE;// 并--有效元素的个数--_size;return true;}private:std::vector<Node> _table;size_t _size;   // 有效元素个数};
}

5. 开散列实现哈希表 (拉链法)

拉链法实现哈希表，是如何解决哈希冲突的呢？

拉链法实现的哈希表也称之为哈希桶，本质上是哈希表中每个位置中存储的并不仅仅是一个节点，而是一个单链表，当产生哈希冲突时，就会将相同位置的节点链入到一个链表中，如下所示：

5.1. 拉链法的实现框架

#pragma once
#include <iostream>
#include <utility>
#include <vector>namespace Xq
{template<class K, class V>struct hash_table_node{struct hash_table_node<K, V>* _next;std::pair<K, V> _kv;hash_table_node(const std::pair<K, V>& kv = std::pair<K, V>()):_kv(kv), _next(nullptr){}};template <class K, class V>class hash_table{private:typedef hash_table_node<K, V> Node;public:hash_table() :_size(0){}bool insert(const std::pair<K, V>& kv) {}Node* find(const K& key) {}bool erase(const K& key) {}private:std::vector<Node*> _table;size_t _size;  // 存储有效数据的个数};
}

5.2. 哈希表扩容问题 (表的大小的设计问题)

在闭散列中实现哈希表时，我们所用的哈希表的初始大小为10，且后续扩容是以2倍的方式进行的，但我们在直接说过，由于除留余数法存在哈希冲突，故为了减少哈希冲突，人们发现，如果表的大小为一个素数，就会减小哈希冲突的可能。

同时，我们可以看看 SGI-STL 版本的哈希表如何处理表的大小的问题的，如下：

可以发现，STL 中哈希表的大小都是一个素数，我们也照葫芦画瓢，如下：

#pragma once
#include <iostream>
#include <utility>
#include <vector>namespace Xq
{template<class K, class V>struct hash_table_node{// 省略 ...};template <class K, class V>class hash_table{private:typedef hash_table_node<K, V> Node;static const size_t _table_size = 28;    // 静态数组的大小static const size_t _table_count_arr[_table_size];    // 哈希表的大小(每个都是素数)public:hash_table() :_size(0){}bool insert(const std::pair<K, V>& kv) {}Node* find(const K& key) {}bool erase(const K& key) {}private:std::vector<Node*> _table;size_t _size;  // 存储有效数据的个数};template<class K, class V>const size_t hash_table<K, V>::_table_count_arr[hash_table<K, V>::_table_size] =      // 哈希表的大小(每个都是素数){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};
}

因为扩容需要得到新的表的大小，故我们写一个接口，用于获取哈希表新的大小，如下： 

// 用来获取下一次扩容后的表的大小
size_t get_prime_size(size_t size)
{for (size_t i = 0; i < _table_size; ++i){if (i == 28) break;if (_table_count_arr[i] > size)return _table_count_arr[i];}return -1;
}

5.3. Xq::hash_table::insert 的实现

分三个大致逻辑：

  • 插入数据 (头插)；
  • 扩容；
  • 去重。

实现如下：

bool insert(const std::pair<K, V>& kv)
{// 去重逻辑if (find(kv.first)) return false;// 扩容逻辑// 空表或者负载因子>=1 进行扩容if (_table.size() == 0 || _size * 10 / _table.size() >= 10){// 创建新表std::vector<Node*> new_table;// 获得新表的大小new_table.resize(get_prime_size(_table.size()), nullptr);// 将旧表的有效节点摘下来, 头插到新表for (size_t i = 0; i < _table.size(); ++i){// 如果当前位置有节点, 不为空// 那么保存下一个节点, 并获取当前节点在新表的位置, 链入到新表中// 遍历下一个节点while (_table[i]){Node* next = _table[i]->_next;size_t pos = _table[i]->_kv.first % new_table.size();_table[i]->_next = new_table[pos];new_table[pos] = _table[i];_table[i] = next;}}// 交换两个表,扩容结束std::swap(_table, new_table);}// 插入数据逻辑size_t pos = kv.first % _table.size();Node* newnode = new Node(kv);// 这里采用头插, 因为是单链表, 时间复杂度为 O(1)newnode->_next = _table[pos];_table[pos] = newnode;++_size;return true;
}

5.4. Xq::hash_table::find 的实现

Node* find(const K& key)
{// 空表, 直接返回空if (_size == 0) return nullptr;// 非空表, 计算目标位置size_t obj_pos = key % _table.size();// 搜索这个单链表Node* cur = _table[obj_pos];while (cur){if (cur->_kv.first == key)return cur;cur = cur->_next;}return nullptr;
}

5.5. Xq::hash_table::erase 的实现

事实上，这里就是一个单链表的删除，代码如下：

bool erase(const K& key)
{if (!find(key) || _size == 0) return false;size_t pos = key % _table.size();//头删Node* cur = _table[pos];if (cur->_kv.first == key){Node* next = cur->_next;delete cur;_table[pos] = next;}// !头删else{while (cur->_next->_kv.first != key){cur = cur->_next;}Node* next = cur->_next->_next;delete cur->_next;cur->_next = next;}--_size;return true;
}

5.6. 拉链法的完整实现 (初始版本)

#pragma once
#include <iostream>
#include <utility>
#include <vector>namespace Xq
{template<class K, class V>struct hash_table_node{struct hash_table_node<K, V>* _next;std::pair<K, V> _kv;hash_table_node(const std::pair<K, V>& kv = std::pair<K, V>()):_kv(kv), _next(nullptr){}};template <class K, class V>class hash_table{private:typedef hash_table_node<K, V> Node;static const size_t _table_size = 28;    // 静态数组的大小static const size_t _table_count_arr[_table_size];    // 哈希表的大小(每个都是素数)public:hash_table() :_size(0){}// 用来获取下一次扩容后的表的大小size_t get_prime_size(size_t size){for (size_t i = 0; i < _table_size; ++i){if (i == 28) break;if (_table_count_arr[i] > size)return _table_count_arr[i];}return -1;}bool insert(const std::pair<K, V>& kv){// 去重逻辑if (find(kv.first)) return false;// 扩容逻辑// 空表或者负载因子>=1 进行扩容if (_table.size() == 0 || _size * 10 / _table.size() >= 10){// 创建新表std::vector<Node*> new_table;// 获得新表的大小new_table.resize(get_prime_size(_table.size()), nullptr);// 将旧表的有效节点摘下来, 头插到新表for (size_t i = 0; i < _table.size(); ++i){// 如果当前位置有节点, 不为空// 那么保存下一个节点, 并获取当前节点在新表的位置, 链入到新表中// 遍历下一个节点while (_table[i]){Node* next = _table[i]->_next;size_t pos = _table[i]->_kv.first % new_table.size();_table[i]->_next = new_table[pos];new_table[pos] = _table[i];_table[i] = next;}}// 交换两个表,扩容结束std::swap(_table, new_table);}// 插入数据逻辑size_t pos = kv.first % _table.size();Node* newnode = new Node(kv);newnode->_next = _table[pos];_table[pos] = newnode;++_size;return true;}Node* find(const K& key){// 空表, 直接返回空if (_size == 0) return nullptr;// 非空表, 计算目标位置size_t obj_pos = key % _table.size();// 搜索这个单链表Node* cur = _table[obj_pos];while (cur){if (cur->_kv.first == key)return cur;cur = cur->_next;}return nullptr;}bool erase(const K& key){if (!find(key) || _size == 0) return false;size_t pos = key % _table.size();//头删Node* cur = _table[pos];if (cur->_kv.first == key){Node* next = cur->_next;delete cur;_table[pos] = next;}// !头删else{while (cur->_next->_kv.first != key){cur = cur->_next;}Node* next = cur->_next->_next;delete cur->_next;cur->_next = next;}--_size;return true;}private:std::vector<Node*> _table;size_t _size;  // 存储有效数据的个数};// 哈希表的大小(每个都是素数)template<class K, class V>const size_t hash_table<K, V>::_table_count_arr[hash_table<K, V>::_table_size] =      {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};
}

5.7. 解决取模操作的限制 

上面的代码，存在问题，假如此时的这个K是一个 string，那么会带来什么样的问题呢？

如下 demo ：

void Test1(void)
{std::string str[] = { "老虎", "狮子", "大熊猫", "长颈鹿", "孔雀" };srand((unsigned int)time(nullptr));Xq::hash_table<std::string, int> my_hash;for (size_t i = 0; i < 10; ++i){std::string tmp = str[rand() % 5];Xq::hash_table_node<std::string, int>* ret = my_hash.find(tmp);// 如果该动物没存在,就插入map中,并将Value赋值为1if (!ret)my_hash.insert(std::make_pair(tmp, 1));// 如果该动物存在,将Value值++即可else++ret->_kv.second;}
}

现象如下：

因为此时的 key 是一个 string， 而默认情况下， string 是不支持取模操作的，故编译报错，如何解决？ 

我们需要利用仿函数和特化机制，让哈希表具有一种功能，能够让特定的类型支持取模操作，在这里，具体操作就是，让哈希表这个类模板具有第三个模板参数，这个模板参数是一个仿函数类型，通过这个仿函数，让特定类型支持取模操作，如下：

// hash_func这个仿函数的主要目的: 将 key 转换为 size_t, 以便于支持取模操作
template<class K>
struct hash_func
{size_t operator()(const K& key){return (size_t)key;}
};// 例如在这里,string默认是不可以进行取模运算的
// 因此在这里利用类模板的特化,针对string特殊处理
template<>
struct hash_func<std::string>
{size_t operator()(const std::string& str){size_t ret = 0;for (auto ch : str){ret *= 131;ret += ch;}return ret;}
};template <class K, class V, class Hash = hash_func<K>>
class hash_table {};

可以看到，上面的代码中，当我们需要将一个 string  类型的 key 转为整形的时候，我们会让其每个字符乘等于131，这是为什么呢？

首先，我们将 string 类的 key 转化为整形的目的是：为了让其可以进行取模，但是如果是以下场景：

  • string str1 = "ate";
  • string str2 = "eat";

我们可以发现，如果我们让其的每个字符直接进行相加求和，那么带来的问题就是它们最后结果是一致的，那么就会带来增大哈希冲突的可能性，因此为了减少哈希冲突，将其每个字符都 *= 131，至于这里为什么是 131，原因如下：

  • 131是一个较大的质数，质数具有较好的散列性质，可以减少哈希冲突的概率。

有了这个模板参数 (Hash)，未来哈希表只要涉及到取模操作，都需要让 key 通过这个仿函数进行取模，在这里只演示 insert 如下：

bool insert(const std::pair<K, V>& kv)
{if (find(kv.first)) return false;// #####################################################// 实例化这个仿函数对象Hash hash_func;// #####################################################if (_table.size() == 0 || _size * 10 / _table.size() >= 10){std::vector<Node*> new_table;new_table.resize(get_prime_size(_table.size()), nullptr);for (size_t i = 0; i < _table.size(); ++i){while (_table[i]){Node* next = _table[i]->_next;// #####################################################// 只要涉及到取模操作, 都需要通过这个模板参数size_t pos = hash_func(_table[i]->_kv.first) % new_table.size();// #####################################################_table[i]->_next = new_table[pos];new_table[pos] = _table[i];_table[i] = next;}}std::swap(_table, new_table);}// #####################################################// 只要涉及到取模操作, 都需要通过这个模板参数size_t pos = hash_func(kv.first) % _table.size();// #####################################################Node* newnode = new Node(kv);newnode->_next = _table[pos];_table[pos] = newnode;++_size;return true;
}

5.8. 拉链法的完整实现 (更新版本)

#pragma once
#include <iostream>
#include <utility>
#include <vector>namespace Xq
{template<class K, class V>struct hash_table_node{struct hash_table_node<K, V>* _next;std::pair<K, V> _kv;hash_table_node(const std::pair<K, V>& kv = std::pair<K, V>()):_kv(kv), _next(nullptr){}};// hash_func这个仿函数的主要目的: 将 key 转换为 size_t, 以便于支持取模操作template<class K>struct hash_func{size_t operator()(const K& key){return (size_t)key;}};// 例如在这里,string默认是不可以进行取模运算的// 因此在这里利用类模板的特化,针对string特殊处理template<>struct hash_func<std::string>{size_t operator()(const std::string& str){size_t ret = 0;// 具体这里为什么要乘于131,请看解释(1)for (auto ch : str){ret *= 131;ret += ch;}return ret;}};template <class K, class V, class Hash = hash_func<K>>class hash_table{private:typedef hash_table_node<K, V> Node;static const size_t _table_size = 28;    // 静态数组的大小static const size_t _table_count_arr[_table_size];    // 哈希表的大小(每个都是素数)public:hash_table() :_size(0){}// 用来获取下一次扩容后的表的大小size_t get_prime_size(size_t size){for (size_t i = 0; i < _table_size; ++i){if (i == 28) break;if (_table_count_arr[i] > size)return _table_count_arr[i];}return -1;}bool insert(const std::pair<K, V>& kv){// 去重逻辑if (find(kv.first)) return false;// 实例化这个仿函数对象Hash hash_func;// 扩容逻辑// 空表或者负载因子>=1 进行扩容if (_table.size() == 0 || _size * 10 / _table.size() >= 10){// 创建新表std::vector<Node*> new_table;// 获得新表的大小new_table.resize(get_prime_size(_table.size()), nullptr);// 将旧表的有效节点摘下来, 头插到新表for (size_t i = 0; i < _table.size(); ++i){// 如果当前位置有节点, 不为空// 那么保存下一个节点, 并获取当前节点在新表的位置, 链入到新表中// 遍历下一个节点while (_table[i]){Node* next = _table[i]->_next;// 只要涉及到取模操作, 都需要通过这个模板参数size_t pos = hash_func(_table[i]->_kv.first) % new_table.size();_table[i]->_next = new_table[pos];new_table[pos] = _table[i];_table[i] = next;}}// 交换两个表,扩容结束std::swap(_table, new_table);}// 插入数据逻辑// 只要涉及到取模操作, 都需要通过这个模板参数size_t pos = hash_func(kv.first) % _table.size();Node* newnode = new Node(kv);newnode->_next = _table[pos];_table[pos] = newnode;++_size;return true;}Node* find(const K& key){Hash hash_func;// 空表, 直接返回空if (_size == 0) return nullptr;// 非空表, 计算目标位置size_t obj_pos = hash_func(key) % _table.size();// 搜索这个单链表Node* cur = _table[obj_pos];while (cur){if (cur->_kv.first == key)return cur;cur = cur->_next;}return nullptr;}bool erase(const K& key){Hash hash_func;if (!find(key) || _size == 0) return false;size_t pos = hash_func(key) % _table.size();//头删Node* cur = _table[pos];if (cur->_kv.first == key){Node* next = cur->_next;delete cur;_table[pos] = next;}// !头删else{while (cur->_next->_kv.first != key){cur = cur->_next;}Node* next = cur->_next->_next;delete cur->_next;cur->_next = next;}--_size;return true;}private:std::vector<Node*> _table;size_t _size;  // 存储有效数据的个数};// 哈希表的大小(每个都是素数)template<class K, class V, class Hash = hash_func<K>>const size_t hash_table<K, V, Hash>::_table_count_arr[hash_table<K, V, Hash>::_table_size] ={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};
}

下篇博客，我们就要讨论哈希表的封装，即 unordered_set 和 unordered_map。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/328677.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

今天遇到一个GPT解决不了的问题

今天遇到一个GPT解决不了的问题

问题描述 你好&#xff0c;postman的一个post请求&#xff0c;编辑器里面放了一个很长的json数据&#xff0c;报Tokenization is skipped for long lines for performance reasons. This can be configured via editor.maxTokenizationLineLength.&#xff0c;但是同样的数据&a…
阅读更多...
家用充电桩远程监控安全管理系统解决方案

家用充电桩远程监控安全管理系统解决方案

家用充电桩远程监控安全管理系统解决方案 在当今电动汽车日益普及的背景下&#xff0c;家用充电桩的安全管理成为了广大车主关注的重点问题。为了实现对充电桩的高效、精准、远程监控&#xff0c;一套完善的家用充电桩远程监控安全管理系统解决方案应运而生。本方案旨在通过先…
阅读更多...
AI 绘画神器 Fooocus 图生图：图像放大或变化、图像提示、图像重绘或扩充、反推提示词、生成参数提取、所需模型下载

AI 绘画神器 Fooocus 图生图：图像放大或变化、图像提示、图像重绘或扩充、反推提示词、生成参数提取、所需模型下载

本文收录于《AI绘画从入门到精通》专栏&#xff0c;专栏总目录&#xff1a;点这里&#xff0c;订阅后可阅读专栏内所有文章。 大家好&#xff0c;我是水滴~~ 本文讲述 Fooocus 的图生图功能&#xff0c;主要内容包括&#xff1a;图像放大或变化、图像提示、图像重绘或扩充、反推…
阅读更多...
深入理解MySQL三大日志：redo log、binlog、undo log

深入理解MySQL三大日志：redo log、binlog、undo log

前言 MySQL是一个功能强大的关系型数据库管理系统&#xff0c;它的高可靠性、高性能和易用性使得它成为众多企业和开发者的首选。在MySQL内部&#xff0c;为了保证数据的完整性、恢复能力和并发性能&#xff0c;设计了一套复杂的日志系统。其中&#xff0c;redo log、bin log和…
阅读更多...
Qt+C++串口调试工具

Qt+C++串口调试工具

程序示例精选 QtC串口调试工具 如需安装运行环境或远程调试&#xff0c;见文章底部个人QQ名片&#xff0c;由专业技术人员远程协助&#xff01; 前言 这篇博客针对《QtC串口调试工具》编写代码&#xff0c;代码整洁&#xff0c;规则&#xff0c;易读。 学习与应用推荐首选。 …
阅读更多...
Mybatis基础操作-删除

Mybatis基础操作-删除

Mybatis基础操作-删除 删除 package com.itheima.mapper;import org.apache.ibatis.annotations.Delete; import org.apache.ibatis.annotations.Mapper;Mapper //在运行时&#xff0c;会自动生成该接口的实现类对象&#xff08;代理对象&#xff09;&#xff0c;并且将该对象…
阅读更多...
Vue3知识总结-4

Vue3知识总结-4

Vue3知识总结-4 文章目录 Vue3知识总结-4插槽Slots渲染作用域默认内容具名插槽插槽中的数据传递具名插槽传递数据 组件声明周期声明周期示意图 组件生命周期的应用动态组件组件保持存活组件被卸载 异步组件依赖注入 插槽Slots 在某些场景中&#xff0c;可能想要为子组件传递一…
阅读更多...
redis中的集群模式

redis中的集群模式

主从复制、主从同步(解决高并发读的问题) 主从同步原理&#xff1a; 1.全量同步 slave&#xff08;从节点&#xff09;每次请求数据同步会带两个参数&#xff1a;replid和offset。 replid&#xff1a;第一次请求同步时&#xff0c;replid和master的replid不一样&#xff0c;这…
阅读更多...
线性系统（一）

线性系统（一）

线性系统&#xff08;一&#xff09; 1.什么是线性系统2.高斯消元法3.高斯-约旦消元法4.线性方程组解的结构 链接: 线性系统&#xff08;二&#xff09; 1.什么是线性系统 线性&#xff1a;未知数只能是一次方项 非线性: 同时&#xff0c;读者也可以通过作图来更直观地感受&…
阅读更多...
TypeScript高级类型 在鸿蒙中的使用 Partial、Required、Readonly、Pick、Record

TypeScript高级类型 在鸿蒙中的使用 Partial、Required、Readonly、Pick、Record

我的工程代码在这里&#xff0c;持续更新中 欢迎交流&#xff0c;谢谢 https://github.com/MartinLi89/WanHarmony Partial <Type> 新定义 一个类型&#xff0c;将所有属性变为可选的类. class TextTS {a: string "1"b: string "2"c: string &…
阅读更多...
即插即用篇 | YOLOv8引入轴向注意力 Axial Attention | 多维变换器中的轴向注意力

即插即用篇 | YOLOv8引入轴向注意力 Axial Attention | 多维变换器中的轴向注意力

本改进已集成到 YOLOv8-Magic 框架。 我们提出了Axial Transformers，这是一个基于自注意力的自回归模型，用于图像和其他组织为高维张量的数据。现有的自回归模型要么因高维数据的计算资源需求过大而受到限制，要么为了减少资源需求而在分布表达性或实现的便捷性上做出妥协。相…
阅读更多...
ppt通过修改幻灯片母版修改页脚

ppt通过修改幻灯片母版修改页脚

修改幻灯片母版 幻灯片母版就可以了&#xff0c;就可以修改页脚
阅读更多...
数学建模——农村公交与异构无人机协同配送优化

数学建模——农村公交与异构无人机协同配送优化

目录 1.题目 2.问题1 1. 问题建模 输入数据 ​编辑 2. 算法选择 3.数据导入 3.模型构建 1. 距离计算 2. 优化模型 具体步骤 进一步优化 1. 重新定义问题 2. 变量定义 3. 优化目标 具体步骤 再进一步优化 具体实现步骤 1. 计算距离矩阵 2. 变量定义 3. 约束…
阅读更多...
基于Django的图书管理系统

基于Django的图书管理系统

文章目录 前言一、页面展示1.登录2.前端页面3.后端页面 二、项目上传&#xff08;1&#xff09;导入数据库&#xff08;2&#xff09;导入项目&#xff08;3&#xff09;数据库密码修改&#xff08;4&#xff09;进入网站 总结 前言 本网站调用Django编写了图书管理网站&#…
阅读更多...
漫谈AI时代的手机

漫谈AI时代的手机

以chatGPT 为代表的大语言的横空出世使人们感受到AI 时代的到来&#xff0c;大语言模型技术的最大特点是机器能”懂人话“&#xff0c;”说人话“了。如同历史上任何一个革命性工具的出现一样&#xff0c;它必将对人类生活和工作产生巨大的影响。 在这里。我们不妨畅想一下啊AI…
阅读更多...
返回分类信息（带层级）

返回分类信息（带层级）

文章目录 1.前端展示分类管理信息1.目前项目架构2.启动前后端项目1.启动mysql容器2.启动后端 renren-fast3.启动前端1.界面2.用户名密码都是admin 3.创建分类管理菜单1.菜单管理 -> 新增 -> 新增目录2.刷新3.能够新增菜单的原因是前端脚手架与renren-fast后端脚手架通信&…
阅读更多...
Linux基础之僵尸进程与孤儿进程

Linux基础之僵尸进程与孤儿进程

目录 一、僵尸进程 1.1 什么是僵尸进程 1.2 为什么要有僵尸状态 1.3 观察我们的僵尸状态 1.4 关于僵尸进程的小Tip 二、孤儿进程 2.1 什么是孤儿进程 一、僵尸进程 1.1 什么是僵尸进程 在上一篇文章中&#xff0c;我们有提到过进程的死亡状态的概念&#xff0c;而我们的…
阅读更多...
国内智能搜索工具实战教程

国内智能搜索工具实战教程

大家好，我是herosunly。985院校硕士毕业，现担任算法研究员一职，热衷于机器学习算法研究与应用。曾获得阿里云天池比赛第一名，CCF比赛第二名，科大讯飞比赛第三名。拥有多项发明专利。对机器学习和深度学习拥有自己独到的见解。曾经辅导过若干个非计算机专业的学生进入到算法…
阅读更多...
c++AVL树的模拟实现

c++AVL树的模拟实现

前面对map/multimap/set/multiset进行了简单的介绍&#xff0c;在其文档介绍中发现&#xff0c;这几个容器有个 共同点是&#xff1a;其底层都是按照二叉搜索树来实现的&#xff0c;但是二叉搜索树有其自身的缺陷&#xff0c;假如往树中 插入的元素有序或者接近有序&#xff0c…
阅读更多...
k8s 二进制安装 优化架构之 部署负载均衡，加入master02

k8s 二进制安装 优化架构之 部署负载均衡，加入master02

目录 一 实验环境 二 部署 CoreDNS 1&#xff0c;所有node加载coredns.tar 镜像 2&#xff0c;在 master01 节点部署 CoreDNS 3&#xff0c; DNS 解析测试 4&#xff0c; 报错分析 5&#xff0c;重新 DNS 解析测试 三 master02 节点部署 1&#xff0…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023