地图和字典

MicroPython 词典和地图使用称为开放寻址和线性探测的技术。本章详细介绍了这两种方法。

开放寻址

开放寻址用于解决冲突。冲突是很常见的情况,当两个项目碰巧散列到同一个插槽或位置时就会发生。例如,假设哈希设置如下:

../_images/collision.png

如果有,以填补插槽的请求070,因为插槽0 不为空,开放地址寻找下一个可用插槽在字典服务这一请求。这种对备用位置的顺序搜索称为探测。有多种序列探测算法,但 MicroPython 使用下一节中描述的线性探测。

线性探测

线性探测是在字典中查找可用地址或槽的方法之一。在 MicroPython 中,它与开放寻址一起使用。为了服务上述请求,与其他探测算法不同,线性探测假定探测1之间有固定的间隔。因此,该请求将通过将项目放置在下一个空闲插槽中来服务,4 在我们的示例中是插槽:

../_images/linprob.png

使用相同的方法(即开放寻址和线性探测)来搜索字典中的项目。假设我们要搜索数据项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;
}