数据结构与算法之查找
寜静致逺 Lv3

散列表(hash 表)

优点: 查找效率高;

缺点:空间效率低。

散列表的构造方法

直接定址法:

Hash(key) = a * key + b (a,b为常数)

优点: 以关键码key的某个线性函数值为散列地址,不会产生冲突。

缺点: 要占用连续的地址空间,空间效率低。

例: {100,300,500,700,800,900 } .

散列函数Hash(key) = key/100 (a=1/100 , b=0 )

0 1 2 3 4 5 6 7 8 9
100 300 500 700 800 900
除留余数法:

Hash(key) = key mod p (p是一个整数)

关键:如何选取合适的 p ?

技巧:设表长为m,取p<= m且为质数

例: {15,23,27,38,53,61,70} .

散列函数Hash(key) = key mod 7

0 1 2 3 4 5 6
70 15 23 48 53 61 27

处理冲突的方法

开放定址法

基本思想: 有冲突就去寻找下一个空的散列地址,只要散列表空间足够大,空的散列表地址总能找到,并将数据元素存入。

H(key)=(H(key)+ d)MOD m(其中 m 为哈希表的表长,d 为一个增量)当得出的哈希地址产生冲突时,选取以下 3 种方法中的一种获取 d 的值,然后继续计算,直到计算出的哈希地址不在冲突为止,这 3 种方法为:

  • 线性探测法: d=1,2,3, … ,m-1
  • 二次探测法: d=1^2 , -1^2 , 2^2 , -2^2 , 3^2, …
  • 伪随机探测法: d=伪随机数

例如,在长度为 11 的哈希表中已填写好 17、60 和 29 这 3 个数据(如图 2(a) 所示),其中采用的哈希函数为:H(key)=key MOD 11,现有第 4 个数据 38 ,当通过哈希函数求得的哈希地址为 5,与 60 冲突,则分别采用以上 3 种方式求得插入位置如图 2(b)所示:

图1开放定址发

  • 本文标题:数据结构与算法之查找
  • 本文作者:寜静致逺
  • 创建时间:2021-02-04 10:15:43
  • 本文链接:https://hujiahao6.gitee.io/2021/02/04/查找/
  • 版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
 评论