Um dicionário de Python é um exemplo de tabela de hash?
-
02-07-2019 - |
Pergunta
Uma das estruturas de dados básicas no Python é o dicionário, que permite gravar "chaves" para procurar "valores" de qualquer tipo. Isso é implementado internamente como uma tabela de hash? se não, o que é?
Solução
Sim, é um mapeamento de hash ou tabela de hash. Você pode ler uma descrição da implementação de dicta de Python, como escrito por Tim Peters, aqui.
É por isso que você não pode usar algo 'não hashable' como uma chave de dicta, 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
Você pode Leia mais sobre tabelas de hash ou Verifique como foi implementado em Python e Por que é implementado dessa maneira.
Outras dicas
Deve haver mais para um dicionário Python do que uma pesquisa de tabela no hash (). Por experimentação bruta, encontrei isso Hash Collision:
>>> 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))
2040142438
2040142438
Possivelmente, há outro nível de pesquisa além do hash () que evita colisões entre as chaves do dicionário. Ou talvez o dict () use um hash diferente.
(A propósito, isso em Python 2.7.10. A mesma história em Python 3.4.3 e 3.5.0 com uma colisão em hash(1.1) == hash(214748749.8)
.)
Sim. Internamente, é implementado como hash aberto com base em um polinômio primitivo sobre z/2 (fonte).
Para expandir a explicação de Nosklo:
a = {}
b = ['some', 'list']
a[b] = 'some' # this won't work
a[tuple(b)] = 'some' # this will, same as a['some', 'list']