Leképezések és szótárak

A MicroPython szótárai és leképezései a nyílt címzés (open addressing) és a lineáris próbálgatás (linear probing) nevű technikákat használják. Ez a fejezet mindkét módszert részletezi.

Nyílt címzés

A nyílt címzést (open addressing) az ütközések feloldására használják. Az ütközések nagyon gyakori jelenségek, és akkor fordulnak elő, amikor két elem véletlenül ugyanabba a rekeszbe vagy helyre kerül a hashelés során. Vegyük például a következő hash beállítást:

Ha kérés érkezik a 0 rekesz feltöltésére 70 értékkel, mivel a 0 rekesz nem üres, a nyílt címzés megkeresi a szótárban a következő szabad rekeszt a kérés kiszolgálásához. Ezt az alternatív hely szekvenciális keresését próbálgatásnak (probing) nevezzük. Több szekvenciakereső próbálgató algoritmus létezik, de a MicroPython a lineáris próbálgatást használja, amelyet a következő szakasz ismertet.

Lineáris próbálgatás

A lineáris próbálgatás az egyik módszer egy szótárban szabad cím vagy rekesz megtalálására. A MicroPythonban a nyílt címzéssel együtt használják. A fent leírt kérés kiszolgálásához a lineáris próbálgatás más próbálgató algoritmusoktól eltérően 1 rögzített lépésközt feltételez a próbálgatások között. A kérést tehát úgy szolgálja ki, hogy az elemet a következő szabad rekeszbe helyezi, ami a példánkban a 4 rekesz:

Ugyanazokat a módszereket, vagyis a nyílt címzést és a lineáris próbálgatást használják egy elem keresésére is a szótárban. Tegyük fel, hogy a 33 adatelemet szeretnénk megkeresni. A kiszámított hash érték 2 lesz. A 2-es rekeszbe nézve a 33 értéket találjuk. Ekkor True értéket adunk vissza. A 70 keresése egészen más, mivel a beszúráskor ütközés történt. Ezért a kiszámított hash érték 0, amely jelenleg a 44 értéket tartalmazza. Ahelyett, hogy egyszerűen False értéket adnánk vissza, szekvenciális keresést végzünk az 1 ponttól kezdve, amíg meg nem találjuk a 70 elemet, vagy szabad rekeszhez nem érünk. Ez a hashekben történő keresés általános módja:

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