Pourquoi ne puis-je pas utiliser une liste comme clé dict en python?

Je suis un peu confus sur ce qui peut / ne peut pas être utilisé comme clé pour un dict 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

Donc, un tuple est un type immuable, mais si je cache une liste à l'intérieur, alors ce ne peut pas être une clé ... ne pourrais-je pas aussi facilement cacher une liste à l'intérieur d'un module?

J'avais une vague idée que la clé doit être "hachable" mais je vais juste admettre ma propre ignorance des détails techniques; Je ne sais pas ce qui se passe vraiment ici. Qu'est-ce qui ne va pas si vous essayez d'utiliser des listes comme clés, avec le hachage comme, par exemple, leur emplacement mémoire?

Il y a un bon article sur le sujet dans le wiki Python: Pourquoi les listes ne peuvent pas être des clés de dictionnaire . Comme expliqué ici:

Qu'est-ce qui ne va pas si vous essayez d'utiliser des listes comme clés, avec le hachage comme, par exemple, leur emplacement mémoire?

Cela peut être fait sans vraiment enfreindre aucune des exigences, mais cela conduit à un comportement inattendu. Les listes sont généralement traitées comme si leur valeur était dérivée des valeurs de leur contenu, par exemple lors de la vérification de l '(in) égalité. Beaucoup s'attendraient - naturellement - à ce que vous puissiez utiliser n'importe quelle liste[1, 2] pour obtenir la même clé, où vous devrez conserver exactement le même objet de liste. Mais la recherche par valeur est interrompue dès qu'une liste utilisée comme clé est modifiée, et pour la recherche par identité, vous devez conserver exactement la même liste - ce qui n'est pas nécessaire pour aucune autre opération de liste commune (du moins aucune à laquelle je puisse penser ).

D'autres objets tels que des modules objectfont de toute façon une bien plus grande part de leur identité d'objet (à quand remonte la dernière fois que vous avez appelé deux objets module distincts sys?), Et sont comparés de toute façon. Par conséquent, il est moins surprenant - ou même attendu - qu'ils, lorsqu'ils sont utilisés comme clés de dict, se comparent également par identité dans ce cas.

Pourquoi ne puis-je pas utiliser une liste comme clé dict en python?

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

