Por que a ordem nos dicionários e conjuntos é arbitrária?

Eu não entendo como o loop sobre um dicionário ou conjunto em python é feito por ordem 'arbitrária'.

Quero dizer, é uma linguagem de programação, então tudo na linguagem deve ser 100% determinado, correto? O Python deve ter algum tipo de algoritmo que decida qual parte do dicionário ou conjunto será escolhida, 1º, segundo e assim por diante.

o que estou perdendo?

Nota: Essa resposta foi escrita antes da dictalteração do tipo de implementação , no Python 3.6. A maioria dos detalhes de implementação nesta resposta ainda se aplica, mas a ordem de listagem das chaves nos dicionários não é mais determinada por valores de hash. A implementação do conjunto permanece inalterada.

A ordem não é arbitrária, mas depende do histórico de inserção e exclusão do dicionário ou conjunto, bem como da implementação específica do Python. Para o restante desta resposta, para 'dicionário', você também pode ler 'conjunto'; conjuntos são implementados como dicionários com apenas chaves e sem valores.

As chaves são hash e os valores de hash são atribuídos aos slots em uma tabela dinâmica (ela pode aumentar ou diminuir com base nas necessidades). E esse processo de mapeamento pode levar a colisões, o que significa que uma chave terá que ser encaixada no próximo slot, com base no que já está lá.

Listar os loops de conteúdo sobre os slots e, portanto, as chaves são listadas na ordem em que residem atualmente na tabela.

Pegue as teclas 'foo'e 'bar', por exemplo, e vamos supor que o tamanho da tabela seja 8 slots. No Python 2.7, hash('foo')é -4177197833195190597, hash('bar')é 327024216814240868. Módulo 8, isso significa que essas duas chaves são encaixadas nos slots 3 e 4 e depois:

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

Isso informa sua ordem de listagem:

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

Todos os slots, exceto 3 e 4, estão vazios, fazendo um loop sobre a tabela, primeiro o slot 3 e depois o slot 4, conforme 'foo'listado anteriormente 'bar'.

bare baz, no entanto, têm valores de hash que são exatamente 8 separados e, portanto, são mapeados exatamente para o mesmo slot 4:

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

Sua ordem agora depende de qual chave foi inserida primeiro; a segunda chave terá que ser movida para o próximo slot:

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

A ordem da tabela difere aqui, porque uma ou outra tecla foi encaixada primeiro.

O nome técnico para a estrutura subjacente usada pelo CPython (a implementação Python mais usada) é uma tabela de hash , que usa endereçamento aberto. Se você está curioso e entende bem o C, dê uma olhada na implementação do C para obter todos os detalhes (bem documentados). Você também pode assistir a esta apresentação do Pycon 2010 de Brandon Rhodes sobre como o CPython dictfunciona, ou pegar uma cópia do Beautiful Code , que inclui um capítulo sobre a implementação, escrito por Andrew Kuchling.

Observe que, a partir do Python 3.3, também é usada uma semente aleatória de hash, tornando imprevisíveis as colisões de hash para impedir certos tipos de negação de serviço (onde um invasor torna um servidor Python sem resposta, causando colisões de hash em massa). Isso significa que a ordem de um determinado dicionário ou conjunto também depende da semente de hash aleatória para a invocação atual do Python.

Outras implementações são livres para usar uma estrutura diferente para dicionários, desde que satisfaçam a interface do Python documentada para eles, mas acredito que todas as implementações até agora usam uma variação da tabela de hash.

O CPython 3.6 apresenta uma nova dict implementação que mantém a ordem de inserção e é mais rápida e eficiente em termos de memória para inicializar. Em vez de manter uma tabela esparsa grande em que cada linha faz referência ao valor de hash armazenado e aos objetos de chave e valor, a nova implementação adiciona uma matriz de hash menor que apenas faz referência a índices em uma tabela 'densa' separada (uma que contém apenas tantas linhas porque existem pares de valores-chave reais) e é a tabela densa que lista os itens contidos em ordem. Veja a proposta do Python-Dev para mais detalhes . Observe que no Python 3.6 isso é considerado um detalhe de implementação, Python-the-language não especifica que outras implementações tenham que manter a ordem. Isso mudou no Python 3.7, onde esse detalhe foi elevado para ser uma especificação de linguagem ; para que qualquer implementação seja adequadamente compatível com o Python 3.7 ou mais recente, é necessário copiar esse comportamento de preservação de pedidos. E para ser explícito: essa alteração não se aplica aos conjuntos, pois os conjuntos já possuem uma estrutura de hash 'pequena'.

O Python 2.7 e mais recente também fornece uma OrderedDictclasse , uma subclasse dictque adiciona uma estrutura de dados adicional para registrar a ordem das chaves. Ao preço de alguma velocidade e memória extra, essa classe se lembra em que ordem você inseriu as chaves; listar chaves, valores ou itens fará isso nessa ordem. Ele usa uma lista duplamente vinculada armazenada em um dicionário adicional para manter o pedido atualizado com eficiência. Veja o post de Raymond Hettinger descrevendo a idéia . OrderedDictos objetos têm outras vantagens, como serem solicitados novamente .

Se você quiser um conjunto ordenado, poderá instalar o osetpacote ; funciona em Python 2.5 e superior.

Esta é mais uma resposta ao Python 3.41 Um conjunto antes de ser fechado como duplicado.

Os outros estão certos: não confie no pedido. Nem finja que existe um.

Dito isto, há uma coisa em que você pode confiar:

list(myset) == list(myset)

Ou seja, a ordem é estável .

Entender por que existe uma ordem percebida requer entender algumas coisas:

• Que o Python usa conjuntos de hash ,

• Como o conjunto de hash do CPython é armazenado na memória e

• Como os números são divididos

Do topo:

Um conjunto de hash é um método de armazenamento de dados aleatórios com tempos de pesquisa muito rápidos.

Tem uma matriz de apoio:

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

Ignoraremos o objeto fictício especial, que existe apenas para facilitar a remoção, porque não removeremos esses conjuntos.

Para ter uma pesquisa realmente rápida, você faz alguma mágica para calcular um hash de um objeto. A única regra é que dois objetos iguais tenham o mesmo hash. (Mas se dois objetos tiverem o mesmo hash, poderão ser desiguais.)

Em seguida, você cria o índice assumindo o módulo pelo comprimento da matriz:

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

Isso torna muito rápido o acesso a elementos.

Hashes são apenas a maior parte da história, como hash(n) % len(storage)e hash(m) % len(storage)pode resultar no mesmo número. Nesse caso, várias estratégias diferentes podem tentar resolver o conflito. O CPython usa a "pesquisa linear" 9 vezes antes de fazer coisas complicadas, portanto, ele procurará à esquerda do slot até 9 lugares antes de procurar em outro lugar.

Os conjuntos de hash do CPython são armazenados assim:

• Um conjunto de hash pode ter no máximo 2/3 de sua capacidade . Se houver 20 elementos e a matriz de suporte tiver 30 elementos, o armazenamento de backup será redimensionado para ser maior. Isso ocorre porque as colisões são mais frequentes com pequenas lojas de apoio e as colisões tornam tudo mais lento.

• A loja de suporte é redimensionada em potências de 4, começando em 8, exceto em conjuntos grandes (elementos de 50 mil) que são redimensionados em potências de dois: (8, 32, 128, ...).

Portanto, quando você cria uma matriz, o armazenamento de backup tem o comprimento 8. Quando estiver 5 cheio e você adicionar um elemento, ele conterá brevemente 6 elementos. 6 > ²⁄₃·8portanto, isso gera um redimensionamento e a loja de backup quadruplica para o tamanho 32.

Finalmente, hash(n)apenas retorna npara números (exceto o -1que é especial).

Então, vamos olhar para o primeiro:

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

len(v_set)é 10, portanto, a loja de suporte é pelo menos 15 (+1) depois que todos os itens foram adicionados . A potência relevante de 2 é 32. Portanto, a loja de suporte é:

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

Nós temos

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

então eles são inseridos como:

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

Então, esperaríamos um pedido como

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

com o 1 ou 33 que não está no início em outro lugar. Isso usará análise linear, portanto, teremos:

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

ou

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

Você pode esperar que o 33 seja o que foi deslocado porque o 1 já estava lá, mas devido ao redimensionamento que acontece enquanto o conjunto está sendo construído, esse não é realmente o caso. Toda vez que o conjunto é reconstruído, os itens já adicionados são efetivamente reordenados.

Agora você pode ver porque

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

pode estar em ordem. Como existem 14 elementos, a loja de suporte é pelo menos 21 + 1, o que significa 32:

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

1 a 13 hash nos primeiros 13 slots. 20 entra no slot 20.

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

55 vai no slot hash(55) % 32que é 23:

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

Se escolhermos 50, esperaríamos

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

E eis que eis:

