当前位置：首页 > news >正文

13【CPP】Hash(闭散列||开散列）

news 来源：原创 2024/5/20 13:03:56

闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有
空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。

线性探测

需要定义三个状态，空、删除、存在。因为如果不定义删除状态，那么在删除元素后就会对该元素后面的元素查找产生影响。

实现

#pragma once
#include<vector>
using namespace std;enum State
{EMPTY,EXIST,DELETE
};template<class K, class V>
struct HashData
{pair<K, V> _kv;State _state=EMPTY;
};template<class K,class V>
class HashTable
{
public:HashTable(){_tables.resize(10);}
public:bool Insert(const pair<K, V>& kv){//负载因子超过0.7就扩容if (_tables.size()==0||_n * 10 / _tables.size() >= 7){//扩容要开全新空间，重新算位置size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;HashTable<K, V> newht;newht._tables.resize(newsize);for (auto& data : _tables){if (data._state == EXIST)//重新算在新表的位置{newht.Insert(data._kv);}}_tables.swap(newht._tables);//vector底层直接交换指针就行}size_t hashi = kv.first % _tables.size();size_t i = 1;//控制步长size_t index = hashi;while (_tables[index]._state==EXIST)//如果存在hashi继续往后走{index = hashi + i;index %= _tables.size();i++;}_tables[index]._kv = kv;_tables[index]._state = EXIST;_n++;return true;}HashData<K, V>* Find(const K& key){if (_tables.size() == 0)return false;size_t hashi = kv.first % _tables.size();size_t i = 1;size_t index = hashi;while (_tables[index]._state != EMPTY){if (_tables[index]._kv.first == key){return &_tables[index];}index = hashi + i;index %= _tables.size();++i;}}bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret){ret->_state = DELETE;--_n;return true;}else{return false;}}private:vector<HashData<K,V>> _tables;size_t _n=0;//存储数据个数
};void Test_hashtable1()
{HashTable<int, int> ht;int a[] = { 4,14,24,34,5,7,1 };for (auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(13, 13));}

问题

上述代码查找存在问题，当插入数据后，扩容前，删除一部分数据再插入数据，并且数据正好占据了其他空位，导致表中状态除了存在就是删除。

HashData<K, V>* Find(const K& key){if (_tables.size() == 0)return false;size_t hashi = kv.first % _tables.size();size_t i = 1;size_t index = hashi;while (_tables[index]._state != EMPTY){if (_tables[index]._kv.first == key){return &_tables[index];}index = hashi + i;index %= _tables.size();++i;//如果已经查找了一圈，那么说明全是存在+删除if (index == hashi){break;}}}

缺陷

线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。解决方案：二次探测、开散列。

开散列

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

实现

插入

namespace HashBucket
{template<class K,class V>struct HashNode{HashNode(const pair<K, V>& kv):_kv(kv){}struct HashNode<K, V>* _next=nullptr;pair<K, V> _kv;};template<class K,class V>class HashTable{typedef HashNode<K, V> Node;public:HashTable(){_tables.resize(10);}bool Insert(const pair<K, V>& kv){size_t hashi = kv.first % _tables.size();//头插Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;}private:vector<Node*> _tables;size_t _n=0;//存储的有效数据个数};
}

这里选择使用头插，时间复杂度o（1），省去了尾插找尾的步骤。hashtable成员变量_tables是一个指针数组，存放的是指向每一个节点链表头的指针。

负载因子

在这里插入图片描述
负载因子越大，冲突的概率越高，查找效率越低，空间利用率越高。
对于闭散列，我们采取当负载因子为1时进行扩容。

扩容

bool Insert(const pair<K, V>& kv){//负载因子等于1时扩容if (_n == _tables.size()){size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;vector<Node*> newtables(newsize, nullptr);for (auto& cur : _tables){while (cur){Node* next = cur->_next;size_t hashi = cur->_kv.first % newtables.size();cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}}_tables.swap(newtables);}size_t hashi = kv.first % _tables.size();//头插Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;}

这里扩容不是重新创一个一个节点，而是把原本_tables中的数据再重新遍历一遍依次插入到新开的vector中，最后实现交换。

加入仿函数/模版特化

如果类型是string或其他自定义类型那么无法计算key，那么可以利用仿函数转化成整形。
在这里插入图片描述
对于需要处理的string或自定义类型，传入自己写好的仿函数即可

仿函数中不一定要取第一个字符的ASCII码，可以取所有字符的和加起来的值去查找，这样可以大大提高效率。
当然还有很多哈希算法更强，如BKDR哈希，详见字符串哈希算法
在这里插入图片描述

完整实现代码

#pragma once
#include<vector>
#include<iostream>
#include<string>using namespace std;namespace OpenAddress
{enum State{EMPTY,EXIST,DELETE};template<class K, class V>struct HashData{pair<K, V> _kv;State _state = EMPTY;};template<class K, class V>class HashTable{public:HashTable(){_tables.resize(10);}public:bool Insert(const pair<K, V>& kv){//负载因子超过0.7就扩容if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7){//扩容要开全新空间，重新算位置size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;HashTable<K, V> newht;newht._tables.resize(newsize);for (auto& data : _tables){if (data._state == EXIST)//重新算在新表的位置{newht.Insert(data._kv);}}_tables.swap(newht._tables);//vector底层直接交换指针就行}size_t hashi = kv.first % _tables.size();size_t i = 1;//控制步长size_t index = hashi;while (_tables[index]._state == EXIST)//如果存在hashi继续往后走{index = hashi + i;index %= _tables.size();i++;}_tables[index]._kv = kv;_tables[index]._state = EXIST;_n++;return true;}HashData<K, V>* Find(const K& key){if (_tables.size() == 0)return false;size_t hashi = key % _tables.size();size_t i = 1;size_t index = hashi;while (_tables[index]._state != EMPTY){if (_tables[index]._kv.first == key){return &_tables[index];}index = hashi + i;index %= _tables.size();++i;//如果已经查找了一圈，那么说明全是存在+删除if (index == hashi){break;}}}bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret){ret->_state = DELETE;--_n;return true;}else{return false;}}void Print()const{for (auto e : _tables){if(e._state==EXIST)cout << e._kv.first << " ";}cout << endl;}private:vector<HashData<K, V>> _tables;size_t _n = 0;//存储数据个数};void Test_hashtable1(){HashTable<int, int> ht;int a[] = { 4,14,24,34,5,7,1 };for (auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(13, 13));ht.Print();}
}namespace HashBucket
{template<class K,class V>struct HashNode{HashNode(const pair<K, V>& kv):_kv(kv){}struct HashNode<K, V>* _next=nullptr;pair<K, V> _kv;};template<class K>struct HashFunc{size_t operator()(const K& key){return key;}};//针对string模版特化template<>struct HashFunc<string>{size_t operator()(const string& s){//BKDR哈希size_t hash = 0;for (auto ch : s){hash += ch;hash *= 31;}return hash;}};template<class K,class V,class Hash=HashFunc<K>>class HashTable{typedef HashNode<K, V> Node;public:~HashTable(){for (auto& cur : _tables){while (cur){Node* next = cur->_next;delete cur;cur = next;}cur = nullptr;}}HashTable(){_tables.resize(10);}bool Insert(const pair<K, V>& kv){//负载因子等于1时扩容Hash hash;if (_n == _tables.size()){size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;vector<Node*> newtables(newsize, nullptr);for (auto& cur : _tables){while (cur){Node* next = cur->_next;size_t hashi = hash(cur->_kv.first) % newtables.size();cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}}_tables.swap(newtables);}size_t hashi = hash(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 hash;size_t hashi =hash( key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return nullptr;}bool Erase(const K& key){Hash hash;//不能向开散列一样find去删size_t hashi = hash(key) % _tables.size();Node* cur = _tables[hashi];//单链表删除需要一个prevNode* prev = nullptr;while (cur){if (cur->_kv.first == key){if (prev){prev->_next = cur->_next;}else{_tables[hashi]= cur->_next;}delete cur;return true;}else{prev = cur;cur = cur->_next;}}return false;}size_t MaxBucketSize(){size_t max = 0;for (size_t i=0;i<_tables.size();i++){size_t size = 0;auto cur = _tables[i];while (cur){++size;cur = cur->_next;}printf("[%d]->%d\n",i, size);if (size > max){max = size;}}return max;}void Print(){for ( auto cur : _tables){while (cur){std::cout << cur->_kv.first << " ";cur = cur->_next;}}cout << endl;}private:vector<Node*> _tables;size_t _n=0;//存储的有效数据个数};void Test_hashbucket1(){HashTable<int, int> ht;int a[] = { 4,14,24,34,5,7,1 };for (auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(13, 13));ht.Insert(make_pair(23, 23));ht.Insert(make_pair(33, 33));ht.Insert(make_pair(43, 43));ht.Print();ht.Erase(13);ht.Erase(33);ht.Print();}/*struct HashStr{size_t operator()(const string& s){size_t hash = 0;for (auto ch : s){hash += ch;hash *= 31;}return hash;}};*/void Test_hashbucket2(){HashTable<string, string> hts;hts.Insert(make_pair("mao", "毛"));hts.Insert(make_pair("dou", "豆"));hts.Print();}void Test_hashbucket3(){size_t N = 100000;HashTable<int, int> ht;srand(time(0));for (size_t i = 0; i < N; i++){size_t x = rand();ht.Insert(make_pair(x, x));}cout << ht.MaxBucketSize() << endl;}
}