Question

数据结构哈希表,急对以下关键字序列建立哈希表{16,29,45,37,58,55...

数据结构哈希表,急 对以下关键字序列建立哈希表{16,29,45,37,58,55,49,26,50,24,36,38},要求填充率为80%,用二次探测再散列法处理冲突：请给出哈希函数,画出此哈希表,并计算在等概率情况下查找成功的平均查找长度,直接要答案,

Answer 1

因为元素个数等于12,要求的填充率为0.8,所以表容量等于12/0.8=15.哈希函数通常采用除留余数法即取模数法,则哈希函数为H
=
key
mod
p,p应该为小于15且大于12的素数,由此得知p为13.而如果发生冲突再哈希时应该对表容量取模,增量序列则为1
-1
4
-4
9
-9.,所以构造的哈希表应如下:0:26
1:^
2:55
3:16
4:29
5:24
6:45
7:58
8:^
9:36
10:49
11:37
12:50
13:38
14:^ASL=(1+3+1+2+4+1+2+3+1+1+2+2)/12=23/12=1.9