¿Por qué no puedo usar una lista como clave de dictado en Python?

Estoy un poco confundido acerca de lo que se puede / no se puede usar como clave para un dictado de 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

Entonces, una tupla es un tipo inmutable, pero si oculto una lista dentro de ella, entonces no puede ser una clave ... ¿No podría ocultar fácilmente una lista dentro de un módulo?

Tenía una vaga idea de que la clave tiene que ser "modificable", pero solo voy a admitir mi propia ignorancia sobre los detalles técnicos; No sé qué está pasando realmente aquí. ¿Qué saldría mal si intentara usar listas como claves, con el hash como, digamos, su ubicación de memoria?

Hay un buen artículo sobre el tema en la wiki de Python: Por qué las listas no pueden ser claves de diccionario . Como se explica allí:

¿Qué saldría mal si intentara usar listas como claves, con el hash como, digamos, su ubicación de memoria?

Se puede hacer sin romper realmente ninguno de los requisitos, pero conduce a un comportamiento inesperado. Las listas se tratan generalmente como si su valor se derivara de los valores de su contenido, por ejemplo, cuando se verifica la (des) igualdad. Muchos esperarían, comprensiblemente, que pueda usar cualquier lista[1, 2] para obtener la misma clave, donde tendría que mantener exactamente el mismo objeto de lista. Pero la búsqueda por valor se rompe tan pronto como se modifica una lista utilizada como clave, y para la búsqueda por identidad es necesario que mantenga exactamente la misma lista, que no es necesaria para ninguna otra operación de lista común (al menos ninguna que se me ocurra ).

Otros objetos, como los módulos, objecthacen un trato mucho más importante con su identidad de objeto de todos modos (¿cuándo fue la última vez que se llamaron dos objetos de módulo distintos sys?), Y de todos modos se los compara. Por lo tanto, es menos sorprendente, o incluso esperado, que, cuando se usan como claves de dictado, también se comparen por identidad en ese caso.

¿Por qué no puedo usar una lista como clave de dictado en Python?

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

(para cualquiera que se tropiece con esta pregunta buscando una forma de evitarla)

como explicaron otros aquí, de hecho no puede. Sin embargo, puede usar su representación de cadena en su lugar si realmente desea usar su lista.

Acabo de descubrir que puede cambiar la Lista a una tupla y luego usarla como claves.

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

El problema es que las tuplas son inmutables y las listas no. Considera lo siguiente

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

¿Qué debería d[li]devolver? ¿Es la misma lista? ¿Qué tal d[[1,2,3]]? Tiene los mismos valores, pero ¿es una lista diferente?

En definitiva, no hay una respuesta satisfactoria. Por ejemplo, si la única clave que funciona es la clave original, entonces, si no tiene ninguna referencia a esa clave, nunca más podrá acceder al valor. Con cualquier otra clave permitida, puede construir una clave sin una referencia al original.

Si ambas sugerencias funcionan, entonces tiene claves muy diferentes que devuelven el mismo valor, lo cual es más que sorprendente. Si solo funciona el contenido original, la clave se estropeará rápidamente, ya que las listas están hechas para ser modificadas.

Aquí hay una respuesta http://wiki.python.org/moin/DictionaryKeys

¿Qué saldría mal si intentara usar listas como claves, con el hash como, digamos, su ubicación de memoria?

Buscar diferentes listas con el mismo contenido produciría resultados diferentes, aunque comparar listas con el mismo contenido las indicaría como equivalentes.

¿Qué pasa con el uso de un literal de lista en una búsqueda de diccionario?

Su awnser se puede encontrar aquí:

Por qué las listas no pueden ser claves de diccionario

Los recién llegados a Python a menudo se preguntan por qué, si bien el lenguaje incluye tanto una tupla como un tipo de lista, las tuplas se pueden usar como claves de diccionario, mientras que las listas no. Esta fue una decisión de diseño deliberada y se puede explicar mejor si primero se comprende cómo funcionan los diccionarios de Python.

Fuente y más información: http://wiki.python.org/moin/DictionaryKeys

Debido a que las listas son mutables, las dictclaves (y los setmiembros) deben ser hash, y el hash de objetos mutables es una mala idea porque los valores hash deben calcularse sobre la base de atributos de instancia.

En esta respuesta, daré algunos ejemplos concretos, con suerte agregando valor a las respuestas existentes. Cada conocimiento se aplica también a los elementos de la setestructura de datos.

Ejemplo 1 : hash de un objeto mutable donde el valor hash se basa en una característica mutable del 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

Después de mutar stupid, ya no se puede encontrar en el dict porque el hash cambió. Solo un escaneo lineal sobre la lista de claves del dict encuentra stupid.

