Ist es sicher, ausgewählte Schlüssel innerhalb einer Bereichsschleife von der Karte zu entfernen?

134

Wie kann man ausgewählte Schlüssel von einer Karte entfernen? Ist es sicher, delete()mit Reichweite zu kombinieren , wie im folgenden Code?

package main

import "fmt"

type Info struct {
    value string
}

func main() {
    table := make(map[string]*Info)

    for i := 0; i < 10; i++ {
        str := fmt.Sprintf("%v", i)
        table[str] = &Info{str}
    }

    for key, value := range table {
        fmt.Printf("deleting %v=>%v\n", key, value.value)
        delete(table, key)
    }
}

https://play.golang.org/p/u1vufvEjSw

Everton
quelle

Antworten:

173

Das ist sicher! Ein ähnliches Beispiel finden Sie auch in Effective Go :

for key := range m {
    if key.expired() {
        delete(m, key)
    }
}

Und die Sprachspezifikation :

Die Iterationsreihenfolge über Karten ist nicht angegeben und es wird nicht garantiert, dass sie von einer Iteration zur nächsten gleich ist. Wenn noch nicht erreichte Karteneinträge während der Iteration entfernt werden , werden die entsprechenden Iterationswerte nicht erzeugt. Wenn Karteneinträge während der Iteration erstellt werden , kann dieser Eintrag während der Iteration erstellt oder übersprungen werden. Die Auswahl kann für jeden erstellten Eintrag und von einer Iteration zur nächsten variieren. Wenn die Karte Null ist, beträgt die Anzahl der Iterationen 0.

Sebastian
quelle
key.expired undefined (Typ Zeichenfolge hat kein Feld oder Methode abgelaufen)
4
@kristen - In dem oben beschriebenen Beispiel sollte der Schlüssel keine Zeichenfolge sein, sondern ein benutzerdefinierter Typ, der die func (a T) expired() boolSchnittstelle implementiert . Für die Zwecke dieses Beispiels könnten Sie versuchen: m := make(map[int]int) /* populate m here somehow */ for key := range (m) { if key % 2 == 0 { /* this is just some condition, such as calling expired */ delete(m, key); } }
Abanana
Sehr verwirrend.
G10guang
150

Sebastians Antwort ist korrekt, aber ich wollte wissen, warum es sicher ist, also habe ich mich ein wenig mit dem Map-Quellcode befasst . Es sieht aus wie bei einem Aufruf von delete(k, v), es setzt im Grunde nur ein Flag (sowie das Ändern des Zählwerts), anstatt den Wert tatsächlich zu löschen:

b->tophash[i] = Empty;

(Leer ist eine Konstante für den Wert 0)

Was die Karte tatsächlich zu tun scheint, ist die Zuweisung einer festgelegten Anzahl von Buckets in Abhängigkeit von der Größe der Karte, die wächst, wenn Sie Einfügungen mit der Rate von 2^B(aus diesem Quellcode ) ausführen :

byte    *buckets;     // array of 2^B Buckets. may be nil if count==0.

Es werden also fast immer mehr Buckets zugewiesen, als Sie verwenden. Wenn Sie eine rangeÜber-die-Karte ausführen, wird der tophashWert jedes Buckets darin überprüft, um festzustellen, 2^Bob er übersprungen werden kann.

Zusammenfassend ist das deleteinnerhalb von a rangesicher, da die Daten technisch immer noch vorhanden sind. Wenn es jedoch überprüft tophash, sieht es, dass es sie einfach überspringen und nicht in die von rangeIhnen ausgeführte Operation einbeziehen kann. Der Quellcode enthält sogar TODO:

 // TODO: consolidate buckets if they are mostly empty
 // can only consolidate if there are no live iterators at this size.

Dies erklärt, warum die Verwendung der delete(k,v)Funktion den Speicher nicht freigibt, sondern nur aus der Liste der Buckets entfernt, auf die Sie zugreifen dürfen. Wenn Sie den eigentlichen Speicher freigeben möchten, müssen Sie die gesamte Karte nicht erreichbar machen, damit die Speicherbereinigung aktiviert wird. Sie können dies mit einer Zeile wie tun

