Mapas e Dicionários

Os dicionários e mapas do MicroPython usam técnicas chamadas endereçamento aberto e sondagem linear. Este capítulo detalha ambos os métodos.

Endereçamento aberto

O endereçamento aberto é usado para resolver colisões. As colisões são ocorrências muito comuns e acontecem quando dois itens acabam tendo o mesmo hash para o mesmo slot ou local. Por exemplo, dada uma configuração de hash como esta:

Se houver uma requisição para preencher o slot 0 com 70, como o slot 0 não está vazio, o endereçamento aberto encontra o próximo slot disponível no dicionário para atender a essa requisição. Essa busca sequencial por um local alternativo é chamada de sondagem (probing). Existem vários algoritmos de sondagem por sequência, mas o MicroPython usa a sondagem linear, descrita na próxima seção.

Sondagem linear

A sondagem linear é um dos métodos para encontrar um endereço ou slot disponível em um dicionário. No MicroPython, ela é usada com o endereçamento aberto. Para atender à requisição descrita acima, diferentemente de outros algoritmos de sondagem, a sondagem linear assume um intervalo fixo de 1 entre as sondagens. A requisição será, portanto, atendida colocando o item no próximo slot livre, que é o slot 4 em nosso exemplo:

Os mesmos métodos, ou seja, endereçamento aberto e sondagem linear, são usados para buscar um item em um dicionário. Suponha que queremos buscar o item de dados 33. O valor de hash calculado será 2. Olhando para o slot 2, encontramos 33. Nesse ponto, retornamos True. Buscar 70 é bem diferente, pois houve uma colisão no momento da inserção. Portanto, o valor de hash calculado é 0, que atualmente contém 44. Em vez de simplesmente retornar False, realizamos uma busca sequencial começando no ponto 1 até que o item 70 seja encontrado ou encontremos um slot livre. Esta é a maneira geral de realizar consultas em hashes:

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