哈希技术
在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字对于一个存储位置f(key)，这种对应关系成为散列函数，又称为哈希函数
散列表/哈希表(Hash Table)
通过哈希技术将记录存储在一块连续的存储空间中，这块连续的存储空间就成为散列表或者哈希表
哈希表的本质
哈希表的本质是一个数组，哈希表是经过加工处理的数组。一般来说，哈希表的实现一般采用两种办法:
- 数组+链表
- 数组+二叉树
为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表（即建立人名 x 到首字母 F(x) 的一个函数关系），在首字母为 W 的表中查找“王”姓的电话号码，显然比直接查找就要快得多。这里使用人名作为关键字，“取首字母”是这个例子中散列函数的函数法则 F()，存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。
散列函数的构造
直接定址法
使用关键字的某个线性函数值直接作为地址
f(key)=a*key+b(a,b常数)
Tips;这种方式基本不会存在哈希冲突，不过比较鸡肋.
数字分析法
如果关键字是位数较多的数字且事先知道关键字的分布,则抽取关键字的一部分来计算散列位置的存储位置
Tips：这种方式极度不灵活，限制太多.
平方取中法
顾名思义,对关键字进行平方后取中间的几位数,比较适用于不知道关键字的分布,而位数又不是很多的情况,可以理解为数字分析法的一种更高级的办法
Tips：这种方式中间的几位数都和关键字的每一位都有关，产生的散列地址较为的均匀。
折叠法
将关键字从左至右分割成位数相等的几部分,然后将这几部分叠加求和,根据表长取结果的后几位作为散列地址,适用于关键字位数较多的情况
除留余数法
最常用的构造散列函数的方法,对于散列表长为m的散列函数公式为:
f(key)=key mod p(p≤m)
Tips:可以与折叠法,平法取中法联用,即在折叠法、平方取中法等运算之后取模.对 p 的选择很重要，一般取素数或 m,若 p 选择不好,容易产生碰撞.
随机法
利用random函数随机产生关键字的地址,适合用于关键字的长度不等时
哈希冲突
key1≠key2,f(key1)=f(key2)
处理哈希冲突
开放定址法
链地址法
公共溢出法
再散列
实现代码
typedef struct
{
int *elem;//数据元素存储基址,动态分布数组
int count;//当前数据元素个数
}HashTable;
int m=0;//散列表表长
int InitHashTable(HashTable *H)
{
int i;
m=HASHSIZE;
H->count=m;
H->elem=(int *)malloc(m*sizeof(int));
for(i=0;i<m;i++)
H->elem[i]=NULLKEY;
}
int Hash(int key)
{
return key % m;//除留余数法
}
void InsertHash(HashTable *H,int key)//插入操作
{
int addr=Hash(key);
while(H->elem[addr]!=NULLKEY)//如果不为空,则冲突
addr=(addr+1)%m;
H->elem[addr]=key;//找到空位后插入关键字
}
int SearchHash(HashTable H,int key,int *addr)
{
*addr=Hash(key);//求散列地址
while(H.elem[*addr]!=key)
{
*addr=(*addr+1)%m;//开放地址线性探测法
if(H.elem[*addr]==NULLKEY||*addr==Hash(key))//如果循环回到原点或者最终指向NULL说明关键字不存在
return 0;
}
return 1;
}