c++哈希（开散列原理及实现）

我把c++哈希表上篇讲解放在这了，建议大家先看这篇。

前言

在上篇文章中我们详细介绍了，哈希的思想及实现原理，也认识到了闭散列最大的缺陷就是空间利用率比较低，容易这也是哈希的缺陷。怎么来解决这个问题呢？下面我们就来学习一种新的方法————————开散列（链地址法）

一、开散列概念

在前面我们讲的开放定址法，是通过哈希函数将关键码与存储位置建立映射关系，从而将关键码，存储在哈希表中，而这种方式，在数据量大的情况下很容易发生哈希冲突（哈希碰撞）。

在这里插入图片描述

为了解决这里的问题，有人提出了，开散列这种方法。
开散列：

当然这里也是利用了哈希映射，只是对底层存储结构做了改变。

开散列法又叫链地址法(开链法)，首先对关键码集合用哈希函数计算散列地址，具有相同地
址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链
接起来，各链表的头结点存储在哈希表中。
通俗的讲，就是我们在闭散列使用的是，vector< int>来模拟哈希表，而使用它发生哈希冲突时我们就要，使用线性探测这种方法来解决它，这样太麻烦了效率还低，不如把哈希表中每个节点换成一个单链表（这里叫哈希桶），这样再发生哈希冲突，我们就可以直接在链表中插入，哈希冲突就很好的解决了。
在这里插入图片描述

二、开散列的实现（链地址法的实现）

2.1、哈希桶结点定义

我们想要利用单链表形式来存储关键码，首先要定义链表结点。
注：代码的注释可以帮助我们理解

template<class K, class V>struct HashNode{HashNode* _next;//链接结点pair<K, V> _kv;//存储关键码HashNode(const pair<K, V>& kv):_kv(kv),_next(nullptr){}};

2.2、哈希函数的实现

同闭散列一样，这里我们也需要哈希函数帮助我们建立，关键码与存储位置之间的关系。

 template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};
template<>//，模板特化，应对string类型情况
struct HashFunc<string>
{size_t operator()(const string& key){// BKDRsize_t hash = 0;for (auto e : key){hash *= 31;//一种算法，可以有效降低字符串映射位置相同的概率hash += e;}cout << key << ":" << hash << endl;return hash;}
};

2.3、插入操作

通过哈希映射找到桶的位置，使用头插尾插都可（同单链表的插入操作）。

在进行插入操作时，如果哈希桶过长（单链表过长）会导致我们的查找效率变低，因此当插入一定量的数据时，我们仍需要进行扩容操作，这里我们也使用负载因此作为是否扩容的依据。

       bool Insert(const pair<K, V>& kv){if (Find(kv.first))//查找防止插入重复return false;Hash hf;if (_n == _tables.size()){vector<Node*> newTables;newTables.resize(_tables.size() * 2, nullptr);// 遍历旧表for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;// 挪动到映射的新表size_t hashi = hf(cur->_kv.first) % newTables.size();cur->_next = newTables[hashi];newTables[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newTables);}size_t hashi = hf(kv.first) % _tables.size();Node* newnode = new Node(kv);// 头插newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;}}

2.4、查找操作

使用关键码（要查找值）映射出哈希值（也就是关键所在桶的序号），在对应桶中查找。

  Node* Find(const K& key){Hash hf;size_t hashi = hf(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return NULL;}

2.5、删除操作

同单链表删除相同

      bool Erase(const K& key){Hash hf;size_t hashi = hf(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;return true;}prev = cur;cur = cur->_next;}return false;}

3、全部代码

剩下的简单成员函数，就交给大家自己看吧

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& key){// BKDRsize_t hash = 0;for (auto e : key){hash *= 31;hash += e;}cout << key << ":" << hash << endl;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<K>>class HashTable{typedef HashNode<K, V> Node;public:HashTable(){_tables.resize(10);}~HashTable(){for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;}}bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;Hash hf;if (_n == _tables.size()){vector<Node*> newTables;newTables.resize(_tables.size() * 2, nullptr);// 遍历旧表for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;// 挪动到映射的新表size_t hashi = hf(cur->_kv.first) % newTables.size();cur->_next = newTables[hashi];newTables[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newTables);}size_t hashi = hf(kv.first) % _tables.size();Node* newnode = new Node(kv);// 头插newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;}Node* Find(const K& key){Hash hf;size_t hashi = hf(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return NULL;}bool Erase(const K& key){Hash hf;size_t hashi = hf(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;return true;}prev = cur;cur = cur->_next;}return false;}private:vector<Node*> _tables;//哈希表size_t _n = 0;};