Maps và Dictionaries

Các dictionary và map trong MicroPython sử dụng các kỹ thuật gọi là open addressing và linear probing. Chương này trình bày chi tiết cả hai phương pháp này.

Open addressing

Open addressing được sử dụng để giải quyết xung đột. Xung đột là các sự kiện rất phổ biến và xảy ra khi hai mục có cùng giá trị hash hoặc cùng vị trí. Ví dụ: với cấu hình hash như sau:

Nếu có yêu cầu điền vào slot 0 với 70, vì slot 0 không rỗng, open addressing tìm slot trống tiếp theo trong dictionary để phục vụ yêu cầu này. Quá trình tìm kiếm tuần tự này để tìm vị trí thay thế được gọi là probing. Có một số thuật toán probing tuần tự nhưng MicroPython sử dụng linear probing được mô tả trong phần tiếp theo.

Linear probing

Linear probing là một trong các phương pháp để tìm địa chỉ hoặc slot có sẵn trong dictionary. Trong MicroPython, nó được sử dụng với open addressing. Để phục vụ yêu cầu được mô tả ở trên, không giống như các thuật toán probing khác, linear probing giả định một khoảng cố định là 1 giữa các lần probe. Do đó yêu cầu sẽ được phục vụ bằng cách đặt mục vào slot trống tiếp theo là slot 4 trong ví dụ của chúng ta:

Các phương pháp tương tự, tức là open addressing và linear probing, được sử dụng để tìm kiếm một mục trong dictionary. Giả sử chúng ta muốn tìm kiếm mục dữ liệu 33. Giá trị hash được tính toán sẽ là 2. Nhìn vào slot 2 cho thấy 33. Lúc này, chúng ta trả về True. Tìm kiếm 70 khá khác vì có xung đột tại thời điểm chèn. Do đó giá trị hash được tính toán là 0, hiện đang giữ 44. Thay vì chỉ đơn giản trả về False, chúng ta thực hiện tìm kiếm tuần tự bắt đầu từ điểm 1 cho đến khi tìm thấy mục 70 hoặc chúng ta gặp một slot trống. Đây là cách chung để thực hiện tra cứu trong các hash:

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