哈希闭散列的实现与机制

O(logN)，搜索的效率取决于搜索过程中元素的比较次数。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

这就是哈希思想的体现。

线性探测的实现

#pragma once
#include <utility>
#include <string>
#include <vector>using namespace std;
namespace open_address	//闭散列：开放寻址法
{enum Status{DELETE,EMPTY,EXIST};template<class K, class V>struct HashDate{pair<K, V> _data;Status _status;};//可以进行int类型的强转template<class K>struct HashFunc{size_t operator()(const K& key)		//传入键值，返回哈希值(映射到哈希表的位置)	{return size_t(key);}};//string类型template<>		//模板特化，需要保留<>struct HashFunc<string>	//特化成<string>{size_t operator()(const string& key)		//传入键值，返回哈希值(映射到哈希表的位置){// BKDRsize_t hash = 0;for (auto& e : key){hash *= 31;hash += e;}return hash;}};template<class K, class V, class HashFunc = HashFunc<K>>class HashTable{public:HashTable(){_t.resize(10);		//初始分配10个HashDate的空间_n = 0;}bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;if (n * 10 / _t.size() >= 7)	//装载因子大于70%，扩容{//开一个新表，重新映射HashTable<K, V> newtable;size_t newsize = _t.size() * 2;	newtable._t.resize(newsize);//遍历旧表，重新映射for (size_t i = 0; i < _t.size(); i++){if (_t[i]._status == EXIST){newtable.Insert(_t[i]._data);		//调用newtable的Insert}}_t.swap(newtable._t);		//交换表}		//先执行扩容，再执行插入，所以不需要++_nHashFunc hf;size_t hashi = hf(kv.first) %  _t.size();	//除留余数法求哈希值。/*要保证哈希值在0~_t.size()-1之间，即需要保证哈希值在可用空间范围之内。如果%capacity，可能导致得到的哈希值大于哈希表的最大长度？*/while (_t[hashi]._status == EXIST)		//出现碰撞，进行探测{hashi++;hashi %= _t.size();		//循环到头，重新开始,避免无限循环、越界}_t[hashi]._data = data;_t[hashi]._status = EXIST;_n++;		//键值个数+1return true;}HashDate<K, V>* Find(const K& key)	//1.要么直接找到2.要么出现冲突，再empty之前探测{HashFunc hf;size_t hashi = hf(key) % _t.size();while (_t[hashi]._status != EMPTY){if (_t[hashi]._data.first == key && _t[hashi]._status == EXIST)	//防止伪删除，不能进入DELETE状态查找return &_t[hashi];hashi++;hashi %= _t.size();		//循环到头，重新开始,避免无限循环、越界}return nullptr;}//伪删除，只是标记状态为DELETE，不释放空间bool Erase(const K& key){HashDate<K, V>* ret = Find(key);if (ret)	//存在（找不到返回空）{ret->_status = DELETE;_n--;		//键值个数-1(删除需要--_n)return true;}elsereturn false;}private:vector<HashDate<K, V>> _t;	//闭散列，存储数据size_t _n;	//键值的个数};}

代码解读

这段代码实现了一个基于开放寻址法的哈希表，以下是对代码的详细解读：

1. 命名空间和枚举定义

namespace open_address {enum Status {DELETE,EMPTY,EXIST};

• open_address 命名空间用于包含所有与开放寻址法哈希表相关的类和函数。
• Status 枚举用于表示哈希表中每个槽的状态，包括已删除（DELETE）、空（EMPTY）和存在（EXIST）。

2. 哈希表节点结构体

template<class K, class V>
struct HashDate {pair<K, V> _data;Status _status;
};

• HashDate 是一个模板结构体，用于表示哈希表中的一个节点，包含一个键值对 _data 和一个状态 _status。

3. 哈希函数模板

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;};
};

• HashFunc 是一个模板结构体，用于生成哈希值。它对 K 类型进行特化，默认实现是将键值转换为 size_t。
• 对于 string 类型，HashFunc 进行了特化，使用 BKDR 哈希算法来生成哈希值。

4. 哈希表类

template<class K, class V, class HashFunc = HashFunc<K>>
class HashTable {
public:HashTable() {_t.resize(10);_n = 0;}bool Insert(const pair<K, V>& kv) {// ...（插入逻辑）}HashDate<K, V>* Find(const K& key) {// ...（查找逻辑）}bool Erase(const K& key) {// ...（删除逻辑）}private:vector<HashDate<K, V>> _t;size_t _n;
};

• HashTable 是一个模板类，用于实现基于开放寻址法的哈希表。
• 构造函数初始化一个大小为10的 vector 来存储哈希表节点，并设置键值对数量 _n 为0。
• Insert 方法用于插入键值对，如果装载因子超过70%，则进行扩容。
• Find 方法用于查找键值对，如果找到则返回指针，否则返回 nullptr。
• Erase 方法用于删除键值对，实际上是进行伪删除，即将状态设置为 DELETE。
• 私有成员 _t 是一个 vector，用于存储哈希表节点，_n 用于记录当前键值对的数量。

5. 插入、查找和删除逻辑

• 插入逻辑中，如果找到相同的键，则返回 false。如果装载因子超过70%，则进行扩容，然后使用哈希函数找到空槽插入新节点。
• 查找逻辑中，使用哈希函数找到键对应的槽，然后进行线性探测直到找到空槽或匹配的键。
• 删除逻辑中，使用查找逻辑找到节点，然后将其状态设置为 DELETE 并减少键值对数量。

这段代码是一个简单的哈希表实现，它通过开放寻址法解决了哈希冲突，并且提供了基本的插入、查找和删除操作。

二次探测

线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题