尧图网站建设 
文章目录哈希的概念直接定址法哈希冲突负载因子将关键字转为整数哈希函数除法散列法/除流余数法处理哈希冲突开放定址法hash框架hash定义插入查找删除整体代码测试代码哈希的概念哈希又称散列是一种组织数据的方式。从译名来看有散乱排列的意思。本质就是通过哈希函数把关键字key跟存储位置建立一个映射关系查找时通过这个哈希函数计算出key存储的位置进行快速查找。直接定址法当关键字的范围比较集中直接定址法就是简单高效的方法比如一组关键字都在[0,99]之间那么我们开一个100个数的数组每个关键字的值直接就是存储位置的小标。也就是说直接定址法本质就是用关键字计算出一个绝对位置或者相对位置。哈希冲突直接定址法的缺点也非常明显当关键字的范围比较分散时就很浪费内存甚至内存不够用。假设我们只要数据范围[0,9999]的N个值我们要映射到一个M个空间的数组中MN,那么就要借助哈希函数关键字key被放到数组h(key)位置这里要注意的是h(key)计算的值必须在[0,M)之间。这里存在的一个问题就是两个不同的key可能会映射到同一个位置去这种问题叫哈希冲突或者哈希碰撞。理想情况下是找出一个好的哈希函数避免冲突但是实际场景中冲突是不可避免的我们只能尽可能去减少冲突的次数。负载因子假设哈希表中已经映射存储N个值哈希表的大小是M,那么负载因子 N/M,负载因子越大哈希冲突的概率就越高空间利用率越高负载因子越小哈希冲入的概率越低空间利用率越低将关键字转为整数我们将关键字映射到数组中位置一般是整数好做映射计算如果不是整数我们要想办法转化成整数。哈希函数一个好的哈希函数应该让N个关键字被等概率的均匀的散列分布到哈希表的M个空间中但是实际中很难做到。除法散列法/除流余数法假设哈希表的大小为M,那么通过key除以M的余数作为映射位置的下标也就是哈希函数为h(key) key%M。当使用除法散列法时建议M取不太接近2的整数次幂的一个质数。处理哈希冲突实践中哈希表一般还是选择除法散列作为哈希函数当然哈希表无论选择什么哈希函数也避免不了冲突解决冲突主要有两种方法开放定址法和链地址法。开放定址法在开放定址法中所有元素都放到哈希表里当一个关键字key用哈希函数计算出位置冲突了则按照某种规则找到一个没有存储数据的位置进行存储开放定址法中负载因子一定是小于的。这里的规则有三种线性探测二次探测双重探测。线性探测从发生冲突的位置开始依次线性向后探测直到寻到下一个没有存储数据的位置为止如果走到哈希表尾则回绕到哈希表头的位置。h(key) hash0 key%M,hash0位置冲突了则线性探测公式为hc(key,i) hashi (hash0i)%M, i{1,2,3,…,M-1},因为负载因子小于1则最多探测M-1次一定能找到一个存储位置key的位置。线性探测的比较简单且容易实现线性探测的问题假设hash0位置连续冲突hash0,hash1,hash2位置已经存储数据了后续映射到hash0,hash1,hash2,hash3的值都会争夺hash3位置这种现象叫群集/堆积。hash框架hash定义切记删除的时候不可以直接删除要进行定义其当前的状态防止直接删除。enumState{EXIST,EMPTY,DELETE};templateclassK,classVstructHashData{pairK,V_kv;State _stateEMPTY;};templateclassK,classVclassHashTable{public:HashTable():_tables(11),_n(0){}private:vectorHashDataK,V_tables;size_t _n;//表中存储的数据个数};插入boolInsert(constpairK,Vkv){//扩容 负载因子if(_n*10/_tables.size()7){//扩2倍效率底且无法保证是质数/*vectorHashDataK, V newtables(_table.size() * 2); for (auto data : _tables) { if (data._state EXIST) { size_t hash0 data.first % newtables.size(); size_t hashi hash0; size_t i 1; while (newtables[hahsi]._state EXIST) { hashi (hash0 i) % newtables.size(); i; } newtables[hashi]._kv kv; newtables[hashi]._state EXIST; } }*/HashTableK,Vnewht;newht._tables.resize(_tables.size()*2);for(autodata:_tables){//旧表的数据映射到新表if(data._stateEXIST){newht.Insert(data._kv);}}_nnewht._n;_tables.swap(newht._tables);}size_t hash0kv.first%_tables.size();size_t hashihash0;size_t i1;while(_tables[hashi]._stateEXIST){//线性探测hashi(hash0i)%_tables.size();i;}_tables[hashi]._kvkv;_tables[hashi]._stateEXIST;_n;returntrue;}查找HashDataK,V*Find(constKkey){size_t hash0key%_tables.size();size_t hashihash0;size_t i1;while(_tables[hashi]._state!EMPTY){if(_tables[hashi]._state!DELETE_tables[hashi]._kv.firstkey){return_tables[hashi];}else{hashi(hash0i)%_tables.size();i;}}returnnullptr;}删除boolErase(constKkey){HashDataK,V*retFind(key);if(ret){ret-_stateDELETE;returntrue;}returnfalse;}整体代码#pragmaonce#includeiostream#includevectorusingnamespacestd;enumState{EXIST,EMPTY,DELETE};templateclassK,classVstructHashData{pairK,V_kv;State _stateEMPTY;};templateclassK,classVclassHashTable{public:HashTable():_tables(11),_n(0){}boolInsert(constpairK,Vkv){//扩容 负载因子if(_n*10/_tables.size()7){//扩2倍效率底且无法保证是质数/*vectorHashDataK, V newtables(_table.size() * 2); for (auto data : _tables) { if (data._state EXIST) { size_t hash0 data.first % newtables.size(); size_t hashi hash0; size_t i 1; while (newtables[hahsi]._state EXIST) { hashi (hash0 i) % newtables.size(); i; } newtables[hashi]._kv kv; newtables[hashi]._state EXIST; } }*/HashTableK,Vnewht;newht._tables.resize(_tables.size()*2);for(autodata:_tables){//旧表的数据映射到新表if(data._stateEXIST){newht.Insert(data._kv);}}_nnewht._n;_tables.swap(newht._tables);}size_t hash0kv.first%_tables.size();size_t hashihash0;size_t i1;while(_tables[hashi]._stateEXIST){//线性探测hashi(hash0i)%_tables.size();i;}_tables[hashi]._kvkv;_tables[hashi]._stateEXIST;_n;returntrue;}HashDataK,V*Find(constKkey){size_t hash0key%_tables.size();size_t hashihash0;size_t i1;while(_tables[hashi]._state!EMPTY){if(_tables[hashi]._state!DELETE_tables[hashi]._kv.firstkey){return_tables[hashi];}else{hashi(hash0i)%_tables.size();i;}}returnnullptr;}boolErase(constKkey){HashDataK,V*retFind(key);if(ret){ret-_stateDELETE;returntrue;}returnfalse;}private:vectorHashDataK,V_tables;size_t _n;};测试代码#includeiostream#includeset#includeunordered_setusingnamespacestd;#includeHashTable.hvoidtest1(){unordered_setints{3,1,6,7,8,2};unordered_setint::iterator its.begin();while(it!s.end()){cout*it ;it;}coutendl;}voidtest2(){constsize_t N1000000;unordered_setintus;setints;vectorintv;v.reserve(N);srand(time(0));for(size_t i0;iN;i){v.push_back(rand()i);}size_t begin1clock();for(autoe:v){us.insert(e);}size_t end1clock();coutset:end1-begin1endl;size_t begin2clock();us.reserve(N);for(autoe:v){s.insert(e);}size_t end2clock();coutunordered_set:end2-begin2endl;}voidtest3(){inta[]{19,30,52,63,11,12,22,35,31};HashTableint,intht;for(autoe:a){ht.Insert({e,e});}intx30;if(ht.Find(x)){cout找到了endl;}ht.Erase(x);if(ht.Find(x)){cout找到了endl;}else{cout没找到了endl;}}intmain(){test3();return0;}觉得我回答有用的话记得点个关注哟谢谢支持 C++哈希表的实现
文章目录哈希的概念直接定址法哈希冲突负载因子将关键字转为整数哈希函数除法散列法/除流余数法处理哈希冲突开放定址法hash框架hash定义插入查找删除整体代码测试代码哈希的概念哈希又称散列是一种组织数据的方式。从译名来看有散乱排列的意思。本质就是通过哈希函数把关键字key跟存储位置建立一个映射关系查找时通过这个哈希函数计算出key存储的位置进行快速查找。直接定址法当关键字的范围比较集中直接定址法就是简单高效的方法比如一组关键字都在[0,99]之间那么我们开一个100个数的数组每个关键字的值直接就是存储位置的小标。也就是说直接定址法本质就是用关键字计算出一个绝对位置或者相对位置。哈希冲突直接定址法的缺点也非常明显当关键字的范围比较分散时就很浪费内存甚至内存不够用。假设我们只要数据范围[0,9999]的N个值我们要映射到一个M个空间的数组中MN,那么就要借助哈希函数关键字key被放到数组h(key)位置这里要注意的是h(key)计算的值必须在[0,M)之间。这里存在的一个问题就是两个不同的key可能会映射到同一个位置去这种问题叫哈希冲突或者哈希碰撞。理想情况下是找出一个好的哈希函数避免冲突但是实际场景中冲突是不可避免的我们只能尽可能去减少冲突的次数。负载因子假设哈希表中已经映射存储N个值哈希表的大小是M,那么负载因子 N/M,负载因子越大哈希冲突的概率就越高空间利用率越高负载因子越小哈希冲入的概率越低空间利用率越低将关键字转为整数我们将关键字映射到数组中位置一般是整数好做映射计算如果不是整数我们要想办法转化成整数。哈希函数一个好的哈希函数应该让N个关键字被等概率的均匀的散列分布到哈希表的M个空间中但是实际中很难做到。除法散列法/除流余数法假设哈希表的大小为M,那么通过key除以M的余数作为映射位置的下标也就是哈希函数为h(key) key%M。当使用除法散列法时建议M取不太接近2的整数次幂的一个质数。处理哈希冲突实践中哈希表一般还是选择除法散列作为哈希函数当然哈希表无论选择什么哈希函数也避免不了冲突解决冲突主要有两种方法开放定址法和链地址法。开放定址法在开放定址法中所有元素都放到哈希表里当一个关键字key用哈希函数计算出位置冲突了则按照某种规则找到一个没有存储数据的位置进行存储开放定址法中负载因子一定是小于的。这里的规则有三种线性探测二次探测双重探测。线性探测从发生冲突的位置开始依次线性向后探测直到寻到下一个没有存储数据的位置为止如果走到哈希表尾则回绕到哈希表头的位置。h(key) hash0 key%M,hash0位置冲突了则线性探测公式为hc(key,i) hashi (hash0i)%M, i{1,2,3,…,M-1},因为负载因子小于1则最多探测M-1次一定能找到一个存储位置key的位置。线性探测的比较简单且容易实现线性探测的问题假设hash0位置连续冲突hash0,hash1,hash2位置已经存储数据了后续映射到hash0,hash1,hash2,hash3的值都会争夺hash3位置这种现象叫群集/堆积。hash框架hash定义切记删除的时候不可以直接删除要进行定义其当前的状态防止直接删除。enumState{EXIST,EMPTY,DELETE};templateclassK,classVstructHashData{pairK,V_kv;State _stateEMPTY;};templateclassK,classVclassHashTable{public:HashTable():_tables(11),_n(0){}private:vectorHashDataK,V_tables;size_t _n;//表中存储的数据个数};插入boolInsert(constpairK,Vkv){//扩容 负载因子if(_n*10/_tables.size()7){//扩2倍效率底且无法保证是质数/*vectorHashDataK, V newtables(_table.size() * 2); for (auto data : _tables) { if (data._state EXIST) { size_t hash0 data.first % newtables.size(); size_t hashi hash0; size_t i 1; while (newtables[hahsi]._state EXIST) { hashi (hash0 i) % newtables.size(); i; } newtables[hashi]._kv kv; newtables[hashi]._state EXIST; } }*/HashTableK,Vnewht;newht._tables.resize(_tables.size()*2);for(autodata:_tables){//旧表的数据映射到新表if(data._stateEXIST){newht.Insert(data._kv);}}_nnewht._n;_tables.swap(newht._tables);}size_t hash0kv.first%_tables.size();size_t hashihash0;size_t i1;while(_tables[hashi]._stateEXIST){//线性探测hashi(hash0i)%_tables.size();i;}_tables[hashi]._kvkv;_tables[hashi]._stateEXIST;_n;returntrue;}查找HashDataK,V*Find(constKkey){size_t hash0key%_tables.size();size_t hashihash0;size_t i1;while(_tables[hashi]._state!EMPTY){if(_tables[hashi]._state!DELETE_tables[hashi]._kv.firstkey){return_tables[hashi];}else{hashi(hash0i)%_tables.size();i;}}returnnullptr;}删除boolErase(constKkey){HashDataK,V*retFind(key);if(ret){ret-_stateDELETE;returntrue;}returnfalse;}整体代码#pragmaonce#includeiostream#includevectorusingnamespacestd;enumState{EXIST,EMPTY,DELETE};templateclassK,classVstructHashData{pairK,V_kv;State _stateEMPTY;};templateclassK,classVclassHashTable{public:HashTable():_tables(11),_n(0){}boolInsert(constpairK,Vkv){//扩容 负载因子if(_n*10/_tables.size()7){//扩2倍效率底且无法保证是质数/*vectorHashDataK, V newtables(_table.size() * 2); for (auto data : _tables) { if (data._state EXIST) { size_t hash0 data.first % newtables.size(); size_t hashi hash0; size_t i 1; while (newtables[hahsi]._state EXIST) { hashi (hash0 i) % newtables.size(); i; } newtables[hashi]._kv kv; newtables[hashi]._state EXIST; } }*/HashTableK,Vnewht;newht._tables.resize(_tables.size()*2);for(autodata:_tables){//旧表的数据映射到新表if(data._stateEXIST){newht.Insert(data._kv);}}_nnewht._n;_tables.swap(newht._tables);}size_t hash0kv.first%_tables.size();size_t hashihash0;size_t i1;while(_tables[hashi]._stateEXIST){//线性探测hashi(hash0i)%_tables.size();i;}_tables[hashi]._kvkv;_tables[hashi]._stateEXIST;_n;returntrue;}HashDataK,V*Find(constKkey){size_t hash0key%_tables.size();size_t hashihash0;size_t i1;while(_tables[hashi]._state!EMPTY){if(_tables[hashi]._state!DELETE_tables[hashi]._kv.firstkey){return_tables[hashi];}else{hashi(hash0i)%_tables.size();i;}}returnnullptr;}boolErase(constKkey){HashDataK,V*retFind(key);if(ret){ret-_stateDELETE;returntrue;}returnfalse;}private:vectorHashDataK,V_tables;size_t _n;};测试代码#includeiostream#includeset#includeunordered_setusingnamespacestd;#includeHashTable.hvoidtest1(){unordered_setints{3,1,6,7,8,2};unordered_setint::iterator its.begin();while(it!s.end()){cout*it ;it;}coutendl;}voidtest2(){constsize_t N1000000;unordered_setintus;setints;vectorintv;v.reserve(N);srand(time(0));for(size_t i0;iN;i){v.push_back(rand()i);}size_t begin1clock();for(autoe:v){us.insert(e);}size_t end1clock();coutset:end1-begin1endl;size_t begin2clock();us.reserve(N);for(autoe:v){s.insert(e);}size_t end2clock();coutunordered_set:end2-begin2endl;}voidtest3(){inta[]{19,30,52,63,11,12,22,35,31};HashTableint,intht;for(autoe:a){ht.Insert({e,e});}intx30;if(ht.Find(x)){cout找到了endl;}ht.Erase(x);if(ht.Find(x)){cout找到了endl;}else{cout没找到了endl;}}intmain(){test3();return0;}觉得我回答有用的话记得点个关注哟谢谢支持