This is the vv1.21.0 version of the MicroPython documentation. The latest development version of this page may be more current.

# Maps and Dictionaries¶

MicroPython dictionaries and maps use techniques called open addressing and linear probing. This chapter details both of these methods.

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:

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:

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:

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