8

Eu sempre uso strings como chaves em dicionários, mas, estudando o tema, notei que é possível usar qualquer objeto imutável. Então, além de strings, dicionários aceitam como chaves objetos como inteiros, floats e tuples. Todos os exemplos abaixo funcionam:

d={"name":"Lucas", 1:'01', (9,10):3}
type(d) #dict

No entanto, se definirmos um dicionário usando listas como chaves, temos o erro TypeError: unhashable type: 'list'. Eu não sei bem o que é hashable, mas li nesta pergunta que tabelas hashes permitem pesquisas eficientes e, ao que me parece, dicionários são um exemplo desse tipo de implementação (isso explicaria o porquê de dicionários serem muito mais eficientes para busca que listas). Mas qual a relação com um objeto ser hashable e sua mutabilidade? A restrição de não usar objetos mutáveis como chaves de dicionário é algo específico do python ou comum a todas as linguagens? Por que dessa restrição?

1
  • 1
    Acho que vale mencionar o início desta resposta: "dizer que hashes são mais rápidos que listas encadeadas é comparar laranjas com bananas" - cada estrutura de dados possui prós e contras, e casos em que uma é mais adequada que outra. Aproveitando, atualizei minha resposta (o exemplo anterior com random não estava muito bom) :-)
    – hkotsubo
    Commented 26/03/2021 às 19:21

2 Respostas 2

4

Imagine que você tem uma lista:

lista = [1,2,3,4,5,6,7,8,9,10]

Se você quiser verificar se um elemento está presente nessa lista, o Python irá precisar percorrer elemento a elemento e comparar um a um:

if (11 in lista): #Irá comparar 11 com 1, depois 11 com 2, depois 11 com 3...

Apenas após comparar todos os elementos da lista ele pode ter a certeza que não achou o elemento que você quer. Um exemplo na vida real seria você procurar um CD de música em um álbum que não está organizado. Você precisa ir página por página até achar (ou não).

Se sua lista tivesse muitos elementos a sua busca demoraria mais.

Dicionário, por sua vez, não importando a quantidade de itens que ele contém, demora em média sempre o mesmo tempo para acessar o conteúdo de uma chave. Um paralelo com a vida real seria você procurar uma palavra em um dicionário. Como ele está organizado alfabeticamente, você sabe exatamente aonde achar a definição (Ou por exemplo se os CD's do exemplo anterior tivessem sido organizados de alguma forma).

Como ele faz isso? As chaves do dicionário precisam ser Hashable (com um neologismo poderíamos dizer Hasheáveis). Não vou entrar em detalhes sobre essa implementação, dado que a outra resposta citada na pergunta já faz isso bem. Mas basicamente o que uma função Hash faz é:

Alguma coisa -> | Função Hash | -> Inteiro (exemplo: 7036520087640895475)

Isto é, se você fornece alguma coisa para essa função, ela calcula um inteiro baseado neste conteúdo fornecido. Boas funções Hash prometem (mas não garantem) que conteúdos diferentes gerem inteiros diferentes, dentre outras características. Nem sempre isso é possível, e é justamente nesse caso em que o acesso pode ser mais demorado. Quando dois conteúdos diferentes geram o mesmo valor, diz-se que houve uma colisão.

Quando você adiciona um par chave-valor ao dicionário, basicamente o que ele faz é:

  • Calcula o hash da chave que você forneceu. Exemplo: (Chave "Azul" gerou o hash 123)
  • Armazena o valor em uma posição da memória vinculada a essa hash 123.

(Se for mais didático, ou mais fácil de entender, pode-se pensar que cada dicionário tem uma lista, e segundo o exemplo acima salva na posição 123 dessa lista. Embora a implementação verdadeira não seja bem assim pois teria muitos "espaços vazios".)

Se em uma ocasião futura você quer acessar o conteúdo de uma chave, você não precisa percorrer todos os elementos do dicionário. Você pode simplesmente calcular novamente o Hash, ir nessa posição da memória e verificar o item que está lá. Por isso o acesso (e verificar se contém) demoram tempo constante independente do tamanho do dicionário. Ele vai direto na posição da memória que o objeto está.

Mas qual a relação com um objeto ser hashable e sua mutabilidade?

O que acontece se o conteúdo desse objeto mudar? Seu hash iria mudar também, e seria impossível localizá-lo no dicionário novamente. Então apenas objetos imutáveis podem garantir uma hash para si.

A restrição de não usar objetos mutáveis como chaves de dicionário é algo específico do python ou comum a todas as linguagens?

Por definição, é algo comum a todas as linguagens. O que pode acontecer que talvez algumas linguagens façam, é utilizar como conteúdo para a hash algum ID do objeto em questão. Por exemplo um ponteiro para o objeto em específico ou algum número que defina esse objeto unicamente. Muitas linguagens permitem você definir sua própria função hash também.

Para uma outra explicação, veja esta pergunta (em inglês).

3
  • 2
    Boa resposta! Só para ser pedante, o único detalhe que eu mudaria é "demora sempre o mesmo tempo para acessar o conteúdo de uma chave", já que não existe função de hash perfeita (i.e. que evita qualquer tipo de colisão). Penso que, em média, o tempo tende a ser constante, embora isso seja mais probabilístico do que certo. Commented 26/03/2021 às 13:07
  • 1
    "Boas funções Hash prometem que conteúdos diferentes gerem inteiros diferentes" - Não, uma função de hash deve garantir que conteúdos iguais gerem sempre o mesmo valor, e conteúdos diferentes podem ou não retornar o mesmo. Claro que para ser útil, o ideal é que seja diferente e as colisões não sejam frequentes, mas elas podem existir sim (exemplo). E justamente por poder ter colisões que não demora sempre o mesmo tempo pra acessar o conteúdo de uma chave, pois o mesmo slot pode acabar tendo mais de um valor, conforme explicado aqui
    – hkotsubo
    Commented 26/03/2021 às 13:52
  • Por isso usei a palavra promete. Uma promessa pode ser cumprida, ou não. De qualquer forma, vou editar a resposta para ficar mais didático. Como esse não era o objetivo central da pergunta, acabei não focando muito nessa parte. Adicionarei também que o tempo constante de acesso é apenas no caso médio. Obrigado pelas sugestões!
    – Naslausky
    Commented 26/03/2021 às 14:09
3

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.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .