Como os dicionários internos do Python são implementados?

Alguém sabe como o tipo de dicionário interno para python é implementado? Meu entendimento é que é algum tipo de tabela de hash, mas não consegui encontrar nenhum tipo de resposta definitiva.

Aqui está tudo sobre os dicionários de Python que eu pude montar (provavelmente mais do que alguém gostaria de saber; mas a resposta é abrangente).

• Os dicionários Python são implementados como tabelas de hash .
• As tabelas de hash devem permitir colisões de hash, ou seja, mesmo que duas chaves distintas tenham o mesmo valor de hash, a implementação da tabela deve ter uma estratégia para inserir e recuperar os pares de chave e valor sem ambiguidade.
• O Python dictusa o endereçamento aberto para resolver colisões de hash (explicadas abaixo) (consulte dictobject.c: 296-297 ).
• A tabela de hash Python é apenas um bloco de memória contíguo (como uma matriz, para que você possa fazer uma O(1)pesquisa por índice).
• Cada slot na tabela pode armazenar uma e apenas uma entrada. Isso é importante.
• Cada entrada na tabela na verdade é uma combinação dos três valores: <hash, chave, valor> . Isso é implementado como uma estrutura C (consulte dictobject.h: 51-56 ).

• A figura abaixo é uma representação lógica de uma tabela de hash Python. Na figura abaixo, 0, 1, ..., i, ...à esquerda, estão os índices dos slots na tabela de hash (eles são apenas para fins ilustrativos e não são armazenados junto com a tabela, obviamente!).

  # Logical model of Python Hash table
  -+-----------------+
  0| <hash|key|value>|
  -+-----------------+
  1|      ...        |
  -+-----------------+
  .|      ...        |
  -+-----------------+
  i|      ...        |
  -+-----------------+
  .|      ...        |
  -+-----------------+
  n|      ...        |
  -+-----------------+

• Quando um novo ditado é inicializado, ele começa com 8 slots . (veja dictobject.h: 49 )

• Ao adicionar entradas à tabela, começamos com um slot, ibaseado no hash da chave. O CPython usa inicialmente i = hash(key) & mask(onde mask = PyDictMINSIZE - 1, mas isso não é realmente importante). Observe que o slot inicial i, que está marcado, depende do hash da chave.
• Se esse slot estiver vazio, a entrada será adicionada ao slot (por entrada, quero dizer, <hash|key|value>). Mas e se esse espaço estiver ocupado !? Provavelmente porque outra entrada possui o mesmo hash (colisão de hash!)
• Se o slot estiver ocupado, o CPython (e até o PyPy) compara o hash AND a chave (por comparação, quero dizer ==comparação e não iscomparação) da entrada no slot com o hash e a chave da entrada atual a ser inserida ( dictobject.c 337,344-345 ), respectivamente. Se os dois corresponderem, ele acha que a entrada já existe, desiste e passa para a próxima entrada a ser inserida. Se o hash ou a chave não corresponderem, a investigação começará .
• A sondagem significa apenas que procura nos slots por slot para encontrar um slot vazio. Tecnicamente, poderíamos apenas ir um a um i+1, i+2, ...e usar o primeiro disponível (isso é análise linear). Mas, por razões explicadas lindamente nos comentários (consulte dictobject.c: 33-126 ), o CPython usa sondagem aleatória . Na sondagem aleatória, o próximo slot é selecionado em uma ordem pseudo-aleatória. A entrada é adicionada ao primeiro slot vazio. Para esta discussão, o algoritmo real usado para escolher o próximo slot não é realmente importante (consulte dictobject.c: 33-126 para o algoritmo para análise ). O importante é que os slots sejam analisados ​​até que o primeiro slot vazio seja encontrado.
• O mesmo acontece com as pesquisas, apenas começa com o slot inicial i (onde i depende do hash da chave). Se o hash e a chave não coincidirem com a entrada no slot, ele começará a investigar, até encontrar um slot com uma correspondência. Se todos os slots estiverem esgotados, ele relatará uma falha.
• BTW, o dictserá redimensionado se estiver com dois terços do total. Isso evita lentidão nas pesquisas. (consulte dictobject.h: 64-65 )

NOTA: Fiz a pesquisa sobre a implementação do Python Dict em resposta à minha própria pergunta sobre como várias entradas em um dict podem ter os mesmos valores de hash. Publiquei uma versão ligeiramente editada da resposta aqui, porque toda a pesquisa também é muito relevante para essa pergunta.

Como os dicionários internos do Python são implementados?

Aqui está o curso curto:

• Eles são tabelas de hash. (Veja abaixo os detalhes da implementação do Python.)
• Um novo layout e algoritmo, a partir do Python 3.6, os torna
  • ordenados por inserção de chave e
  • ocupam menos espaço,
  • praticamente sem nenhum custo no desempenho.
• Outra otimização economiza espaço quando os dict compartilham chaves (em casos especiais).

O aspecto ordenado não é oficial a partir do Python 3.6 (para dar a outras implementações a chance de acompanhar), mas é oficial no Python 3.7 .

Os dicionários do Python são tabelas de hash

Por um longo tempo, funcionou exatamente assim. O Python pré-alocaria 8 linhas vazias e usaria o hash para determinar onde colar o par de valores-chave. Por exemplo, se o hash da chave terminasse em 001, ele seria fixado no índice 1 (ou seja, 2º) (como no exemplo abaixo).

   <hash>       <key>    <value>
     null        null    null
