Um dicionário de Python é um exemplo de tabela de hash?

Question

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 é?

Answer 1

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.

Answer 2

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).)

Answer 3

Sim. Internamente, é implementado como hash aberto com base em um polinômio primitivo sobre z/2 (fonte).

Answer 4

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']