Mapas y diccionarios

Los diccionarios y mapas de MicroPython utilizan técnicas llamadas direccionamiento abierto y sondeo lineal. Este capítulo detalla ambos métodos.

Direccionamiento abierto

El direccionamiento abierto se utiliza para resolver colisiones. Las colisiones son sucesos muy comunes y ocurren cuando dos elementos resultan tener el mismo hash y, por tanto, la misma ranura o ubicación. Por ejemplo, dada una configuración de hash como esta:

Si hay una solicitud para llenar la ranura 0 con 70, dado que la ranura 0 no está vacía, el direccionamiento abierto busca la siguiente ranura disponible en el diccionario para atender esta solicitud. Esta búsqueda secuencial de una ubicación alternativa se denomina sondeo. Existen varios algoritmos de sondeo de secuencias, pero MicroPython utiliza el sondeo lineal que se describe en la siguiente sección.

Sondeo lineal

El sondeo lineal es uno de los métodos para encontrar una dirección o ranura disponible en un diccionario. En MicroPython, se utiliza junto con el direccionamiento abierto. Para atender la solicitud descrita anteriormente, a diferencia de otros algoritmos de sondeo, el sondeo lineal asume un intervalo fijo de 1 entre sondeos. Por tanto, la solicitud se atenderá colocando el elemento en la siguiente ranura libre, que en nuestro ejemplo es la ranura 4:

Se utilizan los mismos métodos, es decir, direccionamiento abierto y sondeo lineal, para buscar un elemento en un diccionario. Supongamos que queremos buscar el elemento de datos 33. El valor de hash calculado será 2. Al mirar la ranura 2 se revela 33. En este punto, devolvemos True. Buscar 70 es bastante diferente, ya que hubo una colisión en el momento de la inserción. Por tanto, el valor de hash calculado es 0, que actualmente contiene 44. En lugar de simplemente devolver False, realizamos una búsqueda secuencial empezando en el punto 1 hasta encontrar el elemento 70 o hasta encontrar una ranura libre. Esta es la forma general de realizar búsquedas en 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;
}