Отображения и словари

Словари и отображения 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;
}