Map dan Kamus

Kamus dan map MicroPython menggunakan teknik yang disebut open addressing dan linear probing. Bab ini menjelaskan kedua metode tersebut.

Open addressing

Open addressing digunakan untuk menyelesaikan tabrakan. Tabrakan adalah kejadian yang sangat umum dan terjadi ketika dua item kebetulan di-hash ke slot atau lokasi yang sama. Misalnya, diberikan pengaturan hash seperti ini:

Jika ada permintaan untuk mengisi slot 0 dengan 70, karena slot 0 tidak kosong, open addressing menemukan slot berikutnya yang tersedia dalam kamus untuk melayani permintaan ini. Pencarian berurutan untuk lokasi alternatif ini disebut probing. Ada beberapa algoritma probing berurutan tetapi MicroPython menggunakan linear probing yang dijelaskan di bagian berikutnya.

Linear probing

Linear probing adalah salah satu metode untuk menemukan alamat atau slot yang tersedia dalam kamus. Di MicroPython, ini digunakan dengan open addressing. Untuk melayani permintaan yang dijelaskan di atas, tidak seperti algoritma probing lainnya, linear probing mengasumsikan interval tetap 1 antara probe. Permintaan tersebut oleh karena itu akan dilayani dengan menempatkan item di slot bebas berikutnya yaitu slot 4 dalam contoh kita:

Metode yang sama, yaitu open addressing dan linear probing, digunakan untuk mencari item dalam kamus. Asumsikan kita ingin mencari item data 33. Nilai hash yang dihitung akan menjadi 2. Melihat slot 2 mengungkapkan 33. Pada titik ini, kita mengembalikan True. Mencari 70 cukup berbeda karena ada tabrakan saat penyisipan. Oleh karena itu nilai hash yang dihitung adalah 0, yang saat ini menyimpan 44. Alih-alih langsung mengembalikan False, kita melakukan pencarian berurutan mulai dari titik 1 hingga item 70 ditemukan atau kita menemukan slot bebas. Ini adalah cara umum untuk melakukan pencarian dalam 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;
}