在了解哈希技术及哈希表之前，首先希望大家对计数排序有一个比较基本的了解(很多人更习惯称计数排序为桶排序，真正意义上的桶排序即是计数排序和哈希技术的结合)。
计数排序中有一个桶的概念，就是将数据n放在编号为n的桶中，用数组元素c[i]来表示编号为i的桶。这样可以用c[i]来查询编号为i的数字在序列中出现的次数，最简单的我们可以通过c[i]的下标i知道查询的编号为i。
对于数据表中若干的数据，我们也希望用计数排序中同样的方法将出现的数据存储在数组中。但问题就在于出现的数据往往过于分散，导致数组空间的利用率非常之低下。于是需要一个函数能够将被存储的数据转化成更加“紧凑”分布的若干个数据，然后像计数排序一下存储到数组中。
例如数据110，210，310，我们将每个数据除以10得到11，21，31，比起原本的数据就更为“紧凑”，节省了大量的空间，当我们访问表中下标为11的存储单位时得到的数据即为110，21即为210······同理，我们还可以将每个数据减去10再除以100，得到1，2，3，节省了更多的空间。
这样的技术我们称为哈希技术，函数称为哈希函数，转化后的值(下标)称为哈希地址，如此构造最终得到的表为哈希表。
但是像有的哈希函数会将数据转化成相同的哈希地址，这样的两个元素我们称为同义词，情况称为哈希冲突。一般将同义词在同一个哈希地址处连成一条链，最终得到哈希表像若干条链，所以哈希表往往又称哈希散列表。
哈希函数的构造方法
这里是几种常见的哈希函数构造方法。
直接定址法直接定址法代表关键字k加上某个常数c得到哈希地址的哈希函数。一般式为：
h(k)(哈希函数)=k+c，这种哈希函数一般适用于关键字的分布基本连续的情况。
除留余数法一般式为：h(k)=k mod p，这是最经常使用的哈希函数之一，或者大部分哈希函数最基础的部分。这种方法的关键在于选好p的值，使得数据落入任意地址的概率较为平均，不会出现某个地址对应的链过长的情况。
很多哈希函数往往是直接定址法和除留余数法的结合：
h(k)=(a*k+b) mod c
数字分析法纯玄学，无公式。
哈希冲突的解决方式
不管教材怎么说，反正我心中哈希技术就只有拉链法(散列化)一种解决哈希冲突的方式。
拉链法就是前面说的，将一个哈希地址的同义词用单链表连接起来的方式，在这种方法中，哈希表的每个单元存放的是同义词单链表的头结点指针。
查找，插入和删除也很简单，只需要计算出哈希值，在对应的单链表中进行查找，插入和删除即可。
拉链法需要注意的是避免某条同义词组成的链过长，使得哈希表退化成几条很长的链的情况。
开放定址法开放定址法就是再出现哈希冲突时，在哈希表中找到一个新的，空闲的位置存放需要插入的元素。找空闲的位置的方法有，线性探测法和平方探测法。
线性探测法简单来说，存入键值为k的元素，h(k)=d，当下标为d的存储空间已经被占时，寻找d+1，d+2····(d+i)%m(m为哈希表长度)，如果有空闲的位置就将键值为k的元素存入。
但是这么做会出现一个问题，就是需要占用下标为d的存储空间的同义词连续出现很多个，后面出现的同义词占据d+1，d+2·····的存储空间，导致需要占用下标为d+1，d+2·······的存储空间的数据又被迫发生哈希冲突。
这种哈希函数值不同的两个元素争抢同一个地址的情况称为堆积问题，像拉链法就不会出现这样的问题。
平方探测法存入键值为k的元素，h(k)=d，当下标为d的存储空间已经被占时，寻找d+12，d-12，d+22，d-22，····(d+i2)%m(m为哈希表长度)，(d-i2)%m，如果有空闲的位置就将键值为k的元素存入。
平方探测法比较线性探测法可以避免一些堆积问题，但是缺点在于无法探测到哈希表上的所有单元。
基于开放地址法构造的哈希表运算 哈希表的存储结构
struct HashTable{KeyType key; int count;};//key为关键字值,count为存入关键值key需要探测的次数
count主要用在计算ASL的值，和其他操作无关。
在看其余的基本操作之前，需要意识到这样一个问题：开放地址法构造的哈希表同义词很大概率是堆积在一起的。如果某个关键词被删除，查找它的同义词很有可能因为它的空缺，导致在线性探测的过程中提前结束。
所以被删除的关键词的状态和存储单元一直为空的状态需要分开定义。
#define NULLKEY -1//关键字=NULLKEY表示当前存储单位为空(从没有过结点) #define DELKEY -2//关键字=DELKEY表示当前存储单位原本的结点被删除哈希表的创建和插入
和二叉搜索树一样，哈希表的创建同样是将n个元素依次插入的过程，所以需要知道如何插入一个元素。
插入时需要统计一个元素插入时的探测次数。
//将关键字k插入到哈希表ha中,n为哈希表中总关键字的个数,p为哈希表容量
void InsertHT(HashTable ha[],int &n,int m,int p,KeyType k){
int i,adr; adr=k%p;//adr为存储单元的下标,i为当前探测(查找)的次数
if (ha[adr].key==NULLKEY||ha[adr].key==DELKEY){//当前地址为空,直接存储
ha[adr].key=k; ha[adr].count=1;//仅探测一次
}
else{i=1;//产生冲突,进行线性探测法
do{//每进行一次线性探测,查找的次数+1
adr=(adr+1)%m; i++;
} while (ha[adr].key!=NULLKEY&&ha[adr].key!=DELKEY);
ha[adr].key=k; ha[adr].count=i;//设置探测次数
}n++;
}
创建hash表就是依次插入元素：
//创建hash表,n为hash表总关键字个数,m为hash表容量
void CreateHT(HashTable ha[],int &n,int m,int p,KeyType keys[],int n1){
for (int i=0;i
哈希表的查找
查找时只需要判断是否一直为空。
//在哈希表中ha查找关键字k
void SearchHT(HashTable ha[],int m,int p,KeyType k){int i=1,adr;
adr=k%p;//计算哈希函数值,用线性探测法寻找k存储的下标,i为查找次数
//需要注意的是这里判断的条件是从没有过结点,不是为空
//如果只是判断为空,线性探测法探测时会因为被删去的结点而中途结束
while (ha[adr].key!=NULLKEY&&ha[adr].key!=k){
i++; adr=(adr+1)%m;
}
if (ha[adr].key==k) printf("成功：关键字%d，比较%d次n",k,i);//查找成功
else printf("失败：关键字%d，比较%d次n",k,i);//查找失败
}
哈希表的删除
首先进行查找。如果查找成功，需要将被删除的关键词的值置为被删除状态。
//删除哈希表中关键字k
bool DeleteHT(HashTable ha[],int &n,int m,int p,KeyType k){
int adr; adr=k%p;//计算哈希函数值
while (ha[adr].key!=NULLKEY&&ha[adr].key!=k) adr=(adr+1)%m;//线性探测进行查找
if (ha[adr].key==k){//删除成功,将关键词的值置为被删除的状态
ha[adr].key=DELKEY; return true;
}
else return false;//删除失败
}
基本运算合集如下：
#define NULLKEY -1//关键字=NULLKEY表示当前存储单位为空(从没有过结点)
#define DELKEY -2//关键字=DELKEY表示当前存储单位原本的结点被删除
struct HashTable{KeyType key; int count;};//key为关键字值,count为存入关键值key需要探测的次数
//将关键字k插入到哈希表ha中,n为哈希表中总关键字的个数,m为哈希表容量
void InsertHT(HashTable ha[],int &n,int m,int p,KeyType k){
int i,adr; adr=k%p;//adr为存储单元的下标,i为当前探测(查找)的次数
if (ha[adr].key==NULLKEY||ha[adr].key==DELKEY){//当前地址为空,直接存储
ha[adr].key=k; ha[adr].count=1;//仅探测一次
}
else{i=1;//产生冲突,进行线性探测法
do{//每进行一次线性探测,查找的次数+1
adr=(adr+1)%m; i++;
} while (ha[adr].key!=NULLKEY&&ha[adr].key!=DELKEY);
ha[adr].key=k; ha[adr].count=i;//设置探测次数
}n++;
}//创建hash表,n为hash表总关键字个数,m为hash表容量
void CreateHT(HashTable ha[],int &n,int m,int p,KeyType keys[],int n1){
for (int i=0;i
ASL值的计算
查找成功的情况下，每个键值查找成功的比较次数等于对应count的值，所以只需要将所有插入进去的关键词对应的count全部相加，再除以关键词数即可。
不成功的情况比较抽象，具体看代码。
void ASL(HashTable ha[],int n,int m,int p){int j;
int succ=0,unsucc=0,s;
//查找成功的ASL值将hash表中不一直为空的存储单位的检测次数相加
for (int i=0;i
事实上这里的计算还有一个隐藏条件每个关键字值出现的频率相同。
基于拉链法构造的哈希表运算
存储结构
需要一个单链表结点的结构体和头结点指针的结构体。
struct NodeType{KeyType key; struct node *next;};//单链表结点类型,key为关键值,next指向下一个指针
struct HashTable{NodeType *firstp;};//头结点指针
哈希表的创建和插入
创建和插入还是放在一起看。插入就是寻找到需要插入的单链表，然后进行单链表的插入。这里甚至只需要头插法，因为链中结点的相对关系不重要，只需要知道链中的结点都为同义词即可。
//将关键字k插入到哈希表ha中,n为关键字个数
void InsertHT(HashTable ha[],int &n,int p,KeyType k){
int adr; adr=k%p;//计算哈希函数值
NodeType *q; q=(NodeType *)malloc(sizeof(NodeType));
q->key=k; q->next=NULL;//q为新插入的结点
if (ha[adr].firstp==NULL) ha[adr].firstp=q;//若单链表adr为空,新插入的结点即为头结点
else{//采用头插法插入到单链表中即可
q->next=ha[adr].firstp; ha[adr].firstp=q;
}n++;
}
创建哈希表。
//创建哈希表
void CreateHT(HashTable ha[],int &n,int m,int p,KeyType keys[],int n1){
for (int i=0;i
哈希表的查找
总结就是先进行一次hash值的计算查找到需要查找的单链表，再进行单链表的查找。
//在哈希表中查找关键字k
void SearchHT(HashTable ha[],int p,KeyType k){int i=0,adr; adr=k%p;//计算哈希函数值
NodeType *q; q=ha[adr].firstp;//用q扫描需要查询的单链表
while (q!=NULL){i++;//i为查找次数
if (q->key==k) break;//查找成功
q=q->next;
}
if (q!=NULL) printf("成功：关键字%d，比较%d次n",k,i);//查找成功
else printf("失败：关键字%d，比较%d次n",k,i);//查找失败
}
哈希表的删除
查找到需要删除结点的单链表，进行单链表结点的删除。
//删除哈希表中关键字k
bool DeleteHT(HashTable ha[],int &n,int m,int p,KeyType k){NodeType *q,*preq;
int adr; adr=k%p;//计算哈希函数值
q=ha[adr].firstp;//q指向对应单链表的首结点
if (q==NULL) return false;//对应单链表为空,删除失败
if (q->key==k){//头结点为需要删除的结点,需要修改头结点的值
ha[adr].firstp=q->next; free(q);
n--; return true;//结点个数-1,删除成功
}preq=q; q=q->next;
while (q!=NULL){//需要删除的结点不是头结点,查找到需要删除的结点的位置
if (q->key==k) break;//找到结点退出循环
q=q->next;
}
if (q!=NULL){
preq->next=q->next; free(q);//删除结点q
n--; return true;//结点个数-1,删除成功
}
else return false;//未找到键值为k的结点,删除失败
}
基本操作合集如下：
struct NodeType{KeyType key; struct node *next;};//单链表结点类型,key为关键值,next指向下一个指针
struct HashTable{NodeType *firstp;};//头结点指针
//将关键字k插入到哈希表ha中,n为关键字个数
void InsertHT(HashTable ha[],int &n,int p,KeyType k){int adr; adr=k%p;//计算哈希函数值
NodeType *q; q=(NodeType *)malloc(sizeof(NodeType));
q->key=k; q->next=NULL;//q为新插入的结点
if (ha[adr].firstp==NULL) ha[adr].firstp=q;//若单链表adr为空,新插入的结点即为头结点
else{//采用头插法插入到单链表中即可
q->next=ha[adr].firstp; ha[adr].firstp=q;
}n++;
}//创建哈希表
void CreateHT(HashTable ha[],int &n,int m,int p,KeyType keys[],int n1){
for (int i=0;ikey==k) break;//查找成功
q=q->next;
}
if (q!=NULL) printf("成功：关键字%d，比较%d次n",k,i);//查找成功
else printf("失败：关键字%d，比较%d次n",k,i);//查找失败
}//删除哈希表中关键字k
bool DeleteHT(HashTable ha[],int &n,int m,int p,KeyType k){NodeType *q,*preq;
int adr; adr=k%p;//计算哈希函数值
q=ha[adr].firstp;//q指向对应单链表的首结点
if (q==NULL) return false;//对应单链表为空,删除失败
if (q->key==k){//头结点为需要删除的结点,需要修改头结点的值
ha[adr].firstp=q->next; free(q);
n--; return true;//结点个数-1,删除成功
}preq=q; q=q->next;
while (q!=NULL){//需要删除的结点不是头结点,查找到需要删除的结点的位置
if (q->key==k) break;//找到结点退出循环
q=q->next;
}
if (q!=NULL){
preq->next=q->next; free(q);//删除结点q
n--; return true;//结点个数-1,删除成功
}
else return false;//未找到键值为k的结点,删除失败
}
