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 (şək69).