设哈希函数为H（K）=KMOD7,哈希表的地址空间为0,...,6,开始时哈希表为空,用线性探测法解决冲突,请画出依次插

第一题：哈希表的定义（一组关键字通过哈希函数得到一段连续的地址）,addr（15）=4,是通过15%11,即15除以11取余数4.
第二题：核心是哈希表处理冲突方法：开放地址法（二次探测再散列）,你查查这个方法的思想,一两句话也解释不清楚
第三题：当做定理记吧!

你怎么问了两遍呢、?
解决冲突的方法：
1.线性探测再散列：2.平方探测再散列：3.再哈希：4.哈希链表：
你题目给的是 用的平方探测再散列,如果数A本来哈希后的地址是0,但是0 ,1 ,位置上已经有数据了 此时 A 的哈希地址+1^2 有冲突 ,A 的哈希地址-1^2 此时因为A 的哈希地址是0 所以 应把A放入在10的地方 应为H(K)=K%11 m=11,所以 应该是0----10 0-1 ：表示 0 的上一个地址 ,你可以把它看成是循环的

H（k） = (3k) mod 11是一种类计算机语言的描述,它的意思是,将k存入到3*k与11取模的空间中,也就是说所有的都放在11个地址空间中,但有时会发生冲突,这时可以考虑使用开放定位地址,而转向使用下一个地址中.而11是一个素数,这里做为哈杀系数.对于哈杀系数一般是使用比需要存储空间的数字略大的素数.素数的冲突机率最小,而数据选用越小,冲突机率越大,而越大则越存储越稀,浪费空间越大.
很多时间书上是这样教你的,一般是将所存储的数据与哈希系数取模.但这里只是用其3倍取模也是一样的,如以下数字放在哈希表中：
1,62,15,32,45,78,65,95,7,12
这个数据是10个,所以我选用的哈杀系数是11,如果使用H(k)=k mod 11采用地址开链法时是这样的：
1 mod 11 存放在1号空间中
62 mod 11 存放在7号空间中
15 mod 11 存放在4号空间中
32 mod 11 存放在10号空间中
45 mod 11 存放在1号空间中,这时发生了冲突,地址开链,则存在另一个地址中空间中
78 mod 11 存在1号发现存在,另存.
.
但是有时我们知道地址的冲突机充非常大时,这样是不行的,因为效率问题,我们可以使用另一个较小的素数进行改变：
如：以下数据列：
12,23,35,46,58,69,81,92,104,115
你会发现这时10个待存数据,可应该选用11作为哈希系数,但你会发现这几个都会产生冲突,如果还用H（k）=k mod 11非常不利,但如果是均匀冲突时则可以用h(k)=3k mod 11解决的!它的好处就是跨大距离而留足开放定地址法进行解决的.如果遇到冲突可以用另一个式子重新放入空间中,当然,如果遇到已经放入的情况,则将i的值进行顺次增加.
以此为例子,你的开放地址法处理冲突存放是：
12*3 mod 11 放在3号空间中
23*3 mod 11 放在3号空间中,但已经存放了,解使用冲突,
23*7 mod 10 +1 放在2号空间中.
35*3 mod 11 放在6号空间中,（若不使用3k mod 11时则放在2号空间,又冲突了,所以乘的作用就是跨大一下跟离而已!）
46*3 mod 11 放在6号空间中,重复冲突,使用开放地址法解决
46*7 mod 10 +1 放在3个空间中,又重复,使用前边的系数解决
2（46*7 mod 10 +1）放在6号空间中,又重复,（这次真是巧合,46*3 mod 11与2*(46*7 mod 10 +1)相等的时候根本不多!）只好换一下系数放在9号空间中了,问题是数据往往有很大的随机性,不像我举例子也找这样规律性的数字!
但原理你是知道了吧?

对于动态查找表而言,1) 表长不确定；2)在设计查找表时,只知道关键字所属范围,而不知道确切的关键字.因此,一般情况需建立一个函数关系,以f(key)作为关键字为key的录在表中的位置,通常称这个函数f(key)为哈希函数.(注意：这个函数并不一定是数学函数)
哈希函数是一个映象,即：将关键字的集合映射到某个地址集合上,它的设置很灵活,只要这个地址集合的大小不超出允许范围即可.
现实中哈希函数是需要构造的,并且构造的好才能使用的好.
用途：加密,解决冲突问题.
用途很广,比特精灵中就使用了哈希函数,你可 以自己看看.
具体可以学习一下数据结构和算法的书.

同时对13取余数.a的结果为12和12.b的是2和5.c的是10和0.d的是12和3.所以选a

h(19)=8,h(1)=1,h(23)=1->2,h(14)=3,h(15)=0,h(68)=2->3->4,h(11)=0->1->2->3->4->5,h(82)=5->6,h(36)=3->4->5->6->7线性探测正确 二次探测H(19)=8H(1)=1H(23)=1,h(23+1^2)=2H(14)=3H(55)=0H(68)=2,h(68+1^2)=3,h(68-1^2)=1,h(68+2^2)=6H(11)=0,h(11+1^2)=1,h(11-1^2)=10H(82)=5H(36)=3,h(36+1^2)=4

哈希表的建立：
key： 0 1 2 3 4 5 6 7 8 9 10 11 12
55 68 11 79 14 27 23 84 19 20 10 1
ASL=(1+1+1+1+1+1+3+2+2+6+11)/12
做此类题应注意哈希冲突函数怎么构建，此题采用线性探测法，即如果产生冲突方法为H+1一直到没有冲突为止。哈希表的建立，是依照key依次算对应的哈希码。
平均查找长度就是查找成功需要的次数除以总个数。答案自己算。这样的题自己多动手。看懂了的话要好评啊！呵呵。

15,38,61,84除11的余数分别为4,5,6,7,没有重复,因此分别就放在这4个下标
49除11的余数为5,发生冲突,因为是二次探测,所以接下来分别探测+1, -1, +4, -4, +9, -9...
显然5 + 1, 5 - 1的位置都有冲突,5 + 4的位置没有冲突
所以最后放入的位置是9,也就是答案D

28 2 X 15 X 11 9 4 32
1 5 1 1 1 3 4 总冲突=16次

依次计算已经存放各关键字的位置：
22 % 11 = 0
12 % 11 = 1
24 % 11 = 2
30 % 11 = 7
52 % 11 = 8
43 % 11 = 10
都没有发生冲突,其位置就是散列函数值
63 % 11 = 8
与52 发生冲突,按照线性探测再散列的方法处理冲突,先探查8 + 1 = 9,这个位置空,没有关键字冲突,因此哈希地址为9

x1探测1次找到自己的位置
x2探测1次，与x1冲突，再探测1次
x3探测1次，与x2冲突，再探测1次，与x1冲突，再探测1次
依次类推
所以总的次数是1+2+。。。+k=(k+1)*k/2