«Странное» упорядочение множеств в python

Когда я преобразую список Python 3.8.0 в набор, результирующее упорядочение набора * очень структурировано нетривиальным способом. Как эта структура извлекается из псевдослучайного списка?

В рамках эксперимента, который я провожу, я генерирую случайный набор. Я был удивлен, увидев, что построение сюжета неожиданно показало неожиданную линейную структуру в наборе. Так что меня озадачивают две вещи: почему преобразование в заданный результат имеет порядок *, который в конечном итоге выделяет эту структуру; и, в меньшей степени, почему псевдослучайное множество вообще имеет эту «скрытую» структуру?

Код:

X = [randrange(250) for i in range(30)]
print(X)
print(set(X))

какие выводы, например

[238, 202, 245, 94, 111, 106, 148, 164, 154, 113, 128, 10, 196, 141, 69, 38, 106, 8, 40, 53, 160, 87, 85, 13, 38, 147, 204, 50, 162, 91]

{128, 8, 10, 141, 13, 147, 148, 154, 160, 162, 164, 38, 40, 50, 53, 196, 69, 202, 204, 85, 87, 91, 94, 106, 238, 111, 113, 245}

График ** из приведенного выше списка выглядит довольно случайным, как и ожидалось:

тогда как построение графика набора (как это упорядочено в выводе) показывает структуру, присутствующую в наборе:

Такое поведение на моей машине на 100% соответствует (больше примеров ниже) со значениями 250 и 30, использованными в приведенном выше коде (пример, который я использовал, не был выбран вишней - это только последний, который я запустил). Настройка этих значений иногда приводит к несколько иной структуре (например, подмножество трех арифметических прогрессий *** вместо двух).

Это воспроизводимо на машинах других людей? Конечно, такая структура существует, кажется, свидетельствует о не очень большой генерации псевдослучайных чисел, но это не объясняет, как преобразование в набор в некотором смысле «извлечет» эту структуру. Насколько мне известно, нет формальной гарантии того, что упорядочение набора (при преобразовании из списка) является детерминированным (и даже если это так, в фоновом режиме не выполняется сложное упорядочение). Так как же это происходит ?!

(*): Я знаю, что наборы являются неупорядоченными коллекциями, но я имею в виду «упорядоченный» в том смысле, что при вызове printоператора набор выводится в некотором порядке, который последовательно выделяет базовую структуру набора.

(**): Эти сюжеты взяты из Wolfram Alpha. Еще два примера ниже:

(***): два графика при изменении диапазона случайных чисел с 250 на 500:

В основном это из-за двух вещей:

• Набор в Python реализован с использованием хеш-таблицы ,
• Хеш целого числа - это само целое число.

Следовательно, индекс, в котором целое число появляется в базовом массиве, будет определяться значением целого числа по модулю длины базового массива. Таким образом, целые числа будут стремиться оставаться в порядке возрастания, когда вы помещаете их в ряд:

>>> list(set(range(10000))) == list(range(10000))
True # this can't be an accident!

Если у вас нет всех чисел из смежного диапазона, то в игру вступает часть «по модулю длины основного массива»:

>>> r = range(0, 50, 4)
>>> set(r)
{0, 32, 4, 36, 8, 40, 12, 44, 16, 48, 20, 24, 28}
>>> sorted(r, key=lambda x: x % 32)
[0, 32, 4, 36, 8, 40, 12, 44, 16, 48, 20, 24, 28]

Последовательность является предсказуемой, если вы знаете длину базового массива и (детерминированный) алгоритм добавления элементов. В этом случае длина массива равна 32, потому что изначально он равен 8 и увеличивается в четыре раза при добавлении элементов.

На экране радара вблизи конца , за исключением (потому что числа 52 и 56 не в наборе), диапазон разделен на две последовательности 0, 4, 8, ...и 32, 36, 40, ...которые чередуются , так как хэш, которые сами значения чисел, взяты по модулю 32 , чтобы выбрать индексы в массиве. Есть столкновения; например, 4 и 36 равны по модулю 32, но 4 был добавлен в набор первым, так что 36 заканчивается с другим индексом.

Вот диаграмма для этой последовательности. Структура в ваших диаграммах - просто более шумная версия, потому что вы генерировали свои числа случайно, а не из диапазона с шагом.

Количество чередующихся последовательностей будет зависеть от размера набора пропорционально длине диапазона, из которого выбираются числа, поскольку это определяет, во сколько раз длина диапазона «оборачивается» по модулю длины базового массива хеш-таблицы. Вот пример с тремя чередующимися последовательностями 0, 6, 12, ..., 66, 72, 78, ...и 36, 42, 48, ...:

>>> set(range(0, 90, 6))
{0, 66, 36, 6, 72, 42, 12, 78, 48, 18, 84, 54, 24, 60, 30}