Por que Python usa tabela de hash para implementar dict, mas não Red-Black Tree? [fechadas]

Por que Python usa tabela de hash para implementar dict, mas não Red-Black Tree?

Qual é a chave? Atuação?

Esta é uma resposta geral, não específica ao Python.

Comparação de complexidade algorítmica

       | Hash Table  |   Red-Black Tree    |
-------+-------------+---------------------+
Space  | O(n) : O(n) | O(n)     : O(n)     |
Insert | O(1) : O(n) | O(log n) : O(log n) |
Fetch  | O(1) : O(n) | O(log n) : O(log n) |
Delete | O(1) : O(n) | O(log n) : O(log n) |
       | avg  :worst | average  : worst    |

O problema com tabelas de hash é que os hashes podem colidir. Existem vários mecanismos para resolver colisões, por exemplo, endereçamento aberto ou encadeamento separado. O pior caso absoluto é que todas as chaves têm o mesmo código de hash; nesse caso, uma tabela de hash será degradada em uma lista vinculada.

Em todos os outros casos, uma tabela de hash é uma ótima estrutura de dados que é fácil de implementar e oferece bom desempenho. Uma desvantagem é que as implementações que podem aumentar rapidamente a tabela e redistribuir suas entradas provavelmente desperdiçarão quase a mesma quantidade de memória que está sendo realmente usada.

As árvores RB são auto-balanceadas e não alteram sua complexidade algorítmica na pior das hipóteses. No entanto, eles são mais difíceis de implementar. Suas complexidades médias também são piores do que as de uma tabela de hash.

Restrições nas chaves

Todas as chaves em uma tabela de hash devem ser laváveis ​​e comparáveis ​​para igualdade entre si. Isso é especialmente fácil para cadeias ou números inteiros, mas também é bastante simples de se estender a tipos definidos pelo usuário. Em algumas linguagens como Java, essas propriedades são garantidas por definição.

As chaves em uma árvore RB devem ter uma ordem total: cada chave deve ser comparável a qualquer outra chave e as duas chaves devem comparar menor, maior ou igual. Essa igualdade de ordenação deve ser equivalente à igualdade semântica. Isso é direto para números inteiros e outros números, também bastante fácil para seqüências de caracteres (a ordem precisa apenas ser consistente e não observável externamente, portanto a ordem não precisa considerar localidades ^[1] ), mas difícil para outros tipos que não têm ordem inerente . É absolutamente impossível ter chaves de tipos diferentes, a menos que seja possível fazer uma comparação entre elas.

^{[1]: Na verdade, estou errado aqui. Duas seqüências de caracteres podem não ser iguais em bytes, mas ainda assim serem equivalentes de acordo com as regras de algum idioma. Veja, por exemplo, normalizações Unicode para um exemplo em que duas seqüências iguais são codificadas de forma diferente. Se a composição de caracteres Unicode é importante para sua chave de hash é algo que uma implementação de tabela de hash não pode saber.}

Pode-se pensar que uma solução barata para chaves RB-Tree seria primeiro testar a igualdade e depois comparar a identidade (isto é, comparar os ponteiros). No entanto, essa ordem não seria transitiva: Se a == be id(a) > id(c), então deve seguir id(b) > id(c)também, o que não é garantido aqui. Então, em vez disso, podemos usar o código hash de chaves como as chaves de pesquisa. Aqui, a ordem funciona corretamente, mas podemos acabar com várias chaves distintas com o mesmo código de hash, que serão atribuídos ao mesmo nó na árvore RB. Para resolver essas colisões de hash, podemos usar encadeamento separado, como nas tabelas de hash, mas isso também herda o pior comportamento de tabelas de hash - o pior dos dois mundos.

Outros aspectos

• Espero que uma tabela de hash tenha melhor localidade de memória do que uma árvore, porque uma tabela de hash é essencialmente apenas uma matriz.

• As entradas nas duas estruturas de dados têm uma sobrecarga bastante alta:

  • tabela de hash: chave, valor e ponteiro da próxima entrada no caso de encadeamento separado. Armazenar também o código hash pode acelerar o redimensionamento.
  • Árvore RB: chave, valor, cor, ponteiro filho esquerdo, ponteiro filho direito. Observe que, embora a cor seja um bit único, os problemas de alinhamento podem significar que você ainda estará desperdiçando espaço suficiente para quase um ponteiro inteiro, ou até quatro ponteiros quando apenas blocos de memória com capacidade para dois podem ser alocados. De qualquer forma, uma entrada da árvore RB consome mais memória que uma entrada da tabela de hash.

• Inserções e deleções em uma árvore RB envolvem rotações de árvores. Estes não são realmente caros, mas envolvem uma sobrecarga. Em um hash, a inserção e a exclusão não são mais caras do que um acesso simples (embora o redimensionamento de uma tabela de hash na inserção seja um O(n)esforço).

• As tabelas de hash são inerentemente mutáveis, enquanto uma árvore RB também pode ser implementada de maneira imutável. No entanto, isso raramente é útil.

Há toda uma gama de razões que podem ser verdadeiras, mas é provável que as principais sejam:

• As tabelas de hash são mais fáceis de implementar do que as árvores. Nem é totalmente trivial, mas as tabelas de hash são um pouco mais fáceis, e o impacto no domínio das chaves legais é menos rigoroso, pois você só precisa de uma função de hash e de igualdade; as árvores exigem uma função de pedido total, e isso é muito mais difícil de escrever.
• As tabelas de hash (maio) têm melhor desempenho em tamanhos pequenos. Isso importa muito porque uma fração significativa do trabalho lida apenas com grandes conjuntos de dados; na prática, muita coisa funciona com apenas dezenas ou centenas de chaves, e não milhões. O desempenho em pequena escala é muito importante e você não pode usar a análise assintótica para descobrir o que há de melhor lá; você precisa realmente implementar e medir.

Mais fácil de gravar / manter, e um vencedor de desempenho em casos de uso típicos? Inscreva-me, por favor!