Kartat ja sanakirjat

MicroPythonin sanakirjat ja kartat käyttävät tekniikoita nimeltä avoin osoitteenmuodostus (open addressing) ja lineaarinen luotaus (linear probing). Tämä luku kertoo yksityiskohtaisesti molemmista menetelmistä.

Avoin osoitteenmuodostus

Avointa osoitteenmuodostusta käytetään törmäysten ratkaisemiseen. Törmäykset ovat hyvin yleisiä ja tapahtuvat, kun kaksi alkiota sattuu hajautumaan samaan paikkaan tai sijaintiin. Esimerkiksi annettuna tällainen hajautusasetelma:

Jos esitetään pyyntö täyttää paikka 0 arvolla 70, koska paikka 0 ei ole tyhjä, avoin osoitteenmuodostus etsii sanakirjasta seuraavan vapaan paikan tämän pyynnön palvelemiseksi. Tätä peräkkäistä vaihtoehtoisen sijainnin etsintää kutsutaan luotaukseksi. On useita peräkkäisluotausalgoritmeja, mutta MicroPython käyttää lineaarista luotausta, jota kuvataan seuraavassa osiossa.

Lineaarinen luotaus

Lineaarinen luotaus on yksi menetelmistä vapaan osoitteen tai paikan löytämiseksi sanakirjassa. MicroPythonissa sitä käytetään avoimen osoitteenmuodostuksen kanssa. Yllä kuvatun pyynnön palvelemiseksi lineaarinen luotaus, toisin kuin muut luotausalgoritmit, olettaa kiinteän 1-välin luotausten välillä. Pyyntö palvellaan siten sijoittamalla alkio seuraavaan vapaaseen paikkaan, joka on esimerkissämme paikka 4:

Samoja menetelmiä, eli avointa osoitteenmuodostusta ja lineaarista luotausta, käytetään alkion etsimiseen sanakirjasta. Oletetaan, että haluamme etsiä data-alkiota 33. Laskettu hajautusarvo on 2. Paikan 2 tarkastelu paljastaa 33. Tässä vaiheessa palautamme True. Arvon 70 etsiminen on melko erilaista, koska lisäyshetkellä tapahtui törmäys. Siksi laskettu hajautusarvo on 0, joka pitää tällä hetkellä sisällään arvon 44. Sen sijaan, että yksinkertaisesti palauttaisimme False, suoritamme peräkkäisen haun pisteestä 1 alkaen, kunnes alkio 70 löytyy tai kohtaamme vapaan paikan. Tämä on yleinen tapa suorittaa hakuja hajautustauluissa:

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