Parmi Tuple et List, pourquoi seul le premier peut-il être utilisé comme clé du dictionnaire ?

Beaucoup de Python débutants se posent souvent cette question, pourquoi Python a-t-il deux types : tuple (tuple) et liste (list) ? Pourquoi le tuple peut-il être utilisé comme clé d'un dictionnaire, mais pas la liste ? Pour comprendre ce problème, vous devez d'abord comprendre comment fonctionne le dictionnaire Python.

1. Comment fonctionne le dictionnaire Python

En Python, les dictionnaires ne sont que du "Mappage", mapper la clé en valeur :

# Vous pouvez obtenir une valeur pour une clé spécifique

value = d[key]

Afin d'implémenter cette fonction, Python doit Cela peut être fait, étant donné une clé, pour trouver quelle valeur correspond à cette clé. Considérons d'abord une implémentation relativement simple. Stockez toutes les paires clé-valeur dans une liste. Chaque fois que cela est nécessaire, parcourez la liste et utilisez la clé pour faire correspondre la clé de la paire clé-valeur. Si elles sont égales, obtenez la valeur. Cependant, cette implémentation devient inefficace lorsque la quantité de données est importante. La complexité de son algorithme est O(n), où n est le nombre de paires clé-valeur stockées. (Pour le principe de fonctionnement spécifique de la table de hachage, vous pouvez vous référer à mon article.

À cette fin, Python utilise la méthode hash (hash) pour l'implémenter, exigeant que chaque objet stocké dans le dictionnaire soit Implémentez la fonction de hachage.Cette fonction peut générer une valeur int, appelée valeur de hachage, Grâce à cette valeur int, vous pouvez déterminer rapidement la position de l'objet dans le dictionnaire. Cependant, en raison de l'existence d'une collision de hachage, il peut y avoir deux objets. . La valeur de hachage est la même, donc lors du processus de recherche dans le dictionnaire, la valeur de hachage doit être comparée et la valeur de value doit être comparée

Le processus général de cette requête est le suivant :

def lookup(d, key):

Le processus de requête dans le dictionnaire est résumé en trois étapes suivantes :

1. Calculez la clé sous forme de valeur de hachage via la fonction de hachage .

2. Déterminez une position via la valeur de hachage. Cette position est un tableau qui stocke

éléments susceptibles d'être en conflit (appelés « buckets » à de nombreux endroits). Chaque élément de

est une paire clé-valeur, idéalement, il n'y a qu'un seul élément dans ce tableau.

3. Parcourez le tableau, trouvez la clé cible, et renvoie la valeur correspondante.

h = hash(key)                  # step 1
    cl = d.data[h]                 # step 2
    for pair in cl:                # step 3
        if key == pair[0]:
            return pair[1]
    else:
        raise KeyError, "Key %s not found." % key

Pour que ce processus de recherche fonctionne correctement, la fonction de hachage doit remplir la condition : si deux clés produisent des valeurs de hachage différentes, alors les deux objets clés ne sont pas égal, c'est-à-dire

pour tout i1, i2, si hash(i1) != hash(i2), alors i1 != i2

Sinon, la valeur de hachage est différente mais l'objet est le même, alors le même objet produit une valeur de hachage différente. Lors de la recherche, vous entrerez dans le mauvais compartiment (étape 2) et vous ne trouverez jamais la valeur que vous recherchez dans le mauvais compartiment

Dans. De plus, pour maintenir une efficacité de recherche élevée dans le dictionnaire, vous devez également vous assurer que : Si deux clés produisent la même valeur de hachage, alors elles sont égales

pour tous les i1, i2, si hash(i1) == hash (i2), alors i1 == i2

Le but de ceci est d'essayer de garantir que chaque compartiment de hachage n'a qu'un seul élément. Pourquoi est-ce la fonction de hachage suivante :

return. 1

Cette fonction de hachage satisfait à la première condition dont nous avons parlé plus haut : si les valeurs de hachage des deux clés sont différentes, alors les deux objets clés ne sont pas les mêmes. Étant donné que la valeur de hachage générée par tous les objets est 1, aucune clé ne peut générer différentes valeurs de hachage et il n'y a pas de situation insatisfaisante. Mais l’inconvénient est que, comme toutes les valeurs de hachage sont identiques, tous les objets sont affectés au même endroit. Lors de la recherche, à la troisième étape, l'efficacité du parcours devient O(n).

La fonction de hachage doit garantir que tous les éléments sont répartis uniformément dans chaque compartiment. La situation idéale est que chaque élément n'est qu'un seul. un poste.

Les deux principes ci-dessus, le premier garantit que vous pouvez obtenir les éléments que vous recherchez dans le dictionnaire, et le second garantit l'efficacité des requêtes.

2. Exigences clés du dictionnaire

Après la discussion ci-dessus, nous devrions comprendre Python Pourquoi y a-t-il telles exigences pour les clés de dictionnaire :

Pour être utilisé comme clé de dictionnaire, l'objet doit prendre en charge la fonction de hachage (c'est-à-dire __hash__), la comparaison d'égalité (__eq__ ou __cmp__) et répondre aux exigences dont nous avons discuté ci-dessus.

