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

Detallar barəsində yazılar

Qeyd edək ki, ədədlər kimi bir-birinə yaxın olan iki açarlar (4618396 və 4618996 kimi), ədədlər kimi bir-birindən əhəmiyyətli dərəcədə fərqlənən (0000991 və 9846995 kimi) iki açardan fərqli olaraq, həmin cədvəldə bir - birindən uzaqda yerləşə bilərlər (şək.68). Bu ondan irəli gəlir ki, yazının mövqeini təyin etmək üçün açarın yalnız axırıncı 3 rəqəmlərindən istifadə edirlər.

Xeşləmə - bu, bir böyük çoxluğun kiçiyə doğru və ya “çoxlu qiymətlərin bir qiymətə” endirilmə üsuludur .

Çevirmə funksiyasının seçilməsi.

Açarı cədvəldəki müəyyən bir indeksə transformasiya edən funksiya xeş-funksiya adlanır.

Bizim halda h(key) = key mod 1000;

Xeş-cədvəl – bu, xeş-funksiya tərəfindən verilən qeyri-adi ünvanlaşdırılmalı adi massivdir.

Xeş-cədvəlin yaradılmasının baxdığımız üsulu bir mənfi cəhətə malikdir.

Tutaq ki, elə bir k1 və k2 kimi iki açar mövcuddur ki, orada h(k1)=h(k2) olur. K1 açarlı yazı cədvələ daxil edildikdə, o, h(k1) mövqeinə salınır. Amma k2 açarı xeşləndikdə, alınmış mövqe k1 açarlı yazının saxlandığı həmin mövqe olacaqdır. Aydındır ki, iki yazı eyni bir mövqeni məşğul edə bilməzlər. Bu cür vəziyyət xeşləmə zamanı kolliziya və ya toqquşma adlanır.
Qeyd etmək lazımdır ki, yaxşı xeş funksiya elə bir funksiya olmalıdır ki, o kolliziyaları minimum etmiş olsun və bütün cədvəl üzrə yazıları bir bərabərdə paylamış olsun.

Mükəmməl xeş-funksiya – bu kolliziyaları yaratmayan funksiyadır.

Xeşləmə zamanı kolliziyaları iki üsulla aradan qaldırmaq olar:

-Açıq ünvanlaşdırma üsulu ilə;

-Zəncir üsulu ilə. 

Açarların çevrilməsi ilə əlaqədar olan əsas çətinlik ondan ibarət olur ki, mümkün ola bilən qiymətlər çoxluğu yaddaş ünvanla-rının buraxıla bilən çoxluqlarından (massivin indekslərindən) əhəmiyyətli dərəcədə geniş olur. Misal kimi 16 - ya qədər hərfdən ibarət olan və minlərlərlə heyətin içərisindən ayrı-ayrı fərdiləri identifikasiya edən açarlardan ibarət adları götürək. Bu halda biz 2¹⁶ açarlar mümkünlükləri ilə işləməli olmalıyıq ki, bunu da 10³ indekslər mümkünlükləri ilə əks etdirmək lazım gələcəkdir. Buna görə də, funksiyası “çoxlu qiymətlər bir qiymətdə” sinifli funksiya kimi olacaqdır. Əgər hər hansı bir k açarı verilmişsə, o zaman axtarış əməliyyatının birinci addımı – onunla əlaqəli olan h = H(k) indeksinin hesablanması, ikinci addım isə (tamamilə vacibdir) - doğrudanmı h-ın T massivində k açarlı elementi identifikasiya etməsinin yoxlanılması olacaqdır.

Axtarışın təşkil olunduğu yazı müəyyən bir cədvəldə saxlanılır. Tələb olunan yazını tapmamışdan əvvəl müəyyəm sayda açarlara baxış keçirtməyi təşkil etmək lazımdır.