用线性探测法解决冲突,可能要探测多个散列地址,这些位置上的键值(不一定都是同义词) 散列表就是哈希表,它用散列函数将键值映射到散列表中的存储位置.同义词是指具有相同散列函数值的关键字.散列表的存储结构是根据关键字的散列函数值来确定关键字在散列表中的存储位置的,对同义词的处理根据不同情况有不同的冲突处理方法.用线性探测法查找闭散列表,可能要探测多个散列地址,这些位置上的键值不一定都是同义词,因为同义词不一定存放在相邻的位置.

0 1 2 3 4 5 6 7 8 15 16 22 30 32 以上是数据在散列表中的分布 计算如下 (1+2+2+4+4+3)/6=8/3 括号里那6个数,从左到右分别是初始关键字序列中的每一个所需查找次数,从左到右 线性探测就是一旦冲突,向后移动寻找新位置,8占了位置1,15%7=1,但被8占了,所以只能移到2,以后查找15时也需要比较2次,16%7=2,但位置2被15占了,16只能移到位置3,以后查找需比较2次,22%7=1,但位置1被占了,向后移,位置2,3都被占了,结果最终移到位置4,以后需要比较4次,如此推理,可得结果

由散列函数计算出的上述关键字序列的散列地址为(4,0,0,6,6,3).前2个关键字插入时,其相应的地址均为开放地址,故将它们直接插入T[4],T[0],当插入第3个关键字时,其散列地址0已被第2个关键字占用.故探查h1=(0+1)%7=1,此地址开放,所以将7放入T[1]中.当插入第5个关键字34时,其散列地址6已被非同义词62先占用,故探查h1=(6+1)%7=0,其散列地址0已被第2个关键字占用,故探查h2=(6+2)%7=1,其散列地址1已被第3个关键字占用,故探查h3=(6+3)%7=2,将其插入到T[2]中.所以哈希表为0 1 2 3 4 5 6 21 7 34 10 46 62

要从表头重新查起,因为在构建表的时候就已经预留了空间,一般是表的75%可以用来存放数据,所以数据时可以完全存进去的,如果不要求二次散列那么就要从头查起!

m=11.---------------------------------------------------------------------------------下标 0 1 2 3 4 5 6 7 8 9 10 key 28 8 72 16 7 5 13 11探测次数 1 1 1 2 5 1 1 4------------------------------------------.

首先将各个数除以13取余数:(6,2,7,1,2,7,7,6)可见20,85与46冲突,58与71冲突.将7+1再对13取余,直到无冲突,类似的6+1对13取余,最后可得h(71)=6;h(28)=2;h(46)=7;h(14)=1;h(2)=3;h(20)=8;h(85)=9;h(58)=10;哈希表存储结构:0 1 2 3 4 5 6 7 8 9 10 14 28 2 71 46 20 85 58 平均查找长度=(1*4+2*2+3*1+4*1)/8=15/8

n(n - 1) / 2解答:线性探测解决冲突的办法指一旦目标空间被占有,则探测相邻的下一个空间,如果空闲则插入,否则继续向下一个探测,如果到了队列末尾则返回队列头探测,一旦全部空间都被占据则无法插入.设那么第i个元素探测和插入的次数是T(i),则可知:T(i) = T(i - 1) + 1,而且T(1) = 1则T(n) = n所以总次数为n(n - 1) / 2

ASLsucc = (1 + 2 + 1 + 2 + 1 + 1 + 3 + 1) / 8 = 1.5

是的,如果你把这个记录置空了,如果原来有个数在这个位置冲突了,它会根据,线性探测方法存在下一个位置,如果这个时候来找这个数的时候,你把这个记录位置为空,编译器就认为没有这个关键字的记录,更不会线性探测下一个位置,也不会找到你要的数了.这样你懂吗?

线性探查再散列的查找成功的平均查找长度的理论值为(1+ 1/(1-a))/2,按照你的要求小于3,得到装填因子a <= 4/5,为0.8,因此存储空间约为250/0.8 = 312.5,上取整为313