songzi 2008-5-6 23:04
哈希表(二）（数据结构）
一、复习上次课内容
[indent]什么是哈希表？如何构造哈希表？
提出问题：如何处理冲突？
[/indent]二、处理冲突的方法
[indent][table=75%][tr=#ffffff][td=1,1,8%] [/td][td=1,1,15%] [/td][td=1,1,13%]成绩一[/td][td=1,1,64%]成绩二...[/td][/tr][tr=#ccffcc][td=1,1,8%]3[/td][td=1,1,15%]...[/td][td=1,1,13%] [/td][td=1,1,64%] [/td][/tr][tr=#ccffcc][td=1,1,8%][color=#ffccff]...[/color][/td][td=1,1,15%][color=#ffccff]...[/color][/td][td=1,1,13%] [/td][td=1,1,64%][color=#ffccff][/color][/td][/tr][tr][td=1,1,8%]24[/td][td=1,1,15%]刘丽[/td][td=1,1,13%]82[/td][td=1,1,64%]95[/td][/tr][tr=#ccffcc][td=1,1,8%]25[/td][td=1,1,15%]...[/td][td=1,1,13%] [/td][td=1,1,64%] [/td][/tr][tr][td=1,1,8%]26[/td][td=1,1,15%]陈伟[/td][td=1,1,13%] [/td][td=1,1,64%] [/td][/tr][tr=#ccffcc][td=1,1,8%]...[/td][td=1,1,15%]...[/td][td=1,1,13%] [/td][td=1,1,64%] [/td][/tr][tr][td=1,1,8%]33[/td][td=1,1,15%]吴军[/td][td=1,1,13%] [/td][td=1,1,64%] [/td][/tr][tr=#ccffcc][td=1,1,8%]...[/td][td=1,1,15%]...[/td][td=1,1,13%] [/td][td=1,1,64%] [/td][/tr][tr][td=1,1,8%]42[/td][td=1,1,15%]李秋梅[/td][td=1,1,13%] [/td][td=1,1,64%] [/td][/tr][tr=#ccffcc][td=1,1,8%]...[/td][td=1,1,15%]...[/td][td=1,1,13%] [/td][td=1,1,64%] [/td][/tr][tr][td=1,1,8%]46[/td][td=1,1,15%]刘宏英[/td][td=1,1,13%] [/td][td=1,1,64%] [/td][/tr][tr=#ccffcc][td=1,1,8%]...[/td][td=1,1,15%]...[/td][td=1,1,13%] [/td][td=1,1,64%] [/td][/tr][tr][td=1,1,8%]72[/td][td=1,1,15%]吴小艳[/td][td=1,1,13%] [/td][td=1,1,64%] [/td][/tr][tr=#ccffcc][td=1,1,8%]...[/td][td=1,1,15%]...[/td][td=1,1,13%] [/td][td=1,1,64%] [/td][/tr][tr=#ccffcc][td=1,1,8%]78[/td][td=1,1,15%]...[/td][td=1,1,13%] [/td][td=1,1,64%] [/td][/tr][/table]如果两个同学分别叫 刘丽 刘兰，当加入刘兰时，地址24发生了冲突，我们可以以某种规律使用其它的存储位置，如果选择的一个其它位置仍有冲突，则再选下一个，直到找到没有冲突的位置。选择其它位置的方法有：
１、开放定址法
[indent]Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1)
其中m为表长，di为增量序列
如果di值可能为1,2,3,...m-1，称[color=#ff0033]线性探测再散列[/color]。
如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2)
称[color=#ff0033]二次探测再散列[/color]。
如果di取值可能为[color=#ff0033]伪随机数列[/color]。称[color=#ff0033]伪随机探测再散列[/color]。
例：在长度为11的哈希表中已填有关键字分别为17,60,29的记录，现有第四个记录，其关键字为38，由哈希函数得到地址为5，若用线性探测再散列，如下：
[align=center][table=75%][tr][td]0[/td][td]1[/td][td]2[/td][td]3[/td][td]4[/td][td]5[/td][td]6[/td][td]7[/td][td]8[/td][td]9[/td][td]10[/td][/tr][tr=#ffcccc][td] [/td][td] [/td][td] [/td][td] [/td][td] [/td][td]60[/td][td]17[/td][td]29[/td][td] [/td][td] [/td][td] [/td][/tr][/table][/align][align=center](a)插入前[/align][align=center][table=75%][tr][td]0[/td][td]1[/td][td]2[/td][td]3[/td][td]4[/td][td]5[/td][td]6[/td][td]7[/td][td]8[/td][td]9[/td][td]10[/td][/tr][tr=#ffcccc][td] [/td][td] [/td][td] [/td][td] [/td][td] [/td][td]60[/td][td]17[/td][td]29[/td][td]38[/td][td] [/td][td] [/td][/tr][/table][/align][align=center](b)线性探测再散列[/align][align=center][table=75%][tr][td]0[/td][td]1[/td][td]2[/td][td]3[/td][td]4[/td][td]5[/td][td]6[/td][td]7[/td][td]8[/td][td]9[/td][td]10[/td][/tr][tr=#ffcccc][td] [/td][td] [/td][td] [/td][td] [/td][td] [/td][td]60[/td][td]17[/td][td]29[/td][td] [/td][td] [/td][td] [/td][/tr][/table][/align][align=center](c)二次探测再散列[/align][align=center][table=75%][tr][td]0[/td][td]1[/td][td]2[/td][td]3[/td][td]4[/td][td]5[/td][td]6[/td][td]7[/td][td]8[/td][td]9[/td][td]10[/td][/tr][tr=#ffcccc][td] [/td][td] [/td][td] [/td][td]38[/td][td] [/td][td]60[/td][td]17[/td][td]29[/td][td] [/td][td] [/td][td] [/td][/tr][/table][/align][align=center](d)伪随机探测再散列[/align][align=center]伪随机数列为9,5,3,8,1...[/align][/indent]２、再哈希法
[indent]当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。缺点：计算时间增加。
[/indent]３、链地址法
[indent]将所有关键字为同义词的记录存储在同一线性链表中。
[img=314,294]http://www.bccn.net/Article/UploadFDL05/200411/20041112073744336.jpg[/img]
[/indent]４、建立一个公共溢出区
[indent]假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表，另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。
[/indent][/indent]三、哈希表的查找
[indent]//开放定址哈希表的存储结构
int hashsize[]={997,...};
typedef struct{
[indent]ElemType *elem;
int count;
int sizeindex;
[/indent]}HashTable;
#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1
Status SearchHash(HashTable H,KeyType K,int &p,int &c){
[indent]p=Hash(K);
while(H.elem[p].key!=NULLKEY && !EQ(K,H.elem[p].key))
[indent]collision(p,++c);
[/indent]if(EQ(K,H.elem[p].key)
[indent]return SUCCESS;
[/indent]else return UNSUCCESS;
[/indent]}
Status InsertHash(HashTable &H,EleType e){
[indent]c=0;
if(SearchHash(H,e.key,p,c))
[indent]return DUPLICATE;
[/indent]else if(c<hashsize[H.sizeindex]/2){
[indent]H.elem[p]=e; ++H.count; return OK;
}
[/indent]else RecreateHashTable(H);
[/indent]}
[/indent]四、总结
[indent]处理冲突的要求是什么？
[/indent]