{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 é implementado simplesmente pela aparência das coisas: ele percorre a lista e abre a primeira.

Isso é tudo detalhe da implementação.

"Arbitrário" não é o mesmo que "não determinado".

O que eles estão dizendo é que não há propriedades úteis da ordem de iteração do dicionário que estão "na interface pública". Quase certamente existem muitas propriedades da ordem de iteração que são totalmente determinadas pelo código que atualmente implementa a iteração de dicionário, mas os autores não as prometem a você como algo que você pode usar. Isso lhes dá mais liberdade para alterar essas propriedades entre versões do Python (ou mesmo apenas em diferentes condições operacionais, ou completamente aleatoriamente em tempo de execução) sem se preocupar com a interrupção do programa.

Portanto, se você escrever um programa que depende de qualquer propriedade em toda a ordem do dicionário, estará "quebrando o contrato" do uso do tipo de dicionário, e os desenvolvedores do Python não estão prometendo que isso sempre funcione, mesmo que pareça funcionar por enquanto, quando você testá-lo. É basicamente o equivalente a confiar em "comportamento indefinido" em C.

As outras respostas a esta pergunta são excelentes e bem escritas. O OP pergunta "como", que eu interpreto como "como eles escapam" ou "por que".

A documentação do Python diz que os dicionários não são ordenados porque o dicionário Python implementa a matriz associativa abstrata do tipo de dados . Como eles dizem

a ordem na qual as ligações são retornadas pode ser arbitrária

Em outras palavras, um estudante de ciência da computação não pode assumir que uma matriz associativa está ordenada. O mesmo vale para conjuntos em matemática

a ordem na qual os elementos de um conjunto são listados é irrelevante

e ciência da computação

um conjunto é um tipo de dados abstrato que pode armazenar determinados valores, sem nenhuma ordem específica

A implementação de um dicionário usando uma tabela de hash é um detalhe de implementação interessante, pois possui as mesmas propriedades que matrizes associativas em relação à ordem.

O Python usa a tabela de hash para armazenar os dicionários, portanto, não há ordem nos dicionários ou outros objetos iteráveis ​​que usam a tabela de hash.

Mas em relação aos índices de itens em um objeto hash, python calcular os índices com base no seguinte código dentrohashtable.c :

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

Portanto, como o valor de hash de números inteiros é o próprio número inteiro ^*, o índice é baseado no número ( ht->num_buckets - 1é uma constante), de modo que o índice calculado por Bitwise - and between (ht->num_buckets - 1)e o próprio número ^* (espere -1, que é o hash é -2 ) e para outros objetos com seu valor de hash.

considere o exemplo a seguir com setesse uso de tabela de hash:

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

Para número 33, temos:

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

Na verdade é isso:

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

A nota neste caso (ht->num_buckets - 1)é 8-1=7ou 0b111.

E para 1919:

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

E para 333:

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

Para obter mais detalhes sobre a função hash python, é bom ler as seguintes citações do código-fonte python :

Principais sutilezas à frente: a maioria dos esquemas de hash depende de ter uma função "boa" de hash, no sentido de simular aleatoriedade. Python não: suas funções hash mais importantes (para strings e ints) são muito regulares em casos comuns:

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

Isso não é necessariamente ruim! Pelo contrário, em uma tabela de tamanho 2 ** i, obtendo os bits i de ordem inferior, pois o índice da tabela inicial é extremamente rápido e não há colisões para dictos indexados por um intervalo contíguo de ints. O mesmo ocorre aproximadamente quando as chaves são seqüências de caracteres "consecutivas". Portanto, isso oferece um comportamento melhor que aleatório em casos comuns, e isso é muito desejável.

OTOH, quando ocorrem colisões, a tendência de preencher fatias contíguas da tabela de hash torna crucial uma boa estratégia de resolução de colisões. Tomar apenas os últimos i bits do código hash também é vulnerável: por exemplo, considere a lista [i << 16 for i in range(20000)]como um conjunto de chaves. Como ints são seus próprios códigos de hash, e isso se encaixa em um ditado de tamanho 2 ** 15, os últimos 15 bits de cada código de hash são todos 0: todos eles são mapeados para o mesmo índice de tabela.

Mas atender a casos incomuns não deve retardar os usuais, por isso, apenas pegamos os últimos bits i. Cabe à resolução da colisão fazer o resto. Se geralmente encontramos a chave que procuramos na primeira tentativa (e, ao que parece, costumamos encontrar - o fator de carga da mesa é mantido em 2/3, de modo que as probabilidades estão a nosso favor), então faz mais sentido manter a sujeira inicial da computação do índice barata.

_{* A função hash da classe int:}

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

Começando no Python 3.7 (e já no CPython 3.6 ), os itens do dicionário permanecem na ordem em que foram inseridos .