小题求大家帮帮忙 新人在线等啊!
已知一组关键字?(32,40,?36,?53,?16,?46,?71,?27,?42,?24,?49,?64)?哈希表长度为13,哈希函数为:H(key)=key%13???(1)设计用线性探测再散列处理冲突的哈希表
[解决办法]
采用除留余数法加线性探查法:
关键字集合的哈希表:(32,40, 36, 53, 16, 46, 71, 27, 42, 24, 49, 64)
解:n=12,m=13 哈希函数:H(key)=key%13 则有:
H(32)=6, 没有冲突,将32放在Ha[6]处
H(40)=1, 没有冲突,将32放在Ha[1]处
H(36)=10, 没有冲突,将32放在Ha[10]处
H(53)=1, 有冲突
d0=1,d1=(1+1)%13=2 没有冲突,将32放在Ha[2]处
H(16)=3, 没有冲突,将32放在Ha[3]处
H(46)=7, 没有冲突,将32放在Ha[7]处
H(71)=5, 没有冲突,将32放在Ha[5]处
H(27)=1, 有冲突
d0=1,d1=(1+1)%13=2 有冲突
d2=(2+1)%13=3 有冲突
d3=(3+1)%13=4 没有冲突,将32放在Ha[4]处
H(42)=3, 有冲突
d0=3,d1=(3+1)%13=4 有冲突
d2=(4+1)%13=5 有冲突
d3=(5+1)%13=6 有冲突
...... 有冲突
d5=(7+1)%13=8 没有冲突,将32放在Ha[8]处
H(24)=11, 没有冲突,将32放在Ha[11]处
H(49)=10, 有冲突
...... 有冲突
d2=(11+1)%13=12 没有冲突,将32放在Ha[12]处
H(64)=12, 有冲突
d0=12,d1=(12+1)%13=0 没有冲突,将32放在Ha[0]处
建立的哈希表如下:
下标 0 1 2 3 4 5 6 7 8 9 10 11 12
K 64 40 53 16 27 71 32 46 42 36 24 49
探查次数 2 1 2 1 4 1 1 1 6 1 1 1 3