מפות ומילונים

מילונים ומפות של MicroPython משתמשים בטכניקות הנקראות מיעון פתוח (open addressing) וגישוש לינארי (linear probing). פרק זה מפרט את שתי השיטות הללו.

מיעון פתוח

מיעון פתוח משמש לפתרון התנגשויות. התנגשויות הן תופעות נפוצות מאוד ומתרחשות כאשר שני פריטים מקבלים במקרה אותו hash לאותו slot או מיקום. לדוגמה, בהינתן מערך hash כזה:

אם קיימת בקשה למלא את ה-slot 0 ב-70, מאחר שה-slot 0 אינו ריק, מיעון פתוח מוצא את ה-slot הזמין הבא במילון כדי לשרת בקשה זו. חיפוש סדרתי זה אחר מיקום חלופי נקרא probing. ישנם מספר אלגוריתמי גישוש סדרתיים אך MicroPython משתמשת בגישוש לינארי המתואר בסעיף הבא.

גישוש לינארי

גישוש לינארי הוא אחת השיטות למציאת כתובת או slot זמין במילון. ב-MicroPython, הוא נמצא בשימוש עם מיעון פתוח. כדי לשרת את הבקשה המתוארת לעיל, בשונה מאלגוריתמי גישוש אחרים, גישוש לינארי מניח מרווח קבוע של 1 בין הגישושים. הבקשה תשורת אם כן על ידי הצבת הפריט ב-slot הפנוי הבא שהוא slot 4 בדוגמה שלנו:

אותן שיטות, כלומר מיעון פתוח וגישוש לינארי, נמצאות בשימוש לחיפוש פריט במילון. נניח שאנו רוצים לחפש את פריט הנתונים 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;
}