Интеграционное тестирование с Redis

Вы должны посмотреть это видео (хотя это специфичный для CPython1 и около словарей), но я предполагаю, что это относится и к наборам).

В принципе, python хэширует элементы и берет последние N бит (где N определяется размером набора) и использует эти биты в качестве индексов массива для размещения объекта в памяти. Затем объекты выводятся в том порядке, в котором они существуют в памяти. Конечно, изображение становится немного более сложным, когда вам нужно разрешать столкновения между хэшами, но это его суть.

Также обратите внимание, что порядок их распечатки определяется порядком, который вы положить их (из-за столкновений). Таким образом, если вы переупорядочиваете список, который вы переходите на set_2, вы можете получить другой порядок, если есть ключевые коллизии.

Например:

list1 = [8,16,24]
set(list1)        #set([8, 16, 24])
list2 = [24,16,8]
set(list2)        #set([24, 16, 8])

Обратите внимание: тот факт, что порядок сохраняется в этих наборах, является «совпадением» и имеет отношение к разрешению конфликтов (о котором я ничего не знаю). Дело в том, что последние 3 бита hash(8), hash(16) и hash(24) совпадают. Поскольку они одинаковы, разрешение конфликтов берет на себя и помещает элементы в «резервные» ячейки памяти вместо первого (лучшего) выбора и поэтому определяется ли 8 местоположение или 16, по которому кто-то прибыл на сторону

Если мы повторим пример с 1, 2 и 3, вы получите последовательный порядок независимо от того, какой порядок у них есть в списке входных данных :

list1 = [1,2,3]
set(list1)      # set([1, 2, 3])
list2 = [3,2,1]
set(list2)      # set([1, 2, 3])

, поскольку последние 3 бита hash(1), hash(2) и hash(3) уникальны.

1Note Реализация, описанная здесь, применима к CPython dict и set. Я думаю, что общее описание действительно для всех современных версий CPython до 3.6. Однако, начиная с CPython3.6, есть дополнительная деталь реализации, которая фактически сохраняет порядок вставки для итерации для dict. Похоже, что set до сих пор не обладает этим свойством. Структура данных описывается этой записью в блоге людьми pypy (которые начали использовать это перед людьми CPython). Исходная идея (по крайней мере для экосистемы python) заархивирована в списке рассылки python-dev .