哈希表，是根据关键字（Key value）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。（摘自维基百科）

对不同的关键字可能得到同一散列地址，即k1!=k2，而f(k1)=f(k2)，这种现象称为碰撞（英语：Collision）,也叫哈希冲突。

处理哈希冲突的方法有很多种：

闭散列法

开链法（哈希桶）

素数表

字符串哈希算法

在这里我们讨论最简单的闭散列法的线性探测法，学会了这种方法，就可以在线性探测法的思想基础上领会其他方法。

线性探测法

定义：通过散列函数hash(key)，找到关键字key在线性序列中的位置，如果当前位置已经有了一个关键字，就长生了哈希冲突，就往后探测i个位置（i小于线性序列的大小），直到当前位置没有关键字存在。


#pragmaonce#include<iostream>#include<string>usingnamespacestd;enumState{EMPTY,EXIST,DELETE};template<classT>structDefaultFunc{size_toperator()(constT&data){return(size_t)data;}};structStringFunc{size_toperator()(conststring&str){size_tsum=0;for(size_ti=0;i<str.size();++i){sum+=str[i];}returnsum;}};template<classK,classFuncModel=DefaultFunc<K>>classHashTable{public:HashTable();HashTable(constsize_tsize);boolPush(constK&data);//增boolRemove(constK&data);//删size_tFind(constK&data);//查boolAlter(constK&data,constK&newdata);//改voidPrint();//打印哈希表protected:size_tHashFunc(constK&data);//散列函数（哈希函数）voidSwap(HashTable<K,FuncModel>&x);protected:K*_table;//哈希表State*_state;//状态表size_t_size;size_t_capacity;FuncModel_HF;//区分默认类型的哈希函数和string类型的哈希函数};


.cpp文件

#define_CRT_SECURE_NO_WARNINGS1#include"HashTable.h"template<classK,classFuncModel=DefaultFunc<K>>HashTable<K,FuncModel>::HashTable():_table(NULL),_state(NULL),_size(0),_capacity(0){}template<classK,classFuncModel=DefaultFunc<K>>HashTable<K,FuncModel>::HashTable(constsize_tsize):_table(newK[size]),_state(newState[size]),_size(0),_capacity(size){//这里别用memset（）来初始化_state，对于枚举类型的动态内存不能用memset初始化//老老实实一个一个初始化for(size_ti=0;i<_capacity;i++){_state[i]=EMPTY;}}template<classK,classFuncModel=DefaultFunc<K>>size_tHashTable<K,FuncModel>::HashFunc(constK&data){return_HF(data)%_capacity;//Mod哈希表的容量，找到在哈希表中的位置，//其实在这里最好Mod一个素数}template<classK,classFuncModel=DefaultFunc<K>>voidHashTable<K,FuncModel>::Swap(HashTable<K,FuncModel>&x)//交换两个哈希表{swap(_table,x._table);swap(_state,x._state);swap(_size,x._size);swap(_capacity,x._capacity);}template<classK,classFuncModel=DefaultFunc<K>>boolHashTable<K,FuncModel>::Push(constK&data){ifif(_size*10>=_capacity*8)//载荷因子不超过0.8{HashTable<K,FuncModel>tmp(2*_capacity+2);for(size_ti=0;i<_capacity;++i){if(_state[i]==EXIST){size_tindex=HashFunc(_table[i]);while(tmp._state[index]==EXIST){index++;}tmp._table[index]=_table[i];tmp._state[index]=EXIST;}}Swap(tmp);}size_tindex=HashFunc(data);while(_state[index]==EXIST){index++;}_table[index]=data;_state[index]=EXIST;_size++;returntrue;}template<classK,classFuncModel=DefaultFunc<K>>voidHashTable<K,FuncModel>::Print(){for(size_ti=0;i<_capacity;++i){if(_state[i]==EXIST){printf("_table[%d]:",i);cout<<_table[i]<<"->存在";}elseif(_state[i]==DELETE){printf("_table[%d]:",i);cout<<_table[i]<<"->删除";}else{printf("_table[%d]:空",i);}cout<<endl;}}template<classK,classFuncModel=DefaultFunc<K>>boolHashTable<K,FuncModel>::Remove(constK&data){if(_size>0){size_tindex=Find(data);if(index>0){_state[index]=DELETE;_size--;returntrue;}elsereturnfalse;}returnfalse;}template<classK,classFuncModel=DefaultFunc<K>>size_tHashTable<K,FuncModel>::Find(constK&data){size_tindex=HashFunc(data);size_ttime=_capacity;while(time--){if(_table[index++]==data){return--index;}if(index==_capacity){index=0;}}return-1;}template<classK,classFuncModel=DefaultFunc<K>>boolHashTable<K,FuncModel>::Alter(constK&data,constK&newdata){size_tindex=Find(data);if(index>0){_state[index]=DELETE;if(Push(newdata))returntrue;elsereturnfalse;}returnfalse;}

在实现过程中要注意的问题有以下几点：

对于线性探测来说，有时候会遇到一开始探测的位置就在哈希table的最后的部分，但是因为哈希冲突key值被冲突到了哈希table的最前部分，所以探测到了table尾后将index置为0，简单又粗暴。


对于对哈希表中的数据的删除是属于弱删除，也就是说删除并没有删除数据，只是把数据的状态_state置为DELETE。

当载荷因子超过0.8时就得增容，载荷因子越高哈希冲突越多，不命中率越高。CPU缓存会大大升高。载荷因子a=填入表中元素的个数/散列表长度。



对代码的两点说明：

在这里我将模板声明与定义分开，涉及了模板的分离编译，对模板分离编译还不太清楚的可以查看博主博客http://helloleex.blog.51cto.com/10728491/1769994

并且为了增强代码的复用性，我使用了仿函数来区别调用默认类型（基本类型，自定义类型）和string类型，使调用更加灵活