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

92

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.

Praveen Gollakota
fonte
3
Como você mesmo descobriu, conjuntos e dicts podem conter vários objetos com hashes iguais se os objetos não forem iguais a si mesmos. O que você está perguntando? Como funcionam as tabelas? Essa é uma questão bastante geral com muito material existente ...
@delnan Eu estava pensando mais sobre isso depois de postar a pergunta; que esse comportamento não pode ser restrito ao Python. E você está certo. Acho que devo me aprofundar na literatura geral sobre a mesa de Hash. Obrigado.
Praveen Gollakota

Respostas:

58

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.

Duncan
fonte
7
Obrigado por me apontar a direção certa sobre a implementação da tabela de hash. Li muito mais do que gostaria sobre tabelas de hash e expliquei minhas descobertas em uma resposta separada. stackoverflow.com/a/9022664/553995
Praveen Gollakota
117

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?

Praveen Gollakota
fonte
9
Isso explica como funciona o preenchimento do dicionário. Mas e se houver uma colisão de hash durante a recuperação de um par key_value. Digamos que temos 2 objetos A e B, ambos com hash de 4. Portanto, primeiro A é atribuído ao slot 4 e, em seguida, B é atribuído ao slot por meio de sondagem aleatória. O que acontece quando eu quero recuperar B. B hashes para 4, então o python primeiro verifica o slot 4, mas a chave não corresponde, portanto, não pode retornar A. Como o slot de B foi atribuído por sondagem aleatória, como B é retornado novamente no tempo O (1)?
sayantankhan
4
@ Bolt64 a sondagem aleatória não é realmente aleatória. Para os mesmos valores de chave, ele sempre segue a mesma sequência de sondagens, então eventualmente encontrará B. Os dicionários não são garantidos como O (1), se você tiver muitas colisões, eles podem levar mais tempo. Com versões mais antigas do Python, é fácil construir uma série de chaves que irão colidir e, nesse caso, as pesquisas no dicionário tornam-se O (n). Este é um vetor possível para ataques DoS, portanto, as versões mais recentes do Python modificam o hashing para tornar mais difícil fazer isso deliberadamente.
Duncan,
3
@Duncan e se A for excluído e, em seguida, fizermos uma pesquisa em B? Acho que você não exclui as entradas, mas as marca como excluídas. Isso significaria que os dictos não são adequados para inserções e exclusões contínuas ....
gen-ys
2
@ gen-ys sim, excluído e não usado, são tratados de forma diferente para pesquisa. Não utilizado interrompe a busca por uma correspondência, mas excluído não. Na inserção, os excluídos ou não usados ​​são tratados como slots vazios que podem ser usados. Inserções e exclusões contínuas são adequadas. Quando o número de slots não usados ​​(não excluídos) cair muito, a tabela hash será reconstruída da mesma maneira como se tivesse crescido muito para a tabela atual.
Duncan
1
Esta não é uma resposta muito boa sobre o ponto de colisão que Duncan tentou remediar. É uma resposta especialmente pobre à referência para implementação de sua pergunta. O ponto principal para entender isso é que, se houver uma colisão, o Python tenta novamente usando uma fórmula para calcular o próximo deslocamento na tabela hash. Na recuperação, se a chave não for a mesma, ele usa a mesma fórmula para pesquisar o próximo deslocamento. Não há nada de aleatório nisso.
Evan Carroll
20

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:

Tabela de hash

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

Rob Wouters
fonte
Obrigado pela explicação e especialmente pelo link para a entrada do wiki Python com o pseudo código!
Praveen Gollakota
2
Desculpe, mas esta resposta está simplesmente errada (assim como o artigo wiki). Python não armazena uma lista ou balde de elementos no hash: ele armazena precisamente um objeto em cada slot da tabela hash. Se o slot que ele tenta primeiro usar estiver ocupado, ele seleciona outro slot (puxando as partes não utilizadas do hash o máximo possível) e depois outro e outro. Como nenhuma tabela de hash está mais do que um terço cheia, ela deve eventualmente encontrar um slot disponível.
Duncan
@Duncan, o wiki do Python diz que é implementado dessa forma. Eu ficaria feliz em encontrar uma fonte melhor. A página wikipedia.org definitivamente não está errada, é apenas uma das soluções possíveis conforme declarado.
Rob Wouters
@Duncan Você pode explicar ... puxando as partes não utilizadas do hash o maior tempo possível? Todos os hashes no meu caso são avaliados em 42. Obrigado!
Praveen Gollakota
@PraveenGollakota Siga o link na minha resposta, que explica em detalhes sangrentos como o hash é usado. Para um hash de 42 e uma tabela com 8 slots inicialmente, apenas os 3 bits mais baixos são usados ​​para encontrar o slot número 2, mas se esse slot já for usado, os bits restantes entram em jogo. Se dois valores tiverem exatamente o mesmo hash, o primeiro vai para o primeiro slot tentado e o segundo, para o próximo slot. Se houver 1000 valores com hashes idênticos, então acabamos tentando 1000 slots antes de encontrar o valor e a pesquisa no dicionário fica muito lenta!
Duncan
4

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

Donald Miner
fonte
2

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}
checkraise
fonte