在解决哈希碰撞中二次探查法模数必须是4k+3的质数的原因 |
您所在的位置:网站首页 › 1317是质数吗 › 在解决哈希碰撞中二次探查法模数必须是4k+3的质数的原因 |
在学数据结构时,我们会发现一些问题没有给出详细的说明,其中在解决哈希碰撞中二次探查法模数必须是4k+3,这是怎么回事呢? 本文将会展开进行讨论。 For primes of the form 4k + 3, we can construct a "quadratic" sequence which examines the whole table in the first d steps 参考:http://vlado.fmf.uni-lj.si/vlado/papers/QuadHash.pdf
对于简单的线性探查法来说,由于是线性探查,因此第i次探查和第j次探查不会重,例如: 线性探查法的哈希函数是H1(x)=x%7。则对于一个7个元素的数组,如下 A[0],A[1],A[2],A[3],A[4],A[5],A[6] status 0 0 1 1 0 0 0 data 9 10
简单解释一下,数组的元素是一个包含status和data域的结构,其中status=0表示未占用,status=1表示占用。
当有一个新的元素例如时15要插入到A中,16%7=2,则与2冲突,直到探查A[4],则结果为
A[0],A[1],A[2],A[3],A[4],A[5],A[6] status 0 0 1 1 1 0 0 data 9 10 15 因此探查的序列L:{2,3,4}。可见L1!=L2!=L3,即第i次探查和第j次探查不会重。线性探查的这个性质也是显然的。
但由于线性探查会造成拥挤的效应,因此需要构造一个二次序列来解决这个问题。
一个基本的想法是将探查序列改造成L:{i,i+1,i-1,i+4,i-4,...i+k2,i-k2}。但如何保证第i次探查和第j次探查不重呢?结论就是如果模数是一个4k+3的质数就可以保证,详细本文不再证明。 我们先举个例子,比如我们有一个4k+3的质数11,假定i=8,即第一次探查为A[8] 则探查的序列为{8,8+1,8-1,8+4,8-4...},这里的探查序列实际上是需要做一个模p的处理。 不妨手工处理一下,可以得到如下结果 A[0],A[1],A[2],A[3],A[4],A[5],A[6],A[7],A[8],A[9],A[10] 探查第i次 10 4 8 9 5 11 6 3 1 2 7 这就出现了本文开头提到的性质,这使得二次探查的序列可以在开始的p步内遍历整个表,而不重。
本质上这是一个完全剩余系的问题。例如一个数7,其完全剩余系为模7后可能的数{0,1,2,3,4,5,6)。 对于一个探查的序列如果是{0,1,2,3,4,5,6},即为线性探查,会导致拥挤效应。 因此最理想的是构造一个计算方便、随机且不重的探查序列,例如{2,6,3,1,4,0}。 为了照顾到这些性质,比较简单的方法就是目前教科书提到的二次探查法,可以满足上述要求。
|
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |