Por que não posso usar uma lista como uma chave de dicionário em python?

Estou um pouco confuso sobre o que pode / não pode ser usado como uma chave para um dicionário python.

dicked = {}
dicked[None] = 'foo'     # None ok
dicked[(1,3)] = 'baz'    # tuple ok
import sys
dicked[sys] = 'bar'      # wow, even a module is ok !
dicked[(1,[3])] = 'qux'  # oops, not allowed

Portanto, uma tupla é um tipo imutável, mas se eu esconder uma lista dentro dela, então não pode ser uma chave .. Eu não poderia facilmente esconder uma lista dentro de um módulo?

Eu tinha uma vaga idéia de que a chave tinha que ser "hashble", mas vou apenas admitir minha própria ignorância sobre os detalhes técnicos; Eu não sei o que realmente está acontecendo aqui. O que daria errado se você tentasse usar listas como chaves, com o hash como, digamos, sua localização na memória?

Há um bom artigo sobre o assunto no wiki do Python: Por que as listas não podem ser chaves de dicionário . Conforme explicado lá:

O que daria errado se você tentasse usar listas como chaves, com o hash como, digamos, sua localização na memória?

Isso pode ser feito sem realmente quebrar nenhum dos requisitos, mas leva a um comportamento inesperado. As listas são geralmente tratadas como se seu valor fosse derivado dos valores de seu conteúdo, por exemplo, ao verificar a (in) igualdade. Muitos - compreensivelmente - esperariam que você pudesse usar qualquer lista [1, 2]para obter a mesma chave, onde você teria que manter exatamente o mesmo objeto de lista. Mas a pesquisa por valor quebra assim que uma lista usada como chave é modificada, e a pesquisa por identidade exige que você mantenha exatamente a mesma lista - o que não é necessário para qualquer outra operação de lista comum (pelo menos nenhuma que eu consiga pensar )

Outros objetos, como módulos e object tornam muito mais importante sua identidade de objeto (quando foi a última vez que você teve dois objetos de módulo distintos chamados sys?), E são comparados por isso de qualquer maneira. Portanto, é menos surpreendente - ou mesmo esperado - que eles, quando usados ​​como chaves de ditado, comparem por identidade também nesse caso.

Por que não posso usar uma lista como uma chave de dicionário em python?

>>> d = {repr([1,2,3]): 'value'}
{'[1, 2, 3]': 'value'}

(para qualquer um que tropeçar nesta questão procurando uma maneira de contornar isso)

como explicado por outros aqui, na verdade você não pode. No entanto, você pode usar sua representação de string, se realmente quiser usar sua lista.

Acabei de descobrir que você pode transformar List em tupla e usá-la como chaves.

d = {tuple([1,2,3]): 'value'}

O problema é que as tuplas são imutáveis, e as listas não. Considere o seguinte

d = {}
li = [1,2,3]
d[li] = 5
li.append(4)

O que deve d[li]retornar? É a mesma lista? Que tal d[[1,2,3]]? Tem os mesmos valores, mas é uma lista diferente?

Em última análise, não há uma resposta satisfatória. Por exemplo, se a única chave que funciona é a chave original, então, se você não tiver nenhuma referência a essa chave, nunca poderá acessar o valor novamente. Com todas as outras chaves permitidas, você pode construir uma chave sem uma referência ao original.

Se ambas as sugestões funcionarem, você tem chaves muito diferentes que retornam o mesmo valor, o que é mais do que surpreendente. Se apenas o conteúdo original funcionar, sua chave irá rapidamente estragar, já que as listas são feitas para serem modificadas.

Aqui está uma resposta http://wiki.python.org/moin/DictionaryKeys

O que daria errado se você tentasse usar listas como chaves, com o hash como, digamos, sua localização na memória?

Procurar listas diferentes com o mesmo conteúdo produziria resultados diferentes, embora comparar listas com o mesmo conteúdo as indicasse como equivalentes.

Que tal usar um literal de lista em uma pesquisa de dicionário?

Seu awnser pode ser encontrado aqui:

Por que as listas não podem ser chaves de dicionário

Os recém-chegados ao Python frequentemente se perguntam por que, embora a linguagem inclua uma tupla e um tipo de lista, as tuplas podem ser usadas como chaves de dicionário, enquanto as listas não. Esta foi uma decisão de design deliberada e pode ser melhor explicada compreendendo primeiro como os dicionários Python funcionam.

Fonte e mais informações: http://wiki.python.org/moin/DictionaryKeys

Como as listas são mutáveis, as dictchaves (e os setmembros) precisam ser hash, e o hash de objetos mutáveis ​​é uma má ideia porque os valores de hash devem ser calculados com base nos atributos da instância.

Nesta resposta, darei alguns exemplos concretos, espero agregar valor às respostas existentes. Cada percepção se aplica aos elementos da setestrutura de dados também.

Exemplo 1 : hash de um objeto mutável onde o valor de hash é baseado em uma característica mutável do objeto.

>>> class stupidlist(list):
...     def __hash__(self):
...         return len(self)
... 
>>> stupid = stupidlist([1, 2, 3])
>>> d = {stupid: 0}
>>> stupid.append(4)
>>> stupid
[1, 2, 3, 4]
>>> d
{[1, 2, 3, 4]: 0}
>>> stupid in d
False
>>> stupid in d.keys()
False
>>> stupid in list(d.keys())
True

Após a mutação stupid, ele não pode mais ser encontrado no dicionário porque o hash mudou. Apenas uma varredura linear sobre a lista de achados de chaves do dict stupid.

Exemplo 2 : ... mas por que não apenas um valor de hash constante?

