哈希表查找——成功和不成功时的平均查找长度

时间:2024-10-22 07:23:38

四、哈希表的装填因子

装填因子 = (哈希表中的记录数) /  (哈希表的长度)

装填因子是哈希表装满程度的标记因子。值越大,填入表中的数据元素越多,产生冲突的可能性越大。

五、不同处理冲突的平均查找长度

技术分享

 

例:

假设散列表的长度是13,三列函数为H(K) = k % 13,给定的关键字序列为{32, 14, 23, 01, 42, 20, 45, 27, 55, 24, 10, 53}。分别画出用线性探测法和拉链法解决冲突时构造的哈希表,并求出在等概率情况下,这两种方法的查找成功和查找不成功的平均查找长度。

(1)线性探测法:

技术分享

查找成功时的查找次数等于插入元素时的比较次数, 查找成功的平均查找长度为:

ASL = (1+2+1+4+3+1+1+3+9+1+1+3)/12 = 2.5

查找成功时的查找次数:第n个位置不成功时的比较次数为:第n个位置到第1个没有数据位置的距离如第0个位置取值为1,第11个位置取值为3,第12个位置取值2

查找不成功的平均查找次数为:

ASL = (1+13+12+11+10+9+8+7+6+5+4+3 + 2)/ 13 = 91/13

哈希表查找不成功怎么计算? 解答:先建好表,然后可以算出每个位置不成功时的比较次数之和,再除以表空间个数

例如:散列函数为hash(x)=x MOD 11,用线性探测,建立了哈希表之后,如何求查找不成功时的平均查找长度!?

       地址:0     1    2    3    4    5    6    7    8    9    10       数据:33     1    13   12  34    38   27   22   -   -   -    成功次数:1     1    1    3    4    1    2    8  不成功次数:9     8    7    6    5    4    3    2    1    1    1

查找成功时的平均查找长度:ASL=(1+1+1+3+4+1+2+8)/8 =47/8 查找不成功时的平均查找长度:ASL=(9+8+7+6+5+4+3+2+1+1+1)/11

说明

第n个位置不成功时的比较次数为,第n个位置到第1个没有数据位置的距离。

  如:第0个位置到第1个没有数据位置(8)的距离为9!

(1) 开放定址法
地址: 0    1    2    3    4    5    6    7    8    9    10    11    12        
数据: 39   12   28   15   42   44    6   25   -   -    36    -    38    
成功次数: 1    3    1    2    2    1    1    9                        1           
不成功次数: 9    8    7    6    5    4    3    2    1    1      2    1      10 
查找成功时的平均查找长度:ASL=(1+3+1+2+2+1+1+9+1+1)/10 =2.2 
查找不成功时的平均查找长度:ASL=(9+8+7+6+5+4+3+2+1+1+2+1+10)/13=4.54

(2)链地址法

java中的hashMap就是这样一种链表+数组的数据结构,查找方法很简单,先利用散列函数(一般是取余数的方法)定位数组具体哪个点,比如1就是余数为1的点的链表中,然后再遍历链表查找具体数值的位置,如,果是53,那就在链表的第四位置,需要查找四次;同理,27就需要查找3次!

技术分享

查找成功时的平均查找长度:

ASL = (1*6+2*4+3*1+4*1)/12 = 7/4

查找不成功时的平均查找长度:

ASL = (4+2+2+1+2+1)/13

注意:查找成功时,分母为哈希表元素个数,查找不成功时,分母为哈希表长度。