在地址空间为0~16的散列区中,对以下关键字序列构造两个哈希表:(Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec) (1)用线性探测开放定址法处理冲突 (2)用链地址法处理冲突 分别求这两个哈希表在等概率情况下查找成功和不成功的平均查找长度。设哈希函数为H(k)=i//2,其中i为关键字第一个字母在字母表中的序号(i>=1)。
时间: 2024-03-01 13:49:24 浏览: 25
首先,根据哈希函数H(k)=i//2,可以将关键字序列映射到0~8的地址空间中。因为关键字序列中的每个月份的第一个字母在字母表中的序号i都不相同,所以不会出现哈希冲突。
1. 线性探测开放定址法处理冲突
对于线性探测开放定址法,当发生哈希冲突时,需要依次向后查找空闲位置,直到找到一个空闲位置或者查找到整个哈希表。因此,平均查找长度与哈希表中记录的填装因子有关,填装因子越大,平均查找长度越大。
假设哈希表的大小为m=8,即有8个地址,关键字序列中有n=12个关键字。填装因子为α=n/m=1.5。
在等概率情况下,查找成功的平均查找长度为:
ASL(success) = (1/12) * (1 + 2 + 3 + ... + 12) = 6.5
查找不成功的平均查找长度为:
ASL(unsuccess) = (1/8) * (1 + (1/2) + (1/3) + ... + (1/8)) ≈ 1.94
2. 链地址法处理冲突
对于链地址法,当发生哈希冲突时,将冲突的关键字放入同一个链表中。因此,平均查找长度与链表的平均长度有关,链表的平均长度越长,平均查找长度越大。
假设哈希表的大小为m=8,即有8个地址,关键字序列中有n=12个关键字。填装因子为α=n/m=1.5。
在等概率情况下,查找成功的平均查找长度为:
ASL(success) = (1/12) * (1 + 2 + 3 + ... + 12) = 6.5
查找不成功的平均查找长度为:
ASL(unsuccess) = (1/12) * (1 + 1.5 + 2 + ... + 4.5) = 2.5
其中,链表的平均长度为:
AvgLen = α = 1.5
因此,在链地址法中,查找不成功的平均查找长度比线性探测开放定址法要小。