>>> class stupidlist2(list):
...     def __hash__(self):
...         return id(self)
... 
>>> stupidA = stupidlist2([1, 2, 3])
>>> stupidB = stupidlist2([1, 2, 3])
>>> 
>>> stupidA == stupidB
True
>>> stupidA in {stupidB: 0}
False

Isso também não é uma boa ideia, porque objetos iguais devem hash de forma idêntica para que você possa encontrá-los em um dictou set.

Exemplo 3 : ... ok, que tal hashes constantes em todas as instâncias ?!

>>> class stupidlist3(list):
...     def __hash__(self):
...         return 1
... 
>>> stupidC = stupidlist3([1, 2, 3])
>>> stupidD = stupidlist3([1, 2, 3])
>>> stupidE = stupidlist3([1, 2, 3, 4])
>>> 
>>> stupidC in {stupidD: 0}
True
>>> stupidC in {stupidE: 0}
False
>>> d = {stupidC: 0}
>>> stupidC.append(5)
>>> stupidC in d
True

As coisas parecem funcionar conforme o esperado, mas pense no que está acontecendo: quando todas as instâncias de sua classe produzem o mesmo valor de hash, você terá uma colisão de hash sempre que houver mais de duas instâncias como chaves em a dictou presentes em a set.

Encontrar a instância certa com my_dict[key]ou key in my_dict(ou item in my_set) precisa realizar tantas verificações de igualdade quantas forem as instâncias destupidlist3 nas chaves do dicionário (no pior caso). Nesse ponto, o objetivo do dicionário - pesquisa O (1) - foi completamente derrotado. Isso é demonstrado nas seguintes temporizações (feitas com IPython).

Alguns tempos para o exemplo 3

>>> lists_list = [[i]  for i in range(1000)]
>>> stupidlists_set = {stupidlist3([i]) for i in range(1000)}
>>> tuples_set = {(i,) for i in range(1000)}
>>> l = [999]
>>> s = stupidlist3([999])
>>> t = (999,)
>>> 
>>> %timeit l in lists_list
25.5 µs ± 442 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
>>> %timeit s in stupidlists_set
38.5 µs ± 61.2 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
>>> %timeit t in tuples_set
77.6 ns ± 1.5 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

Como você pode ver, o teste de associação em nosso stupidlists_seté ainda mais lento do que uma varredura linear no todo lists_list, enquanto você tem o tempo de pesquisa super rápido esperado (fator 500) em um conjunto sem muitas colisões de hash.

TL; DR: você pode usar tuple(yourlist)como dictchaves, porque as tuplas são imutáveis ​​e hashable.

A resposta simples à sua pergunta é que a lista de classes não implementa o método hash que é necessário para qualquer objeto que deseja ser usado como uma chave em um dicionário. No entanto, a razão pela qual o hash não é implementado da mesma maneira que é, digamos que a classe de tupla (com base no conteúdo do contêiner) é porque uma lista é mutável, portanto, a edição da lista exigiria que o hash fosse recalculado, o que pode significar que a lista em agora localizado no balde errado na tabela de hash subjacente. Observe que, como você não pode modificar uma tupla (imutável), esse problema não ocorre.

Como uma observação lateral, a implementação real da pesquisa de dictobjetos é baseada no Algoritmo D de Knuth Vol. 3, Seç. 6,4 Se você tem esse livro disponível, pode valer a pena ler; além disso, se você estiver realmente interessado, pode dar uma olhada nos comentários do desenvolvedor sobre a implementação real do dictobjeto aqui. Ele fornece detalhes sobre como funciona exatamente. Há também uma palestra python sobre a implementação de dicionários que pode ser do seu interesse. Eles passam pela definição de uma chave e o que é um hash nos primeiros minutos.

De acordo com a documentação do Python 2.7.2:

Um objeto é hashble se tiver um valor hash que nunca muda durante seu tempo de vida (precisa de um método hash ()) e pode ser comparado a outros objetos (precisa de um método eq () ou cmp ()). Objetos hashable comparados iguais devem ter o mesmo valor hash.

A hashabilidade torna um objeto utilizável como uma chave de dicionário e um membro de conjunto, porque essas estruturas de dados usam o valor de hash internamente.

Todos os objetos embutidos imutáveis ​​do Python são hashable, enquanto nenhum container mutável (como listas ou dicionários) é. Objetos que são instâncias de classes definidas pelo usuário são hashable por padrão; todos eles se comparam desiguais e seu valor de hash é seu id ().

Uma tupla é imutável no sentido de que você não pode adicionar, remover ou substituir seus elementos, mas os próprios elementos podem ser mutáveis. O valor de hash da lista depende dos valores de hash de seus elementos e, portanto, ele muda quando você altera os elementos.

Usar id's para hashes de lista implicaria que todas as listas seriam comparadas de maneira diferente, o que seria surpreendente e inconveniente.

Um dicionário é um HashMap que armazena o mapa de suas chaves, o valor convertido em uma nova chave com hash e o mapeamento de valor.

algo como (código psuedo):

{key : val}  
hash(key) = val

Se você está se perguntando quais são as opções disponíveis que podem ser usadas como chave para o seu dicionário. Então

qualquer coisa que seja hash (pode ser convertido em hash e manter o valor estático, ou seja, imutável de modo a fazer uma chave hash como indicado acima) é elegível, mas como os objetos de lista ou conjunto podem ser variados em movimento, então o hash (chave) também deve para variar apenas para estar em sincronia com sua lista ou conjunto.

Podes tentar :

hash(<your key here>)

Se funcionar bem, pode ser usado como chave para o seu dicionário ou então convertê-lo em algo hashble.

Em resumo :

1. Converta essa lista em tuple(<your list>).
2. Converta essa lista em str(<your list>).

dictas chaves precisam ser hashable. As listas são mutáveis ​​e não fornecem um método hash válido .