الخرائط والقواميس

تستخدم قواميس وخرائط MicroPython تقنيات تُسمى العنونة المفتوحة (open addressing) والاستكشاف الخطي (linear probing). يفصّل هذا الفصل كلتا الطريقتين.

العنونة المفتوحة

تُستخدم العنونة المفتوحة لحل التصادمات. التصادمات حدوثها شائع جدًا وتحدث عندما يصادف أن عنصرين ينتجان نفس قيمة التجزئة (hash) لنفس الفتحة أو الموضع. على سبيل المثال، بالنظر إلى إعداد تجزئة كهذا:

إذا كان هناك طلب لملء الفتحة 0 بالقيمة 70، فبما أن الفتحة 0 ليست فارغة، تجد العنونة المفتوحة الفتحة المتاحة التالية في القاموس لخدمة هذا الطلب. يُسمى هذا البحث التسلسلي عن موضع بديل بـ الاستكشاف (probing). هناك عدة خوارزميات لاستكشاف التسلسل ولكن 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;
}