...010001    ffeb678c    633241c4 # addresses of the keys and values
     null        null    null
      ...         ...    ...

Cada linha ocupa 24 bytes em uma arquitetura de 64 bits, 12 em 32 bits. (Observe que os cabeçalhos das colunas são apenas rótulos para nossos propósitos aqui - eles realmente não existem na memória.)

Se o hash terminasse da mesma forma que o hash de uma chave preexistente, isso é uma colisão e, em seguida, colocaria o par de valores-chave em um local diferente.

Depois que 5 valores-chave são armazenados, ao adicionar outro par de valores-chave, a probabilidade de colisões de hash é muito grande, portanto o dicionário é dobrado em tamanho. Em um processo de 64 bits, antes do redimensionamento, temos 72 bytes vazios e, depois, desperdiçamos 240 bytes devido às 10 linhas vazias.

Isso demanda muito espaço, mas o tempo de pesquisa é bastante constante. O algoritmo de comparação de chaves é calcular o hash, ir para o local esperado, comparar o ID da chave - se eles são o mesmo objeto, são iguais. Caso contrário, compare os valores de hash, se não forem iguais, não serão iguais. Senão, finalmente comparamos as chaves para igualdade e, se forem iguais, retornamos o valor. A comparação final para igualdade pode ser bastante lenta, mas as verificações anteriores geralmente atalhos a comparação final, tornando as pesquisas muito rápidas.

As colisões tornam as coisas mais lentas, e um invasor teoricamente poderia usar colisões de hash para executar um ataque de negação de serviço; portanto, randomizamos a inicialização da função hash, de modo que calcule hashes diferentes para cada novo processo Python.

O espaço desperdiçado descrito acima nos levou a modificar a implementação de dicionários, com um novo recurso interessante: os dicionários agora são ordenados por inserção.

As novas tabelas de hash compactas

Em vez disso, começamos pré-alocando uma matriz para o índice da inserção.

Como nosso primeiro par de valores-chave fica no segundo slot, indexamos assim:

[null, 0, null, null, null, null, null, null]

E nossa tabela é preenchida apenas por pedido de inserção:

   <hash>       <key>    <value>
...010001    ffeb678c    633241c4 
      ...         ...    ...

Portanto, quando procuramos uma chave, usamos o hash para verificar a posição que esperamos (nesse caso, vamos diretamente para o índice 1 da matriz) e depois para esse índice na tabela de hash (por exemplo, índice 0 ), verifique se as chaves são iguais (usando o mesmo algoritmo descrito anteriormente) e, se houver, retorne o valor.

Mantemos tempo de pesquisa constante, com pequenas perdas de velocidade em alguns casos e ganhos em outros, com as vantagens de economizar bastante espaço em relação à implementação pré-existente e manter a ordem de inserção. O único espaço desperdiçado são os bytes nulos na matriz de índice.

Raymond Hettinger introduziu isso no python-dev em dezembro de 2012. Ele finalmente entrou no CPython no Python 3.6 . A ordenação por inserção foi considerada um detalhe de implementação do 3.6 para permitir que outras implementações do Python tenham a chance de acompanhar.

Chaves compartilhadas

Outra otimização para economizar espaço é uma implementação que compartilha chaves. Portanto, em vez de termos dicionários redundantes que ocupam todo esse espaço, temos dicionários que reutilizam as chaves compartilhadas e os hashes das chaves. Você pode pensar assim:

     hash         key    dict_0    dict_1    dict_2...
...010001    ffeb678c    633241c4  fffad420  ...
      ...         ...    ...       ...       ...

Para uma máquina de 64 bits, isso pode economizar até 16 bytes por chave por dicionário extra.

Chaves compartilhadas para objetos personalizados e alternativas

Esses ditados de chave compartilhada devem ser usados ​​para objetos personalizados ' __dict__. Para obter esse comportamento, acredito que você precisa concluir o preenchimento do seu __dict__antes de instanciar seu próximo objeto ( consulte PEP 412 ). Isso significa que você deve atribuir todos os seus atributos no arquivo __init__ou __new__, caso contrário, poderá não economizar espaço.

No entanto, se você conhece todos os seus atributos no momento em que __init__é executado, você também pode fornecer o __slots__seu objeto e garantir que ele __dict__não seja criado (se não estiver disponível nos pais), ou mesmo permitir, __dict__mas garantir que seus atributos previstos sejam armazenados em slots de qualquer maneira. Para mais informações __slots__, veja minha resposta aqui .

Veja também:

• PEP 509 - Adicione uma versão privada ao ditado
• PEP 468 - Preservando a ordem de **kwargsem uma função.
• PEP 520 - Preservando a ordem de definição de atributo da classe
• PyCon 2010: O Dicionário do Poder - Brandon Rhodes
• PyCon 2017: o dicionário ainda mais poderoso - Brandon Rhodes
• PyCon 2017: Dicionários Python modernos Uma confluência de uma dúzia de grandes idéias - Raymond Hettinger
• dictobject.c - implementação de dict real do CPython em C.

Os dicionários Python usam o endereçamento aberto ( referência dentro do código Beautiful )

NB! O endereçamento aberto , também conhecido como hash fechado , não deve, como observado na Wikipedia, ser confundido com seu hash aberto oposto !

O endereçamento aberto significa que o dict usa slots de matriz e, quando a posição principal de um objeto é tomada no dict, o local do objeto é procurado em um índice diferente na mesma matriz, usando um esquema de "perturbação", no qual o valor de hash do objeto faz parte .