Mapas e Dicionários

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

Endereçamento aberto

O endereçamento aberto é utilizado para resolver colisões. As colisões são ocorrências muito comuns e acontecem quando dois elementos têm o mesmo valor de hash para a mesma posição ou localização. Por exemplo, dado um hash configurado da seguinte forma:

Se houver um pedido para preencher a posição 0 com 70, como a posição 0 não está vazia, o endereçamento aberto encontra a próxima posição disponível no dicionário para atender este pedido. Esta pesquisa sequencial por uma localização alternativa chama-se sondagem. Existem vários algoritmos de sondagem sequencial, mas o MicroPython utiliza a sondagem linear descrita na próxima secção.

Sondagem linear

A sondagem linear é um dos métodos para encontrar um endereço ou posição disponível num dicionário. No MicroPython, é utilizada com endereçamento aberto. Para atender o pedido descrito acima, ao contrário de outros algoritmos de sondagem, a sondagem linear assume um intervalo fixo de 1 entre sondagens. O pedido será portanto atendido colocando o elemento na próxima posição livre, que é a posição 4 no nosso exemplo:

Os mesmos métodos, ou seja, endereçamento aberto e sondagem linear, são utilizados para pesquisar um elemento num dicionário. Suponha que queremos pesquisar o elemento de dados 33. O valor de hash calculado será 2. Ao olhar para a posição 2, encontramos 33. Neste ponto, retornamos True. A pesquisa por 70 é bastante 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 pesquisa sequencial a partir do ponto 1 até que o elemento 70 seja encontrado ou encontremos uma posição livre. Esta é a forma geral de realizar pesquisas 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;
}