arrays - 为什么线性探测使用相对主要的步骤？

Question

我正在阅读 linear probing在hash table tutorial并发现了这个:

The step size is almost always 1 with linear probing, but it is acceptable to use other step sizes as long as the step size is relatively prime to the table size so that every index is eventually visited. If this restriction isn't met, all of the indices may not be visited...

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

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

我观察到这个相对主要的性质在我手工计算的几个例子中起作用，但我不明白为什么它在所有情况下都起作用。

简而言之，我的问题是:为什么数组的每个索引都以与数组大小互质的步长访问？有这方面的证据吗？

谢谢!

Answer 1

维基百科关于 Cyclic Groups

The units of the ring Z/nZ are the numbers coprime to n.

Also :

[If two numbers are co-prime] There exist integers x and y such that ax + by = 1

所以，如果“a”是你的步长，“b”是数组的长度，你可以到达任何索引“z”

axz + byz = z

=>

axz = z (mod b)

即步进“xz”次(并环绕数组“yz”次)。