哈希表（散列表）二次探测

2025-01-21 技术教程

#pragmaonce#include<iostream>#include<string>usingnamespacestd;enumState{EMPTY,DELETE,EXIST,};template<classK,classV>structHashTableNode{K_key;V_value;};template<classK>struct__HashFunc//默认的返回哈希键值key的仿函数{size_toperator()(constK&key){returnkey;}};//特化string的__HashFunc仿函数template<>struct__HashFunc<string>{size_toperator()(conststring&str){size_tkey=0;for(size_ti=0;i<str.size();i++){key+=str[i];}returnkey;}};//实现哈希表的Key/Value形式的二次探测template<classK,classV,classHashFunc=__HashFunc<K>>classHashTable{typedefHashTableNode<K,V>Node;public:HashTable(size_tcapacity=10):_tables(newNode[capacity]),_size(0),_states(newState[capacity]),_capacity(capacity){//memset有问题是以字节为单位初始化的但第二个参数值为int//memset(_states,EMPTY,sizeof(State)*capacity);for(size_ti=0;i<capacity;i++){_states[i]=EMPTY;}}~HashTable(){if(NULL!=_tables){delete[]_tables;_tables=NULL;}if(NULL!=_states){delete[]_states;_states=NULL;}}boolInsert(constK&key,constV&value){_CheckCapacity();//用GetNextIndex解决哈希冲突size_tindex=_HashFunc(key);//二次探测size_ti=1;while(_states[index]==EXIST){index=_GetNextIndex(index,i++);if(index>=_capacity){index=index%_capacity;}}_tables[index]._key=key;_tables[index]._value=value;_states[index]=EXIST;_size++;returntrue;}Node*Find(constK&key){size_tindex=_HashFunc(key);size_tstart=index;size_ti=1;//存在或者被删除两种状态while(_states[index]!=EMPTY){if(_tables[index]._key==key){if(_states[index]==EXIST){returnindex;}else//被删除DELETE{return-1;}}index=_GetNextIndex(index,i++);if(index>=_capacity){index=index%_capacity;}//因为有填充因子不为100%不会出现全满且key！=_key导致死循环的情况}return-1;}boolRemove(constK&key){intindex=Find(key);if(index!=-1){_states[index]=DELETE;--_size;returntrue;}returnfalse;}//二次探测计算出存放位置size_t_HashFunc(constK&key){HashFunchf;returnhf(key)%_capacity;//仿函数hf()}//哈希冲突时得到下一个index的可以利用上一个index的值这样能提高效率比如string的index计算就比较费时size_t_GetNextIndex(size_tprev,size_ti){returnprev+2*i-1;}voidPrint(){for(size_ti=0;i<_capacity;i++){if(_states[i]==EXIST){cout<<i<<"EXIST:"<<_tables[i]._key<<"-------"<<_tables[i]._value<<endl;}elseif(_states[i]==DELETE){cout<<i<<"DELETE:"<<_tables[i]._key<<"-------"<<_tables[i]._value<<endl;}else{cout<<i<<"EMPTY:"<<_tables[i]._key<<"-------"<<_tables[i]._value<<endl;}}}voidSwap(HashTable<K,V,HashFunc>&ht){swap(_size,ht._size);swap(_states,ht._states);swap(_tables,ht._tables);swap(_capacity,ht._capacity);}protected:void_CheckCapacity()//扩容{//动态的可扩容的//高效哈希表的载荷因子大概在0.7-0.8较好if(10*_size/_capacity>=7)//_size/_capacity为0因为都是×××所以乘10//保证载荷因子在0.7之内{HashTable<K,V,HashFunc>tmp(2*_capacity);for(size_ti=0;i<_capacity;i++){if(_states[i]==EXIST){tmp.Insert(_tables[i]._key,_tables[i]._value);}}Swap(tmp);}}protected:Node*_tables;State*_states;//状态表size_t_size;size_t_capacity;};