专升本（计算机专业课件)数据结构第章课件散列查找上key讲义.pdf

《专升本（计算机专业课件)数据结构第章课件散列查找上key讲义.pdf》由会员分享，可在线阅读，更多相关《专升本（计算机专业课件)数据结构第章课件散列查找上key讲义.pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、处理冲突的方法拉链法例：有一堆数据元素，关键字分别为19,14,23,1,68,20,84,27,55,11,10,7 9,散列函数H(key)=key%1319%13=614%13=123%13=101%13=168%13=320%13=784%13=627%13=155%13=311%13=1110%13=1079%13=1用拉 链 法(又称链接法、链地址法)处理“冲突”：把所有“同义词”存储在一个链表中散列查找例：有一堆数据元素，关键字分别为19,14,23,1,68,20,84,27,55,11,10,7 9,散列函数H(key)=key%13查找目标:27的查找长度=327第 1 页

2、 共 9 页散列查找例：有一堆数据元素，关键字分别为19,14,23,1,68,20,84,27,55,11,10,7 9,散列函数H(key)=key%13散列查找例：有一堆数据元素，关键字分别为19,14,23,1,68,20,84,27,55,11,10,7 9,散列函数H(key)=key%13查找长度在查找运算中，需要对比关键字的次数称为查找长度第 2 页 共 9 页散列查找例：有一堆数据元素，关键字分别为19,14,23,1,68,20,84,27,55,11,10,7 9,散列函数H(key)=key%131055查找目标:2127U79亲，这 边 建 议 您 通过散列函数计算目

3、标元素存储地址：Addr=H(Key)去看看学校真超呢21%13=821的查找长度=1 v有的教材也会把“空指针”的判定算作一次比较散列查找例：有一堆数据元素，关键字分别为19,14,23,1,68,20,84,27,55,11,10,7 9,散列函数H(key)=key%13查找目标:66的查找长度=466第3页 共9页散列查找例：有一堆数据元素，关键字分别为19,14,23,1,68,20,84,27,55,11,10,7 9,散列函数H(key)=key%13散列查找例：有一堆数据元素，关键字分别为19,14,23,1,68,20,84,27,55,11,10,7 9,散列函数H(key

4、)=key%13最理想情况：散列查找时间复杂度可到达0(1)ASL成 功 二1 +1+1+1+141+j+H 】+!+运+1欲言又止稍加思考如何设计冲突更I少的散列函数？12=1第 4 页 共 9 页散列查找例：有一堆数据元素，关键字分别为19,14,23,1,68,20,84,27,55,11,10,7 9,散列函数H(key)=key%13常见的散列函数设计目标一一让不同关键字的冲突尽可能地少除留余数法-H(key)=key%p散列表表长为m,取一个不大于m但最接近或等于m的质数p巳质数又称素数。指除了 1和此整数自身外,不能被其他自然数整除的数例：散列表表长1 3,散列函数H(key)=

5、key%13例：散列表表长1 5,散列函数H(key)=key%1314第 5 页 共 9 页常见的散列函数E设计目标一一让不同关键字的冲突尽可能地少除留余数法-H(key)=key%p散列表表长为m,取一个不大于m但最接近或等于m的质数p设：可能出现的关键字=1,2,3,4,5,6,7,8,9,102质数又称素数。指除了 1和此整数自II身外,不能被其他自然数整除的数0 1 2 3 4 5 6 7散列表表长8,散列函数H(key)=key%80 1 2 3 4 5 6 7散列表表长8,散列函数H(key)=key%7常见的散列函数设计目标一一让不同关键字的冲突尽可能地少除留余数法-H(key

6、)=key%p散列表表长为m,取一个不大于m但最接近或等于m的质数p质数又称素数。指除了 1和此整数自身外,不能被其他自然数整除的数设：可能出现的关键字=2,4,6,8,10,12 Y如：中国人更喜欢双数，车牌号散列表表长8,散列函数H(key)=key%8双数更多散列表表长8,散列函数H(key)=key%7一一用质数取模，分布更均匀，冲突更少。参 见 数论Tips：散列函数的设计要结合实际的关键字分布特点来考虑，不要教条化第 6 页 共 9 页常见的散列函数设计目标一一让不同关键字的冲突尽可能地少直接定址法-H(key)=key 或 H(key)=a*key+b其中，a和b是常数。这种方法

7、计算最简单，且不会产生冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。例：存储同一个班级的学生信息，班内学生学号为(1120112176Tl20112205)H(key)=key-11201121760 1 2 3 4 5.26 27 28 29.176.177.178.179.180.181.202.203.204.205常见的散列函数设计目标一一让不同关键字的冲突尽可能地少数字分析法 选取数码分布较为均匀的若干位作为散列地址设关键字是r进 制 数(如 十 进 制 数)，而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码

8、出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时可选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。例：以“手机号码”作为关键字设计散列函数138XXXX2875138XXXX1682138XXXX9125设计长度为10000的散列表，以手机号后四位作为散列地址199XXXX1684199XXXX12369998 9999第7页 共9页常见的散列函数E设计目标一一让不同关键字的冲突尽可能地少平方取中法一一取关键字的平方值的中间几位作为散列地址。具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每

9、位都有关系，因此使得散列地址分布比较均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。13102=1,716,10011102=1,232,10013002=1,690,00012102=1,464,10012002=1,440,000常见的散列函数V设计目标一一让不同关键字的冲突尽可能地少平方取中法一一取关键字的平方值的中间几位作为散列地址。具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。例：要存储整个学校的学生信息，以“身份证号”作为关键字设计散列函数身份证

10、号码规则：前1、2位数字表示：所在省份的代码；第3、4位数字表示：所在城市的代码；第5、6位数字表示：所在区县的代码；第7-14位数字表示：出生年、月、日；第15、16位数字表示：所在地的派出所的代码；第17位数字表示性别：奇数表示男性，偶数表示女性;第18位数字是校检码。99999假设学生不超过十万人，可身份证号平方取中间5位第8页 共9页常见的散列函数设计目标一一让不同关键字的冲突尽可能地少例：要存储整个学校的学生信息，以“身份证号”作为关键字设计散列函数999999999999999999若散列表的长度为1000000000000000000（别数了，有18个0 3）则可以直接用身份证号作为散列地址，且不可能有冲突，查找时间复杂度为。散列查找是典型的“用空间换时间”的算法，只要散列函数设计的合理，则散列表越长，冲突的概率越低。知识回顾与重要考点下次一定第9页 共9页