Почему порядок в словарях и множествах произвольный?

Я не понимаю, как зацикливание словаря или набора в python осуществляется в произвольном порядке.

Я имею в виду, что это язык программирования, поэтому все в языке должно быть определено на 100%, верно? У Python должен быть какой-то алгоритм, который решает, какая часть словаря или набора выбрана, 1-я, вторая и так далее.

Чего мне не хватает?

Примечание. Этот ответ был написан до изменения реализации dictтипа в Python 3.6. Большинство деталей реализации в этом ответе все еще применимы, но порядок перечисления ключей в словарях больше не определяется значениями хеша. Заданная реализация остается неизменной.

Порядок не является произвольным, но зависит от истории вставки и удаления словаря или набора, а также от конкретной реализации Python. В оставшейся части этого ответа, для словаря, вы также можете прочитать «set»; наборы реализованы в виде словарей с просто ключами и без значений.

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

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

Возьмем , к примеру, ключи 'foo'и 'bar'предположим, что размер таблицы составляет 8 слотов. В Python 2.7 hash('foo')есть -4177197833195190597, hash('bar')есть 327024216814240868. По модулю 8 это означает, что эти два ключа расположены в слотах 3 и 4, а затем:

>>> hash('foo')
-4177197833195190597
>>> hash('foo') % 8
3
>>> hash('bar')
327024216814240868
>>> hash('bar') % 8
4

Это информирует их порядок перечисления:

>>> {'bar': None, 'foo': None}
{'foo': None, 'bar': None}

Все слоты, кроме 3 и 4, являются пустыми, поэтому в цикле по таблице сначала перечисляются слоты 3, а затем слоты 4, поэтому они 'foo'перечислены раньше 'bar'.

barи baz, тем не менее, имеют значения хеш-функции, которые находятся точно на расстоянии 8 и, таким образом, отображаются в один и тот же слот 4:

>>> hash('bar')
327024216814240868
>>> hash('baz')
327024216814240876
>>> hash('bar') % 8
4
>>> hash('baz') % 8
4

Их порядок теперь зависит от того, какой ключ был выделен первым; второй ключ должен быть перемещен в следующий слот:

>>> {'baz': None, 'bar': None}
{'bar': None, 'baz': None}
>>> {'bar': None, 'baz': None}
{'baz': None, 'bar': None}

Порядок таблиц здесь отличается, потому что один или другой ключ был выделен первым.

Техническое имя для базовой структуры, используемой CPython (наиболее часто используемая реализация Python), - это хеш-таблица , в которой используется открытая адресация. Если вам любопытно, и вы достаточно хорошо понимаете C, посмотрите на реализацию C для всех (хорошо задокументированных) деталей. Вы также можете посмотреть эту презентацию Pycon 2010 Брэндона Роудса о том, как dictработает CPython , или получить копию Beautiful Code , которая включает главу по реализации, написанную Эндрю Кучлингом.

Обратите внимание, что в Python 3.3 также используется случайное начальное число хешей, что делает коллизии хешей непредсказуемыми для предотвращения определенных типов отказа в обслуживании (когда злоумышленник делает сервер Python без ответа, вызывая массовые коллизии хеша). Это означает, что порядок данного словаря или набора также зависит от случайного начального числа хеша для текущего вызова Python.

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

CPython 3.6 представляет новую dict реализацию, которая поддерживает порядок вставки, а также быстрее и эффективнее при загрузке. Вместо того чтобы хранить большую разреженную таблицу, в которой каждая строка ссылается на сохраненное хеш-значение и объекты ключа и значения, новая реализация добавляет меньший хеш- массив, который ссылается только на индексы в отдельной «плотной» таблице (та, которая содержит только столько строк поскольку существуют фактические пары ключ-значение), и именно плотная таблица приводит список элементов по порядку. Смотрите предложение к Python-Dev для более подробной информации . Обратите внимание, что в Python 3.6 это считается деталью реализацииPython-the-language не указывает, что другие реализации должны сохранять порядок. Это изменилось в Python 3.7, где эта деталь была повышена до спецификации языка ; чтобы любая реализация была должным образом совместима с Python 3.7 или новее, она должна скопировать это поведение, сохраняющее порядок. И чтобы быть в явном виде: это изменение не относится к наборам, так как наборы уже имеют «маленькую» хеш-структуру.

