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.