Qual é a maneira correta e boa de implementar __hash __ ()?

150

Qual é a maneira correta e boa de implementar __hash__()?

Eu estou falando sobre a função que retorna um código hash que é usado para inserir objetos em tabelas de hash aka dicionários.

Como __hash__()retorna um número inteiro e é usado para "agrupar" objetos em hashtables, presumo que os valores do número inteiro retornado sejam distribuídos uniformemente para dados comuns (para minimizar colisões). Qual é uma boa prática para obter esses valores? As colisões são um problema? No meu caso, eu tenho uma classe pequena que atua como uma classe de contêiner contendo algumas entradas, algumas flutuações e uma string.

user229898
fonte

Respostas:

185

Uma maneira fácil e correta de implementar __hash__()é usar uma tupla chave. Não será tão rápido quanto um hash especializado, mas se você precisar, provavelmente deverá implementar o tipo em C.

Aqui está um exemplo do uso de uma chave para hash e igualdade:

class A:
    def __key(self):
        return (self.attr_a, self.attr_b, self.attr_c)

    def __hash__(self):
        return hash(self.__key())

    def __eq__(self, other):
        if isinstance(other, A):
            return self.__key() == other.__key()
        return NotImplemented

Além disso, a documentação de__hash__ possui mais informações, que podem ser valiosas em algumas circunstâncias particulares.

John Millikin
fonte
1
Além da pequena sobrecarga de fatorar a __keyfunção, isso é tão rápido quanto qualquer hash pode ser. Claro, se se sabe que os atributos são números inteiros e não há muitos, suponho que você possa executar um pouco mais rápido com um hash de rolagem em casa, mas provavelmente não seria tão bem distribuído. hash((self.attr_a, self.attr_b, self.attr_c))será surpreendentemente rápido (e correto ), pois a criação de pequenos tuples é especialmente otimizada, e empurra o trabalho de obter e combinar hashes para os C embutidos, o que normalmente é mais rápido que o código no nível Python.
ShadowRanger
Digamos que um objeto da classe A esteja sendo usado como chave para um dicionário e se um atributo da classe A mudar, seu valor de hash também mudará. Isso não criaria um problema?
Matrix
1
Como a resposta de @ loved.by.Jesus abaixo menciona, o método hash não deve ser definido / substituído para um objeto mutável (definido por padrão e usa id para igualdade e comparação).
Matrix
@ Miguel, eu corri para o problema exato , o que acontece é que o dicionário retorna Noneuma vez que a chave muda. A maneira como resolvi foi armazenando o ID do objeto como uma chave em vez de apenas o objeto.
Jaswant P
O @JaswantP Python, por padrão, usa a ID do objeto como a chave para qualquer objeto hash.
Matrix
22

John Millikin propôs uma solução semelhante a esta:

class A(object):

    def __init__(self, a, b, c):
        self._a = a
        self._b = b
        self._c = c

    def __eq__(self, othr):
        return (isinstance(othr, type(self))
                and (self._a, self._b, self._c) ==
                    (othr._a, othr._b, othr._c))

    def __hash__(self):
        return hash((self._a, self._b, self._c))

O problema com esta solução é que o hash(A(a, b, c)) == hash((a, b, c)). Em outras palavras, o hash colide com o da tupla de seus principais membros. Talvez isso não importe com muita frequência na prática?

Atualização: os documentos do Python agora recomendam o uso de uma tupla, como no exemplo acima. Observe que a documentação declara

A única propriedade necessária é que os objetos que comparam iguais tenham o mesmo valor de hash

Note que o oposto não é verdadeiro. Objetos que não comparam iguais podem ter o mesmo valor de hash. Essa colisão de hash não fará com que um objeto substitua outro quando usado como uma chave de ditado ou elemento de conjunto , desde que os objetos também não sejam comparáveis .

Solução desatualizada / incorreta

