哈希表
基本知识
Hash，一般翻译做“散列”，也有直接音译为”哈希“的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
HASH主要用于信息安全领域中加密算法，他把一些不同长度的信息转化成杂乱的128位的编码里,叫做HASH值. 也可以说，hash就是找到一种数据内容和数据存放地址之间的映射关系
基本概念
* 若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function)，按这个思想建立的表为散列表。
* 对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，这种现象称冲突。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象” 作为记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称散列地址。
* 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数(Uniform Hash function)，这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。
常用的构造散列函数的方法
散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位ǐ
1. 直接寻址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a•key + b，其中a和b为常数（这种散列函数叫做自身函数）
2. 数字分析法
3. 平方取中法
4. 折叠法
5. 随机数法
6. 除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p, p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。
处理冲突的方法
1. 开放寻址法；Hi=(H(key) + di) MOD m, i=1,2,…, k(k<=m-1)，其中H(key)为散列函数，m为散列表长，di为增量序列，可有下列三种取法：
1. di=1,2,3,…, m-1，称线性探测再散列；
2. di=1^2, (-1)^2, 2^2,(-2)^2, (3)^2, …, ±(k)^2,(k<=m/2)称二次探测再散列;
3. di=伪随机数序列，称伪随机探测再散列。 ==
2. 再散列法：Hi=RHi(key), i=1,2,…,k RHi均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。
3. 链地址法(拉链法)
4. 建立一个公共溢出区
查找的性能分析
散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均查找长度来衡量。
查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素：
1. 散列函数是否均匀；
2. 处理冲突的方法；
3. 散列表的装填因子。
散列表的装填因子定义为：α= 填入表中的元素个数 / 散列表的长度
α是散列表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小。
实际上，散列表的平均查找长度是装填因子α的函数，只是不同处理冲突的方法有不同的函数。
字符串哈希函数（著名的ELFhash算法）
int ELFhash(char *key)
{ unsigned long h=0;
while(*key)
{ h=(h<<4)+*key++;
unsigned long g=h&0Xf0000000L;
if(g) h^=g>>24;
h&=~g;
}
return h%MOD;
}
下面是一个Hash表及其功能实现
typedef struct //定义哈希表的结构
{int elem[MAXSIZE]; //数据元素体
HAVEORNOT elemflag[MAXSIZE]; //元素状态标志，没有记录、有记录、有过记录但已被删除
int count; //哈希表中当前元素的个数
}HashTable;
BOOL DeleteHash(HashTable &H,Record e)
{//在查找成功时删除待删元素e，并返回True，否则返回False
int &p;
if(!SearchHash(H,e.keynum,p)) //表中不存在待删元素
return False;
else
{H.elemflag[p]=DELKEY; //设置标志为DELKEY，表明该元素已被删除
H.count--; //哈希表当前长度减一
return True;
}
}
BOOL SearchHash(HashTable H,int k,int &p)
{//在开放定址哈希表H中查找关键字为k的数据元素，若查找成功，以p指示
//待查数据元素在表中的位置，并返回True；否则，以p指示插入位置，并
//返回False
int &p1;
p1=p=Hash(k); //求得哈希地址
while(H.elemflag[p]==HAVEKEY&&k!=H.elem[p])
//该位置中填有记录并且关键字不相等
{p++; //冲突处理方法：线性探测再散列
if(p>=MAXSIZE) p=p%MAXSIZE; //循环搜索
if(p==p1) return False; //整个表已搜索完，没有找到待查元素
}
if(k==H.elem[p]&&H.elemflag[p]==HAVEKEY) //查找成功，p指示待查元素位置
return True;
else return False; //查找不成功
}
1、用数组
[c-sharp] view plaincopy
#include <stdio.h>
#define N 4
typedef int datatype;
typedef struct
{
datatype key;
}Hretype;
int LHashsearch(Hretype HT[N], datatype k)
{
int addr,i=0;
addr = k % N;
while(i<N && HT[addr].key != -1 && HT[addr].key != k)
{
i++;
addr = (addr+1)%N;
}
if(i == N)
return -1; //表溢出
else
return addr;
}
int LHinsert(Hretype HT[N], Hretype R)
{
int addr;
addr = LHashsearch(HT, R.key);
if(addr==-1 || HT[addr].key == R.key)
{
return 1;
}
else
{
HT[addr] = R;
return 0;
}
}
int main()
{
Hretype R[6];
Hretype HT[N];
for(int i=0;i<N;i++)
HT[i].key = -1;
for(i=0;i<6;i++)
R[i].key = i;
for(i=0;i<6;i++)
{
int value = LHinsert(HT,R[i]);
if(value)
printf("表溢出或记录已存在!/n");
else
{
printf("插入成功!/n");
}
}
return 0;
}
2、用链表
[c-sharp] view plaincopy
#include <stdio.h>
#include <stdlib.h>
#define N 4
typedef int datatype;
typedef struct node
{
datatype key;
struct node *next;
}Renode;
Renode *LinkHsearch(Renode *HT[N], datatype k)
{
Renode *p;
int addr = k % N;
p = HT[addr];
while(p && p->key !=k)
p = p->next;
return p;
}
void LinkHinsert(Renode *HT[N], Renode *S)
{
int addr;
Renode *p;
p = LinkHsearch(HT,S->key);
if(p)
{
printf("记录已存在/n");
free(S);
}
else
{
addr = S->key % N;
S->next = HT[addr];
HT[addr] = S;
printf("已插入/n");
}
}
int main()
{
Renode *HT[N];
//指针数组初始化
for(int i=0;i<N;i++)
HT[i] = NULL;
for(i=0;i<6;i++)
{
Renode *S = (Renode*)malloc(sizeof(Renode));
S->key = i;
LinkHinsert(HT,S);
}
for(i=0;i<6;i++)
{
Renode *S = (Renode*)malloc(sizeof(Renode));
S->key = i;
LinkHinsert(HT,S); //注意指针数组实参
}
return 0;
}