Por que um dicionário Python pode ter várias chaves com o mesmo hash?

Estou tentando entender a hashfunção Python nos bastidores. Criei uma classe personalizada em que todas as instâncias retornam o mesmo valor de hash.

class C:
    def __hash__(self):
        return 42

Eu apenas presumi que apenas uma instância da classe acima pode estar em a dicta qualquer momento, mas na verdade a dictpode ter vários elementos com o mesmo hash.

c, d = C(), C()
x = {c: 'c', d: 'd'}
print(x)
# {<__main__.C object at 0x7f0824087b80>: 'c', <__main__.C object at 0x7f0823ae2d60>: 'd'}
# note that the dict has 2 elements

Eu experimentei um pouco mais e descobri que se eu substituir o __eq__método de forma que todas as instâncias da classe sejam comparadas iguais, então o dictúnico permite uma instância.

class D:
    def __hash__(self):
        return 42
    def __eq__(self, other):
        return True

p, q = D(), D()
y = {p: 'p', q: 'q'}
print(y)
# {<__main__.D object at 0x7f0823a9af40>: 'q'}
# note that the dict only has 1 element

Portanto, estou curioso para saber como um dictpode ter vários elementos com o mesmo hash.

Para obter uma descrição detalhada de como o hashing do Python funciona, veja minha resposta para Por que o retorno antecipado é mais lento do que os outros?

Basicamente, ele usa o hash para escolher um slot na mesa. Se houver um valor no slot e o hash corresponder, ele compara os itens para ver se eles são iguais.

Se o hash não corresponder ou os itens não forem iguais, ele tenta outro slot. Há uma fórmula para escolher isso (que descrevo na resposta referenciada), e isso gradualmente puxa as partes não utilizadas do valor hash; mas, depois de usá-los todos, ele acabará por abrir caminho em todos os slots da tabela de hash. Isso garante que eventualmente encontraremos um item correspondente ou um espaço vazio. Quando a pesquisa encontra um slot vazio, ela insere o valor ou desiste (dependendo se estamos adicionando ou obtendo um valor).

O importante a observar é que não há listas ou depósitos: há apenas uma tabela hash com um determinado número de slots, e cada hash é usado para gerar uma sequência de slots candidatos.

Aqui está tudo sobre os dictos do Python que fui capaz de reunir (provavelmente mais do que qualquer um gostaria de saber; mas a resposta é abrangente). Um grito para Duncan por apontar que os dictos Python usam slots e me conduzem por esta toca do coelho.

• Dicionários Python são implementados como tabelas hash .
• As tabelas de hash devem permitir colisões de hash, ou seja, mesmo se duas chaves tiverem 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 de forma inequívoca.
• Python dict usa endereçamento aberto para resolver colisões de hash (explicado abaixo) (veja dictobject.c: 296-297 ).
• A tabela hash do Python é apenas um bloco contínuo de memória (como uma espécie de array, então você pode O(1)pesquisar 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 -. Isso é implementado como uma estrutura C (ver dictobject.h: 51-56 )

• A figura abaixo é uma representação lógica de uma tabela hash Python. Na figura abaixo, 0, 1, ..., i, ... à esquerda são os índices dos slots na tabela 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 dicionário é inicializado, ele começa com 8 slots . (ver dictobjeto.h: 49 )

• Ao adicionar entradas à tabela, começamos com algum slot, ique é baseado no hash da chave. CPython usa inicial i = hash(key) & mask. Onde mask = PyDictMINSIZE - 1, mas isso não é realmente importante). Observe que o slot inicial, i, que é verificado depende do hash da chave.
• Se esse slot estiver vazio, a entrada é adicionada ao slot (por entrada, quero dizer, <hash|key|value> ). Mas e se esse slot estiver ocupado !? Provavelmente porque outra entrada tem o mesmo hash (colisão de hash!)
• Se o slot estiver ocupado, CPython (e até mesmo PyPy) compara o hash E a chave (por comparação, quero dizer ==comparação, não a iscomparação) da entrada no slot com a chave da entrada atual a ser inserida ( dictobject.c: 337 , 344-345 ). Se ambos forem iguais, ele pensa que a entrada já existe, desiste e segue para a próxima entrada a ser inserida. Se o hash ou a chave não corresponderem, ele iniciará a investigação .
• Sondar significa apenas pesquisar os slots por slot para encontrar um slot vazio. Tecnicamente, poderíamos ir um por um, i + 1, i + 2, ... e usar o primeiro disponível (que é a sondagem linear). Mas por razões explicadas lindamente nos comentários (ver dictobject.c: 33-126 ), CPython usa sondagem aleatória . Na sondagem aleatória, o próximo slot é escolhido 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 (ver dictobject.c: 33-126 para o algoritmo de sondagem). O importante é que os slots sejam testados até que o primeiro slot vazio seja encontrado.
• A mesma coisa acontece para pesquisas, apenas começa com o slot inicial i (onde i depende do hash da chave). Se o hash e a chave não corresponderem à entrada no slot, ele começa a sondar até encontrar um slot que corresponda. Se todos os slots estiverem esgotados, ele reporta uma falha.
• BTW, o dicionário será redimensionado se estiver dois terços cheio. Isso evita lentidão nas pesquisas. (ver dictobject.h: 64-65 )

