从平方探测法引申——平方数列取模的规律数列

2019-04-14 08:27发布

  • 今天跟人复习了散列表中的平方探测法,发现一个十分有趣的事实
自然数列 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 …… 平方数列 1 4 9 16 25 36 49 64 81 100 121 144 169 196 255 265 289 …… mod 6 1 4 3 4 1 0 1 4 3 4 1 0 1 4 3 4 1 …… mod 7 1 4 2 2 4 1 0 1 4 2 2 4 1 0 1 4 2 …… mod 17 1 4 9 16 8 2 15 13 13 15 2 8 16 9 4 1 0 …… 可以发现 对6取余,是一个循环数列,循环节是143410.
并且除掉0之后,这串子数列是对称的
这个结论对于7和17也是成立的 那么 是不是对于任意的正整数k>2,都是成立的呢? 对于任意的自然数n来说,总可以表示成n=a*k±r,其中a是商,r是余数
所以 n2=(ak±r)2=a2k2±2ark+r2r[0,k2]
所以
n2r2(modk) 对于一个k的周期来说 (k为偶数。k为奇数时只是多处理一个数字,原理是一样的) Mod k 1 2 3 4 …… k/2 k/2+1 k/2+2 …… k-1 0 我们有
k2+1k2+1(modk)
k2+2(k22)(modk)
k2+3(k23)(modk)
……
k11(modk)
k0(modk) Mod k 1 2 3 4 …… k/2 -k/2+1 -k/2+2 …… k-1 0 可以看到 余数是从1,2……,k/2,-k/2+1……-2,-1,0这样变化的。
又有
{n2r2(modk)r2=r2 自然就会看到这是个对称的变化了。 那么,形如
{an|an=nλ,λN+}
这样的数列呢?
容易得到当λ 是偶数的时候,还是有这样的性质。
当λ 是奇数的时候
rλ=(r)λ
此时就不是对称的了。 对于平方探测法 F(i)=i2来说
i>k2 的时候,必定在前面有i0 使得 Hash(x)+i20Hash(x)+i2(modk)
这就产生了冲突,这个冲突是必定存在的。 于是,Hash的可选空位必定小于等于k/2.