抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

二叉排序树

(1) 若其左子树非空,则左子树上所有结点的值均小于根节点的值。

(2) 若其右子树非空,则右子树上的所有结点的值均大于等于根结点的值。

(3) 其左子树本身又各是一棵二叉排序树。

散列表(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开放定址发

评论

❤️ 感谢 0 位小伙伴的 0 次陪伴
🌏载入天数...载入时分秒...
Copyright © 2020-2021