| 网站首页 | 技术文章 | 下载频道 | 博客 | 编程论坛 |
 
| 技术教程首页 | 开发语言 | WEB开发 | .NET技术 | 数据库 | 操作系统 | 网页制作 |
 
 
您现在的位置: 编程中国 >> 技术教程 >> 开发语言 >> 数据结构 >> 正文
  ►  数据结构教程 第三十三课 哈希表(二)
数据结构教程 第三十三课 哈希表(二)
作者:未知    阅读人次:……    文章来源:未知    发布时间:2004/11/12    网友评论()条
 

教学目的: 掌握哈希表处理冲突的方法及哈希表的查找算法

教学重点: 哈希表处理冲突的方法

教学难点: 开放定址法

授课内容:

一、复习上次课内容

什么是哈希表?如何构造哈希表?

提出问题:如何处理冲突?

二、处理冲突的方法

    成绩一 成绩二...
3 ...    
... ...  
24 刘丽 82 95
25 ...    
26 陈伟    
... ...    
33 吴军    
... ...    
42 李秋梅    
... ...    
46 刘宏英    
... ...    
72 吴小艳    
... ...    
78 ...    

如果两个同学分别叫 刘丽 刘兰,当加入刘兰时,地址24发生了冲突,我们可以以某种规律使用其它的存储位置,如果选择的一个其它位置仍有冲突,则再选下一个,直到找到没有冲突的位置。选择其它位置的方法有:

1、开放定址法

Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1)

其中m为表长,di为增量序列

如果di值可能为1,2,3,...m-1,称线性探测再散列

如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2)

二次探测再散列

如果di取值可能为伪随机数列。称伪随机探测再散列

例:在长度为11的哈希表中已填有关键字分别为17,60,29的记录,现有第四个记录,其关键字为38,由哈希函数得到地址为5,若用线性探测再散列,如下:

0 1 2 3 4 5 6 7 8 9 10
          60 17 29      

(a)插入前

0 1 2 3 4 5 6 7 8 9 10
          60 17 29 38    

(b)线性探测再散列

0 1 2 3 4 5 6 7 8 9 10
          60 17 29      

(c)二次探测再散列

0 1 2 3 4 5 6 7 8 9 10
      38   60 17 29      

(d)伪随机探测再散列

伪随机数列为9,5,3,8,1...

2、再哈希法

当发生冲突时,使用第二个、第三个、哈希函数计算地址,直到无冲突时。缺点:计算时间增加。

3、链地址法

将所有关键字为同义词的记录存储在同一线性链表中。

4、建立一个公共溢出区

假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表,另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。

三、哈希表的查找

//开放定址哈希表的存储结构

int hashsize[]={997,...};

typedef struct{

ElemType *elem;

int count;

int sizeindex;

}HashTable;

#define SUCCESS 1

#define UNSUCCESS 0

#define DUPLICATE -1

Status SearchHash(HashTable H,KeyType K,int &p,int &c){

p=Hash(K);

while(H.elem[p].key!=NULLKEY && !EQ(K,H.elem[p].key))

collision(p,++c);

if(EQ(K,H.elem[p].key)

return SUCCESS;

else return UNSUCCESS;

}

Status InsertHash(HashTable &H,EleType e){

c=0;

if(SearchHash(H,e.key,p,c))

return DUPLICATE;

else if(c<hashsize[H.sizeindex]/2){

H.elem[p]=e; ++H.count; return OK;

}

else RecreateHashTable(H);

}

四、总结

处理冲突的要求是什么?

 

 
文章录入:静夜思    责任编辑:静夜思 
  • 上一篇文章:

  • 下一篇文章:

  •  
    相关文章
    原创地带
    24小时热门帖子