對映與字典

MicroPython 的字典與對映使用了稱為開放定址（open addressing）與線性探測（linear probing）的技術。本章詳述這兩種方法。

開放定址

開放定址 用於解決碰撞問題。碰撞是相當常見的情況，當兩個項目恰好雜湊到相同的插槽或位置時就會發生。例如，給定如下的雜湊配置：

如果有一個請求要以 70 填入插槽 0，由於插槽 0 並非空的，開放定址便會在字典中尋找下一個可用的插槽來處理此請求。這種對替代位置進行的循序搜尋稱為 探測（probing）。探測有數種序列演算法，但 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;
}