#pragmaonce#include<vector>#include<string>template<classK,classV>structHashTableNode{K_key;V_value;HashTableNode<K,V>*_next;HashTableNode(constK&key,constV&value):_key(key),_value(value),_next(NULL){}};template<classK>struct__HashFunc{size_toperator()(constK&key){returnkey;}};template<>struct__HashFunc<string>{staticsize_tBKDRHash(constchar*str){unsignedintseed=131;//31131131313131131313unsignedinthash=0;while(*str){hash=hash*seed+(*str++);}return(hash&0x7FFFFFFF);}size_toperator()(conststring&key){returnBKDRHash(key.c_str());}};template<classK,classV,classHashFunc=__HashFunc<K>>classHashTable{typedefHashTableNode<K,V>Node;public:HashTable(size_tcapacity):_size(0){_tables.resize(_GetNextPrime(capacity));}HashTable(constHashTable<K,V>&ht);HashTable<K,V>&operator=(constHashTable<K,V>&ht);~HashTable(){for(size_ti=0;i<_tables.size();++i){Node*cur=_tables[i];while(cur){Node*del=cur;cur=cur->_next;deletedel;}}}boolInsert(constK&key,constV&value){_CheckCapacity();size_tindex=_HashFunc(key,_tables.size());Node*cur=_tables[index];while(cur){if(cur->_key==key)returnfalse;cur=cur->_next;}Node*tmp=newNode(key,value);tmp->_next=_tables[index];_tables[index]=tmp;++_size;returntrue;}Node*Find(constK&key){size_tindex=_HashFunc(key,_tables.size());Node*cur=_tables[index];while(cur){if(cur->_key==key)returncur;cur=cur->_next;}returnNULL;}boolRemove(constK&key){size_tindex=_HashFunc(key,_tables.size());if(_tables[index]==NULL)returnfalse;if(_tables[index]->_key==key){Node*del=_tables[index];_tables[index]=_tables[index]->_next;deletedel;returntrue;}Node*prev=_tables[index];Node*cur=prev->_next;while(cur){if(cur->_key==key){prev->_next=cur->_next;deletecur;returntrue;}prev=cur;cur=cur->_next;}returnfalse;}voidPrint(){for(size_ti=0;i<_tables.size();++i){printf("[%d]->",i);Node*cur=_tables[i];while(cur){cout<<cur->_key<<":"<<cur->_value<<"->";cur=cur->_next;}cout<<"NULL"<<endl;}cout<<endl;}voidSwap(HashTable<K,V>&ht){swap(_tables,ht._tables);swap(_size,ht._size);}protected:void_CheckCapacity(){if(_size==_tables.size()){size_tnewCapacity=_GetNextPrime(_tables.size());if(newCapacity==_tables.size())return;/*vector<Node*>newTables;newTables.resize(newCapacity);for(size_ti=0;i<_tables.size();++i){Node*cur=_tables[i];while(cur){Node*tmp=cur;cur=cur->_next;size_tindex=_HashFunc(tmp->_key,newCapacity);//???tmp->_next=newTables[index];newTables[index]=tmp;}_tables[i]=NULL;}_tables.swap(newTables);*/HashTable<K,V>tmp(_tables.size());for(size_ti=0;i<_tables.size();++i){Node*cur=_tables[i];while(cur){tmp.Insert(cur->_key,cur->_value);cur=cur->_next;}}this->Swap(tmp);}}//使用素数表对齐做哈希表的容量，降低哈希冲突size_t_GetNextPrime(size_tsize){constint_PrimeSize=28;staticconstunsignedlong_PrimeList[_PrimeSize]={53ul,97ul,193ul,389ul,769ul,1543ul,3079ul,6151ul,12289ul,24593ul,49157ul,98317ul,196613ul,393241ul,786433ul,1572869ul,3145739ul,6291469ul,12582917ul,25165843ul,50331653ul,100663319ul,201326611ul,402653189ul,805306457ul,1610612741ul,3221225473ul,4294967291ul};for(size_ti=0;i<_PrimeSize;++i){if(_PrimeList[i]>size){return_PrimeList[i];}}return_PrimeList[_PrimeSize-1];}size_t_HashFunc(constK&key,constsize_tcapacity){returnHashFunc()(key)%capacity;}protected:vector<Node*>_tables;size_t_size;};voidTestDic(){HashTable<string,string>dict(10);dict.Insert("he","他");dict.Insert("she","她");dict.Insert("hash","哈希");dict.Insert("hello","你好");dict.Print();HashTableNode<string,string>*ret=dict.Find("hash");if(ret){cout<<ret->_value<<endl;}}voidTest(){HashTable<string,vector<string>>ht(10);vector<string>vec;vec.push_back("男");vec.push_back("20");vec.push_back("123456");ht.Insert("张三",vec);HashTableNode<string,vector<string>>*ret=ht.Find("张三");if(ret){cout<<"姓名："<<ret->_key<<endl;cout<<"性别："<<ret->_value[0]<<endl;cout<<"年龄："<<ret->_value[1]<<endl;cout<<"电话号码："<<ret->_value[2]<<endl;}}

#include<iostream>usingnamespacestd;#include"HashTablesBucket.h"intmain(){//TestDic();Test();return0;}

TestDic:

Test: