行业知识
13【CPP】Hash(闭散列||开散列)
闭散列
��散列:也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有
空位置,那么可以把key存放到冲突位置中的“下一个” 空位置中去。
线性探测
需要定义三个状态,空、删除、存在。因为如果不定义删除状态,那么在删除元素后就会对该元素后面的元素查找产生影响。
实现
#pragma once#includeusing namespace std;enum State{EMPTY,EXIST,DELETE};templatestruct HashData{pair _kv;State _state=EMPTY;};templateclass HashTable{public:HashTable(){_tables.resize(10);}public:bool Insert(const pair& kv){//负载因子超过0.7就扩容if (_tables.size()==0||_n * 10 / _tables.size() >= 7){//扩容要开全新空间,重新算位置size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;HashTable 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* 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* ret = Find(key);if (ret){ret->_state = DELETE;--_n;return true;}else{return false;}}private:vector _tables;size_t _n=0;//存储数据个数};void Test_hashtable1(){HashTable 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* 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{templatestruct HashNode{HashNode(const pair& kv):_kv(kv){}struct HashNode* _next=nullptr;pair _kv;};templateclass HashTable{typedef HashNode Node;public:HashTable(){_tables.resize(10);}bool Insert(const pair& 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 _tables;size_t _n=0;//存储的有效数据个数};} 这里选择使用头插,时间复杂度o(1),省去了尾插找尾的步骤。hashtable成员变量_tables是一个指针数组,存放的是指向每一个节点链表头的指针。
负载因子
负载因子越大,冲突的概率越高,查找效率越低,空间利用率越高。
对于闭散列,我们采取当负载因子为1时进行扩容。
扩容
bool Insert(const pair& kv){//负载因子等于1时扩容if (_n == _tables.size()){size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;vector 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#include#includeusing namespace std;namespace OpenAddress{enum State{EMPTY,EXIST,DELETE};templatestruct HashData{pair _kv;State _state = EMPTY;};templateclass HashTable{public:HashTable(){_tables.resize(10);}public:bool Insert(const pair& kv){//负载因子超过0.7就扩容if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7){//扩容要开全新空间,重新算位置size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;HashTable 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* 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* 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 HashTable 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{templateHashNode(const pair}struct HashNodesize_t operator()(const K& key){return key;}};//针对string模版特化templatesize_t operator()(const string& s){//BKDR哈希size_t hash = 0;for (auto ch : s){hash += ch;hash *= 31;}return hash;}};templatetypedef HashNodefor (auto& cur : _tables){while (cur){Node* next = cur-_next;delete cur;cur = next;}cur = nullptr;}}HashTable(){_tables.resize(10);}bool Insert(const pair//负载因子等于1时扩容Hash hash;if (_n == _tables.size()){size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;vectorwhile (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;isize_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 _kv.first _next;}}cout HashTable 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(){HashTablesize_t N = 100000;HashTablesize_t x = rand();ht.Insert(make_pair(x, x));}cout
上一篇:FFT逆变换(IFFT)编程指南,步骤详解与实战技巧
下一篇:如何选择用硬盘启动?
最新文章
- 如何下载收音机应用程序
- 无领导面试接下来的半结构化面试,一组8个人,hr最后一个提问的我。那我是不是基本落选了?
- 揭秘三佰下载全攻略,轻松获取完整版,不容错过!
- CMS监控软件详解,功能亮点、选择指南一网打尽!
- 联想主机启动不了怎么办视频
- Excel源代码深度解析,轻松打开,探索底层结构秘诀!
- 如何清理旧系统文件?
- 揭秘ecstore源码,电商系统的核心架构与功能特色探究
- Cospa下载指南,一键获取使用教程,轻松上手!
- 我以前在部队陪领导打乒乓球,乒乓球打不赢专业的,一般业余的很少人能赢我,现在想找一份工作好难,自己除了执行力强,比较聪明,特长突出,长得帅外也没有什么优点,谁能介绍一份可以打乒乓球的工作^