Mape i rječnici

MicroPython rječnici i mape koriste tehnike pod nazivom otvoreno adresiranje i linearno sondiranje. Ovo poglavlje detaljno opisuje obje metode.

Otvoreno adresiranje

Otvoreno adresiranje koristi se za razrješavanje kolizija. Kolizije su vrlo česta pojava i događaju se kada se dva elementa hashiraju u isti pretinac ili lokaciju. Na primjer, kod ovakve postavke hasha:

Ako postoji zahtjev za popunjavanjem pretinca 0 vrijednošću 70, budući da pretinac 0 nije prazan, otvoreno adresiranje pronalazi sljedeći dostupni pretinac u rječniku za obradu tog zahtjeva. Ova sekvencijalna pretraga za alternativnom lokacijom naziva se sondiranje. Postoji nekoliko algoritama sekvencijalnog sondiranja, ali MicroPython koristi linearno sondiranje koje je opisano u sljedećem odjeljku.

Linearno sondiranje

Linearno sondiranje jedna je od metoda za pronalaženje dostupne adrese ili pretinca u rječniku. U MicroPythonu se koristi s otvorenim adresiranjem. Za obradu gore opisanog zahtjeva, za razliku od drugih algoritama sondiranja, linearno sondiranje pretpostavlja fiksni interval od 1 između sondiranja. Zahtjev će se stoga obraditi smještanjem elementa u sljedeći slobodni pretinac, što je u našem primjeru pretinac 4:

Iste metode, tj. otvoreno adresiranje i linearno sondiranje, koriste se za pretraživanje elementa u rječniku. Pretpostavimo da želimo potražiti podatkovni element 33. Izračunata hash vrijednost bit će 2. Pogled u pretinac 2 otkriva 33. U tom trenutku vraćamo True. Pretraživanje za 70 prilično je drugačije jer je u trenutku umetanja došlo do kolizije. Stoga je izračunata hash vrijednost 0, koja trenutno drži 44. Umjesto da jednostavno vratimo False, izvodimo sekvencijalnu pretragu počevši od točke 1 dok ne pronađemo element 70 ili ne naiđemo na slobodni pretinac. Ovo je opći način izvođenja pretraživanja u hashevima:

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