散列（哈希）查找

散列查找

散列表（Hash Table）

散列表（Hash Table），又称哈希表，是一种数据结构，特点是：数据元素的关键字与其存储地址直接相关

如何建立“关键字”与“存储地址”的联系？

通过“散列函数（哈希函数）”：Addr=H(key)

若不同的关键字通过散列函数映射到同一个值，则称他们为“同义词”

通过散列函数确定的位置已经存放了其他元素，则称这种情况为“冲突”

处理冲突的方法——拉链法

用拉链法（又称链接法，链地址法）处理“冲突”：把所有“同义词”存储在一个链表中

散列查找

通过散列函数计算目标元素存储地址：Addr=H(Key)

27%13=1

27的查找长度=3（对比次数）

查找目标：21

21%13=8

21的查找长度=0

查找长度——在查找运算中，需要对比关键字的次数称为查找长度

平均查找长度：

[ASL_{成功}=frac{1*6+2*4+3+4}{12}=1.75 ]

第一层结点6个，对比1次有6个机会

第二层结点4个，对比2次有4次机会

第三层结点1个

第四层结点1个

“冲突”越多，查找效率越低

下面那样情况就很好

最理想情况：散列查找时间复杂度可达到O(1)

[ASL_{失败}=frac{0+4+0+2+0+0+2+1+0+0+2+1+0}{13}=0.92 ]

第一个对比0次就失败

第二个对比4次失败。。。

装填因子α=表中记录数/散列表长度

装填因子会直接影响散列表的查找效率

如何设计冲突更少的散列函数

常见的散列函数

除留余数法——H(key) = key%p

散列表表长为m，去一个不大于m但最接近或等于m的质数p

（质数：又称素数，指除了1和此整数自身外，不能被其他自然数整除的数）

相反概念——合数

表长15，浪费了2个位置

设计目标——让不同关键字冲突尽可能的少

所以要取质数

散列函数的设计要结合关键字分布特点来考虑，不要教条化

直接定址法——H(key) = key 或 H(key) = a*key +b

其中，a和b是常数。这种方法计算最简单，且不会产生冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费

数字分析法——选取数码分布较为均匀的若干位作为散列地址

设关键字是r进制数（如十进制数），而r个数码在各位上出现的频率不一定相同，可能在某些位上均匀一些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时可选取数码分布较为均匀的若干位作为散列地址。这种方法适用于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。