HashTable-散列表/哈希表，是根据关键字（key）而直接访问在内存存储位置的数据结构。

它通过一个关键值的函数将所需的数据映射到表中的位置来访问数据，这个映射函数叫做散列函数，存放记录的数组叫做散列表。

构造哈希表的方法：

1.直接定址法--取关键字的某个线性函数为散列地址，Hash（Key）= Key 或 Hash（Key）= A*Key + B，A、B为常数。

2.除留余数法--取关键值被某个不大于散列表长m的数p除后的所得的余数为散列地址。Hash（Key）= Key % P。

3.平方取中法

4.折叠法

5.随机数法

6.数学分析法

常用方法为直接定址法，除留余数法。

K类型代码：

#pragmaonce#include<string>enumStatus{EXIST,DELETE,EMPTY,};//仿函数template<classK>structDefaultHashFuncer{size_toperator()(constK&key){returnkey;}};staticsize_tBKDRHash(constchar*str){unsignedintseed=131;//31131131313131131313unsignedinthash=0;while(*str){hash=hash*seed+(unsignedchar)(*str++);}return(hash&0x7FFFFFFF);}template<>structDefaultHashFuncer<string>{size_toperator()(conststring&str){//size_tvalue=0;//for(size_ti=0;i<str.size();++i)//{//value+=str[i];//}//returnvalue;returnBKDRHash(str.c_str());}};template<classK,classHashFuncer=DefaultHashFuncer<K>>classHashTable{public:HashTable():_tables(NULL),_status(NULL),_size(0),_capacity(0){}HashTable(size_tsize):_tables(newK[size]),_status(newStatus[size]),_size(0),_capacity(size){//memset(_status,0,sizeof(Status)*_size);for(size_ti=0;i<_capacity;++i){_status[i]=EMPTY;}}HashTable(constHashTable<K,HashFuncer>&ht){HashTable<K,HashFuncer>tmp(ht._capacity);for(size_t){}}HashTable<K,HashFuncer>&operator=(HashTable<K,HashFuncer>ht);~HashTable(){if(_tables){delete[]_tables;delete[]_status;}_size=0;_capacity=0;}boolInsert(constK&key){/*if(_size==_capacity){cout<<"Full"<<endl;returnfalse;}*/_CheckCapacity();size_tindex=_HashFunc(key);//线性探测while(_status[index]==EXIST){if(_tables[index]==key){returnfalse;}++index;if(index==_capacity)index=0;}_status[index]=EXIST;_tables[index]=key;++_size;returntrue;}intFind(constK&key){inti=0;size_tindex=_HashFunc(key);while(_status[index]!=EMPTY){if(_tables[index]==key&&_status[index]!=DELETE){returnindex;}++i;index=_HashFunc(key)+i*i;++index;if(index==_capacity){index=0;}}return-1;}boolRemove(constK&key){intindex=Find(key);if(index!=-1){_status[index]=DELETE;returntrue;}returnfalse;}voidSwap(HashTable<K,HashFuncer>&ht){swap(_tables,ht._tables);swap(_size,ht._size);swap(_status,ht._status);swap(_capacity,ht._capacity);}size_t_HashFunc(constK&key){////returnkey%_capacity;HashFuncerhf;returnhf(key)%_capacity;}voidPrintTables(){for(size_ti=0;i<_capacity;++i){if(_status[i]==EXIST){printf("[%d]:E->",i);cout<<_tables[i];}elseif(_status[i]==DELETE){printf("[%d]:D->",i);cout<<_tables[i];}else{printf("[%d]:N",i);}cout<<endl;}}void_CheckCapacity(){if(_size*10>=_capacity*7){/*K*tmpTables=newK[2*_capacity];K*tmpStatus=newStatus[2*_capacity];for(size_ti=0;i<_capacity;++i){if(){}}*/HashTable<K,HashFuncer>tmp(2*_capacity);for(size_ti=0;i<_capacity;++i){if(_status[i]==EXIST){tmp.Insert(_tables[i]);}}this->Swap(tmp);}}protected:K*_tables;Status*_status;size_t_size;size_t_capacity;};

a:变量分析：

1.K类型的数组，用来存储key。

2.Status类型的数组，用来标志每一个位置状态。

3._size,用于表示有效数据个数。

4._capacity，容量

b:难点分析

1.使用仿函数计算不同类型数据的Key。

2.处理哈希冲突以及载荷因子。

KV类型的代码

#pragmaonce#include<string>enumStatus{EXIST,DELETE,EMPTY,};template<classK,classV>structKeyValue{K_key;V_value;KeyValue(constK&key=K(),constV&value=V()):_key(key),_value(value){}};template<classK>structDefaultHashFuncer{size_toperator()(constK&key){returnkey;}};staticsize_tBKDRHash(constchar*str){unsignedintseed=131;//31131131313131131313unsignedinthash=0;while(*str){hash=hash*seed+(unsignedchar)(*str++);}return(hash&0x7FFFFFFF);}template<>structDefaultHashFuncer<string>{size_toperator()(conststring&str){//size_tvalue=0;//for(size_ti=0;i<str.size();++i)//{//value+=str[i];//}//returnvalue;returnBKDRHash(str.c_str());}};template<classK,classV,classHashFuncer=DefaultHashFuncer<K>>classHashTable{typedefKeyValue<K,V>KV;public:HashTable(size_tsize):_tables(newKV[size]),_status(newStatus[size]),_size(0),_capacity(size){//memset(_status,0,sizeof(Status)*_size);for(size_ti=0;i<_capacity;++i){_status[i]=EMPTY;}}~HashTable(){if(_tables){delete[]_tables;delete[]_status;}_size=0;_capacity=0;}boolInsert(constK&key,constV&value){if(_size==_capacity){cout<<"Full"<<endl;returnfalse;}//_CheckCapacity();//二次方探测inti=1;size_tindex=_HashFunc0(key);while(_status[index]==EXIST){if(_tables[index]._key==key){returnfalse;}index=_HashFunci(index,i++);}_status[index]=EXIST;_tables[index]=KV(key,value);++_size;returntrue;}KV*Find(constK&key);size_t_HashFunc0(constK&key){HashFuncerhf;returnhf(key)%_capacity;}size_t_HashFunci(size_tprevHash,inti){return(prevHash+2*i-1)%_capacity;}protected:KV*_tables;Status*_status;size_t_size;size_t_capacity;};

同理上面K类型，不同的是_tables的每一个元素是一个KeyValue<K,V>类型的结构体。

处理哈希冲突的闭散列方法

1.线性探测

2.二次探测

以上就是本人在学习过程中的一些经验总结。当然，本人能力有限，难免会有纰漏，希望大家可以指正。