数据结构与算法：哈希表

1.哈希表和哈希

1.1.知识引入

1.2.为什么需要哈希表呢？

2.简易的哈希表

2.1.哈希表的基础结构

2.2.如何实现基础的哈希表

2.2.1.增

2.2.2.删

2.2.3.查

2.3.泛型编程下的哈希表

3.简易的哈希桶

1.哈希表和哈希

1.1.知识引入

哈希表（Hash Table）是一种基于哈希技术实现的数据结构，它通过将键映射到存储位置来实现高效的数据访问。哈希表通常由一个数组和一个哈希函数组成。当需要插入、查找或删除数据时，通过哈希函数计算键的哈希值，并将该值作为索引在数组中查找或操作对应的数据。

哈希（Hash）是一种将数据映射到固定大小的唯一值的技术。

哈希的本质就是一种映射关系！哈希函数是实现哈希的方式！

例如：

我们可以通过取模操作将15映射到5这个数字，
我们也可以通过字符对应的ASCII值相加，将hello映射到数字532

只要实现了映射关系这样子就能称为 “哈希” ，而这种映射的实现叫做哈希函数，是使得不同的输入数据产生不同的哈希值，同时尽量减少不同输入数据产生相同哈希值的概率。

这里值得注意的是：

我们无法避免哈希值产生冲突，也就是不同的key可能对应着一样的哈希值，但是我们清楚如果过分的出现哈希值冲突，会影响哈希表的作用
我们能做到的只是优化哈希函数来尽量减少哈希冲突

1.2.为什么需要哈希表呢？

首先对于大部分的数据结构，每一次我们查找时总是无法避免遍历整个结构，这样子的效率总是会有一点点低下的，因此哈希表这个数据结构就诞生了，它的O(1)时间复杂度，高性能，可以实现多样的结构，提高实际开发的效率

高效的查找操作：通过哈希函数将键映射到数组中的位置，可以快速定位到对应的值，时间复杂度为O(1)。相比于其他数据结构如数组或链表，哈希表的查找速度更快。

快速的插入和删除操作：同样通过哈希函数定位到位置后，可以直接插入或删除对应的值，时间复杂度也是O(1)。这使得哈希表在需要频繁插入和删除元素的场景下非常高效。

空间利用率高：哈希表使用数组来存储数据，相比于其他数据结构如树，它不需要额外的指针来连接节点，因此空间利用率更高。

适用于大规模数据：哈希表在处理大规模数据时仍然能够保持较高的性能。通过合理选择哈希函数和调整数组大小，可以减少冲突的概率，提高哈希表的效率。

并且它通过将输入数据（也称为键）通过哈希函数转换成一个固定长度的哈希值（也称为散列值），并将该哈希值与存储空间进行关联。

2.简易的哈希表

2.1.哈希表的基础结构

哈希表的简易原理：

哈希表分为闭散列和开散列（哈希桶）两种结构，闭散列就是一段连续的有限空间
哈希表内对于元素位置的判断为 “空位置” “删除位置” “存在位置”
哈希表需要存在一定数量的空位置，当我们访问到空时就可以退出，当我们删除了存在的数据时，需要设置该位置为删除，如果设置为空，就会导致查找到部分就退出了
空的位置越多哈希表的效率越高，但是随之空间浪费越大，空的位置越少，哈希表的效率越低，越接近于完全遍历的数据结构，失去了哈希表的优势

那么我们就抽象出来哈希表的简易结构！

代码实现结构如下：

// 枚举类型实现哈希表节点的三种状态
enum STATUS
{EMPTY,EXIST,DELETE
};template<class K, class V>
// 定义一个哈希个体的结构体
struct HashData
{pair<K, V> _kv;STATUS _status = EMPTY;
};template<class K, class V>class HashTable
{
public:// 定义默认空间HashTable() { _table.resize(10); }// 增bool Insert(const pair<K, V>& kv) {// 具体实现}// 删bool Erase(const K& key) {// 具体实现}// 查HashData<K, V>* Find(const K& key){// 具体实现}private:// 用数组这个数据结构来存放若干个哈希节点结构体// 数组实现的哈希表vector<HashData<K, V>> _table;// 节点数size_t _num = 0;
};

2.2.如何实现基础的哈希表

这一部分我们主要是对代码进行剖析，注重理解，摸清原理，临摹一份哈希表，从增删查开始！！

2.2.1.增

基本的增加数据的实现

bool Insert(const pair<K, V>& kv)
{// 哈希函数size_t Hash_i = kv.first % _table.size();// 不为空向后走 while (_table[Hash_i]._status == EXIST){Hash_i++;// 超过capacity就取模回来Hash_i %= _table.size();}// 找到 空 或者 删除 位置可以插入_table[Hash_i]._kv = kv;_table[Hash_i]._status = EXIST;return true;
}

这一段代码中：

哈希函数的实现是通过传入的pair值的key对总的size取模，来获得位置，整体逻辑就是如果一个位置存在数据，那么我们就不能插入，需要向后走，直到找到空位置，退出循环进行插入，并返回true
当我们不断地向后遍历，发现等于数组的长度时，也就是Hash_i = 10时，这时从0下标开始重新遍历

那么简易的原理就很容易接受了，但是我们发现两个问题

如果加入大量的数据，这个大小显然是不够的，所以需要扩容
缺少了返回false的情况，这里需要引入查找这个模块，我们后面解决

对于问题一，我们首先引入一个存储哈希key个数的变量

我们在上面讲过我们需要控制哈希表中 “空” 位置的数量，一般来说我们通过负载因子来实现，随着数据的插入，num的就会增加，随之空位置数目就减少，负载因子增加，所以哈希表会设定一个负载因子的最大值，当超过这个值时，哈希表会进行扩容！！！

完整的代码如下：

bool Insert(const pair<K, V>& kv)
{// 找不到就退出if (Find(key) != nullptr)return false;// double load_fator = (double)_num / (double)_table.size();// 扩容，当负载因子lf超过0.7时 进行扩容if (_num * 10 / _table.size() == 7){HashTable<K, V> newHT;// 扩容两倍newHT._table.resize(_table.size() * 2);// 遍历旧的哈希表 // 因为扩容后，负载因子不会超过0.7 直接进入插入操作for (size_t i = 0; i < _table.size(); i++){// 将旧表的数据插入新表中if (_table[i]._status == EXIST)newHT.Insert(_table[i]._kv);}// 将新表覆盖旧表_table.swap(newHT._table);}size_t Hash_i = kv.first % _table.size();// 不为空向后走 while (_table[Hash_i]._status == EXIST){Hash_i++;// 超过capacity就取模回来Hash_i %= _table.size();}// 找到 空 或者 删除 位置可以插入_table[Hash_i]._kv = kv;_table[Hash_i]._status = EXIST;_num++;return true;}

代码逻辑：

首先我们通过Find方法来判断有没有重复的键（key），因为这里对应的是unorder_set不允许重复的键，如果找不到这个key就进行插入
当我们需要扩容时，我们通过这个负载因子进行判断，如果负载过大为了哈希表的效率，我们需要扩容，当然我们可以按照我们插入的逻辑来实现这个扩容！！！可是我们会发现原本的13%10=3，现在13%20=13，也就是插入的位置发生变化。那么我们就需要重新对这个哈希表进行调整，所以这里我们通过新增一个哈希表，间接的将数据插入到新表中，再通过交换指针来实现表的替换（本质上是代码的复用！！！）

到了这里哈希表的“增”就基本大功告成了!!!

2.2.2.删

bool Erase(const K& key)
{if (Find(key) == nullptr)return false;// 注意这里是 伪删除 （我们并没有将对应数据完全删去）HashData<K, V>* del = Find(key);del->_status = DELETE;_num--;return true;
}

没什么好说的就是在结构体数组（哈希表）找对应key结构体的地址，然后删除。值得注意的是，这里的删除我们只是修改了“状态”和减少了“key”的个数，这个位置上的数据并没有删去，再结合“增”中的逻辑：不为空就可以插入，那么这里的删除只是为了将状态从存在转为删除，是一种伪删除，目的是通过插入来实现覆盖式的插入。

2.2.3.查

查找我们需要注意：

在哪里查找
要找到什么

首先我们知道查找一个数据存不存在，肯定是访问一个结构体对象的状态是否为EXIST，但是上面我们再删除中讲了这个删除是个伪删除，也就是当我们删除了key=3这个结构体，在这个结构体数组中还会存在key=3吗？答案是会的这个结构体为 DELETE，但是key=3，所以我们需要在删除和存在中查找。

这里也体现了哈希表的特殊之处，我们之前回想一下，是不是会疑惑为什么哈希表不只设置“存在”和“空”两种状态，这样子不是更加简洁吗？首先哈希表在遍历时，遇到空就退出，如果只有“空”和“存在”

当我们删除节点43后，会发现当遍历到33时发现下一个节点为空（因为只有“空”和“存在”），那么就会退出。具体一点当我们查找key=53时，Hash_i=3，也就是从下标为3开始判断，最终从43处退出，并且结果是找不到。

当我们知道了需要在非空中找key时，我们继续思考我们要找什么，有人可能会说不就是找key等于kv,first的情况么？

// 查
HashData<K, V>* Find(const K& key)
{size_t Hash_i = key % _table.size();// 为空时退出查找while (_table[Hash_i]._status != EMPTY){if (_table[Hash_i]._kv.first == key)return &_table[Hash_i];Hash_i++;}return nullptr;
}

我们来看一下这个样例，

这时我们可能还是有点不太理解，结合一下我们在删除模块对删除定性是一个“伪删除”，我们如醍醐灌顶般发现其实这个key=3还在这个哈希表中等待被人覆盖，如果插入的是（3,3）那么此时就会发生冲突（默认不允许同名的key）j，因为没有完全删除。当我们先插入（33,33）时，通过哈希函数已经覆盖了key=3所在的位置，所以后续可以正常插入！！！

所以我们需要优化一下这个函数，也就是回到了找什么这个问题！不能只找key=kv.first这个节点，我们还需要判断这个key对应的区域不为删除！

// 查
HashData<K, V>* Find(const K& key)
{size_t Hash_i = key % _table.size();// 为空时退出查找while (_table[Hash_i]._status != EMPTY){if (_table[Hash_i]._kv.first == key && _table[Hash_i]._status != DELETE)return &_table[Hash_i];Hash_i++;}return nullptr;
}

当然这里还是有点抽象！

主要是这里查找的逻辑需要满足增和删这两种情况，因为DELETE状态只是为了实现哈希表特性专门在EXIST和EMPTY中间的临时状态，仅仅为了哈希表为空时退出的保护！！！

2.3.泛型编程下的哈希表

我们回到我们的哈希函数

这里我们通过kv.first来对size取模，这种思路只能符合整型类型的key，但是实际上我们哈希表是一种高效存储的数据结构，就避免不了存储string类型，甚至是自定义类型，这些类型可以取模吗？？？当然是不行的，这也就是哈希函数存在的意义了，实现不同类型的哈希映射，来实现不同的哈希表！！！

因此借助仿函数和全特化语法来实现不同的类型进入不同的路径，实现不同的哈希关系。

// 枚举类型实现哈希表节点的三种状态
enum STATUS
{EMPTY,EXIST,DELETE
};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;}
};template<class K, class V>
struct HashData
{pair<K, V> _kv;STATUS _status = EMPTY;
};template<class K, class V, class Hash = HashFunc<K>>class HashTable
{
public:// 定义默认空间HashTable() { _table.resize(10); }// 增bool Insert(const pair<K, V>& kv) {// 具体实现}// 删bool Erase(const K& key) {// 具体实现}// 查HashData<K, V>* Find(const K& key){// 具体实现}private:// 用数组这个数据结构来存放若干个哈希节点结构体// 数组实现的哈希表vector<HashData<K, V>> _table;// 节点数size_t _num = 0;
};

