Hărți și dicționare

Dicționarele și hărțile MicroPython folosesc tehnici numite adresare deschisă și sondare liniară. Acest capitol detaliază ambele metode.

Adresarea deschisă

Adresarea deschisă este folosită pentru a rezolva coliziunile. Coliziunile apar foarte frecvent și se produc atunci când două elemente ajung să aibă același hash, adresând aceeași locație sau același slot. De exemplu, având o configurație de hash ca aceasta:

Dacă există o cerere de a umple slotul 0 cu 70, deoarece slotul 0 nu este gol, adresarea deschisă găsește următorul slot disponibil din dicționar pentru a servi această cerere. Această căutare secvențială a unei locații alternative se numește sondare. Există mai mulți algoritmi de sondare secvențială, dar MicroPython folosește sondarea liniară, descrisă în secțiunea următoare.

Sondarea liniară

Sondarea liniară este una dintre metodele de găsire a unei adrese sau a unui slot disponibil într-un dicționar. În MicroPython, este folosită împreună cu adresarea deschisă. Pentru a servi cererea descrisă mai sus, spre deosebire de alți algoritmi de sondare, sondarea liniară presupune un interval fix de 1 între sondări. Cererea va fi deci servită prin plasarea elementului în următorul slot liber, care este slotul 4 în exemplul nostru:

Aceleași metode, adică adresarea deschisă și sondarea liniară, sunt folosite pentru a căuta un element într-un dicționar. Să presupunem că dorim să căutăm elementul de date 33. Valoarea hash calculată va fi 2. Examinarea slotului 2 dezvăluie 33. În acest punct, returnăm True. Căutarea lui 70 este destul de diferită, deoarece a existat o coliziune la momentul inserării. Prin urmare, valoarea hash calculată este 0, care în prezent conține 44. În loc să returnăm pur și simplu False, efectuăm o căutare secvențială începând din punctul 1 până când elementul 70 este găsit sau întâlnim un slot liber. Aceasta este modalitatea generală de a efectua căutări în hash-uri:

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