数据结构（Python Java）（微课版） 课件 8.4 散列查找

数据结构与算法设计散列查找散列函数冲突处理8.4散列表查找查找性能分析概念的引入二分法，顺序查找，二叉排序树都以关键字的比较作为查找的基础如果建立关键字与存储地址的映射关系，则已知关键字时，可以直接定位到相应的存储位置上，从而达到查找的目的理想情况下，无须任何比较就可以找到待查关键字，查找的期望时间为O(1)散列查找以节点的关键字K为自变量，通过一个确定的函数关系h，计算出函数值h(K)这个值可理解为节点的存储地址，将节点存入h(K)所指的存储位置上查找时，根据关键字，用函数h(K)计算出地址，再到相应的单元里去取出节点函数h称为散列函数，h(K)称为散列地址散列方法存储的线性表称为散列表(HashTable)，也称为哈希表散列查找直接定址法取关键字或关键字的某个线性函数值为散列地址，即H(key)=key或H(key)=a×key+b，其中a和b为常数散列函数有如下序列的关键字集合{1000，2000，5000，7000，8000，10000}，选取散列函数为H(key)=key/1000有几十个记录，关键字为8位十进制数，哈希地址为4位十进制数散列函数8134653281372242813874228130136781322817813389678136853781419355…..…..

分析：只取8

只取1

只取3、4

只取2、7、5

数字分布近乎随机所以：取作为哈希地址数字分析法平方取中法求关键字的平方值，扩大相近数的差别根据表长度取中间的几位数作为散列函数值散列函数平方后得到：{0010000，0012100，1020100，1002001，0012321}根据表长度，取中间三位数作为散列地址：{100，121，201，020，123}数据集{0100,0010,1010,1001,0111}，散列表长度为1000关键字为：0442205864，哈希地址位数为4散列函数586442200410088H(key)=0088移位叠加5864022404

6092H(key)=6092折叠叠加折叠法将关键字分成位数相同的几部分，然后取这几部分的叠加和作为散列地址。数据集合{18,27,1,20,22,6,10,13,41,15,25}，建立关键字与存储位置的关系为：h(key)=keymod11散列函数22113251527618412010除留余数法取关键字除以自然数n的余数作为散列地址散列表的冲突现象两个不同的关键字，可能得到相同的散列函数值，从而被映射到表的同一位置上称为冲突或碰撞发生冲突的若干个关键字称为该散列函数的同义词避免冲突选择合适的散列函数关键字的个数小于或等于散列表的长度冲突处理冲突不可能完全避免若关键字的个数大于散列表的长度,则无论怎样设计h，也不可能完全避免冲突设计散列函数时尽可能使冲突最少要确定解决冲突的方法，使发生冲突的同义词能够存储到散列表中。散列表的冲突线性探测例：{26，36，41，38，44，15，68，12，06，51}

构造哈希表t[0..12],哈希函数：h(key)=key%13余数分别为：{0，10，2，12，5，2，3，12，6，12}(26，36，41，38，44)没有冲突15发生冲突，用线性探测法，h1=(2+1)%13，得到位置3此位置未填值，是开放的位置，则15存进t[3]68与15发生冲突，原本不是同义词的两个关键字，争夺同一个后继散列地址，出现堆积用线性探测法，h1=(3+1)%13,则68存进t[4];12与38冲突，用线性探测法，h1=(12+1)%13,此位置与26冲突继续线性探测，h2=(12+2)%13,开放地址，则t[1]=12; ……冲突处理-开放地址法堆积现象散列地址不同的关键字，争夺同一个后继位置使得非同义词也加入了探测序列，增加了探查的长度，即增加了查找时间若散列函数不好或装填因子过大，会使堆积加剧装填因子α=填入表中的元素个数/哈希表的长度冲突处理-开放地址法再平方探测按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上先加1的平方个单位，若仍然存在，则减1的平方个单位。随之是2的平方，3的平方等等。直至不发生哈希冲突。伪随机探测按顺序决定值时，如果某数据已经存在，通过随机函数随机生成一个数，在原来值的基础上加上伪随机数，直至不发生哈希冲突。冲突处理-开放地址法冲突处理-链地址法分配指针数组，建立m个空链表，由哈希函数对关键字转换后，映射到同一哈希地址的同义词均加入到相应指向的链表中。又称：拉链法优点：链式地址法处理冲突简单，且无堆积现象由于链式地址法中各链表上的节点空间是动态申请的，故它更适合于造表前无法确定表长的情况链式地址法中装填因子可以α≥1，空间利用率高在用链式地址法构造的散列表中，删除节点的操作易于实现。只要简单地删去链表上相应的节点即可。缺点：指针占用较大空间时，会造成空间浪费。链地址法分析查找过程中，关键字的比较次数，取决于产生冲