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 hash code. 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).
Mas se eu mudar o value
do objeto, consequentemente o seu hash code também mudará (já que o método __hash__
se baseia no valor do 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]) # abc
# mudando o value, o hash code também muda
t1.value = 2
print(d[t1]) # KeyError
Ao mudar o value
, o valor do hash code também muda, e ao tentar usar o objeto como chave, dá erro:
adicionar 1
calculando hash de 1=1
{Test(1): 'abc'}
acessando uma chave
calculando hash de 1=1
abc
calculando hash de 2=2
KeyError: Test(2)
Por isso que objetos mutáveis não são bons candidatos a chaves, pois o hash costuma ser baseado no seu valor (seguindo a regra de que objetos iguais retornam hashes iguais). E se o valor pode mudar, consequentemente o hash também muda, e aí não será mais possível localizar o respectivo valor no dicionário, já que este usa o valor do hash para tal.
Algumas linguagens permitem que objetos mutáveis sejam usados como chaves (e aí você que se vire para garantir que eles não mudarão), mas o Python optou por deixar que apenas objetos hashable possam ser usados como chaves.
Vale lembrar que uma tupla só é hashable se os seus elementos também forem:
d = {}
# tupla só contém elementos hashable
t = (1, 'abc')
d[t] = 1
# tupla contém uma lista, que não é hashable
t = (1, [2, 3])
d[t] = 2 # TypeError: unhashable type: 'list'
Isso é comum a todas as linguagens, já que tabela de hash é um conceito mais geral (Estruturas de Dados), e o que muda é a implementação. Em Python, objetos que não são hashable já dão erro logo que você tenta usá-los como chave de um dicionário. Mas Java, por exemplo, é diferente: todos os objetos possuem uma implementação padrão de hashCode
(mas que deve ser sobrescrita para que seja de fato útil). Mas a ideia geral é sempre a mesma: calcula-se um valor de hash para encontrar a posição do elemento na tabela de hash (e se esse valor pode mudar, o objeto não é um bom candidato a chave).
Mais detalhes sobre tabelas de hash podem ser vistos nesta pergunta.
random
não estava muito bom) :-)