2

我正在阅读哈希表教程中的线性探测并遇到了这个问题：

线性探测的步长几乎总是 1，但使用其他步长是可以接受的，只要步长与表大小相对质数，以便最终访问每个索引。如果不满足此限制，则可能无法访问所有索引...

（基本问题是：您需要从任意索引开始访问数组中的每个索引，并向前跳过固定数量的索引 [跳过] 到下一个索引，必要时使用模数换行到数组的开头。）

我理解为什么如果步长不是相对于表大小的素数，为什么不能访问所有索引，但我不明白为什么反过来是真的：如果步长相对素数，所有索引都将被访问数组大小。

我已经观察到这个相对主要的属性在我手工计算的几个示例中起作用，但我不明白为什么它在每种情况下都有效。

简而言之，我的问题是：为什么数组的每个索引都以相对于数组大小为质数的步长来访问？有证据吗？

谢谢！

4

2 回答 2

3

关于循环群的维基百科

环 Z/nZ 的单位是与 n 互质的数。

还有：

[如果两个数互质] 存在整数 x 和 y 使得 ax + by = 1

因此，如果“a”是您的步长，“b”是数组的长度，您可以通过以下方式达到任何索引“z”

axz + byz = z

=>

axz = z (mod b)

即步进“xz”次（并环绕数组“yz”次）。

于 2012-07-30T08:11:34.647 回答
1

步数是lcm(A,P)/P或数组大小A/gcd(A,P)在哪里，是这个神奇的互质数。AP

所以如果gcd(A,P) != 1然后步数将小于A
相反如果gcd(A,P) == 1（coprimes）则步数将为A并且将访问所有索引

于 2012-07-31T00:20:25.393 回答