文档介绍：该【习题题5-1Hash函数答案说明 】是由【莫比乌斯】上传分享，文档一共【5】页，该文档可以免费在线阅读，需要了解更多关于【习题题5-1Hash函数答案说明 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:将散列到同一个值的所有元素保留到一个链表中。首先插入4371,h(4371)=4371(mod10)=1,故插入1位置。插入1323,h(1323)=1323(mod10)=3,故插入3位置。插入6173,h(6173)=6173(mod10)=3,故插入3位置,此时发生冲突(与1323插入同一位置),故添加一个链表并保存到此链表中。插入4199,h(4199)=4199(mod10)=9,故插入9位置。插入4344,h(4344)=4344(mod10)=4,故插入4位置。插入9679,h(9679)=9679(mod10)=9,故插入9位置,此时发生冲突(与4199插入同一位置),故添加一个链表并保存到此链表中。插入1989,h(1989)=1989(mod10)=9,故插入9位置,此时发生冲突(与4199,9679插入同一位置),故添加一个链表并保存到此链表中。线性探测:hi(x)=(hash(x)+f(i))modTableSize,其中f(i)=i,i为发生冲突的次数,f(0)=0。相当于逐个探测散列表,最后将值散列到最接近的一个空单元中(可以理解为,若发生冲突,则插入到下一个空单元中)。首先插入4371,h0(4371)=(4371(mod10)+f(0))mod10=1,故插入1位置。插入1323,h0(1323)=(1323(mod10)+f(0))mod10=3,故插入3位置。插入6173,h0(6173)=(6173(mod10)+f(0))mod10=3,故插入3位置,此时发生冲突(与1323插入同一位置)。发生第一次冲突,计算h1(6173)=(6173(mod10)+f(1))mod10=4,故插入4位 置。插入4199,h0(4199)=(4199(mod10)+f(0))mod10=9,故插入9位置。插入4344,h0(4344)=(4344(mod10)+f(0))mod10=4,故插入4位置,此时发生冲突(与6173。插入同一位置)。发生第一次冲突计算h1(4344)=(4344(mod10)+f(1))mod10=5,故插入5位置。插入9679,h0(9679)=(9679(mod10)+f(0))mod10=9,故插入9位置,此时发生冲突(与4199插入同一位置)。发生第一次冲突计算h1(9679)=(9679(mod10)+f(1))mod10=0,故插入0位置。插入1989,h0(1989)=(1989(mod10)+f(0))mod10=9,故插入9位置,此时发生冲突(与4199插入同一位置)。发生第一次冲突计算h1(1989)=(1989(mod10)+f(1))mod10=0,故插入0位置, 此时发生冲突(与9679插入同一位置)。发生第二次冲突计算h2(1989)=(1989(mod10)+f(2))mod10=1,故插入1位置, 此时发生冲突(与4371插入同一位置)。发生第三次冲突计算h3(1989)=(1989(mod10)+f(3))mod10=2,故插入2位置。平方探测:hi(x)=(hash(x)+f(i))modTableSize,其中f(i)=i2,i为发生冲突的次数,f(0)=0。首先插入4371,h0(4371)=(4371(mod10)+f(0))mod10=1,故插入1位置。插入1323,h0(1323)=(1323(mod10)+f(0))mod10=3,故插入3位置。插入6173,h0(6173)=(6173(mod10)+f(0))mod10=3,故插入3位置,此时发生冲突(与1323插入同一位置)。发生第一次冲突,计算h1(6173)=(6173(mod10)+f(1))mod10=4,故插入4位 置。插入4199,h0(4199)=(4199(mod10)+f(0))mod10=9,故插入9位置。插入4344,h0(4344)=(4344(mod10)+f(0))mod10=4,故插入4位置,此时发生冲突(与6173插入同一位置)。发生第一次冲突计算h1(4344)=(4344(mod10)+f(1))mod10=5,故插入5位置。插入9679,h0(9679)=(9679(mod10)+f(0))mod10=9,故插入9位置,此时发生冲突(与4199插入同一位置)。发生第一次冲突计算h1(9679)=(9679(mod10)+f(1))mod10=0,故插入0位置。插入1989,h0(1989)=(1989(mod10)+f(0))mod10=9,故插入9位置,此时发生冲突(与4199插入同一位置)。发生第一次冲突计算h1(1989)=(1989(mod10)+f(1))mod10=0,故插入0位置, 此时发生冲突(与9679插入同一位置)。发生第二次冲突计算h2(1989)=(1989(mod10)+f(2))mod10=3,故插入3位置, 此时发生冲突(与1323插入同一位置)。发生第三次冲突计算h3(1989)=(1989(mod10)+f(3))mod10=8,故插入8位置。双散列:hi(x)=(hash(x)+f(i))modTableSize,其中f(i)=i*hash2(x),i为发生冲突的次数,f(0)=0。题中hash2(x)=7-(xmod7)。首先插入4371,h0(4371)=(4371(mod10)+f(0))mod10=1,故插入1位置。插入1323,h0(1323)=(1323(mod10)+f(0))mod10=3,故插入3位置。插入6173,h0(6173)=(6173(mod10)+f(0))mod10=3,故插入3位置,此时发生冲突(与1323插入同一位置)。发生第一次冲突,计算hash2(6173)=7-(6173mod7)=1,f(1)=1*hash2(6173)=1,h1(6173)=(6173(mod10)+f(1))mod10=4,故插入4位置。插入4199,h0(4199)=(4199(mod10)+f(0))mod10=9,故插入9位置。插入4344,h0(4344)=(4344(mod10)+f(0))mod10=4,故插入4位置,此时发生冲突(与6173插入同一位置)。发生第一次冲突,计算hash2(4344)=7-(4344mod7)=3,f(1)=1*hash2(4344)=3, h1(4344)=(4344(mod10)+f(1))mod10=7,故插入7位置。插入9679,h0(9679)=(9679(mod10)+f(0))mod10=9,故插入9位置,此时发生冲突(与4199插入同一位置)。发生第一次冲突,计算hash2(9679)=7-(9679mod7)=2,f(1)=1*hash2(9679)=2, h1(9679)=(9679(mod10)+f(1))mod10=1,故插入1位置,此时发生冲突(与 4371插入同一位置)。发生第二次冲突,计算f(2)=2*hash2(9679)=4,h1(9679)=(9679(mod 10)+f(2))mod10=3,故插入3位置,此时发生冲突(与1323插入同一位置)。发生第三次冲突,计算f(3)=3*hash2(9679)=6,h1(9679)=(9679(mod 10)+f(3))mod10=5,故插入5位置。插入1989,h0(1989)=(1989(mod10)+f(0))mod10=9,故插入9位置,此时发生冲突(与4199插入同一位置)。发生第一次冲突计算hash2(1989)=7-(1989mod7)=6,f(1)=1*hash2(1989)=6, h1(1989)=(1989(mod10)+f(1))mod10=5,故插入5位置,此时发生冲突(与 9679插入同一位置)。发生第二次冲突,计算f(2)=2*hash2(1989)=12,h1(1989)=(1989(mod 10)+f(2))mod10=1,故插入1位置,此时发生冲突(与4371插入同一位置)。发生第三次冲突,计算f(3)=3*hash2(1989)=18,h1(1989)=(1989(mod 10)+f(3))mod10=7,故插入7位置,此时发生冲突(与4344插入同一位置)。发生第四次冲突,计算f(4)=4*hash2(1989)=24,h1(1989)=(1989(mod 10)+f(4))mod10=3,故插入3位置,此时发生冲突(与1323插入同一位置)。发生第五次冲突,计算f(5)=5*hash2(1989)=30,h1(1989)=(1989(mod 10)+f(5))mod10=9,故插入9位置,此时发生冲突(与4199插入同一位置)。此时,可以知道,将再次逐个探测位置9->5->7->3->9,最终无法插入1989。