Ai está! A implementação Python de dict verifica a igualdade de hash de duas chaves e a igualdade normal ( ==) das chaves ao inserir itens. Então, em resumo, se existem duas chaves, ae be hash(a)==hash(b), mas a!=b, em seguida, ambos podem existir harmoniosamente em um dict Python. Mas se hash(a)==hash(b) e a==b , então eles não podem estar no mesmo dict.

Como temos que testar após cada colisão de hash, um efeito colateral de muitas colisões de hash é que as pesquisas e inserções se tornarão muito lentas (como Duncan aponta nos comentários ).

Acho que a resposta curta à minha pergunta é: "Porque é assim que é implementado no código-fonte;)"

Embora seja bom saber isso (para pontos geek?), Não tenho certeza de como ele pode ser usado na vida real. Porque, a menos que você esteja tentando quebrar algo explicitamente, por que dois objetos que não são iguais teriam o mesmo hash?

Editar : a resposta abaixo é uma das maneiras possíveis de lidar com colisões de hash, mas não é assim que Python faz isso. O wiki de Python mencionado abaixo também está incorreto. A melhor fonte fornecida por @Duncan abaixo é a própria implementação: https://github.com/python/cpython/blob/master/Objects/dictobject.c Peço desculpas pela confusão.

Ele armazena uma lista (ou depósito) de elementos no hash e, em seguida, itera por meio dessa lista até encontrar a chave real nessa lista. Uma imagem diz mais do que mil palavras:

Aqui você vê John Smithe Sandra Deetanto hash para 152. Bucket 152contém os dois. Ao pesquisar, Sandra Deeele primeiro encontra a lista no intervalo 152, em seguida, percorre essa lista até que Sandra Deeseja encontrada e retorne521-6955 .

O seguinte está errado, está aqui apenas para contexto: No wiki do Python você pode encontrar (pseudo?) Código de como o Python executa a pesquisa.

Na verdade, existem várias soluções possíveis para esse problema, verifique o artigo da wikipedia para uma boa visão geral: http://en.wikipedia.org/wiki/Hash_table#Collision_resolution

As tabelas de hash, em geral, devem permitir colisões de hash! Você terá azar e duas coisas acabarão resultando na mesma coisa. Embaixo, há um conjunto de objetos em uma lista de itens que possui a mesma chave hash. Normalmente, há apenas uma coisa nessa lista, mas, neste caso, ela continuará agrupando-as na mesma. A única maneira de saber que eles são diferentes é por meio do operador de igual.

Quando isso acontece, seu desempenho piora com o tempo, e é por isso que você deseja que sua função hash seja o mais "aleatória possível".

No tópico, não vi o que exatamente o python faz com instâncias de classes definidas pelo usuário quando o colocamos em um dicionário como chaves. Vamos ler um pouco da documentação: ela declara que apenas objetos hashable podem ser usados ​​como chaves. Hashable são todas as classes internas imutáveis ​​e todas as classes definidas pelo usuário.

As classes definidas pelo usuário têm os métodos __cmp __ () e __hash __ () por padrão; com eles, todos os objetos são comparados desigualmente (exceto com eles mesmos) e x .__ hash __ () retorna um resultado derivado de id (x).

Portanto, se você tem um __hash__ constante em sua classe, mas não fornece nenhum método __cmp__ ou __eq__, então todas as suas instâncias são desiguais para o dicionário. Por outro lado, se você fornecer qualquer método __cmp__ ou __eq__, mas não fornecer __hash__, suas instâncias ainda serão desiguais em termos de dicionário.

class A(object):
    def __hash__(self):
        return 42


class B(object):
    def __eq__(self, other):
        return True


class C(A, B):
    pass


dict_a = {A(): 1, A(): 2, A(): 3}
dict_b = {B(): 1, B(): 2, B(): 3}
dict_c = {C(): 1, C(): 2, C(): 3}

print(dict_a)
print(dict_b)
print(dict_c)

Resultado

{<__main__.A object at 0x7f9672f04850>: 1, <__main__.A object at 0x7f9672f04910>: 3, <__main__.A object at 0x7f9672f048d0>: 2}
{<__main__.B object at 0x7f9672f04990>: 2, <__main__.B object at 0x7f9672f04950>: 1, <__main__.B object at 0x7f9672f049d0>: 3}
{<__main__.C object at 0x7f9672f04a10>: 3}