Mappe e dizionari

I dizionari e le mappe di MicroPython utilizzano tecniche chiamate indirizzamento aperto e scansione lineare. Questo capitolo descrive in dettaglio entrambi questi metodi.

Indirizzamento aperto

L”indirizzamento aperto viene usato per risolvere le collisioni. Le collisioni sono eventi molto comuni e si verificano quando due elementi vengono mappati con hash allo stesso slot o alla stessa posizione. Ad esempio, data una configurazione di hash come questa:

Se c’è una richiesta di riempire lo slot 0 con 70, poiché lo slot 0 non è vuoto, l’indirizzamento aperto trova il successivo slot disponibile nel dizionario per soddisfare questa richiesta. Questa ricerca sequenziale di una posizione alternativa è chiamata probing. Esistono diversi algoritmi di scansione sequenziale, ma MicroPython usa la scansione lineare descritta nella sezione successiva.

Scansione lineare

La scansione lineare è uno dei metodi per trovare un indirizzo o uno slot disponibile in un dizionario. In MicroPython viene usata con l’indirizzamento aperto. Per soddisfare la richiesta descritta sopra, a differenza di altri algoritmi di scansione, la scansione lineare presuppone un intervallo fisso di 1 tra le scansioni. La richiesta verrà quindi soddisfatta collocando l’elemento nel successivo slot libero, che nel nostro esempio è lo slot 4:

Gli stessi metodi, ovvero l’indirizzamento aperto e la scansione lineare, vengono usati per cercare un elemento in un dizionario. Supponiamo di voler cercare l’elemento dati 33. Il valore hash calcolato sarà 2. Esaminando lo slot 2 si trova 33. A questo punto restituiamo True. La ricerca di 70 è piuttosto diversa, poiché al momento dell’inserimento si era verificata una collisione. Pertanto il valore hash calcolato è 0, che attualmente contiene 44. Invece di restituire semplicemente False, eseguiamo una ricerca sequenziale a partire dal punto 1 finché non viene trovato l’elemento 70 o non incontriamo uno slot libero. Questo è il modo generale di eseguire le ricerche negli hash:

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