Python 2.7 и новее также предоставляет OrderedDictкласс , подкласс dictкоторого добавляет дополнительную структуру данных для записи порядка ключей. Ценой некоторой скорости и дополнительной памяти этот класс запоминает, в каком порядке вы вставляли ключи; перечисление ключей, значений или элементов будет происходить в таком порядке. Он использует двусвязный список, хранящийся в дополнительном словаре, чтобы эффективно обновлять заказ. Посмотрите пост Раймонда Хеттингера с изложением идеи . OrderedDictобъекты имеют другие преимущества, такие как возможность переупорядочения .

Если вы хотели заказать комплект, вы можете установить osetпакет ; это работает на Python 2.5 и выше.

Это скорее ответ на Python 3.41 Набор до того, как он был закрыт как дубликат.

Другие правы: не полагайтесь на порядок. Даже не притворяйся, что есть.

Тем не менее, есть одна вещь, на которую вы можете положиться:

list(myset) == list(myset)

То есть порядок стабилен .

Понимание, почему существует предполагаемый порядок, требует понимания нескольких вещей:

• Этот Python использует хэш-наборы ,

• Как хэш-набор CPython хранится в памяти и

• Как числа хешируются

Сверху:

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

У него есть резервный массив:

# A C array; items may be NULL,
# a pointer to an object, or a
# special dummy object
_ _ 4 _ _ 2 _ _ 6

Мы будем игнорировать специальный фиктивный объект, который существует только для упрощения удаления, поскольку мы не будем удалять из этих наборов.

Чтобы получить действительно быстрый поиск, вы делаете некоторую магию, чтобы вычислить хеш из объекта. Единственное правило состоит в том, что два равных объекта имеют одинаковый хэш. (Но если два объекта имеют одинаковый хэш, они могут быть неравными.)

Затем вы вносите в индекс, беря модуль по длине массива:

hash(4) % len(storage) = index 2

Это позволяет быстро получить доступ к элементам.

Хэши - это только большая часть истории, поскольку hash(n) % len(storage)и hash(m) % len(storage)могут привести к тому же числу. В этом случае несколько разных стратегий могут попытаться разрешить конфликт. CPython использует «линейное зондирование» 9 раз, прежде чем делать сложные вещи, поэтому он будет искать слева от слота до 9 мест, прежде чем искать в другом месте.

Хеш-наборы CPython хранятся так:

• Набор хешей может быть не более 2/3 . Если имеется 20 элементов, а резервный массив имеет длину 30 элементов, резервное хранилище изменится, чтобы быть больше. Это потому, что вы часто сталкиваетесь с небольшими запасными магазинами, а столкновения замедляют все.

• Резервное хранилище изменяет размеры в степени 4, начиная с 8, за исключением больших наборов (50 тыс. Элементов), размер которых изменяется в степени двух: (8, 32, 128, ...).

Поэтому, когда вы создаете массив, резервное хранилище имеет длину 8. Когда оно заполнено на 5 единиц, и вы добавляете элемент, он будет кратко содержать 6 элементов. 6 > ²⁄₃·8так что это вызывает изменение размера, и резервное хранилище увеличивается в четыре раза до размера 32.

Наконец, hash(n)просто возвращается nдля чисел (кроме, -1который является специальным).

Итак, давайте посмотрим на первый:

v_set = {88,11,1,33,21,3,7,55,37,8}

len(v_set)равно 10, поэтому резервное хранилище составляет не менее 15 (+1) после добавления всех элементов . Соответствующая сила 2 равна 32. Таким образом, резервное хранилище:

__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __

У нас есть

hash(88) % 32 = 24
hash(11) % 32 = 11
hash(1)  % 32 = 1
hash(33) % 32 = 1
hash(21) % 32 = 21
hash(3)  % 32 = 3
hash(7)  % 32 = 7
hash(55) % 32 = 23
hash(37) % 32 = 5
hash(8)  % 32 = 8

так что эти вставки как:

__  1 __  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __
   33 ← Can't also be where 1 is;
        either 1 or 33 has to move

Таким образом, мы ожидаем, что заказ как

{[1 or 33], 3, 37, 7, 8, 11, 21, 55, 88}

с 1 или 33, который не находится в начале где-то еще. Это будет использовать линейное зондирование, поэтому мы будем иметь:

       ↓
__  1 33  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __

или

       ↓
__ 33  1  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __

Вы можете ожидать, что 33 будет смещенным, потому что 1 уже была там, но из-за изменения размера, которое происходит во время построения набора, на самом деле это не так. Каждый раз, когда набор перестраивается, уже добавленные элементы эффективно переупорядочиваются.

Теперь вы можете понять, почему

{7,5,11,1,4,13,55,12,2,3,6,20,9,10}

может быть в порядке. Всего 14 элементов, поэтому резервное хранилище составляет не менее 21 + 1, что означает 32:

__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __

