1 files changed, 63 insertions, 0 deletions
diff --git a/docs/develop/maps.rst b/docs/develop/maps.rst
new file mode 100644
index 000000000..8f899fa1d
--- /dev/null
+++ b/docs/develop/maps.rst
@@ -0,0 +1,63 @@
+.. _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 <https://en.wikipedia.org/wiki/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;
+   }