A documentação do Python__hash__ sugere que você combine os hashes dos subcomponentes usando algo como o XOR , o que nos dá o seguinte:

class B(object):

    def __init__(self, a, b, c):
        self._a = a
        self._b = b
        self._c = c

    def __eq__(self, othr):
        if isinstance(othr, type(self)):
            return ((self._a, self._b, self._c) ==
                    (othr._a, othr._b, othr._c))
        return NotImplemented

    def __hash__(self):
        return (hash(self._a) ^ hash(self._b) ^ hash(self._c) ^
                hash((self._a, self._b, self._c)))

Atualização: como Blckknght aponta, alterar a ordem de a, bec pode causar problemas. Eu adicionei um adicional ^ hash((self._a, self._b, self._c))para capturar a ordem dos valores que estão sendo hash. Esta final ^ hash(...)pode ser removida se os valores combinados não puderem ser reorganizados (por exemplo, se eles tiverem tipos diferentes e, portanto, o valor de _anunca será atribuído a _bou _c, etc.).

millerdev
fonte
5
Geralmente, você não deseja executar um XOR direto com os atributos, pois isso causará colisões se você alterar a ordem dos valores. Ou seja, hash(A(1, 2, 3))será igual a hash(A(3, 1, 2))(e eles vão tanto de hash igual a qualquer outra Ainstância com uma permutação de 1, 2e 3como seus valores). Se você deseja evitar que sua instância tenha o mesmo hash que uma tupla de seus argumentos, simplesmente crie um valor sentinela (como uma variável de classe ou como global) e inclua-o na tupla a ser hash: return hash ((_ sentinel , self._a, self._b, self._c))
Blckknght
1
Seu uso de isinstancepode ser problemático, pois um objeto de uma subclasse de type(self)agora pode ser igual a um objeto de type(self). Então você pode achar que a adição de um Care um Forda um set()podem resultar em apenas um objeto inserido, dependendo da ordem de inserção. Além disso, você pode ter uma situação em que a == bé verdadeiro, mas b == aé falso.
MaratC
1
Se você está subclassificando B, pode mudar isso paraisinstance(othr, B)
millerdev
7
Um pensamento: a tupla de chave poderia incluir o tipo de classe, o que impediria outras classes com o mesmo conjunto de chaves de atributos de ser mostrado para ser igual: hash((type(self), self._a, self._b, self._c)).
21915 Ben Mosher
2
Além do ponto sobre o uso em Bvez de type(self), também é considerado uma prática recomendada retornar NotImplementedao encontrar um tipo inesperado em __eq__vez de False. Isso permite que outros tipos definidos pelo usuário implementem um __eq__que conheça Be possa comparar o mesmo, se desejar.
Mark-Amery
16

Paul Larson, da Microsoft Research, estudou uma ampla variedade de funções de hash. Ele me disse aquilo

for c in some_string:
    hash = 101 * hash  +  ord(c)

funcionou surpreendentemente bem para uma ampla variedade de strings. Descobri que técnicas polinomiais semelhantes funcionam bem para calcular um hash de subcampos díspares.

George V. Reilly
fonte
8
Aparentemente Java faz isso da mesma maneira mas utilizando 31 em vez de 101
user229898
3
Qual é a lógica por trás desses números? Existe um motivo para escolher 101 ou 31?
bigblind
1
Aqui está uma explicação para multiplicadores principais: stackoverflow.com/questions/3613102/… . 101 parece funcionar particularmente bem, com base nos experimentos de Paul Larson.
George V. Reilly
4
O Python usa (hash * 1000003) XOR ord(c)para strings com multiplicação envolvente de 32 bits. [Citação ]
tylerl 14/08/13
4
Mesmo se isso for verdade, não tem utilidade prática nesse contexto, porque os tipos de string Python incorporados já fornecem um __hash__método; não precisamos rolar os nossos. A questão é como implementar __hash__para uma classe típica definida pelo usuário (com várias propriedades apontando para tipos internos ou talvez para outras classes definidas pelo usuário), que essa resposta não aborda de maneira alguma.
Mark Amery
3

