(10)--第七章第五节哈希表-哈希表的查找及性能分析.pdf

目录01【哈希表的查找及冲突处理】

CONTENTS02【哈希表的查找性能分析】

01哈希表的查找及冲突处理

•冲突：不同的关键字映射到相同的哈希地址。

•处理冲突的方法：

–(1)开放定址法

•用H(key)⊕d，如：线性探测再散列：

i

•H(key)⊕1，H(key)⊕2，...

–(2)再哈希法

•H(key)冲突，试用H(key)，H(key)，...

123

–(3)链地址法

•发生冲突的记录链成单链表。

–(4)建立公共溢出区

•所有冲突记录存入溢出区。

1构造哈希表举例：

•例：关键字{19,14,23,1,68,20,85,9}，哈希函数

H(key)=keyMOD11，用下列方法处理冲突，构造哈希表，

并计算平均查找长度。

–（1）开放定址法（线性探测再散列）

•方法：从空表开始，依次插入关键字构造哈希表。

012345678910

1构造哈希表举例：

–关键字：{19,14,23,1,68,20,85,9}

–哈希函数：H(key)=keyMOD11

–处理冲突：开放定址法（线性探测再散列）

key19142316820859

H(key)83112989

+123910

+24100

查找长度11123133ASL=15/8

012345678910

92311468192085

31213113

2链地址法构造哈希表

–关键字：{19,14,23,1,68,20,0/\

85,9}1231/\

–哈希函数：H(key)=keyMOD268/\

314/\

11

4/\

–处理冲突：链地址法5/\

key191423168208596/\

H(key)831129897/\

查找长度111