map = nil
Verran
quelle
2
Es hört sich also so an, als ob Sie sagen, dass es sicher ist, einen beliebigen Wert aus der Karte zu löschen, nicht nur den 'aktuellen', richtig? Und wenn es an der Zeit ist, einen Hash auszuwerten, den ich zuvor willkürlich gelöscht habe, wird er sicher übersprungen?
Flimzy
@Flimzy Das ist richtig, wie Sie auf diesem Spielplatz sehen können play.golang.org/p/FwbsghzrsO . Beachten Sie, dass wenn der von Ihnen gelöschte Index der erste im Bereich ist, dieser weiterhin angezeigt wird, da er bereits in k, v geschrieben wurde. Wenn Sie den Index jedoch auf einen anderen Wert als den ersten setzen, den der Bereich findet, werden nur zwei Schlüssel angezeigt / Wertepaare statt drei und keine Panik.
Verran
1
Ist das "macht eigentlich keinen Speicher frei" noch relevant? Ich habe versucht, diesen Kommentar in der Quelle zu finden, kann ihn aber nicht finden.
Tony
11
Wichtiger Hinweis: Denken Sie daran, dass dies nur die aktuelle Implementierung ist und sich in Zukunft ändern kann. Sie dürfen sich also nicht auf zusätzliche Eigenschaften verlassen, die möglicherweise "unterstützt" werden. Die einzigen Garantien, die Sie haben, sind die in der Spezifikation angegebenen, wie in Sebastians Antwort beschrieben . (Das heißt, das Erforschen und Erklären der Go-Interna ist sicher interessant,
lehrreich
4

Ich habe mich gefragt, ob ein Speicherverlust auftreten könnte. Also habe ich ein Testprogramm geschrieben:

package main

import (
    log "github.com/Sirupsen/logrus"
    "os/signal"
    "os"
    "math/rand"
    "time"
)

func main() {
    log.Info("=== START ===")
    defer func() { log.Info("=== DONE ===") }()

    go func() {
        m := make(map[string]string)
        for {
            k := GenerateRandStr(1024)
            m[k] = GenerateRandStr(1024*1024)

            for k2, _ := range m {
                delete(m, k2)
                break
            }
        }
    }()

    osSignals := make(chan os.Signal, 1)
    signal.Notify(osSignals, os.Interrupt)
    for {
        select {
        case <-osSignals:
            log.Info("Recieved ^C command. Exit")
            return
        }
    }
}

func GenerateRandStr(n int) string {
    rand.Seed(time.Now().UnixNano())
    const letterBytes = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
    b := make([]byte, n)
    for i := range b {
        b[i] = letterBytes[rand.Int63() % int64(len(letterBytes))]
    }
    return string(b)
}

Es sieht so aus, als würde GC den Speicher freigeben. Also ist es okay.

vitvlkv
quelle
0

Kurz gesagt, ja. Siehe vorherige Antworten.

Und auch das von hier aus :

ianlancetaylor kommentierte am 18. Februar 2015
Ich denke, der Schlüssel zum Verständnis besteht darin, zu erkennen, dass es beim Ausführen des Hauptteils einer for / range-Anweisung keine aktuelle Iteration gibt. Es gibt eine Reihe von Werten, die gesehen wurden, und eine Reihe von Werten, die nicht gesehen wurden. Während der Ausführung des Körpers wurde eines der angezeigten Schlüssel / Wert-Paare - das letzte Paar - den Variablen der Bereichsanweisung zugewiesen. Dieses Schlüssel / Wert-Paar hat nichts Besonderes, es ist nur eines von denen, die bereits während der Iteration gesehen wurden.

Die Frage, die er beantwortet, betrifft das Ändern von Kartenelementen range, die während einer Operation vorhanden sind, weshalb er die "aktuelle Iteration" erwähnt. Aber es ist auch hier relevant: Sie können Schlüssel während eines Bereichs löschen, und das bedeutet nur, dass Sie sie später im Bereich nicht mehr sehen werden (und wenn Sie sie bereits gesehen haben, ist das in Ordnung).

Larry Clapp
quelle