Maps und Dictionaries

MicroPython-Dictionaries und -Maps verwenden Techniken namens Open Addressing und lineares Sondieren. Dieses Kapitel beschreibt beide Methoden im Detail.

Open Addressing

Open Addressing wird zur Auflösung von Kollisionen verwendet. Kollisionen kommen sehr häufig vor und treten auf, wenn zwei Elemente zufällig auf denselben Slot oder dieselbe Position gehasht werden. Nehmen wir zum Beispiel eine Hash-Einrichtung wie diese an:

Wenn die Anforderung besteht, den Slot 0 mit 70 zu füllen, sucht Open Addressing den nächsten verfügbaren Slot im Dictionary, um diese Anforderung zu bedienen, da der Slot 0 nicht leer ist. Diese sequentielle Suche nach einer alternativen Position wird als Sondieren bezeichnet. Es gibt mehrere Algorithmen für das sequentielle Sondieren, aber MicroPython verwendet das lineare Sondieren, das im nächsten Abschnitt beschrieben wird.

Lineares Sondieren

Lineares Sondieren ist eine der Methoden, um eine verfügbare Adresse oder einen verfügbaren Slot in einem Dictionary zu finden. In MicroPython wird es zusammen mit Open Addressing verwendet. Um die oben beschriebene Anforderung zu bedienen, geht das lineare Sondieren im Gegensatz zu anderen Sondierungsalgorithmen von einem festen Abstand von 1 zwischen den Sondierungen aus. Die Anforderung wird daher bedient, indem das Element in den nächsten freien Slot eingefügt wird, der in unserem Beispiel der Slot 4 ist:

Dieselben Methoden, d. h. Open Addressing und lineares Sondieren, werden verwendet, um nach einem Element in einem Dictionary zu suchen. Angenommen, wir möchten nach dem Datenelement 33 suchen. Der berechnete Hash-Wert ist 2. Ein Blick auf Slot 2 zeigt 33. An diesem Punkt geben wir True zurück. Die Suche nach 70 verläuft ganz anders, da es zum Zeitpunkt des Einfügens eine Kollision gab. Daher ist der berechnete Hash-Wert 0, der derzeit 44 enthält. Anstatt einfach False zurückzugeben, führen wir eine sequentielle Suche beginnend bei Punkt 1 durch, bis das Element 70 gefunden wird oder wir auf einen freien Slot stoßen. Dies ist die allgemeine Vorgehensweise zum Durchführen von Suchvorgängen in Hashes:

// not yet found, keep searching in this table
pos = (pos + 1) % set->alloc;

if (pos == start_pos) {
    // search got back to starting position, so index is not in table
    if (lookup_kind & MP_MAP_LOOKUP_ADD_IF_NOT_FOUND) {
        if (avail_slot != NULL) {
            // there was an available slot, so use that
            set->used++;
            *avail_slot = index;
            return index;
        } else {
            // not enough room in table, rehash it
            mp_set_rehash(set);
            // restart the search for the new element
            start_pos = pos = hash % set->alloc;
        }
    }
} else {
     return MP_OBJ_NULL;
}