Попытка понять, почему генератор первичного списка возвращает упорядоченные списки вплоть до n = 8194, после чего списки больше не упорядочены [дублировать]

Одна ключевая вещь, которая намекается на отличный ответ mgilson , но явно не упоминается ни в одном из существующих ответов:

Малые целые числа хеш для себя:

>>> [hash(x) for x in (1, 2, 3, 88)]
[1, 2, 3, 88]

Строки hash для значений, которые непредсказуемы. Фактически, с 3.3 по умолчанию, , они построены на семя, которое рандомизировано при запуске . Итак, вы получите разные результаты для каждого нового сеанса интерпретатора Python, но:

>>> [hash(x) for x in 'abcz']
[6014072853767888837,
 8680706751544317651,
 -7529624133683586553,
 -1982255696180680242]

Итак, рассмотрим простейшую возможную реализацию хеш-таблицы: просто массив из N элементов, где вставка значение означает, что он помещается в hash(value) % N (при отсутствии столкновений). И вы можете сделать приблизительное предположение о том, насколько велика N - она ​​будет немного больше, чем количество элементов в ней. При создании набора из последовательности из 6 элементов N легко может быть, например, 8.

Что происходит, когда вы храните эти 5 чисел с N = 8? Ну, hash(1) % 8, hash(2) % 8 и т. Д. Являются только самими числами, но hash(88) % 8 равно 0. Итак, массив хеш-таблицы заканчивается удерживанием 88, 1, 2, NULL, NULL, 5, NULL, 7. Поэтому вам должно быть легко понять, почему итерация набора может дать вам 88, 1, 2, 5, 7.

Конечно, Python не гарантирует , что вы получите этот заказ каждый раз. Небольшое изменение способа, которое он угадывает при правильном значении для N, может означать, что 88 заканчивается где-то другим (или заканчивается столкновением с одним из других значений). И, фактически, запуская CPython 3.7 на моем Mac, я получаю 1, 2, 5, 7, 88 .0

Между тем, когда вы создаете хэш из последовательности размером 11, а затем вставляете в него рандомизированные хэши, что происходит? Даже предполагая простейшую реализацию и предполагая, что нет столкновений, вы все еще не знаете, какой заказ вы собираетесь получить. Он будет согласован в течение одного прогона интерпретатора Python, но при следующем запуске он будет отличаться. (Если вы не установили PYTHONHASHSEED в 0 или какое-то другое значение int.) Это именно то, что вы видите.

Конечно, стоит посмотреть на , как наборы фактически реализовано , а не гадать. Но то, что вы предполагаете, основываясь на предположении простейшей реализации хеш-таблицы, - это (запрет на столкновение и запрещение расширения хеш-таблицы), что именно происходит.

Причиной такого поведения является то, что Python использует хеш-таблицы для реализации словаря: https://en.wikipedia.org/wiki/Hash_table#Open_addressing

Позиция ключ определяется его адресом памяти. Если вы знаете память повторного использования Python для некоторых объектов:

>>> a = 'Hello world'
>>> id(a)
140058096568768
>>> a = 'Hello world'
>>> id(a)
140058096568480

Вы можете видеть, что объект a имеет разные адреса каждый раз, когда он инициализирован.

Но для небольших целых чисел это не изменение :

>>> a = 1
>>> id(a)
40060856
>>> a = 1
>>> id(a)
40060856

Даже если мы создадим второй объект с другим именем, он будет таким же:

>>> b = 1
>>> id(b)
40060856

Этот подход позволяет сэкономить память, которую использует интерпретатор Python.

Наборы Python AFAIK реализованы с использованием хэш-таблицы . Порядок, в котором элементы отображаются, зависит от используемой функции хэша. В рамках одного и того же запуска программы хеш-функция, вероятно, не изменяется, поэтому вы получаете тот же порядок.

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

Наборы основаны на хэш-таблице. Хэш значения должен быть последовательным, поэтому порядок будет также - если два элемента хэш не совпадают с одним и тем же кодом, и в этом случае порядок вставки изменит порядок вывода.