第3章查找和排序内容摘要：
方法 :通过比较确定元素位置 13/23 二 . 建立哈希表 构造哈希函数常用的方法 – 数字分析法 – 平方取中法 – 折叠法 – 除留余数法 （ 求模取余法 ） – 直接定址法 14/23 三 .冲突及冲突处理 1. 冲突 :在哈希元素 （ 地址 ） 求解过程中 ，不同关键字值对应到同一个存储地址的现象 , 即 K1K2， 但 H（ K1） = H（ K2） 2. 均匀的哈希函数可以减少冲突 ， 不能避免冲突。 3. 处理冲突 •开放地址法 •链地址法 •再哈希法 •公共溢出区法 15/23 处理冲突 —— 开放地址法 发生冲突后 ， 求解下一个地址 Hi =(H(key)+di)MOD m i=1,2,… ,k(k m1) m:哈希表长度 ,di:增量序列 增量序列的不同取法 ， 构成不同的开放地址法。 1)线性探测再散列 di=1,2,… ,m1 2)二次探测再散列 di=12 ,12,22,22, … ,+k2,k2 (k m/2) 16/23 处理冲突 —— 链地址法 发生冲突后 ,将所有函数值相同的记录连成单链表 ： H(41)=H(1)=1 H(67)=3 H(530=H(13)=5 H(22)=H(46)=H(30)=6 1 2 3 4 5 6 7 41 1 NULL 46 13 NULL 30 NULL 22 NULL 53 NULL NULL NULL 67 17/23 四 . 建立哈希表举例 数列 {22,41,53,46,30,13,1,67},表长 9 哈希函数 : H(key) = key MOD 8 , 用线性探测解决冲突 Hi=(H(key)+di) MOD m 1) 计算 H(22） =6， 该地址空 ， 可用； 。阅读剩余 0%
本站所有文章资讯、展示的图片素材等内容均为注册用户上传(部分报媒/平媒内容转载自网络合作媒体)，仅供学习参考。
用户通过本站上传、发布的任何内容的知识产权归属用户或原始著作权人所有。如有侵犯您的版权，请联系我们反馈本站将在三个工作日内改正。