Skip to main content
1 de 4
hkotsubo
  • 66,9mil
  • 25
  • 87
  • 170

Conforme visto na pergunta que você citou, o que as tabelas de hash fazem é calcular o valor do hash de cada chave, para que saibam em qual posição da tabela o elemento ficará.

No caso do Python, objetos podem implementar o método __hash__ para retornar o seu respectivo hashcode. E de acordo com a documentação, um objeto é hashable se "o valor do seu hash não muda durante o seu tempo de vida, e pode ser comparado com outros objetos" (em suma, além do método __hash__, ele precisa implementar também o __eq__).

A documentação também cita que objetos que são considerados iguais devem retornar o mesmo valor do hash. Então geralmente o que os tipos imutáveis fazem é retornar o hash baseado no seu valor. E como eles são imutáveis, o valor não muda, e portanto o hash também não.

Isso é importante porque se o hash ficar mudando, o objeto não servirá mais como chaves de dicionários, já que eles usam o valor do hash internamente, para fazer o lookup. Veja este exemplo:

class Teste:
    def __init__(self, value):
        self.value = value

    def __hash__(self):
        # implementação simples, retorna o hash do valor
        h = hash(self.value)
        print(f'calculando hash de {self.value}={h}')
        return h

    def __eq__(self, other):
        return self.value == other.value

    def __repr__(self):
        return f'Test({self.value})'

t1 = Teste(1)
t2 = Teste('xyz')
d = {}
print('adicionar 1')
d[t1] = 'abc'

print('adicionar xyz')
d[t2] = 2

print(d) # {Test(1): 'abc', Test(xyz): 2}
print('acessando uma chave')
print(d[t1]) # abc
# mesmo sendo outro objeto, se o hash é o mesmo, ele encontra
print(d[Teste(1)]) # abc

Criei uma classe Teste que é hashable (implementa __hash__ e __eq__, e instâncias iguais sempre retornam o mesmo hash). Usei instâncias dessa classe como chaves de um dicionário, e veja como o método __hash__ é chamado, tanto para setar um valor quanto para recuperá-lo. Repare também na última linha, que mesmo sendo outra instância, ele encontra o mesmo valor, já que o valor do hash retornado é o mesmo.

A saída é:

adicionar 1
calculando hash de 1=1
adicionar xyz
calculando hash de xyz=2899992705165252900
{Test(1): 'abc', Test(xyz): 2}
acessando uma chave
calculando hash de 1=1
abc
calculando hash de 1=1
abc

No caso da string "xyz", o hash pode variar a cada execução do Python, conforme explicado aqui - mas ao longo do mesmo processo, ele permanece o mesmo (aqui também explica isso).

Agora, imagine que o hash não seja constante, e mude a cada execução. O que aconteceria?

from random import randint

class Teste:
    def __init__(self, value):
        self.value = value

    def __hash__(self):
        # implementação ERRADA, hash muda toda hora
        h = randint(1, 10)
        print(f'calculando hash de {self.value}={h}')
        return h

    def __eq__(self, other):
        return self.value == other.value

    def __repr__(self):
        return f'Test({self.value})'

t1 = Teste(1)
d = {}
print('adicionar 1')
d[t1] = 'abc'

print(d) # {Test(1): 'abc', Test(xyz): 2}
print('acessando uma chave')
print(d[t1]) # ERRO

Como eu usei randint, o valor do hash mudará toda hora. Fazendo um teste, a saída foi:

adicionar 1
calculando hash de 1=3
{Test(1): 'abc'}
acessando uma chave
calculando hash de 1=6

E logo depois, na linha que tenta acessar d[t1], ocorre o erro:

KeyError: Test(1)

Ou seja, como o hash retornado mudou, ele não consegue mais acessar o valor que adicionei anteriormente (pois ele usou o hash que foi retornado naquele momento).

Por isso que objetos mutáveis não servem como chaves de um dicionário: se o objeto muda seu valor, então o hash dele mudaria (já que __hash__ e __eq__ devem "andar juntos" - objetos iguais têm o mesmo valor de hash). E se o hash muda, não dá para encontrar o valor correspondente, já que o valor do hash é fundamental para encontrá-lo.


Isso é comum a todas as linguagens, já que tabelas de hash é um conceito mais geral, e o que muda é a implementação.

hkotsubo
  • 66,9mil
  • 25
  • 87
  • 170