映射与字典

MicroPython 的字典和映射使用了称为开放寻址（open addressing）和线性探测（linear probing）的技术。本章详细介绍这两种方法。

开放寻址

开放寻址 用于解决冲突。冲突是非常常见的情况，当两个项恰好哈希到同一个槽位或位置时就会发生。例如，给定如下的哈希设置：

如果有一个请求要用 70 填充槽位 0，由于槽位 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;
}