Ejemplo 2 : ... pero ¿por qué no solo un valor 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

Tampoco es una buena idea porque los objetos iguales deben tener un hash idéntico de modo que pueda encontrarlos en un dicto set.

Ejemplo 3 : ... ok, ¿qué pasa con los hash constantes en todas las instancias?

>>> 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

Las cosas parecen funcionar como se esperaba, pero piense en lo que está sucediendo: cuando todas las instancias de su clase producen el mismo valor hash, tendrá una colisión hash siempre que haya más de dos instancias como claves en a dicto presentes en a set.

Encontrar la instancia correcta con my_dict[key]o key in my_dict(o item in my_set) necesita realizar tantas verificaciones de igualdad como instancias de stupidlist3en las claves del dict (en el peor de los casos). En este punto, el propósito del diccionario - búsqueda O (1) - está completamente derrotado. Esto se demuestra en los siguientes tiempos (realizados con IPython).

Algunos tiempos para el ejemplo 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 puede ver, la prueba de membresía en nuestro stupidlists_setes incluso más lenta que un escaneo lineal en su totalidad lists_list, mientras que tiene el tiempo de búsqueda súper rápido esperado (factor 500) en un conjunto sin muchas colisiones de hash.

TL; DR: se puede usar tuple(yourlist)como dictclaves, porque las tuplas son inmutables y se pueden usar con hash.

La respuesta simple a su pregunta es que la lista de clases no implementa el método hash que se requiere para cualquier objeto que desee ser utilizado como clave en un diccionario. Sin embargo, la razón por la que el hash no se implementa de la misma manera en, digamos, la clase tupla (según el contenido del contenedor) es porque una lista es mutable, por lo que editar la lista requeriría recalcular el hash, lo que puede significar que la lista en ahora ubicado en el cubo incorrecto dentro de la tabla hash subyacente. Tenga en cuenta que, dado que no puede modificar una tupla (inmutable), no se encuentra con este problema.

Como nota al margen, la implementación real de la búsqueda de dictobjects se basa en el Algoritmo D de Knuth Vol. 3, sec. 6.4. Si tiene ese libro a su disposición, puede que valga la pena leerlo; además, si está realmente interesado, puede que le guste echar un vistazo a los comentarios de los desarrolladores sobre la implementación real de dictobject aquí. Entra en gran detalle sobre cómo funciona exactamente. También hay una conferencia de Python sobre la implementación de diccionarios que puede interesarle. En los primeros minutos, se repasa la definición de una clave y lo que es un hash.

Según la documentación de Python 2.7.2:

Un objeto es hash si tiene un valor hash que nunca cambia durante su vida (necesita un método hash ()) y se puede comparar con otros objetos (necesita un método eq () o cmp ()). Los objetos hash que se comparan iguales deben tener el mismo valor hash.

Hashability hace que un objeto se pueda utilizar como clave de diccionario y miembro de un conjunto, porque estas estructuras de datos utilizan el valor hash internamente.

Todos los objetos incorporados inmutables de Python son hash, mientras que ningún contenedor mutable (como listas o diccionarios) lo es. Los objetos que son instancias de clases definidas por el usuario son hash de forma predeterminada; todos se comparan de manera desigual, y su valor hash es su id ().

Una tupla es inmutable en el sentido de que no puede agregar, eliminar o reemplazar sus elementos, pero los elementos en sí pueden ser mutables. El valor hash de la lista depende de los valores hash de sus elementos, por lo que cambia cuando cambia los elementos.

El uso de id's para hashes de listas implicaría que todas las listas se comparan de manera diferente, lo que sería sorprendente e inconveniente.

Un diccionario es un HashMap que almacena el mapa de sus claves, el valor convertido a una nueva clave hash y la asignación de valores.

algo como (código psuedo):

{key : val}  
hash(key) = val

Si se pregunta cuáles son las opciones disponibles que se pueden utilizar como clave para su diccionario. Luego

cualquier cosa que sea hash (se puede convertir en hash y mantener un valor estático, es decir, inmutable para hacer una clave hash como se indicó anteriormente) es elegible, pero como la lista o el conjunto de objetos pueden variar sobre la marcha, el hash (clave) también debería ser necesario para variar solo para estar sincronizado con su lista o conjunto.

Puedes probar :

hash(<your key here>)

Si funciona bien, se puede usar como clave para su diccionario o convertirlo en algo que pueda tener un hash.

En breve :

1. Convierte esa lista en tuple(<your list>).
2. Convierta esa lista en str(<your list>).

dictlas claves deben ser hash. Las listas son mutables y no proporcionan un método hash válido .