11-散列表-算法导论
2016-06-06 23:55:31 0 举报AI智能生成
算法导论的第十一章笔记
作者其他创作
大纲/内容
11-散列表-算法导论
什么是散列表
笼统来说，散列表类似于普通数组，是采用直接寻址的一种数据结果，不过元素的下标是通过对关键字key进行就算而得到的（数组是直接将关键字key作为下标）
直接寻址表
几种操作
return T[k]
T[x.key]=x
T[x.key]=NIL
操作时间都为O(1)
散列表（也叫哈希表）
直接寻址的缺点
当全域U很大，但实际存储的关键字集合相对来说很小时，会浪费很多空间
散列与直接寻址方式的区别
直接寻址
具有关键字k的元素被存放在槽k中
散列方式
具有关键字k的元素放在槽h(k)中；h为散列函数，用于计算关键字k在槽的位置
散列函数h的作用在于缩小了数组下标的范围
解决h 映射冲突的方法
链接法
将散列到同一个槽中的所有元素放在一个链表中
此时可以将每个槽都看做一个链表，只有一个元素的即为只含单一节点的链表
性能分析
简单均匀散列假设下，一次查找成功与不成功的平均时间都是 F(1+alfa)——alfa = 需要存储的元素个数/散列表的槽数
开放寻址法
散列函数
好的散列函数特点
满足or近似满足 简单均匀散列假设
除法散列法
h(k) = k mod m; m是槽的个数
注意：m一般取不太接近2的整数幂的素数； m应该避免取某些值，eg. m取为2.^p是很糟糕的值
乘法散列法
h(k) = [ m*( k*A - [k*A] )]—— 即：关键字k乘以常数A(0A1)后取其小数部分，然后再乘以m 后取整
优点
对m的选择不是很关键， m可以取 2.^p
一般而言，乘法散列函数如下取更好
A = 0.618033988....(黄金分割点)——推荐值，也可取其他0-1间的值；然后按乘法散列函数计算即可
全域散列法
基本思想：无招胜有招——为了防止某种散列函数在某种情况下出现最坏的槽分布结果，采取随机选择散列函数的规避保证平均性能很好
职业：暂无
0 条评论
下一页
