Mappar och ordböcker

MicroPythons ordböcker och mappar använder tekniker som kallas öppen adressering och linjär sondering. Detta kapitel beskriver båda dessa metoder.

Öppen adressering

Open addressing används för att lösa kollisioner. Kollisioner är mycket vanliga och uppstår när två element råkar hashas till samma plats eller position. Tänk dig till exempel en hash-uppsättning som denna:

Om det finns en begäran om att fylla plats 0 med 70, och plats 0 inte är tom, hittar öppen adressering nästa lediga plats i ordboken för att hantera denna begäran. Denna sekventiella sökning efter en alternativ plats kallas sondering. Det finns flera algoritmer för sekvenssondering, men MicroPython använder linjär sondering som beskrivs i nästa avsnitt.

Linjär sondering

Linjär sondering är en av metoderna för att hitta en ledig adress eller plats i en ordbok. I MicroPython används den tillsammans med öppen adressering. För att hantera den begäran som beskrevs ovan antar linjär sondering, till skillnad från andra sonderingsalgoritmer, ett fast intervall på 1 mellan sonderingarna. Begäran hanteras därför genom att elementet placeras i nästa lediga plats, vilket är plats 4 i vårt exempel:

Samma metoder, dvs. öppen adressering och linjär sondering, används för att söka efter ett element i en ordbok. Anta att vi vill söka efter dataelementet 33. Det beräknade hashvärdet blir 2. Om vi tittar på plats 2 hittar vi 33. Vid denna punkt returnerar vi True. Att söka efter 70 är ganska annorlunda eftersom det uppstod en kollision vid infogningstillfället. Det beräknade hashvärdet är därför 0, som för närvarande innehåller 44. I stället för att bara returnera False utför vi en sekventiell sökning som börjar vid punkt 1 tills elementet 70 hittas eller vi stöter på en ledig plats. Detta är det allmänna sättet att utföra uppslagningar i hashar:

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