Eu posso tentar responder a segunda parte da sua pergunta.

As colisões provavelmente resultarão não do próprio código de hash, mas do mapeamento do código de hash para um índice em uma coleção. Por exemplo, sua função hash pode retornar valores aleatórios de 1 a 10000, mas se sua tabela hash tiver apenas 32 entradas, você terá colisões na inserção.

Além disso, eu pensaria que as colisões seriam resolvidas internamente pela coleção, e existem muitos métodos para resolver colisões. O mais simples (e o pior) é, dada uma entrada para inserir no índice i, adicione 1 a i até encontrar um local vazio e insira nele. A recuperação funciona da mesma maneira. Isso resulta em recuperações ineficientes para algumas entradas, pois você pode ter uma entrada que requer percorrer toda a coleção para encontrar!

Outros métodos de resolução de colisão reduzem o tempo de recuperação movendo entradas na tabela de hash quando um item é inserido para espalhar as coisas. Isso aumenta o tempo de inserção, mas pressupõe que você leia mais do que insere. Também existem métodos que tentam ramificar diferentes entradas em colisão para que elas sejam agrupadas em um ponto específico.

Além disso, se você precisar redimensionar a coleção, precisará refazer tudo ou usar um método de hash dinâmico.

Em resumo, dependendo do que você estiver usando o código hash, talvez seja necessário implementar seu próprio método de resolução de colisão. Se você não os estiver armazenando em uma coleção, provavelmente poderá usar uma função de hash que apenas gera códigos de hash em um intervalo muito grande. Nesse caso, você pode garantir que seu contêiner seja maior do que precisa (quanto maior, melhor, é claro), dependendo das preocupações com a memória.

Aqui estão alguns links, se você estiver mais interessado:

hash coalescente na wikipedia

A Wikipedia também possui um resumo de vários métodos de resolução de colisões:

Além disso, " Organização e processamento de arquivos " da Tharp abrange muitos métodos de resolução de colisões extensivamente. IMO é uma ótima referência para algoritmos de hash.

Kryptic
fonte
1

Uma explicação muito boa sobre quando e como implementar a __hash__função está no site da programiz :

Apenas uma captura de tela para fornecer uma visão geral: (Retirado em 2019-12-13)

Captura de tela de https://www.programiz.com/python-programming/methods/built-in/hash 2019-12-13

Quanto à implementação pessoal do método, o site acima mencionado fornece um exemplo que corresponde à resposta do millerdev .

class Person:
def __init__(self, age, name):
    self.age = age
    self.name = name

def __eq__(self, other):
    return self.age == other.age and self.name == other.name

def __hash__(self):
    print('The hash is:')
    return hash((self.age, self.name))

person = Person(23, 'Adam')
print(hash(person))
Jesus amado
fonte
0

Depende do tamanho do valor do hash que você retorna. É uma lógica simples que, se você precisar retornar um int de 32 bits com base no hash de quatro ints de 32 bits, terá colisões.

Eu preferiria operações pouco. Como, o seguinte pseudocódigo C:

int a;
int b;
int c;
int d;
int hash = (a & 0xF000F000) | (b & 0x0F000F00) | (c & 0x00F000F0 | (d & 0x000F000F);

Esse sistema também poderia funcionar para carros alegóricos, se você simplesmente os considerasse seu valor de bit em vez de realmente representar um valor de ponto flutuante, talvez melhor.

Para cordas, tenho pouca ou nenhuma idéia.

Cachorro
fonte
Eu sei que haverá colisões. Mas não tenho idéia de como eles são tratados. Além disso, meus valores de atributo em combinação são muito escassamente distribuídos, então eu estava procurando uma solução inteligente. E de alguma forma eu esperava que houvesse uma prática recomendada em algum lugar.
User229898