Um dicionário Python é um exemplo de tabela de hash?
187
Uma das estruturas básicas de dados no Python é o dicionário, que permite registrar "chaves" para procurar "valores" de qualquer tipo. Isso é implementado internamente como uma tabela de hash? se não, o que é?
Se você estiver interessado nos detalhes técnicos, um artigo no Beautiful Code lida com os aspectos internos da dictimplementação do Python .
Torsten Marek
Esse foi um dos meus capítulos favoritos em Beautiful Code.
DGentry 22/09/08
4
Aqui está uma palestra de Brandon Craig Rhodes discutindo como o dicionário python funciona, youtube.com/watch?v=C4Kc8xzcA68 .
Chandola
Procurei um diagrama representando um ditado por um tempo agora, que decifra a implementação na memória e no CPython. Obrigado por consultar o livro!
Chen A.
Respostas:
240
Sim, é um mapeamento de hash ou tabela de hash. Você pode ler uma descrição da implementação de dict do python, conforme escrito por Tim Peters, aqui .
É por isso que você não pode usar algo 'não lavável' como uma chave de dict, como uma lista:
>>> a ={}>>> b =['some','list']>>> hash(b)Traceback(most recent call last):File"<stdin>", line 1,in<module>TypeError: list objects are unhashable
>>> a[b]='some'Traceback(most recent call last):File"<stdin>", line 1,in<module>TypeError: list objects are unhashable
As costuras do link Tim Peters a serem quebradas, existe um link limpo lá fora?
precisa
1
@ MattAlcock: Eu atualizei o link. Às vezes (geralmente devido a alguém que deseja remover seu endereço de email em algum lugar), os arquivos da lista python são reconstruídos e os IDs dos emails são alterados, quebrando assim esses links. Os administradores do pydotorg geralmente tentam evitar isso atualmente.
Martijn Pieters
Mas o uso .keys()pode recuperar uma lista de chaves. Uma tabela de hash real não armazena chaves, apenas hashes para economizar espaço.
Deve haver mais em um dicionário Python do que uma pesquisa de tabela em hash (). Por experimentação bruta, encontrei esta colisão de hash :
>>> hash(1.1)2040142438>>> hash(4504.1)2040142438
No entanto, não quebra o dicionário:
>>> d ={1.1:'a',4504.1:'b'}>>> d[1.1]'a'>>> d[4504.1]'b'
Verificação de sanidade:
>>>for k,v in d.items():print(hash(k))20401424382040142438
Possivelmente, existe outro nível de pesquisa além do hash () que evita colisões entre as chaves do dicionário. Ou talvez dict () use um hash diferente.
(A propósito, isso no Python 2.7.10. A mesma história no Python 3.4.3 e 3.5.0 com uma colisão em hash(1.1) == hash(214748749.8).)
Portanto, colisões são inevitáveis. O conjunto S pode conter um número infinitamente grande de itens e você deseja que ele faça hash em um número que um computador possa armazenar. Toda implementação utilizável de uma tabela de hash resolve colisões, com dois dos métodos mais frequentes sendo a) endereçamento aberto eb) encadeamento. Só porque ele não utiliza um hash perfeito, não significa que não seja uma tabela de hash.
TurnipEntropy
1
As colisões ocorrerão em geral, porque existem infinitos valores possíveis de hashable e códigos de hash finitos. Mesmo uma tabela de hash teria que lidar com a colisão de alguma forma.
Yanfeng Liu
3
@YanfengLiu Eu acredito que esses são exatamente os mesmos pontos que o TurnipEntropy fez.
Bob Stein
1
No Python 3.7, parece que existem 2E20 menos 1 possível valores de hash, de fato. De -1E20 menos 1 a (+) 1E20 menos 1. Tente hash('I wandered lonely as a cloud, that drifts on high o\'er vales and hills, when all at once, I saw a crowd, a host of golden daffodils.')Isso fornece um decimal de 19 dígitos - -4037225020714749784se você é nerd o suficiente para se importar. Continue com suas próprias palavras, crianças, e o hash ainda é um número de 19 dígitos. Suponho que exista um limite no comprimento da string que você pode fazer hash no Python, mas é seguro dizer muito mais strings possíveis do que valores possíveis. E hash(False)= 0 por sinal.
Will Croxford
22
Sim. Internamente, é implementado como hash aberto com base em um polinômio primitivo sobre Z / 2 ( fonte ).
dictimplementação do Python .Respostas:
Sim, é um mapeamento de hash ou tabela de hash. Você pode ler uma descrição da implementação de dict do python, conforme escrito por Tim Peters, aqui .
É por isso que você não pode usar algo 'não lavável' como uma chave de dict, como uma lista:
Você pode ler mais sobre tabelas de hash ou verificar como elas foram implementadas em python e por que são implementadas dessa maneira .
fonte
.keys()pode recuperar uma lista de chaves. Uma tabela de hash real não armazena chaves, apenas hashes para economizar espaço.Deve haver mais em um dicionário Python do que uma pesquisa de tabela em hash (). Por experimentação bruta, encontrei esta colisão de hash :
No entanto, não quebra o dicionário:
Verificação de sanidade:
Possivelmente, existe outro nível de pesquisa além do hash () que evita colisões entre as chaves do dicionário. Ou talvez dict () use um hash diferente.
(A propósito, isso no Python 2.7.10. A mesma história no Python 3.4.3 e 3.5.0 com uma colisão em
hash(1.1) == hash(214748749.8).)fonte
hash('I wandered lonely as a cloud, that drifts on high o\'er vales and hills, when all at once, I saw a crowd, a host of golden daffodils.')Isso fornece um decimal de 19 dígitos --4037225020714749784se você é nerd o suficiente para se importar. Continue com suas próprias palavras, crianças, e o hash ainda é um número de 19 dígitos. Suponho que exista um limite no comprimento da string que você pode fazer hash no Python, mas é seguro dizer muito mais strings possíveis do que valores possíveis. Ehash(False)= 0 por sinal.Sim. Internamente, é implementado como hash aberto com base em um polinômio primitivo sobre Z / 2 ( fonte ).
fonte
Para expandir a explicação de nosklo:
fonte