Мапи та словники

Словники та мапи 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;
}