Eşlemeler ve Sözlükler

MicroPython sözlükleri ve eşlemeleri, açık adresleme (open addressing) ve doğrusal yoklama (linear probing) adı verilen teknikleri kullanır. Bu bölüm bu yöntemlerin her ikisini de ayrıntılı olarak açıklar.

Açık adresleme

Çakışmaları çözmek için açık adresleme kullanılır. Çakışmalar çok yaygın olarak meydana gelir ve iki öğe aynı yuvaya veya konuma hash’lendiğinde gerçekleşir. Örneğin, şu şekilde bir hash kurulumu verildiğinde:

0 numaralı yuvayı 70 ile doldurma isteği varsa, 0 numaralı yuva boş olmadığından, açık adresleme bu isteği karşılamak için sözlükte bir sonraki uygun yuvayı bulur. Alternatif bir konum için yapılan bu sıralı aramaya yoklama (probing) denir. Çeşitli yoklama dizisi algoritmaları vardır, ancak MicroPython bir sonraki bölümde açıklanan doğrusal yoklamayı kullanır.

Doğrusal yoklama

Doğrusal yoklama, bir sözlükte uygun bir adres veya yuva bulma yöntemlerinden biridir. MicroPython’da açık adresleme ile birlikte kullanılır. Yukarıda açıklanan isteği karşılamak için, diğer yoklama algoritmalarının aksine, doğrusal yoklama yoklamalar arasında 1 değerinde sabit bir aralık varsayar. Bu nedenle istek, öğeyi bir sonraki boş yuvaya yerleştirerek karşılanacaktır; örneğimizde bu 4 numaralı yuvadır:

Bir sözlükte bir öğe aramak için de aynı yöntemler, yani açık adresleme ve doğrusal yoklama kullanılır. 33 veri öğesini aramak istediğimizi varsayalım. Hesaplanan hash değeri 2 olacaktır. 2 numaralı yuvaya bakıldığında 33 ortaya çıkar. Bu noktada True döndürürüz. 70 aramak ise oldukça farklıdır, çünkü ekleme sırasında bir çakışma olmuştu. Bu nedenle hesaplanan hash değeri 0‘dır ve bu yuva şu anda 44 değerini tutmaktadır. Yalnızca False döndürmek yerine, 70 öğesi bulunana veya boş bir yuvayla karşılaşana kadar 1 noktasından başlayarak sıralı bir arama gerçekleştiririz. Bu, hash’lerde arama yapmanın genel yoludur:

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