Mapy a slovníky

Slovníky a mapy v MicroPythonu používají techniky zvané otevřené adresování a lineární prozkoumávání. Tato kapitola obě tyto metody podrobně popisuje.

Otevřené adresování

Otevřené adresování se používá k řešení kolizí. Kolize jsou velmi častým jevem a nastávají, když se dvě položky náhodou zahashují do téhož slotu nebo umístění. Například při hashovacím uspořádání jako toto:

Pokud přijde požadavek na naplnění slotu 0 hodnotou 70, a slot 0 není prázdný, otevřené adresování najde další dostupný slot ve slovníku, který tento požadavek obslouží. Tomuto sekvenčnímu hledání náhradního umístění se říká prozkoumávání (probing). Existuje několik algoritmů sekvenčního prozkoumávání, ale MicroPython používá lineární prozkoumávání, které je popsáno v další části.

Lineární prozkoumávání

Lineární prozkoumávání je jednou z metod hledání dostupné adresy nebo slotu ve slovníku. V MicroPythonu se používá spolu s otevřeným adresováním. Pro obsluhu výše popsaného požadavku lineární prozkoumávání, na rozdíl od jiných prozkoumávacích algoritmů, předpokládá pevný interval 1 mezi jednotlivými kroky. Požadavek tedy bude obsloužen umístěním položky do dalšího volného slotu, kterým je v našem příkladu slot 4:

Stejné metody, tj. otevřené adresování a lineární prozkoumávání, se používají k vyhledávání položky ve slovníku. Předpokládejme, že chceme vyhledat datovou položku 33. Vypočtená hodnota hashe bude 2. Pohled na slot 2 odhalí 33. V tomto okamžiku vrátíme True. Hledání 70 je zcela odlišné, protože v době vložení došlo ke kolizi. Vypočtená hodnota hashe je tedy 0, který aktuálně obsahuje 44. Namísto prostého vrácení False provedeme sekvenční hledání počínaje bodem 1, dokud není položka 70 nalezena nebo dokud nenarazíme na volný slot. Toto je obecný způsob provádění vyhledávání v hashích:

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