列表与探测法"/>

散列表与探测法

动态查找的时候,如果用查找树同时对俩个变量名(字符串)进行查找,会导致效率不高的问题.
引入散列的思想:把字符串变成数字,使得对字符串的比较变成对数字的比较.

查找的本质:已知对象求位置
(1)有序安排对象:半序,全序
(2)直接算出的对象位置:散列

散列的基本概述

散列查找法的俩项基本工作:

计算位置:构造散列函数确定关键词的存储位置
解决冲突:应用某种策略解决多个关键词位置相同的问题

时间复杂度是O(1),查找时间和问题规模无关.

散列表(哈希表)

装填因子:设散列表空间大小是m,填入表中的元素个数是n.则称a=n/m是散列表的装填因子.

散列函数的构造方法

一个好的散列函数需要考虑以下俩个因素:
1)计算简单,以便于提高转换速度.
2)关键字对应的地址空间分布均匀,以尽量减少冲突.

数字构造

(1)直接定址法:取关键词的某个线性函数值作为散列地址,h(key)=a*key+b

(2)除留余数法
此时的p一般取Tablesize,满足p是素数.

(3)数字分析法
分析数字关键字在各位上的变化情况,取比较随机的位作为散列地址.

(4)折叠法
把关键词分割成位数相同的几部分,然后叠加.

(5)平方取中法

字符构造

1.一个简单的散列函数—ASCII码加和法
2.前三个字符移位法
3.好的散列函数—移位法
（设计关键词中所有的n个字符，并且分布的好）

Index Hash(const char*Key,int TableSize)
{unsigned int h=0;//散列函数值初始化为0while(*key !='\0'){h=(h<<5)+*k++;}return h%TableSize;
}

处理冲突的方法：

换个位置：开放地址法

一旦发生冲突之后（该地址已有其他元素），按照某种规则去寻找另外一个空的地址。

1）若发生了第i次冲突，试探的下一个位置将会增加d(i),基本公式是 h(key)=(h（key)+d) mod tablesize
2)根据d的不同设计三种解决冲突方法：线性探测，平方探测，双散列

线性探测

令d=i(以增量序列1，2……（TableSize-1)循环试探下一个存储地址
会产生聚集现象。

平方探测法

以增量序列±q^2的增量序列来循环探测下一个存储地址 q<=[tablesize/2]
二次探测不一定能够探测得到每个位置，但是如果散列表长度设置为某个（4k+3)形式的素数的时候，平方探测法就可以探查整个散列表的空间。

typedef struct HashTbl*HashTable;
struct HashTbl{int TableSize;Cell* TheCells;}HashTable inilt(int TableSize)
{HashTable H;if(TableSize<min){Error("散列表太小");return NULL;}//分配散列表H=(HashTable)malloc(sizeof(struct HashTbl));if(H==NULL){FatalError("空间溢出");}H->TableSize=nextPrime(TableSize);//分配散列表cellsH->TheCells=(Cell*)malloc(sizeof(Cell)*H->TableSize);if(H->TheCells==null)Error("空间溢出");for(i=0;i<H->TableSize;i++)H->TheCell{i].info=Empty;return H;}Position Find(int key,HashTable H)
{Position cur,new;int cnum=0;//记录冲突次数new=cur=Hash(Key,H->TableSize);while(H->TheCells[NewPos].info !=Empty && H->TheCells[New]. E!=Key){//字符串类型的关键词需要strcmp函数if(++cnum%2){new=cur+(cunm+1)/2*(cum+1)/2;while(new>=H->TableSize)new-=H->TableSize;}else{new=cur-cnum/2-cnum/2;while(new<0)new+=H->TableSize;}}return new;}    

在开放地址散列表中，删除操作要很小心。通常只能”懒惰删除",也就是需要增加一个删除标记（Deleted),而并不是要真正删除它，以便于查找的时候不会断链，其空间可以在下次插入的时候重用。

双散列探测法

探测序列应该保证所有的散列存储单元都能够被探测得到，应该具有以下的效果。
d(i)为i*h2（key)

h2(key)=p-(key mod p)

再散列

当散列表的元素太多，装填因子a过大，查找效率会降低。
散列表扩大时候，原有元素要重新计算放置到新表中。
一般装填因子的范围是0.5~0.75

分离链接法

同一位置的冲突对象组织在一起，放在同一个单链表中：链地址法

ListNode* Find(int key,HashTable H)
{ListNode* P;int pos;pos=Hash(Key,H->TableSize);//初始散列位置P=H->Thelists[pos].Next;//获取链表头while(P!=null && strcmp(P->e,Key))P=P->next;return P;
}

散列表的性能分析

平均查找长度（ASL）用来度量散列表的查找效率：成功和不成功
关键词的比较次数取决于产生冲突的多少
影响冲突的三个因素：
1）散列函数是否均匀
2）处理冲突的方法
3）散列表的装填因子a

选择合适的h(Key),散列表的查找期望是常数O（1），它几乎与关键字的空间大小n无关！也适合于关键字直接比较量大的问题 。
它是以较小的装填因子为前提，因此散列方法是以空间换取时间的策略。
散列存储对关键字是随机的，不便于顺序查找关键字，也不适合范围查找或者最大值最小值查找。
开放地址法：散列表是一个数组，存储效率搞，随机查找。但是它容易出现聚集现象。
分离链接法：散列表是顺序存储和链式存储的结合，链表

部分的存储效率和查找效率都比较低。