Mühazirə 1 Giriş Əsas anlayışlar. "Məlumat"

Verilənlərin əldə edilməsinin sürətləndirilməsi metodları

Xeşləmə zamanı kolliziyaların aradan qaldırılmasının ən sadə üsulu həmin yazının massivdəki növbəti boş mövqeyə yerləşdirilməsidir. Məsələn, 0596397 açarlı yazı hələlik boş olan 398 xanasına yerləşdirilir, çünki, 397 xanası artıq tutulmuşdur. Bu yazı araya salınanda, 397 mövqeinə (8764397 kimi açarlı) və ya 398 mövqeinə (2194398 kimi açarlı) xeşləndirilən digər yazı hal-hazırda 400-ə bərabər olan növbəti boş mövqeyə salınır.
Bu üsul həmçinin, xətti yoxlama adlandırılır, o, xeşləmə zamanı kolliziyaların aradan qaldırılmasının müəyyən bir ümumi üsuluna aid misaldır və o, təkrar xeşləmə adlanır.
Açıq ünvanlaşdırma üsulunun mənfi cəhətləri
Birincisi, o, qeyd olunmuş ölçüdə cədvəl tələb edir. Əgər yazıların sayı bu ölçüdən çox olarsa, o zaman böyük ölçülü cədvəl artırmadan onları araya salmaq və artıq cədvəldə olan bütün yazıların açarları üçün yeni xeşləmə funksiyasından istifadə edərək, xeşləmə qiymətinin təkrarən hesablanması mümkün olmayacaqdır.
İkincisi, bu cür cədvəldən yazını ləğv etmək çətin olur.
Zəncirlər üsulu ilə xeşləmədə kolliziyaların aradan qaldırılması
Bu üsul ondan ibarət olur ki, açarları eyni bir qiymətlə xeşləndirilən bütün yazılardan əlaqəli siyahılar təşkil olunurlar.
Tutaq ki, xeş-funksiya 0-dan (n-1)-ə qədər olan diapazonda qiymətləri çıxışa verir. Bu zaman n ölçülü və başlıqlar qovşaqlarından ibarət olan müəyyən bir “bucket” massivi təsvir olunur. Bucket (i) elementi açarları i-də xeşlənən bütün yazıların siyahısını göstərir. Yazının axtarışında qovşaqlar massivində i mövqeini tutan siyahı başlığına müraciət həyata keçirilir. Əgər yazı tapılmamışsa, o zaman onu siyahının sonuna salırlar.
Fərz edək ki, 10 elementlərdən ibarət olan massiv vardır və xeş-funksiya (key mod 10)-a bərabərdir. Açarlr açağıdakı ardıcıllıqda yerləşmişlər:
75 66 42 192 91 40 49 87 67 16 417 130 372 227
Uyğun bir əlaqəli siyahılı başlıqlar qovşaqlarının massivi aşağıda verilmişdir.

Şək.68. Uyğun bir əlaqəli siyahılı başlıqlar qovşaqlarının massivi

Zəncirlər üsulu ilə qurulmuş cədvəldən qovşağın ləğv edilməsi sadəcə olaraq, əlaqəli siyahıdan qovşağın ləğv edilməsindən ibarət olur. Ləğv olunmuş qovşaq heç cür axtarış alqoritminin effektivliyinə təsir göstərmir .Alqoritm elə işləyəkdir ki, guya heç vaxt bu qovşaq cədvələ salınmamışdı. Qeyd etmək lazımdıır ki, axtarışın böyük effektivliyini əldə erməkdən ötrü bu siyahı dinamiki olaraq, yenidən nizamlana bilər.

Zəncirlər üsulunun əsas mənfi cəhəti ondan ibarət olur ki, göstəricilər qovşaqları üçün əlavə fəza tələb olunur. Amma zəncirlər üsulundan istifadə edən alqoritmlərdə təkrar xeşləmədən istifadə edən alqoritmlərlə müqayisədə ilkin massiv kiçik olur. Bu ona görə baş verir ki, zəncirlər üsulunda bütün massivin doldurulması o qədər də fəlakətli hadisə olmur. Həmişə əlavə qovşaqları ayırmaq və onları müxtəlif siyahılara əlavə etmək mümkün olur. Əlbəttə ki, əgər bu siyahılar çox uzun olsalar, o zaman bütün xeşləmə ideyası öz mənasını itirəcəkdir – düz ünvanlaşdırma və bunun da nəticəsi kimi, effektiv axtarış olmayacaqdır.