Warum kann unter Tuple und List nur ersteres als Schlüssel des Wörterbuchs verwendet werden?

Viele Python-Anfänger haben oft die Frage: Warum gibt es in Python zwei Typen: Tupel (Tupel) und Liste (Liste)? Warum kann Tupel als Schlüssel eines Wörterbuchs verwendet werden, Liste jedoch nicht? Um dieses Problem zu verstehen, müssen Sie zunächst verstehen, wie das Python-Wörterbuch funktioniert.

1. So funktioniert das Python-Wörterbuch

In Python sind Wörterbücher nur „Mapping“, also Zuordnung von Schlüssel zu Wert :

# Sie können einen Wert für einen bestimmten Schlüssel erhalten

value = d[key]

Um diese Funktion zu implementieren, muss Python dies tun kann gegeben sein einen Schlüssel, um herauszufinden, welcher Wert diesem Schlüssel entspricht. Betrachten wir zunächst eine relativ einfache Implementierung. Speichern Sie bei Bedarf die Liste und verwenden Sie den Schlüssel, um den Schlüssel des Schlüssel-Wert-Paares abzugleichen. Diese Implementierung wird jedoch ineffizient, wenn die Datenmenge groß ist. Die Komplexität seines Algorithmus beträgt O(n), wobei n die Anzahl der gespeicherten Schlüssel-Wert-Paare ist. (Informationen zum spezifischen Funktionsprinzip der Hash-Tabelle finden Sie in diesem Artikel von mir.

Zu diesem Zweck verwendet Python die Hash-Methode (Hash), um sie zu implementieren, und erfordert, dass jedes im Wörterbuch gespeicherte Objekt ausgeführt wird Implementieren Sie die Hash-Funktion. Mithilfe dieses Int-Werts können Sie die Position des Objekts im Wörterbuch schnell ermitteln . Der Hash-Wert ist derselbe, daher muss beim Durchsuchen des Wörterbuchs der Hash-Wert verglichen werden und der Wert des Werts muss verglichen werden.

Der allgemeine Prozess dieser Abfrage ist wie folgt:

def lookup(d, key):

Der Wörterbuchabfrageprozess ist in den folgenden drei Schritten zusammengefasst:

1. Berechnen Sie den Schlüssel als Hashwert über die Hash-Funktion .

2. Bestimmen Sie eine Position anhand des Hashwerts. Diese Position ist ein Array, das

Elemente speichert, die in Konflikt geraten können (an vielen Stellen „Buckets“ genannt). Jedes Element von

ist ein Schlüssel-Wert-Paar, idealerweise gibt es nur 1 Element in diesem Array.

3. Durchlaufen Sie das Array, finden Sie den Zielschlüssel, und den entsprechenden Wert zurückgeben.

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

Damit dieser Suchvorgang ordnungsgemäß funktioniert, muss die Hash-Funktion die Bedingung erfüllen: Wenn zwei Schlüssel unterschiedliche Hash-Werte erzeugen, sind dies die beiden Schlüsselobjekte nicht gleich, das heißt

für alle i1, i2, wenn hash(i1) != hash(i2), dann i1 != i2

Ansonsten ist der Hashwert unterschiedlich, aber das Objekt ist derselbe, dann erzeugt dasselbe Objekt einen anderen Hash-Wert. Bei der Suche geben Sie den falschen Bucket ein (Schritt 2) und finden den gesuchten Wert nie im falschen Bucket

In Um eine hohe Sucheffizienz im Wörterbuch aufrechtzuerhalten, müssen Sie außerdem Folgendes sicherstellen: Wenn zwei Schlüssel denselben Hashwert erzeugen, dann sind sie gleich

für alle i1, i2, wenn hash(i1) == hash (i2), dann i1 == i2

Der Zweck besteht darin, sicherzustellen, dass jeder Hash-Bucket nur ein Element hat. Warum ist dies die folgende Hash-Funktion? 1

Diese Hash-Funktion erfüllt die erste Bedingung, über die wir oben gesprochen haben: Wenn die Hash-Werte der beiden Schlüssel unterschiedlich sind, dann sind die beiden Schlüsselobjekte nicht gleich. Da der von allen Objekten generierte Hash-Wert 1 ist, gibt es keinen Schlüssel, der unterschiedliche Hash-Werte generieren kann, und es gibt keine unbefriedigende Situation. Der Nachteil hierbei ist jedoch, dass alle Objekte demselben Ort zugeordnet werden, da alle Hashwerte gleich sind. Bei der Suche wird im dritten Schritt die Durchlaufeffizienz zu O(n).

Die Hash-Funktion sollte sicherstellen, dass alle Elemente gleichmäßig in jedem Bucket verteilt sind. Die ideale Situation ist, dass jedes Element nur ein Element enthält eine Stelle.

Die beiden oben genannten Prinzipien: Das erste stellt sicher, dass Sie die gesuchten Elemente aus dem Wörterbuch erhalten, und das zweite sorgt für die Effizienz der Abfrage.

2. Wörterbuchschlüsselanforderungen

Nach der obigen Diskussion sollten wir verstehen, warum es Python gibt Solche Anforderungen für Wörterbuchschlüssel: Um als Wörterbuchschlüssel verwendet zu werden, muss das Objekt die Hash-Funktion (d. h. __hash__) und den Gleichheitsvergleich (__eq__ oder __cmp__) unterstützen und die oben besprochenen Anforderungen erfüllen.

3. Warum List nicht als Schlüssel verwendet werden kann

Auf diese Frage lautet die direkteste Antwort: list unterstützt die __hash__-Methode nicht, warum also? Für die Hash-Funktion der Liste haben wir möglicherweise die folgenden zwei Möglichkeiten, sie zu implementieren:

Die erste basiert auf der ID. Damit ist die Bedingung erfüllt: „Wenn die Hashwerte unterschiedlich sind, dann sind natürlich auch ihre IDs unterschiedlich.“ Wenn man jedoch bedenkt, dass Listen im Allgemeinen als Container verwendet werden, kann Hashing basierend auf der ID zu den folgenden zwei Situationen führen:

用相同的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设置为对象的一个属性。

Das obige ist der detaillierte Inhalt vonWarum kann unter Tuple und List nur ersteres als Schlüssel des Wörterbuchs verwendet werden?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!