Почему словарь не является детерминированным?

Недавно я переключился с Python 2.7 на Python 3.3, и кажется, что, хотя в Python 2 упорядочение ключей словаря было произвольным, но последовательным, в Python 3 упорядочивание ключей словаря, полученного с помощью, например, vars() выглядит недетерминированным.

Если я запустил:

class Test(object): pass
parameters = vars(Test)
print(list(parameters.keys()))

как в Python 2.7, так и в Python 3.3, тогда:

  • Python 2.7 последовательно дает мне

    ['__dict__', '__module__', '__weakref__', '__doc__']

  • С Python 3.3 я могу получить любой случайный порядок - например:

    ['__weakref__', '__module__', '__qualname__', '__doc__', '__dict__']
['__doc__', '__dict__', '__qualname__', '__module__', '__weakref__']
['__dict__', '__module__', '__qualname__', '__weakref__', '__doc__']
['__weakref__', '__doc__', '__qualname__', '__dict__', '__module__']

Откуда этот детерминизм? И почему что-то вроде

list({str(i): i for i in range(10)}.keys())

... согласован между прогонами, всегда давая

['3', '2', '1', '0', '7', '6', '5', '4', '9', '8']

...?

Ответы

Ответ 1

Обновление: в Python 3.6, dict имеет новую реализацию, которая сохраняет порядок вставки. Начиная с Python 3.7, это сохраняющее порядок поведение гарантировано:

природа сохранения порядка вставки объектов dict была объявлена официальной частью спецификации языка Python.

Это результат исправления безопасности 2012 года, которое было включено по умолчанию в Python 3.3 (прокрутите вниз до "Улучшения безопасности").

Из объявления:

Рандомизация хэшей приводит к тому, что порядок итераций и наборы становятся непредсказуемыми и различаются в зависимости от запуска Python. Python никогда не гарантировал порядок итераций ключей в dict или set, и приложениям никогда не рекомендуется полагаться на него. Исторически сложилось так, что порядок повторения итераций не очень часто менялся в разных выпусках и всегда оставался неизменным между последовательными выполнениями Python. Таким образом, некоторые существующие приложения могут полагаться на диктовку или устанавливать порядок. Из-за этого и того факта, что многие приложения Python, которые не принимают ненадежные входные данные, не подвержены этой атаке, во всех стабильных выпусках Python, упомянутых здесь, HAND RANDOMIZATION ОТКЛЮЧЕНО ПО УМОЛЧАНИЮ.

Как отмечалось выше, последний бит с большой буквы больше не имеет значения в Python 3.3.

См. Также документацию object.__hash__() (боковая панель "Примечание").

Если это абсолютно необходимо, вы можете отключить рандомизацию хеша в версиях Python, затронутых этим поведением, установив для переменной среды PYTHONHASHSEED значение 0.

Ваш контрпример:

list({str(i): i for i in range(10)}.keys())

… На самом деле не всегда дает одинаковый результат в Python 3.3, хотя количество различных упорядочений ограничено из- за способа обработки коллизий хешей:

$ for x in {0..999}
> do
>   python3.3 -c "print(list({str(i): i for i in range(10)}.keys()))"
> done | sort | uniq -c
     61 ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
     73 ['1', '0', '3', '2', '5', '4', '7', '6', '9', '8']
     62 ['2', '3', '0', '1', '6', '7', '4', '5', '8', '9']
     59 ['3', '2', '1', '0', '7', '6', '5', '4', '9', '8']
     58 ['4', '5', '6', '7', '0', '1', '2', '3', '8', '9']
     55 ['5', '4', '7', '6', '1', '0', '3', '2', '9', '8']
     62 ['6', '7', '4', '5', '2', '3', '0', '1', '8', '9']
     63 ['7', '6', '5', '4', '3', '2', '1', '0', '9', '8']
     60 ['8', '9', '0', '1', '2', '3', '4', '5', '6', '7']
     66 ['8', '9', '2', '3', '0', '1', '6', '7', '4', '5']
     65 ['8', '9', '4', '5', '6', '7', '0', '1', '2', '3']
     53 ['8', '9', '6', '7', '4', '5', '2', '3', '0', '1']
     62 ['9', '8', '1', '0', '3', '2', '5', '4', '7', '6']
     52 ['9', '8', '3', '2', '1', '0', '7', '6', '5', '4']
     73 ['9', '8', '5', '4', '7', '6', '1', '0', '3', '2']
     76 ['9', '8', '7', '6', '5', '4', '3', '2', '1', '0']

Как отмечалось в начале этого ответа, это больше не относится к Python 3.6:

$ for x in {0..999}
> do
>   python3.6 -c "print(list({str(i): i for i in range(10)}.keys()))"
> done | sort | uniq -c
   1000 ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']

Ответ 2

Обратите внимание, что Python 3.7 все еще имеет недетерминированные наборы. Дикты сохраняют порядок вставки, а наборы - нет.