.. _maps: Maps and Dictionaries ===================== MicroPython dictionaries and maps use techniques called open addressing and linear probing. This chapter details both of these methods. Open addressing --------------- `Open addressing `_ is used to resolve collisions. Collisions are very common occurrences and happen when two items happen to hash to the same slot or location. For example, given a hash setup as this: .. image:: img/collision.png If there is a request to fill slot ``0`` with ``70``, since the slot ``0`` is not empty, open addressing finds the next available slot in the dictionary to service this request. This sequential search for an alternate location is called *probing*. There are several sequence probing algorithms but MicroPython uses linear probing that is described in the next section. Linear probing -------------- Linear probing is one of the methods for finding an available address or slot in a dictionary. In MicroPython, it is used with open addressing. To service the request described above, unlike other probing algorithms, linear probing assumes a fixed interval of ``1`` between probes. The request will therefore be serviced by placing the item in the next free slot which is slot ``4`` in our example: .. image:: img/linprob.png The same methods i.e open addressing and linear probing are used to search for an item in a dictionary. Assume we want to search for the data item ``33``. The computed hash value will be 2. Looking at slot 2 reveals ``33``, at this point, we return ``True``. Searching for ``70`` is quite different as there was a collision at the time of insertion. Therefore computing the hash value is ``0`` which is currently holding ``44``. Instead of simply returning ``False``, we perform a sequential search starting at point ``1`` until the item ``70`` is found or we encounter a free slot. This is the general way of performing look-ups in hashes: .. code-block:: c // 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; }