小编Fai*_*rdy的帖子

我正在研究python如何实现字典.python字典实现中的一个等式涉及使用等式的空字典时隙的伪随机探测

j = ((j*5) + 1) % 2**i

这里解释了.

我已经读过这个问题,Python的内置字典是如何实现的,基本上理解字典是如何实现的.

我不明白的是为什么/如何等式:

j = ((j*5) + 1) % 2**i   

循环通过所有剩余的 2**i.例如,如果i = 3总起始大小为8, j则通过循环:

0
1
6
7
4
5
2
3
0

如果起始大小是16,它将经历循环:

0 1 6 15 12 13 2 11 8 9 14 7 4 5 10 3 0

这对于探测字典中的所有插槽非常有用. 但为什么它有效呢？ 为什么 j = ((j*5)+1)工作但没有工作,j = ((j*6)+1) 或者j = ((j*3)+1) 两者都陷入较小的周期.

我希望能够更直观地理解这一点,而不仅仅是方程式,这就是他们使用它的原因.

我已经看过这个页面 https://wiki.python.org/moin/TimeComplexity 但我没有在列表中看到相反的功能.列表反转的时间复杂度是多少？

我的时间实验表明,对于较大的尺寸,它是O(n).任何人都可以证实吗？

timeit反转大小列表的时间

   10    .1027
  100    .2347
 1000    .6704
10000   6.204
20000  12.9