dict və set necə işləyir

dict və set Python-un ən çox istifadə olunan strukturlarıdır və ikisi də heş cədvəlidir. Bu mövzuda CPython-un dict-inin necə qurulduğunu görürük: nəzəriyyədən (heş funksiyaları, açıq ünvanlama, yük əmsalı) real reallaşdırmaya keçid. İstifadə qaydaları üçün dict əsasları və çoxluqlar mövzularına baxın.

Kompakt dict

Python 3.6-dan dict iki hissədən ibarətdir:

• indices: kiçik tam ədədlərdən ibarət heş massivi (boş slot, silinmiş slot və ya entries-dəki mövqe).
• entries: (hash, key, value) yazıları, daxil edilmə sırası ilə.

Axtarış indices-də açıq ünvanlama aparır, tapılan mövqe ilə entries-ə baxır. Üstünlüklər: yaddaş azalır (seyrək massivdə yalnız kiçik indekslər saxlanılır, böyük yazılar sıx yerləşir) və sıra təbii şəkildə saxlanılır. Sıra Python 3.7-dən dilin zəmanətidir.

Probing

CPython sadə xətti probing yox, açardan asılı pertürbasiya işlədir: i = (5*i + perturb + 1) & mask, burada perturb hər addımda 5 bit sağa sürüşür və heşin yuxarı bitləri də ardıcıllığa təsir edir. Beləliklə, aşağı bitləri eyni olan açarlar tez ayrılır, klasterləşmə azalır.

def slots(h, size, n):
    mask = size - 1
    perturb = h & (2**64 - 1)
    i = h & mask
    out = []
    for _ in range(n):
        out.append(i)
        perturb >>= 5
        i = (i * 5 + perturb + 1) & mask
    return out

print(slots(1, 8, 5))
print(slots(1000, 8, 5))

[1, 6, 7, 4, 5]
[0, 0, 1, 6, 7]

Modelin reallaşdırılması