Я изучаю, как 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)
, оба из которых застревают в меньших циклах.
Я надеюсь получить более интуитивное понимание этого, чем просто работает уравнение и почему они его использовали.