Maps และ Dictionaries

dictionaries และ maps ของ MicroPython ใช้เทคนิคที่เรียกว่า open addressing และ linear probing บทนี้อธิบายรายละเอียดทั้งสองวิธีนี้

Open addressing

Open addressing ถูกใช้เพื่อแก้ไขการชน การชนเกิดขึ้นบ่อยมากและเกิดขึ้นเมื่อสองรายการมี hash ไปยัง slot หรือตำแหน่งเดียวกัน ตัวอย่างเช่น กำหนดการตั้งค่า hash แบบนี้:

หากมีคำขอเติม slot 0 ด้วย 70 เนื่องจาก slot 0 ไม่ว่าง open addressing จะหา slot ถัดไปที่ว่างใน dictionary เพื่อดำเนินการตามคำขอนี้ การค้นหาตามลำดับสำหรับตำแหน่งสำรองนี้เรียกว่า probing มีอัลกอริทึม probing ลำดับหลายชนิดแต่ MicroPython ใช้ linear probing ที่อธิบายในส่วนถัดไป

Linear probing

Linear probing เป็นหนึ่งในวิธีการหาที่อยู่หรือ slot ที่ว่างใน dictionary ใน MicroPython ใช้ร่วมกับ open addressing เพื่อดำเนินการตามคำขอที่อธิบายข้างต้น ต่างจากอัลกอริทึม probing อื่น ๆ linear probing สันนิษฐานช่วงคงที่ 1 ระหว่างการ probe คำขอจะถูกดำเนินการโดยการวางรายการใน slot ว่างถัดไปซึ่งคือ slot 4 ในตัวอย่างของเรา:

วิธีการเดียวกัน กล่าวคือ open addressing และ linear probing ถูกใช้เพื่อค้นหารายการใน dictionary สมมติว่าเราต้องการค้นหา data item 33 ค่า hash ที่คำนวณได้จะเป็น 2 การมองที่ slot 2 เผย 33 ณ จุดนี้ เราคืนค่า True การค้นหา 70 ค่อนข้างแตกต่างเนื่องจากมีการชนในเวลาของการแทรก ดังนั้นค่า hash ที่คำนวณได้คือ 0 ซึ่งปัจจุบันถือ 44 แทนที่จะคืนค่า False เฉย ๆ เราทำการค้นหาตามลำดับเริ่มต้นที่จุด 1 จนกว่าจะพบรายการ 70 หรือเราพบ slot ว่าง นี่คือวิธีทั่วไปในการทำการค้นหาใน hashes:

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