3. Pourquoi List ne peut pas être utilisé comme clé

Quant à cette question, la réponse la plus directe est : list ne prend pas en charge la méthode __hash__, alors pourquoi ?

Pour la fonction de hachage de list, nous pouvons avoir les deux façons suivantes de l'implémenter :

La première est basée sur l'identifiant. Cela satisfait à la condition - "Si les valeurs de hachage sont différentes, alors bien sûr leurs identifiants sont différents." Cependant, étant donné que les listes sont généralement utilisées comme conteneurs, le hachage basé sur l'ID peut conduire aux deux situations suivantes :

用相同的list作为key去字典中找某个元素可能会得到不同的结果，因为是基于id hash的，所以即使他们的内容相同，字典依然将他们作为不同的元素对待。创建一个一模一样的list用字典查找永远会得到一个KeyError。

第二种，基于内容。tuple就是这样做的，但是要注意一点，tuple是不可以修改的，但list是可以修改的。当list修改之后，你就永远别想再从字典中拿回来了。见下面的代码。  

>>> l = [1, 2]
>>> d = {}
>>> d[l] = 42
>>> l.append(3)
>>> d[l] # 原来的hash值是基于[1, 2]hash的，
         # 现在是基于[1, 2, 3]，所以找不到
Traceback (most recent call last):
  File "<interactive input>", line 1, in ?
KeyError: [1, 2, 3]
>>> d[[1, 2]] # 基于hash [1, 2]
              # 但是遍历的时候找不到key相等的键值对
              #（因为字典里的key变成了[1, 2, 3]
Traceback (most recent call last):
  File "<interactive input>", line 1, in ?
KeyError: [1, 2]

   

鉴于两种实现的方式都存在一定的副作用，所以Python规定：

内置的list不能作为字典的key.

但tuple是不可变，所以tuple可以作为字典的key。

（2018年1月2日更新，上面我说tuple不可变可以作为字典的key，这句话并不是完全正确的。tuple只是相对不可改变的，如果tuple中有元素是可变对象，那么虽然tuple不可改变，那么其中元素所指向的对象是可变的，所以同样会出现上面“list不能作为字典的key”这个问题，即含有可变对象的tuple也不能作为字典的key，举个例子就很好懂了。）

In [11]: li = [1,2,] 
In [12]: d = dict() 
In [13]: t2 = (1,2,)
In [14]: t3 = (1,2,li,) 
In [15]: d[li] = 1
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-15-cc334e53316a> in <module>()
----> 1 d[li] = 1
 
TypeError: unhashable type: &#39;list&#39;
 
In [16]: d[t2] = 2
 
In [17]: d[t3] = 3
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-17-c9021fe91ba8> in <module>()
----> 1 d[t3] = 3
 
TypeError: unhashable type: &#39;list&#39;

   

4.自定义的类型作为字典的Key

用户自定义的类型就可以作为key了，默认的hash(object)是 id(object), 默认的cmp(object1, object2)是cmp(id(object1), id(object2))，同样是可以修改的对象，为什么这里就没有上面说的问题呢？

一般来说，在映射中比较常见的需求是用一个object替换掉原来的，所以id比内容更重要，就可以基于id来hash如果内容重要的话，自定义的类型可以通过覆盖__hash__函数和__cmp__函数或__eq__函数来实现

总结

值得注意的是：将对象和一个value关联起来，更好的做法是将value设置为对象的一个属性。

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!