맵과 딕셔너리

MicroPython 딕셔너리와 맵은 개방 주소법(open addressing)과 선형 탐사(linear probing)라는 기법을 사용합니다. 이 장에서는 이 두 가지 방법을 모두 자세히 다룹니다.

개방 주소법

개방 주소법 은 충돌을 해결하는 데 사용됩니다. 충돌은 매우 흔히 발생하는 일로, 두 항목이 같은 슬롯이나 위치로 해싱될 때 일어납니다. 예를 들어, 다음과 같은 해시 설정이 주어졌다고 합시다:

슬롯 0 을 70 으로 채우라는 요청이 있을 때, 슬롯 0 이 비어 있지 않으므로 개방 주소법은 이 요청을 처리하기 위해 딕셔너리에서 사용 가능한 다음 슬롯을 찾습니다. 이렇게 대체 위치를 순차적으로 찾는 것을 탐사(probing) 라고 합니다. 여러 가지 순차 탐사 알고리즘이 있지만 MicroPython은 다음 절에서 설명할 선형 탐사를 사용합니다.

선형 탐사

선형 탐사는 딕셔너리에서 사용 가능한 주소나 슬롯을 찾는 방법 중 하나입니다. MicroPython에서는 개방 주소법과 함께 사용됩니다. 위에서 설명한 요청을 처리할 때, 다른 탐사 알고리즘과 달리 선형 탐사는 탐사 간 간격이 1 로 고정되어 있다고 가정합니다. 따라서 이 요청은 다음 빈 슬롯에 항목을 넣어 처리되는데, 우리 예시에서는 슬롯 4 입니다:

딕셔너리에서 항목을 검색할 때도 동일한 방법, 즉 개방 주소법과 선형 탐사가 사용됩니다. 데이터 항목 33 을 검색한다고 가정해 봅시다. 계산된 해시 값은 2입니다. 슬롯 2를 살펴보면 33 이 나옵니다. 이 시점에 우리는 True 를 반환합니다. 70 을 검색하는 것은 삽입 시점에 충돌이 있었기 때문에 상당히 다릅니다. 따라서 계산된 해시 값은 0 인데, 현재 이 슬롯은 44 를 담고 있습니다. 단순히 False 를 반환하는 대신, 우리는 70 항목을 찾거나 빈 슬롯을 만날 때까지 1 지점부터 순차 검색을 수행합니다. 이것이 해시에서 조회를 수행하는 일반적인 방법입니다:

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