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

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

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

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

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

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

Как отмечалось выше, последний бит с заглавной буквы больше не соответствует действительности в 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']

Обратите внимание, что Python 3.7 по-прежнему имеет недетерминированные наборы. dicts сохраняет порядок вставки, а наборы — нет. Наборы могут демонстрировать такое же случайное поведение.

python3 -c "print({str(i) for i in range(9)})"

по-прежнему дает разные результаты от одного запуска к другому.