Maps en dictionaries

MicroPython-dictionaries en -maps gebruiken technieken die open addressing en linear probing worden genoemd. Dit hoofdstuk beschrijft beide methoden.

Open addressing

Open addressing wordt gebruikt om botsingen op te lossen. Botsingen komen heel vaak voor en treden op wanneer twee items toevallig naar dezelfde slot of locatie hashen. Bijvoorbeeld, gegeven een hash-opzet als deze:

Als er een verzoek is om slot 0 te vullen met 70, en slot 0 is niet leeg, dan vindt open addressing de volgende beschikbare slot in de dictionary om dit verzoek af te handelen. Deze sequentiële zoektocht naar een alternatieve locatie wordt probing genoemd. Er zijn verschillende sequentiële probing-algoritmen, maar MicroPython gebruikt linear probing, dat in het volgende gedeelte wordt beschreven.

Linear probing

Linear probing is een van de methoden om een beschikbaar adres of slot in een dictionary te vinden. In MicroPython wordt het gebruikt in combinatie met open addressing. Om het hierboven beschreven verzoek af te handelen, gaat linear probing, in tegenstelling tot andere probing-algoritmen, uit van een vast interval van 1 tussen probes. Het verzoek wordt daarom afgehandeld door het item in de volgende vrije slot te plaatsen, wat in ons voorbeeld slot 4 is:

Dezelfde methoden, namelijk open addressing en linear probing, worden gebruikt om naar een item in een dictionary te zoeken. Stel dat we naar het data-item 33 willen zoeken. De berekende hash-waarde is 2. Als we naar slot 2 kijken, vinden we 33. Op dit punt retourneren we True. Zoeken naar 70 verloopt heel anders, omdat er bij het invoegen een botsing was. De berekende hash-waarde is daarom 0, dat momenteel 44 bevat. In plaats van simpelweg False te retourneren, voeren we een sequentiële zoektocht uit die begint bij punt 1 totdat het item 70 is gevonden of we een vrije slot tegenkomen. Dit is de algemene manier om opzoekingen in hashes uit te voeren:

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