Por que a ordem do dicionário não é determinística no Python 3.3?

Nas versões do Python anteriores à 3.3, a ordem das chaves do dicionário era arbitrária, mas consistente. No entanto, no Python 3.3, essa ordem tornou-se não determinística.

Essa mudança resulta de uma correção de segurança implementada em 2012 e habilitada por padrão no Python 3.3. A randomização de hash, introduzida para resolver vulnerabilidades de segurança, faz com que a ordem de iteração de dicionários e conjuntos seja imprevisível e difira entre as execuções do Python.

Para desabilitar a randomização de hash, você pode definir a variável de ambiente PYTHONHASHSEED como 0.

Exemplo contraintuitivo

Embora o contra-exemplo na pergunta não produza consistentemente o mesmo resultado no Python 3.3, seu número limitado de ordenações diferentes decorre do tratamento de colisões de hash.

Esta limitação não está mais presente no Python 3.6 e versões posteriores, onde a ordem de inserção dos dicionários é sempre preservada.