资源描述：
《数据结构_课件_散列表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、散列表在查找的过程中，时间主要用于关键字值间的比较。 可不可以不经过关键字值间的比较就找到我要的记录呢？一、基本概念若能在待查记录的关键字值和它的存储位置之间建立一个确定的对应关系则查找时不必再进行关键字值间的比较！一、基本概念举例一、基本概念学号姓名成绩32001王春玲82032002李月何93132003孙志77232004杨小强85332005周泉624关键字值存储地址存储地址=关键字值-32001哈希函数一、基本概念关键字值和存储地址要一一对应的！你每次都有那么好的运气，能构造出理想的哈希函数吗？举例一、基本概念电话号码姓名5278
2、630王春玲5379624李月何5238477孙志5966554杨小强5238121周泉关键字值存储地址存储地址=关键字值中的个位数0123456789527863053796245238477冲突！59665545238121定义根据设定的哈希函数及处理冲突的方法将查找表中各数据元素存储在一段有限的连续空间中，即得哈希表。一、基本概念基本要求二、构造哈希函数的基本方法设关键字集K中有n个关键字，哈希表长为m，即哈希表地址集为[0,m-1]，则哈希函数H应满足：1.对任意ki∈K，i=1,2,…,n，有0≤H(ki)≤m-1；2.对任意ki∈K
3、，H(ki)取[0,m-1]中任一值的概率相等。方法取关键字key的一个线性函数为哈希函数，即：H(key)=a×key+b，其中a、b为常数，且a≠0。1、直接定址法举例1、直接定址法设有人口统计表如下，试以直接定址法设计哈希函数。年龄人数1岁14322岁2318……100岁15存储地址01…99H(key)=key-1keyHH(key)2、数字分析法方法若关键字是ｒ进制数，且可预知全部可能出现的关键字值，则可取关键字中若干位构成哈希地址。设要在长为100的哈希地址空间中保存80个数据元素，部分关键字值如下，试用数字分析法设计哈希函数。举例
4、位号：①②③④⑤⑥⑦⑧ ①②③④⑤⑥⑦⑧８１３４６５３２ ８１３３８９６７８１３７２２４２ ８１３５４１５７８１３８７４２２ ８１３６８５３７８１３０１３６７ ８１４１９３５５８１３２２８１７ ８１４９０２７５可取④⑤⑥⑦中任意两位为哈希地址H(key)=key%100000/10002、数字分析法方法若关键字较短，则可先对关键字值求平方，然后取运算结果的中间几位为哈希地址。3、平方取中法3、平方取中法举例设某计算机语言中标识符定义为一个字母或一个字母加一个数字，又知字母、数字的机内码（以八进制数表示）如下：
5、Ａ：０１ Ｂ：０２ Ｃ：０３…Ｚ：３２０：６０ １：６１ ２：６２…９：７１现以标识符的机内码为关键字，构造哈希表，试用平方取中法设计哈希函数。标识符ＡＩＪＩ０Ｐ１Ｐ２Ｑ１Ｑ２Ｑ３机内码的平方值００１００００１２１００００１４４００００１３７０４００４３１０５４１４３１４７０４４７３４７４１４７４１３０４４７４５６５１机内码０１００１１００１２００１１６０２０６１２０６２２１６１２１６２２１６３H(key)=(key*key)/1000%1000举例4、折叠法移位叠加将各部分按最低位对齐，然后相加；间界叠加将关键字值从一端向另一端沿分界线来回折
6、迭，然后对齐相加。方法将关键字值分割成位数相同的几个部分，然后取这几部分的叠加和（舍去进位）作为哈希地址。4、折叠法举例设某图书馆的馆藏图书不足10000种，现欲以国际标准图书编号为关键字构造哈希表，试用折叠法设计哈希函数。移位叠加58644220040088+1设有编号：0-442-20586-4，即：0442205864，由低位向高位，每四位一折，可得三段，再将各部分按最低位对齐后相加，并舍去进位，即得对应的哈希地址。4、折叠法举例设某图书馆的馆藏图书不足10000种，现欲以国际标准图书编号为关键字构造哈希表，试用折叠法设计哈希函数。间界叠
7、加58640224046092+设有编号：0-442-20586-4，即：0442205864，由低位向高位，每四位为一段，各段沿分割界来回折迭后对齐相加，舍去进位即得哈希地址。5、除留余数法方法取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。一般情况下，p应为质数举例设有一组关键字如下：（19,14,23,01,68,20,84,27,55,11,10,79），试用除留余数法设计哈希函数。可取p为13，即令H(key)=key%13。5、除留余数法给定一组关键字为:12,39,18,24,33,21，若取p=9,则他们对应的哈希
8、函数值将为:3,3,0,6,6,3例如：为什么要对p加限制？可见，若p中含质因子3,则所有含质因子3的关键字均映射到“3的倍数”的地址上，从而增加了“
