Maps et dictionnaires

Les dictionnaires et les maps de MicroPython utilisent des techniques appelées adressage ouvert et sondage linéaire. Ce chapitre détaille ces deux méthodes.

Adressage ouvert

L”adressage ouvert est utilisé pour résoudre les collisions. Les collisions sont des phénomènes très courants qui se produisent lorsque deux éléments aboutissent par hachage au même emplacement. Par exemple, étant donné une configuration de hachage comme celle-ci :

S’il y a une demande de remplir l’emplacement 0 avec 70, comme l’emplacement 0 n’est pas vide, l’adressage ouvert recherche le prochain emplacement disponible dans le dictionnaire pour satisfaire cette demande. Cette recherche séquentielle d’un emplacement alternatif est appelée sondage. Il existe plusieurs algorithmes de sondage par séquence, mais MicroPython utilise le sondage linéaire décrit dans la section suivante.

Sondage linéaire

Le sondage linéaire est l’une des méthodes permettant de trouver une adresse ou un emplacement disponible dans un dictionnaire. Dans MicroPython, il est utilisé avec l’adressage ouvert. Pour satisfaire la demande décrite ci-dessus, contrairement à d’autres algorithmes de sondage, le sondage linéaire suppose un intervalle fixe de 1 entre les sondages. La demande sera donc satisfaite en plaçant l’élément dans le prochain emplacement libre, soit l’emplacement 4 dans notre exemple :

Les mêmes méthodes, à savoir l’adressage ouvert et le sondage linéaire, sont utilisées pour rechercher un élément dans un dictionnaire. Supposons que nous voulions rechercher l’élément de données 33. La valeur de hachage calculée sera 2. L’examen de l’emplacement 2 révèle 33. À ce stade, nous renvoyons True. La recherche de 70 est tout à fait différente car il y a eu une collision au moment de l’insertion. Par conséquent, la valeur de hachage calculée est 0, qui contient actuellement 44. Au lieu de simplement renvoyer False, nous effectuons une recherche séquentielle à partir du point 1 jusqu’à ce que l’élément 70 soit trouvé ou que nous rencontrions un emplacement libre. Voici la manière générale d’effectuer des recherches dans les hachages :

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