地图和字典

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