这样子我们就完成了泛型编程下哈希表的结构了！！！

完整的代码


enum STATUS
{EMPTY,EXIST,// 哈希的空 和 删除 不等价，删除只是为了 不为空 为了哈希的合理性DELETE
};template<class K>
struct HashFunc
{size_t operator()(const size_t& key){return (size_t)key;}size_t operator()(const string& key){size_t hash = 0;for (auto e : key){// 对哈希映射关系的实现// 防止"abc"和"acb"的哈希关系重复hash *= 31;hash += e;}return hash;}
};template<class K, class V>
struct HashData
{pair<K, V> _kv;STATUS _status = EMPTY;
};template<class K, class V, class HashFunc = HashFunc<K>>
class HashTable
{
public:HashTable(){_table.resize(10);}// 增bool Insert(const pair<K, V>& kv){if (Find(kv.first) != nullptr)return false;// 扩容，当负载因子lf超过0.7时 进行扩容if (_num * 10 / _table.size() == 7){size_t newSize = _table.size() * 2;HashTable<K, V> newHT;newHT._table.resize(newSize);// 遍历旧的哈希表 // 因为扩容后，负载因子不会超过0.7 直接进入插入操作for (size_t i = 0; i < _table.size(); i++){if (_table[i]._status == EXIST)newHT.Insert(_table[i]._kv);}// 将新表覆盖旧表_table.swap(newHT._table);}// 需要设置仿函数对key进行操作HashFunc hs_func;size_t Hash_i = hs_func(kv.first) % _table.size();// 不为空向后走 while (_table[Hash_i]._status == EXIST){Hash_i++;// 超过capacity就取模回来Hash_i %= _table.size();}// 找到 空 或者 删除 位置可以插入_table[Hash_i]._kv = kv;_table[Hash_i]._status = EXIST;_num++;return true;}// 删bool Erase(const K& key){if (Find(key) == nullptr)return false;// 注意这里是 伪删除 （我们并没有将对应数据完全删去）HashData<K, V>* del = Find(key);del->_status = DELETE;_num--;return true;}// 查HashData<K, V>* Find(const K& key){// 需要设置仿函数对key进行操作HashFunc hs_func;size_t Hash_i = hs_func(key) % _table.size();// 为空时退出查找 存在和删除 中寻找while (_table[Hash_i]._status != EMPTY){if (_table[Hash_i]._kv.first == key && _table[Hash_i]._status != DELETE) { return &_table[Hash_i]; }Hash_i++;}return nullptr;}private:vector<HashData<K, V>> _table;// 哈希表中key的个数size_t _num = 0;
};

因为我们设置仿函数，所以需要对key进行操作，不同的类型，使用对应的不同的哈希函数。

另外对于哈希映射，我们如果只是单纯的进行ASCII值相加会出现“abc”和“acb”的哈希值一致，所以我们常常需要针对不同的类型，进行不同的算法设计，来减少哈希冲突的发生。

详细见：经典字符串hash函数介绍及性能比较_hash的性能比较-CSDN博客

那么我们就可以对这个哈希表的学习进行“完结撒花”了！！！

3.简易的哈希桶

我们发现哈希表的这个结构效率还不是很高，毕竟是通过数组来实现的，也就是一个闭散列，而实际上一般哈希表的实现是通过哈希桶这个结构的，也就是开散列，那什么是哈希桶呢？

接下来我们就要开始哈希桶的篇章了。

首先我们提出一个问题：在哈希桶中我们分别插入1,91,3,33,43,53,5,7这几个数据后，哈希桶的逻辑结构是怎么样的？

哈希桶的本质就是实现一个存储桶的首个节点的地址的指针数组，桶的本质就是一个单向链表。当我们对这个哈希桶进行访问的本质就是：指针数组对应下标是否为空，不为空就是访问桶内的数据，为空就是向后寻找。

实现代码如下，因为主要的逻辑就是增加一个链表结构，并没有太大的难度，并且基本的结构在简易哈希表部分就已经讲的很明白了，但是不同的是这里不再需要像哈希表那样判断3种状态，这一块我们在下一篇博客中再次讲解！！！

// 仿函数！！！
struct HashFunc
{size_t operator()(const size_t& key){return (size_t)key;}size_t operator()(const string& key){size_t hash = 0;for (auto e : key){hash *= 31;hash += e;}return hash;}// 也可以通过函数重载来实现，不过需要设置多种类型
};template<class K, class V>
struct HashNode
{HashNode* _next;pair<K, V> _kv;HashNode(const pair<K, V>& kv):_kv(kv), _next(nullptr){}};template<class K, class V, class Hash = HashFunc>class HashTable
{typedef HashNode<K, V> HashNode;
public:// 定义默认空间HashTable() { _table.resize(10); }// 析构，释放空间~HashTable(){for (size_t i = 0; i < _table.size(); i++){HashNode* current = _table[i];HashNode* next = nullptr;while (current != nullptr){next = current->_next;delete current;current = next;}_table[i] = nullptr;}}// 增bool Insert(const pair<K, V>& kv){Hash hs_func;// 当负载因子为1时才进行扩容if (_num == _table.size()){vector<HashNode*> newT;newT.resize(_table.size() * 2);for (size_t i = 0; i < _table.size(); i++){HashNode* current = _table[i];HashNode* next = nullptr;// 将旧表的内容插入进新表while (current != nullptr){next = current->_next;// 头插逻辑size_t Hash_i = hs_func(current->_kv.first) % newT.size();current->_next = newT[Hash_i];current = next;}_table[i] = nullptr;}_table.swap(newT);}size_t Hash_i = hs_func(kv.first) % _table.size();HashNode* newNode = new HashNode(kv);// 头插（针对哈希桶）// 新节点的下一个节点就是原本的头节点newNode->_next = _table[Hash_i];_table[Hash_i] = newNode;_num++;return true;}// 删bool Erase(const K& key){Hash hs_func;size_t Hash_i = hs_func(key) % _table.size();HashNode* current = _table[Hash_i];HashNode* prev = nullptr;while (current != nullptr){if (current->_kv.first == key){if (prev == nullptr){_table[Hash_i] = current->_next;}else{prev->_next = current->_next;}delete current;return true;}prev = current;current = current->_next;}return false;}// 查HashNode* Find(const K& key){Hash hs_func;size_t Hash_i = hs_func(key) % _table.size();HashNode* current = _table[Hash_i];while (current != nullptr){if (current->_kv.first == key)return current;current = current->_next;}return nullptr;}private:// 指针数组存储哈希桶的首元素地址vector<HashNode*> _table;// 节点数size_t _num = 0;
};