数据结构（十一）散列表结构
散列表实践
h(x)=x mod 10 的结果:
4371 mod 10=1
1323 mod 10=3
6173 mod 10=3
4199 mod 10=9
4344 mod 10=4
9679 mod 10=9
1989 mod 10=9
- 分离链接的散列表
将散列到同一个值的所有元素保留在一个链表中
- 使用线性探测的散列表
hi(x)=(hash(x)+f(i))mod TableSize，其中f(i)=i，i为发生冲突的次数，f(0)=0。逐个探测散列表，若发生冲突，则插入到下一个空单元中
- 使用平方探测的散列表
hi(x)=(hash(x)+f(i))mod TableSize，其中f(i)=i2，i为
发生冲突的次数，f(0)=0。
c. 平方探测：hi(x)=(hash(x)+f(i))mod TableSize，其中f(i)=i2，i为
发生冲突的次数，f(0)=0。
1) 首先插入4371，h0(4371)=(4371(mod 10)+f(0))mod 10=1，故插入1位置。
2) 插入1323，h0(1323)=(1323(mod 10)+f(0))mod 10=3，故插入3位置。
3) 插入6173，h0(6173)=(6173(mod 10)+f(0))mod 10=3，故插入3位置，此时发
生冲突（与1323插入同一位置）。
发生第一次冲突，计算h1(6173)=(6173(mod 10)+f(1))mod 10=4，故插入4位 置。
4) 插入4199，h0(4199)=(4199(mod 10)+f(0))mod 10=9，故插入9位置。
5) 插入4344，h0(4344)=(4344(mod 10)+f(0))mod 10=4，故插入4位置，此时发
生冲突（与6173插入同一位置）。
发生第一次冲突计算h1(4344)=(4344(mod 10)+f(1))mod 10=5，故插入5位置。
6) 插入9679，h0(9679)=(9679(mod 10)+f(0))mod 10=9，故插入9位置，此时发
生冲突（与4199插入同一位置）。
发生第一次冲突计算h1(9679)=(9679(mod 10)+f(1))mod 10=0，故插入0位置。
7) 插入1989，h0(1989)=(1989(mod 10)+f(0))mod 10=9，故插入9位置，此时发
生冲突（与4199插入同一位置）。
发生第一次冲突计算h1(1989)=(1989(mod 10)+f(1))mod 10=0，故插入0位置， 此时发生冲突（与9679插入同一位置）。
发生第二次冲突计算h2(1989)=(1989(mod 10)+f(2))mod 10=3，故插入3位置， 此时发生冲突（与1323插入同一位置）。
发生第三次冲突计算h3(1989)=(1989(mod 10)+f(3))mod 10=8，故插入8位置。
- 使用第二个散列函数h2（X）=7-（X mod 7）进行双散列的散列表
h2（X）=7-（X mod 7）的结果:
hash(4371)=7-3=4
hash(1323)=7-0=7
hash(6173)=7-6=1
hash(4344)=7-4=3
hash(4199)=7-6=1
hash(9679)=7-5=2
hash(1989)=7-1=6
hi(x)=(hash(x)+f(i))mod TableSize，其中f(i)=i*hash2(x)，
i为发生冲突的次数,f(0)=0。题中hash2(x)=7-(x mod 7)。
1) 首先插入4371，h0(4371)=(4371(mod 10)+f(0))mod 10=1，故插入1位置。
2) 插入1323，h0(1323)=(1323(mod 10)+f(0))mod 10=3，故插入3位置。
3) 插入6173，h0(6173)=(6173(mod 10)+f(0))mod 10=3，故插入3位置，此时发
生冲突（与1323插入同一位置）。
4) 发生第一次冲突，计算hash2(6173)=7-(6173 mod 7)=1，f(1)=1*hash2(6173)=1，
h1(6173)=(6173(mod 10)+f(1))mod 10=4，故插入4位置。
5) 插入4199，h0(4199)=(4199(mod 10)+f(0))mod 10=9，故插入9位置。
6) 插入4344，h0(4344)=(4344(mod 10)+f(0))mod 10=4，故插入4位置，此时发
生冲突（与6173插入同一位置）。
发生第一次冲突，计算hash2(4344)=7-(4344 mod 7)=3，f(1)=1*hash2(4344)=3， h1(4344)=(4344(mod 10)+f(1))mod 10=7，故插入7位置。
7) 插入9679，h0(9679)=(9679(mod 10)+f(0))mod 10=9，故插入9位置，此时发
生冲突（与4199插入同一位置）。
发生第一次冲突，计算hash2(9679)=7-(9679mod 7)=2，f(1)=1*hash2(9679)=2，
h1(9679)=(9679(mod 10)+f(1))mod 10=1，故插入1位置，此时发生冲突（与4371插入同一位置）。
发生第二次冲突，计算f(2)=2*hash2(9679)=4，h1(9679)=(9679(mod
10)+f(2))mod 10=3，故插入3位置，此时发生冲突（与1323插入同一位置）。
发生第三次冲突，计算f(3)=3*hash2(9679)=6，h1(9679)=(9679(mod
10)+f(3))mod 10=5，故插入5位置。
8) 插入1989，h0(1989)=(1989(mod 10)+f(0))mod 10=9，故插入9位置，此时发
生冲突（与4199插入同一位置）。
发生第一次冲突计算hash2(1989)=7-(1989 mod 7)=6，f(1)=1*hash2(1989)=6，
h1(1989)=(1989(mod 10)+f(1))mod 10=5，故插入5位置，此时发生冲突（与9679插入同一位置）。
发生第二次冲突，计算f(2)=2*hash2(1989)=12，h1(1989)=(1989(mod
10)+f(2))mod 10=1，故插入1位置，此时发生冲突（与4371插入同一位置）。
发生第三次冲突，计算f(3)=3*hash2(1989)=18，h1(1989)=(1989(mod
10)+f(3))mod 10=7，故插入7位置，此时发生冲突（与4344插入同一位置）。
发生第四次冲突，计算f(4)=4*hash2(1989)=24，h1(1989)=(1989(mod
10)+f(4))mod 10=3，故插入3位置，此时发生冲突（与1323插入同一位置）。
发生第五次冲突，计算f(5)=5*hash2(1989)=30，h1(1989)=(1989(mod
10)+f(5))mod 10=9，故插入9位置，此时发生冲突（与4199插入同一位置）。
此时，可以知道，将再次逐个探测位置9->5->7->3->9，最终无法插入1989。