问题是关于Hash函数的Linear Probing的。
问题可以规约为，两个互质的数 j 和 k （j<k) , 如果不断地做 j+j+j+..., 那么得出的数 模 k 能不能遍历到任何比 k 小的数？
也就是说， n x j % k 能否得到所有 小于或等于 k的数 1，2，3 ，... , k-1 ，k ? （其中 n = 1,2,3,4....)
答案是可以的。而且， 如果按照 n = 1,2,3,4....的顺序乘下去的话，恰好在 第 k 步 就能够遍历所有比k小的数和等于k的数。
比如， 1x7=7, 2x7=14, 3x7=21, 4x7=28, 5x7=35, 6x7=42,7x7=49,8x7=56, 9x7=63,
你看，9 步 遍历了0到9.
其实，只需要证明，在第k步之前，n x j % k得出的值是不会重复的，否则，假设重复，那么不妨设 n1 的时候n1 x j % k = q = n2 x j % k,其中n1 < n2 < k ,
那么，就得到， n2 x j - n1 x j = ( n2 - n1 ) x j 就是是 k 的倍数了。 不妨设为 p x j = q x k. （这里我们的假设是 “在第k步之前” , 所以 p < k ).
那么 由于 j , k互质，则 可知 k 可以整除 p (这是个定理，证明就不给了）, 但是我们的前提是 p < k，所以不可能， 所以矛盾。
所以 ”在第k步之前，n x j % k得出的值是不会重复的“。所以， 如果 n x j 按照n = 1,2,3,4....的顺序乘下去的话，恰好在 第 k 步 就能够遍历所有比k小的数和等于k的数。
注：这个想法其实是想证明《数据结构与算法分析（c++版）》（Cliffer A. Shaffer)第337页提出的关于Hash Linear Probe Function的一段话.....