映射（Maps）与字典（Dictionaries）

MicroPython 字典和映射使用的是被称为开放地址和线性探测的技术。这一章节将详细介绍这两种技术。

开放寻址

开放寻址 是用来解决冲突的一项技术。冲突是非常常见的情况，发生在两个项目的哈希值相同时。例如，给定一个哈希设置如下：

如果请求填充槽 0 的值为 70，因为槽 0 不为空，开放寻址将找到下一个可用的槽来服务这个请求。这种对替代位置的顺序搜索称为 探测 。存在数种用于顺序探测的算法，但 MicroPython 使用的是线性探测，这是在下一节中描述的。

线性探测

线性探测是在字典中找到可用地址或槽的一种方法。在 MicroPython 中，它被用于开放寻址。为了服务上述描述的请求，线性探测假设每次探测的固定的间隔为 1 。请求将被放置到下一个能满足需求的空闲槽中，在我们的例子中，即槽 4 ：

在字典中搜索项也是使用同样的方法，即开放寻址和线性探测。假设我们想搜索数据项 33 。计算出的哈希值将是 2 。查看槽 2 会显示 33 ，此时，我们返回 True 。搜索 70 则展现出非常不同的过程，因为在插入时发生了冲突。因为计算出的哈希值是 0 ，它当前正在保存着 44 。不过，此时我们并不是直接返回 False ，而是执行一个顺序搜索，从点 1 开始，直到找到项目 70 或遇到一个空闲槽。这是一个在哈希中执行搜索的寻常方式：

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