Skip to main content
4 de 4
adicionou 206 caracteres ao conteúdo
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 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.

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