Mapy i słowniki

Słowniki i mapy w MicroPython wykorzystują techniki zwane adresowaniem otwartym oraz sondowaniem liniowym. Ten rozdział szczegółowo opisuje obie te metody.

Adresowanie otwarte

Adresowanie otwarte jest używane do rozwiązywania kolizji. Kolizje są bardzo częstym zjawiskiem i występują, gdy dwa elementy zostają zahaszowane do tego samego slotu lub miejsca. Na przykład, dla konfiguracji haszowania takiej jak ta:

Jeśli pojawi się żądanie zapełnienia slotu 0 wartością 70, to ponieważ slot 0 nie jest pusty, adresowanie otwarte znajduje następny dostępny slot w słowniku, aby obsłużyć to żądanie. To sekwencyjne wyszukiwanie alternatywnej lokalizacji nazywane jest sondowaniem. Istnieje kilka algorytmów sondowania sekwencyjnego, ale MicroPython używa sondowania liniowego, które opisano w następnej sekcji.

Sondowanie liniowe

Sondowanie liniowe jest jedną z metod znajdowania dostępnego adresu lub slotu w słowniku. W MicroPython jest ono używane wraz z adresowaniem otwartym. Aby obsłużyć opisane powyżej żądanie, w przeciwieństwie do innych algorytmów sondowania, sondowanie liniowe zakłada stały odstęp 1 pomiędzy kolejnymi sondowaniami. Żądanie zostanie zatem obsłużone poprzez umieszczenie elementu w następnym wolnym slocie, którym w naszym przykładzie jest slot 4:

Te same metody, tj. adresowanie otwarte i sondowanie liniowe, są używane do wyszukiwania elementu w słowniku. Załóżmy, że chcemy wyszukać element danych 33. Obliczona wartość haszująca wyniesie 2. Sprawdzenie slotu 2 ujawnia 33. W tym momencie zwracamy True. Wyszukiwanie 70 przebiega zupełnie inaczej, ponieważ w chwili wstawiania doszło do kolizji. Dlatego obliczona wartość haszująca wynosi 0, gdzie aktualnie przechowywane jest 44. Zamiast po prostu zwrócić False, wykonujemy wyszukiwanie sekwencyjne, zaczynając od punktu 1, aż element 70 zostanie znaleziony lub natrafimy na wolny slot. Jest to ogólny sposób wykonywania wyszukiwań w haszach:

// 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;
}