1 до 13 хэша в первых 13 слотах. 20 идет в слот 20.

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ __ __ 20 __ __ __ __ __ __ __ __ __ __ __

55 идет в слот, hash(55) % 32который составляет 23:

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ __ __ 20 __ __ 55 __ __ __ __ __ __ __ __

Если бы мы выбрали 50 вместо этого, мы ожидали бы

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ 50 __ 20 __ __ __ __ __ __ __ __ __ __ __

И о чудо

{1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 20, 50}
#>>> {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 50, 20}

pop реализован довольно просто по внешнему виду: он пересекает список и выдает первый.

Это все детали реализации.

«Произвольный» - это не то же самое, что «неопределенный».

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

Таким образом, если вы пишете программу, которая зависит от какого-либо свойства в любом порядке словаря, то вы «нарушаете договор» использования типа словаря, и разработчики Python не обещают, что это всегда будет работать, даже если кажется, что оно работает сейчас, когда вы проверяете это. Это в основном эквивалент доверия к «неопределенному поведению» в C.

Другие ответы на этот вопрос превосходны и хорошо написаны. ФП спрашивает «как», что я интерпретирую как «как им сойти с рук» или «почему».

Документация Python говорит, что словари не упорядочены, потому что словарь Python реализует ассоциативный массив абстрактных типов данных . Так как они сказали

порядок, в котором возвращаются привязки, может быть произвольным

Другими словами, студент по информатике не может предположить, что ассоциативный массив упорядочен. То же самое верно для наборов в математике

порядок, в котором перечислены элементы набора, не имеет значения

и информатика

набор - это абстрактный тип данных, который может хранить определенные значения без какого-либо определенного порядка

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

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

Но в отношении индексов элементов в хэш - объекта, питон вычислить индексы , основанные на следующий код вhashtable.c :

key_hash = ht->hash_func(key);
index = key_hash & (ht->num_buckets - 1);

Таким образом, поскольку хеш-значение целых чисел представляет собой само целое число ^*, индекс основан на числе ( ht->num_buckets - 1является константой), поэтому индекс, вычисляемый побитовым и между ними, (ht->num_buckets - 1)и само число ^* (ожидаемо для -1, его хэш равен -2 ) и для других объектов с их хэш-значением.

рассмотрим следующий пример с setиспользованием хеш-таблицы:

>>> set([0,1919,2000,3,45,33,333,5])
set([0, 33, 3, 5, 45, 333, 2000, 1919])

Для номера 33у нас есть:

33 & (ht->num_buckets - 1) = 1

Это на самом деле это:

'0b100001' & '0b111'= '0b1' # 1 the index of 33

Обратите внимание, в этом случае (ht->num_buckets - 1)это 8-1=7или 0b111.

И для 1919:

'0b11101111111' & '0b111' = '0b111' # 7 the index of 1919

И для 333:

'0b101001101' & '0b111' = '0b101' # 5 the index of 333

Для более подробной информации о хэш-функции python полезно прочитать следующие цитаты из исходного кода python :

Основные тонкости впереди: большинство хеш-схем зависят от наличия «хорошей» хеш-функции в смысле симуляции случайности. Python не делает: его наиболее важные хеш-функции (для строк и целых) очень регулярны в обычных случаях:

>>> map(hash, (0, 1, 2, 3))
  [0, 1, 2, 3]
>>> map(hash, ("namea", "nameb", "namec", "named"))
  [-1658398457, -1658398460, -1658398459, -1658398462]

Это не обязательно плохо! Наоборот, в таблице размером 2 ** i, бита младшего разряда i в качестве начального индекса таблицы чрезвычайно быстрая, и нет никаких коллизий для кодов, индексируемых непрерывным диапазоном целых чисел. То же самое примерно верно, когда ключи являются «последовательными» строками. Так что это дает поведение лучше случайного в обычных случаях, и это очень желательно.

OTOH, когда происходят коллизии, тенденция заполнять непрерывные фрагменты хеш-таблицы делает хорошую стратегию разрешения коллизий решающей. Использование только последних i-х бит хеш-кода также уязвимо: например, рассмотрите список [i << 16 for i in range(20000)]как набор ключей. Поскольку целые числа являются их собственными хеш-кодами, и это соответствует размеру 2 ** 15, последние 15 бит каждого хеш-кода равны 0: все они соответствуют одному и тому же индексу таблицы.

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

_{* Хеш-функция для класса int:}

class int:
    def __hash__(self):
        value = self
        if value == -1:
            value = -2
        return value

Начиная с Python 3.7 (и уже в CPython 3.6 ), элементы словаря остаются в том порядке, в котором они были вставлены .