So implementieren Sie ein Python-Dikt

Das Diktatobjekt in Python zeigt an, dass es sich um einen primitiven Python-Datentyp handelt, der in Form von Schlüssel-Wert-Paaren gespeichert wird. Wie der Name schon sagt, ist es sehr effizient zu finden der entsprechende Wert durch den Schlüsselnamen. Die Zeitkomplexität beträgt O(1) auf konstanter Ebene.

diktieren Sie die zugrunde liegende Implementierung (empfohlen). Lernen: Python-Video-Tutorial)

In Python2 wird die unterste Ebene des Diktats durch Hash Table implementiert und die Methode der offenen Adresse wird zum Lösen von Konflikten verwendet.

Also Die zeitliche Komplexität seiner Suche beträgt O(1).

Das Operationsimplementierungsprinzip von Dict (einschließlich Einfügen, Löschen und Pufferpool usw.)

Stellen Sie zunächst die Elementsuchstrategie des PyDictObject-Objekts vor:

Es gibt zwei Suchstrategien, nämlich Lookdict und Lookdict_string ist die spezielle Form von Lookdict bei der Suche nach PyStringObject Lookdict lautet:

(1) Suche nach dem ersten Eintrag:

a) Erhalten Sie den Eintragsindex entsprechend dem Hash-Wert

b) Wenn der Eintrag nicht verwendet wird Zustand, die Suche endet; wenn der Schlüssel, auf den der Eintrag zeigt, mit dem gesuchten Schlüssel übereinstimmt. Wenn die Schlüssel gleich sind, ist die Suche erfolgreich

c) Wenn sich der aktuelle Eintrag im Dummy-Zustand befindet, set freeslot (der freeslot kann hier als nächste sofort verfügbare Adresse zum Speichern des Eintrags zurückgegeben werden)

d) Überprüfen Sie den aktiven Eintrag. Wenn der Wert, auf den sein Schlüssel zeigt, mit dem gesuchten Wert übereinstimmt, wird der Suche ist erfolgreich

(2) Durchlaufen Sie die Elemente in der verbleibenden Erkennungskette:

a) Erhalten Sie entsprechend der verwendeten Erkennungsfunktion den nächsten zu überprüfenden Eintrag in der Erkennungskette

b) Ein nicht verwendeter Eintrag wurde erkannt, was darauf hinweist, dass die Suche fehlgeschlagen ist:

Wenn der Freeslot nicht leer ist, geben Sie den Freeslot zurück; andernfalls geben Sie den nicht verwendeten Eintrag zurück

c) Überprüfen Sie, ob der Schlüssel vorhanden ist des Eintrags ist mit der Referenz des gesuchten Schlüssels identisch. Wenn sie identisch sind, ist die Suche erfolgreich und der Eintrag wird zurückgegeben

d) Überprüfen Sie den Eintrag, ob der Wert des Schlüssels mit dem Wert von übereinstimmt der gesuchte Schlüssel. Wenn sie identisch sind, ist die Suche erfolgreich und der Eintrag

wird zurückgegeben. e) Wenn während des Durchlaufvorgangs ein Eintrag im Dummy-Status gefunden wird und Freeslot nicht festgelegt ist, setzen Sie Freeslot

Das Folgende ist: Die Strategie zum Einfügen und Löschen von Elementen des PyDictObject-Objekts:

Wenn die Suche erfolgreich ist, wird der Wert direkt ersetzt Wenn die Suche fehlschlägt, wird der Eintrag im unbenutzten Zustand oder Dummy-Zustand zurückgegeben. Legen Sie den Schlüssel, den Wert und die Hash-Werte fest und passen Sie die Größe von ma_table entsprechend den aktuell eingefügten Elementen an (die Anpassung basiert auf der Laderate, die entsprechend angepasst wird). (ob es größer als 2/3 ist); das Löschen ist ebenfalls ähnlich. Berechnen Sie zuerst den Hash-Wert und durchsuchen Sie dann den entsprechenden Eintrag. Die Suche ist erfolgreich. Löschen Sie die im Eintrag verwalteten Elemente und ändern Sie den Eintrag aus dem aktiven Status in den Dummy-Status

Im Implementierungsprozess von PyDictObject wird der Pufferpool verwendet. Wenn das PyDictObject-Objekt zerstört wird, beginnt es, gepufferte PyDictObject-Objekte zu akzeptieren Der definierte Pufferpool kann 80 akzeptieren. Wenn sich beim Erstellen eines neuen PyDictObject-Objekts eines im Pufferpool befindet, kann es direkt aus dem Pufferpool entnommen werden. Verwenden Sie

Für weitere technische Artikel zu Python , besuchen Sie bitte die Spalte Python-Tutorial, um mehr zu erfahren!

Das obige ist der detaillierte Inhalt vonSo implementieren Sie ein Python-Dikt. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!