(pour quiconque trébuche sur cette question à la recherche d'un moyen de la contourner)

comme expliqué par d'autres ici, en effet vous ne pouvez pas. Vous pouvez cependant utiliser sa représentation sous forme de chaîne à la place si vous souhaitez vraiment utiliser votre liste.

Vous venez de trouver que vous pouvez changer List en tuple, puis l'utiliser comme clés.

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

Le problème est que les tuples sont immuables et que les listes ne le sont pas. Considérer ce qui suit

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

Que devrait d[li]revenir? Est-ce la même liste? Et pourquoi pas d[[1,2,3]]? Il a les mêmes valeurs, mais est-ce une liste différente?

En fin de compte, il n'y a pas de réponse satisfaisante. Par exemple, si la seule clé qui fonctionne est la clé d'origine, alors si vous n'avez aucune référence à cette clé, vous ne pourrez plus jamais accéder à la valeur. Avec chaque autre clé autorisée, vous pouvez construire une clé sans référence à l'original.

Si mes deux suggestions fonctionnent, alors vous avez des clés très différentes qui renvoient la même valeur, ce qui est plus qu'un peu surprenant. Si seul le contenu d'origine fonctionne, alors votre clé va rapidement mal tourner, car les listes sont faites pour être modifiées.

Voici une réponse http://wiki.python.org/moin/DictionaryKeys

Qu'est-ce qui ne va pas si vous essayez d'utiliser des listes comme clés, avec le hachage comme, par exemple, leur emplacement mémoire?

La recherche de différentes listes avec le même contenu produirait des résultats différents, même si la comparaison de listes avec le même contenu les indiquerait comme équivalentes.

Qu'en est-il de l'utilisation d'un littéral de liste dans une recherche de dictionnaire?

Étant donné que les listes sont mutables, les dictclés (et les setmembres) doivent être hachables et le hachage d'objets mutables est une mauvaise idée car les valeurs de hachage doivent être calculées sur la base des attributs d'instance.

Dans cette réponse, je donnerai quelques exemples concrets, j'espère ajouter de la valeur en plus des réponses existantes. Chaque aperçu s'applique également aux éléments de la setstructure de données.

Exemple 1 : hachage d'un objet mutable où la valeur de hachage est basée sur une caractéristique mutable de l'objet.

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

Après la mutation stupid, il ne peut plus être trouvé dans le dict car le hachage a changé. Seul un balayage linéaire sur la liste des clés du dict est trouvé stupid.

Exemple 2 : ... mais pourquoi pas simplement une valeur de hachage 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

Ce n'est pas non plus une bonne idée car les objets égaux doivent hacher de manière identique pour que vous puissiez les trouver dans un dictou set.

Exemple 3 : ... ok, qu'en est-il des hachages constants sur toutes les instances?!

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

Les choses semblent fonctionner comme prévu, mais pensez à ce qui se passe: lorsque toutes les instances de votre classe produisent la même valeur de hachage, vous aurez une collision de hachage chaque fois qu'il y a plus de deux instances en tant que clés dans a dictou présentes dans a set.

Trouver la bonne instance avec my_dict[key]ou key in my_dict(ou item in my_set) nécessite d'effectuer autant de contrôles d'égalité qu'il y a d'instances destupidlist3 dans les clés du dict (dans le pire des cas). À ce stade, le but du dictionnaire - la recherche O (1) - est complètement vaincu. Ceci est démontré dans les timings suivants (fait avec IPython).

Quelques horaires pour l'exemple 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)

Comme vous pouvez le voir, le test d'appartenance à notre stupidlists_setest encore plus lent qu'un balayage linéaire sur l'ensemblelists_list , alors que vous avez le temps de recherche super rapide attendu (facteur 500) dans un ensemble sans beaucoup de collisions de hachage.

TL; DR: vous pouvez utiliser tuple(yourlist)comme dictclés, car les tuples sont immuables et hachables.

Votre awnser peut être trouvé ici:

Pourquoi les listes ne peuvent pas être des clés de dictionnaire

Les nouveaux arrivants en Python se demandent souvent pourquoi, alors que le langage comprend à la fois un tuple et un type de liste, les tuples sont utilisables comme clés de dictionnaire, alors que les listes ne le sont pas. Il s'agissait d'une décision de conception délibérée et peut être mieux expliquée en comprenant d'abord le fonctionnement des dictionnaires Python.

Source et plus d'informations: http://wiki.python.org/moin/DictionaryKeys

La réponse simple à votre question est que la liste de classes n'implémente pas la méthode de hachage qui est requise pour tout objet qui souhaite être utilisé comme clé dans un dictionnaire. Cependant, la raison pour laquelle le hash n'est pas implémenté de la même manière que dans la classe de tuple (basée sur le contenu du conteneur) est qu'une liste est modifiable, donc l'édition de la liste nécessiterait le recalcul du hachage, ce qui peut signifier que la liste dans maintenant situé dans le mauvais compartiment dans la table de hachage sous-jacente. Notez que puisque vous ne pouvez pas modifier un tuple (immuable), il ne rencontre pas ce problème.

En remarque, l'implémentation réelle de la recherche de dictobjects est basée sur l'algorithme D de Knuth Vol. 3, Sec. 6.4. Si vous avez ce livre à votre disposition, il pourrait être intéressant de le lire, et si vous êtes vraiment, vraiment intéressé, vous pouvez jeter un coup d'œil aux commentaires des développeurs sur l' implémentation réelle de dictobject ici. Il entre dans les moindres détails quant à son fonctionnement. Il y a aussi une conférence python sur l'implémentation de dictionnaires qui pourrait vous intéresser. Ils passent en revue la définition d'une clé et ce qu'est un hachage dans les premières minutes.

Selon la documentation Python 2.7.2:

Un objet peut être haché s'il a une valeur de hachage qui ne change jamais pendant sa durée de vie (il a besoin d'une méthode hash ()), et peut être comparé à d'autres objets (il a besoin d'une méthode eq () ou cmp ()). Les objets hachables qui se comparent égaux doivent avoir la même valeur de hachage.

Hashability rend un objet utilisable en tant que clé de dictionnaire et membre d'ensemble, car ces structures de données utilisent la valeur de hachage en interne.

Tous les objets intégrés immuables de Python sont hachables, alors qu'aucun conteneur mutable (comme les listes ou les dictionnaires) ne le sont. Les objets qui sont des instances de classes définies par l'utilisateur sont hachables par défaut; ils se comparent tous de manière inégale, et leur valeur de hachage est leur id ().

Un tuple est immuable dans le sens où vous ne pouvez pas ajouter, supprimer ou remplacer ses éléments, mais les éléments eux-mêmes peuvent être mutables. La valeur de hachage de la liste dépend des valeurs de hachage de ses éléments et change donc lorsque vous modifiez les éléments.

Utiliser des id pour les hachages de liste impliquerait que toutes les listes se comparent différemment, ce qui serait surprenant et peu pratique.

Un dictionnaire est un HashMap qui stocke la carte de vos clés, la valeur convertie en une nouvelle clé hachée et le mappage de valeurs.

quelque chose comme (code psuedo):

{key : val}  
hash(key) = val

Si vous vous demandez quelles sont les options disponibles qui peuvent être utilisées comme clé pour votre dictionnaire. ensuite

tout ce qui peut être haché (peut être converti en hachage et conserver une valeur statique, c'est-à-dire immuable afin de créer une clé hachée comme indiqué ci-dessus) est éligible, mais comme les objets de liste ou d'ensemble peuvent varier en cours de route, le hachage (clé) devrait également avoir besoin pour varier simplement pour être synchronisé avec votre liste ou votre ensemble.

Tu peux essayer :

hash(<your key here>)

Si cela fonctionne bien, il peut être utilisé comme clé pour votre dictionnaire ou bien le convertir en quelque chose de hachable.

En bref :

1. Convertissez cette liste en tuple(<your list>).
2. Convertissez cette liste en str(<your list>).

dictles clés doivent être hachables. Les listes sont mutables et ne fournissent pas de méthode de hachage valide .