¿Por qué no puedo usar una lista como clave de dictado en python? ¿Exactamente qué se puede y qué no se puede usar y por qué?

Encontré que los siguientes son todos válidos:

>>> d = {}
>>> d[None] = 'foo'
>>> d[(1, 3)] = 'baz'

Incluso un módulo se puede utilizar como clave de dictado:

>>> import sys
>>> d[sys] = 'bar'

Sin embargo, una lista no puede, y tampoco una tupla que contiene una lista:

>>> d[[2]] = 'spam'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>> d[(1, [3])] = 'qux'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

¿Por qué almacenar una lista dentro de la tupla significa que ya no puede ser una clave de dictado? Después de todo, podría “ocultar” fácilmente una lista dentro de un módulo (y de hecho, por ejemplo, sys.path ya es una lista).

Tenía una vaga idea de que la clave debe ser “hashable”, pero no tengo una comprensión detallada de lo que esto significa o por qué existe tal limitación. ¿Qué saldría mal si Python permitiera usar listas como claves, por ejemplo, usando su ubicación de memoria como hash?

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 Python permitiera usar listas como claves, por ejemplo, usando su ubicación de memoria como hash?

Causaría algún comportamiento inesperado. Las listas generalmente se tratan como si su valor se derivara de los valores de su contenido, por ejemplo, cuando se verifica la (des)igualdad. Muchos, comprensiblemente, esperarían 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 interrumpe tan pronto como se modifica una lista utilizada como clave, y la búsqueda por identidad requiere realizar un seguimiento de ese objeto de lista exacto, que no es un requisito común para trabajar con listas.

Otros objetos, como módulos y objecthaga un trato mucho más grande con su identidad de objeto de todos modos (¿cuándo fue la última vez que tuvo dos objetos de módulo distintos llamados sys?), y son comparados por eso de todos modos. Por lo tanto, es menos sorprendente, o incluso esperado, que, cuando se usan como claves de dictado, también se comparan 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 tropiece con esta pregunta buscando una forma de evitarla)

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

Una lista se puede convertir en una tupla, que se puede usar como clave de dictado: por ejemplo

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

El problema es que las tuplas son inmutables y las listas no. Considere este ejemplo:

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

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

En última instancia, no hay una respuesta satisfactoria:

• Si la única clave que funciona es la clave original, entonces se vuelve imposible acceder al valor sin conservar una referencia a la clave original (y tener acceso a ella)

• Si solo funciona una clave con el mismo contenido, la modificación de la clave cambia el funcionamiento de la búsqueda; y cualquier otro código que tenga una referencia a esa lista podría modificarla, posiblemente causando una sorpresa más adelante.

• Si ambos funcionan, entonces tiene claves muy diferentes asignadas al mismo valor, lo cual es más que un poco sorprendente.

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

¿Qué saldría mal si tratara de 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 indicaría que son equivalentes.

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

Debido a que las listas son mutables, dict llaves (y set miembros) necesitan ser hashable, y hash de objetos mutables es una mala idea porque los valores hash debería calcularse sobre la base de los atributos de la instancia.

En esta respuesta, daré algunos ejemplos concretos, con la esperanza de agregar valor a las respuestas existentes. Toda intuición se aplica a los elementos de la set estructura de datos también.

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

Esa tampoco es una buena idea porque los objetos iguales deben tener un hash idéntico de modo que pueda encontrarlos en un dict o set.

Ejemplo 3: … ok, ¿qué pasa con hashes 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 cada vez que haya más de dos instancias como claves en un dict o presente en un set.

Encontrar la instancia correcta con my_dict[key] o key in my_dict (o item in my_set) necesita realizar tantas comprobaciones de igualdad como instancias de stupidlist3 en las claves del dict (en el peor de los casos). En este punto, el propósito del diccionario (búsqueda O(1)) está completamente anulado. Esto se demuestra en los siguientes tiempos (hechos 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_set es incluso más lento que un escaneo lineal en todo el lists_listmientras tiene el tiempo de búsqueda súper rápido esperado (factor 500) en un conjunto sin muchas colisiones de hash.

TL; DR: puedes usar tuple(yourlist) como dict claves, porque las tuplas son inmutables y hashable.

La respuesta simple a su pregunta es que la lista de clases no implementa el método picadillo que se requiere para cualquier objeto que desee ser utilizado como clave en un diccionario. Sin embargo, la razón por la cual picadillo no se implementa de la misma manera que, por ejemplo, la clase de tupla (basada en el contenido del contenedor) se debe a que una lista es mutable, por lo que editar la lista requeriría que se vuelva a calcular el hash, lo que puede significar que la lista ahora está ubicada en el lugar incorrecto cubo 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 disponible para usted, podría valer la pena leerlo, además, si está realmente interesado, puede echar un vistazo a los comentarios del desarrollador sobre el implementación de dictobject aquí. Entra en gran detalle en cuanto a cómo funciona exactamente. También hay una conferencia pitón sobre la implementación de diccionarios que te pueden interesar. Pasan por la definición de una clave y qué es un hash en los primeros minutos.