Qarışıq anlayışlar

giriş

Hash File təşkili metodu, hash funksiyasından istifadə edilərək məlumatların yaradıldığı məlumat bloklarında saxlanılan metoddur. Bu qeydlərin saxlandığı yaddaş yeri məlumat bloku və ya məlumat vedrası adlanır. Bu məlumat qutusu bir və ya daha çox qeyd saxlaya bilir.

Hash funksiyası ünvanı yaratmaq üçün hər hansı bir sütun dəyərindən istifadə edə bilər. Çox vaxt, hash funksiyası, məlumat bloğunun hash indeksini - ünvanını yaratmaq üçün əsas düymədən istifadə edir. Hash funksiyası istənilən mürəkkəb riyazi funksiyaya sadə riyazi funksiya ola bilər. Birincil açarın özünü məlumat blokunun ünvanı hesab edə bilərik. Yəni hər bir sıra ünvanı birincil açarla eyni olan məlumat blokunda saxlanacaqdır. Bu, bir hash funksiyasının verilənlər bazasında nə qədər sadə ola biləcəyini nəzərdə tutur.

Pin

Yuxarıdakı diaqramda əsas blok dəyəri ilə eyni məlumat bloku ünvanı təsvir edilmişdir. Bu hash funksiyası mod, sin, cos, eksponent və s. Kimi sadə riyazi funksiya da ola bilər. Təsəvvür edin ki, məlumat blokunun ünvanını təyin etmək üçün mod (5) kimi hash funksiyamız var. Yəni yuxarıdakı işdə nə baş verir? Əsas düymələrə mod (5) tətbiq edir və sırasıyla 3,3,1,4 və 2 əmələ gətirir və qeydlər həmin məlumat bloku adreslərində saxlanılır.

Pin

Yuxarıdakı iki diaqramdan artıq hash funksiyasının necə işlədiyi aydınlaşdı.

İki növ hash fayl təşkilatı var - StatikDynamic Hashing.

Statik Hashing

Bu hashing metodunda nəticələnən məlumat çöpü ünvanı həmişə eyni olacaq. Yəni, mod (103) hash funksiyasından istifadə edərək EMP_ID = 5 üçün ünvan yaratmaq istəyiriksə, həmişə eyni vedrə ünvanı 3 ilə nəticələnir. Burada vedrə adresində heç bir dəyişiklik olmayacaqdır. Beləliklə, bu statik qarışıq üçün yaddaşdakı məlumat paketlərinin sayı davamlı olaraq qalır. Nümunəmizdə, məlumatları saxlamaq üçün istifadə olunan yaddaşda beş məlumat qabımız olacaq.

Pin

Bir qeyd axtarılır

Hash funksiyasından istifadə edərək xaş açarı üçün data bucket ünvanı yaradılır. Daha sonra qeyd həmin yerdən alınır. yəni; əgər biz ID 104 üçün bütün qeydləri götürmək istəyiriksə və əgər hash funksiyası ID-də mod (5) olarsa, yaradılan ünvan 4 olardı. Sonra birbaşa 4 ünvanına müraciət edib 104 nömrəsi üçün bütün qeydləri əldə edəcəyik. Burada ID bir hash açarı kimi çıxış edir.

Bir qeyd daxil edin

Yeni bir qeydin cədvələ daxil edilməsinə ehtiyac olduqda, yeni qeyd üçün hash düyməsinə əsasən bir adres yaradacağıq. Ünvan yaradıldıqdan sonra qeyd həmin yerdə saxlanılır.

Bir qeyd silin

Hash funksiyasından istifadə edərək əvvəlcə silinməsi lazım olan qeydləri gətirəcəyik. Sonra yaddaşdakı həmin ünvan üçün qeydləri siləcəyik.

Bir qeyd yeniləyin

Yeniləmə üçün qeyd edilmiş məlumat qeydləri statik qarışıq funksiyasından istifadə edilərək axtarılır və sonra həmin ünvandakı qeyd yenilənir.

 

Tutaq ki, fayla bəzi qeydlər əlavə etməliyik. Lakin hash funksiyası ilə yaradılan data bucket ünvanı doludur və ya həmin ünvanda onsuz da mövcuddur. Veriləri necə əlavə edirik? Statik qarışıqdakı bu vəziyyət deyilir vedrə daşması. Bu, bu metoddakı kritik vəziyyətlərdən / çatışmazlıqlardan biridir. Bu vəziyyətdə məlumatları harada saxlayacağıq? Məlumatları itirə bilmərik. Bu vəziyyəti aradan qaldırmaq üçün müxtəlif üsullar var. Ən çox istifadə olunan metodlar aşağıda verilmişdir:

Qapalı hashing

Bu metodla eyni ünvana sahib yeni bir məlumat vedrəsini təqdim edirik və tam məlumat paketindən sonra əlaqələndiririk. Kovanın daşmasını aradan qaldırmaq üçün bu üsullara qapalı hashing və ya deyilir daşqın zəncirləmə.

Yeni bir R2 rekordunu daxil etməli olduğumuzu düşünün masaları. Statik hash funksiyası, məlumat paketi ünvanını 'AACDBF' olaraq yaradır. Ancaq bu paket yeni məlumatları saxlamaq üçün doludur. Bu vəziyyətdə edilən şey, 'AACDBF' məlumat paketinin sonuna yeni bir məlumat paketi əlavə edilir və onunla əlaqələndirilir. Sonra yeni kovaya yeni rekord R2 daxil edilir. Beləliklə, statik hashing ünvanını saxlayır. Dolu olduqda istənilən sayda yeni məlumat paketi əlavə edə bilər.

Pin

Açıq Hashing

Bu metodda yeni bir qeydin köhnəsinə yazmaq əvəzinə daxil olmaq üçün növbəti mövcud məlumat bloku istifadə olunur. Bu üsula Açıq Hashing və ya deyilir xətti sınaq.

Aşağıdakı nümunədə R2-nin daxil edilməsi lazım olan yeni bir qeyddir. Ancaq hash funksiyası 237 olaraq ünvan yaradır. Lakin onsuz da doludur. Beləliklə, sistem növbəti mövcud məlumat qutusunu 238 axtarır və ona R2 təyin edir.

Pin

Xətti zondlamada köhnə vedrə ilə yeni vedrə arasındakı fərq ümumiyyətlə düzəldilir və halların çoxu 1 olacaqdır.

Kvadrat zondlama

Bu xətti araşdırmaya bənzəyir. Ancaq burada köhnə və yeni vedrə arasındakı fərq doğrudur. Yeni vedrə adresini təyin etmək üçün kvadratik funksiyadan istifadə edirik.

Qoşa Hashing

Bu, başqa bir xətti araşdırma metodudur. Burada fərq xətti araşdırmada olduğu kimi düzəldilir, lakin bu sabit fərq başqa bir hash funksiyasından istifadə etməklə hesablanır. Buna görə ad ikiqat qarışıqdır.

Dinamik Hashing

Bu hashing metodu statik hashing problemlərini aradan qaldırmaq üçün istifadə olunur - vedrə daşması. Bu hashing metodunda qeydlər artdıqca və ya azaldıqca məlumat paketləri böyüyür və ya azalır. Bu hashing üsulu, genişləndirilə bilən hashing üsulu olaraq da bilinir. Bu metodu anlamaq üçün bir nümunə görək.

Cədvəldə üç qeyd R1, R2 və R4 olduğunu düşünək. Bu qeydlər müvafiq olaraq 100100, 010110 və 110110 ünvanları yaradır. Bu saxlama metodu bu ünvanın yalnız bir hissəsini nəzərə alır - xüsusən məlumatları saxlamaq üçün yalnız bir bit. Beləliklə, onlardan üçünü 0 və 1 ünvanlarına yükləməyə çalışır.

Burada R3 ilə nə olacaq? R3 üçün vedrə yeri yoxdur. R3-i yerləşdirmək üçün vedrə dinamik şəkildə böyüməlidir. Beləliklə, ünvanı dəyişdirmək üçün 2 bit deyil, 1 bit var və daha sonra mövcud məlumatları 2 bit ünvanlı olaraq yeniləyir. Sonra R3 yerləşdirməyə çalışır.

Pin

İndi R1 və R2 adreslərinin yeni ünvanı əks etdirmək üçün dəyişdirildiyini və R3-in də daxil edildiyini görə bilərik. Verilərin ölçüsü artdıqca, mövcud vedrələrə daxil etməyə çalışır. Kovalar yoxdursa, daha böyük ünvanı nəzərə almaq üçün bit sayı artır və bu səbəbdən buketlər artır. Hər hansı bir qeydi silsək və məlumatları daha az vedrə ilə saxlamaq olarsa, vedrə ölçüsünü kiçiltir. Yuxarıda gördüklərimizin əksini edir. Dinamik bir hashing necə işləyir. Əvvəlcə məlumatların saxlanması üçün hash funksiyası ilə yaradılan yalnız qismən indeks / adres hesab olunur. Məlumatların sayı artdıqca və daha çox vedrə tələb olunduqda, indeksin daha böyük hissəsi məlumatları saxlamağı düşünür.

Dinamik qarışıqların üstünlükləri

  • Məlumat sistemdə böyüdükcə performans aşağı düşmür. Sadəcə məlumatları yerləşdirmək üçün yaddaş ölçüsünü artırır.
  • Böyüyən və məlumatlarla daraldığı üçün yaddaş yaxşı istifadə olunur. Yalan istifadə edilməmiş heç bir yaddaş olmayacaq.
  • Verilərin tez-tez böyüdüyü və azaldığı dinamik verilənlər bazaları üçün yaxşıdır.

 

Dinamik həşəratın dezavantajları

  • Məlumat ölçüsü artdıqca, vedrə ölçüsü də artır. Bu ünvanlar vedrə ünvanı masalarında saxlanılacaqdır. Bunun səbəbi, vedrələrin böyüdülməsi və azalması nəticəsində məlumatların ünvanı dəyişməyə davam edəcəkdir. Verilərdə böyük bir artım olduqda, bu vedrə ünvan masasının saxlanması yorucu olur.
  • Kovanın daşması vəziyyəti bu vəziyyətdə də meydana gələcək. Ancaq bu vəziyyətə çatmaq üçün statik qarışıqdan daha az vaxt tələb oluna bilər.

Sifarişli İndeksləmə və Hashing müqayisəsi

Sifarişli indeksləşdirmə

Hashing

Yaddaşdakı ünvanlar əsas dəyər üçün sıralanır. Bu açar dəyər birincil açar və ya cədvəldəki hər hansı digər sütun ola bilər. Ünvanlar açar dəyərdəki hash funksiyasından istifadə edərək yaradılır. Bu açar dəyər birincil açar və ya cədvəldəki hər hansı digər sütun ola bilər.
Bu metodun performansı, fayldakı məlumatlar artdıqca aşağı düşür. Veriləri sıralanmış bir formada saxladığı üçün, əlavə / silmə / yeniləmə əməliyyatı olduqda, qeydləri düzəltmək üçün əlavə bir səy lazımdır. Bu onun fəaliyyətini azaldır. Məlumatların tez-tez əlavə edilməsi və silinməsi olduqda dinamik qarışıqların performansı yaxşı olacaqdır. Ancaq verilənlər bazası çox böyükdürsə, təmir daha sərfəli olacaq.

Statik hashing əvvəllər qeyd ölçüsü id-nin məlum olduğu kiçik verilənlər bazaları üçün yaxşı olacaqdır. Məlumatlarda bir artım varsa, vedrənin aşması kimi ciddi problemlərlə nəticələnir.

Silmə / yeniləmə əməliyyatı səbəbindən istifadə edilməmiş məlumat blokları olacaq. Bu məlumat blokları yenidən istifadə üçün buraxılmayacaq. Beləliklə, yaddaşın vaxtaşırı saxlanılması tələb olunur. Başqa bir vəziyyətdə, yaddaş boşa çıxır və performans da azalacaq. Yaddaşın qorunması da əlavə xərclərə başa gələcək. Həm statik, həm də dinamik qarışıqda yaddaş yaxşı idarə olunur. Kovanın daşması da statik qarışıqda daha yaxşı dərəcədə idarə olunur. Məlumat blokları, dinamik qarışmada azalmaq və böyümək üçün nəzərdə tutulmuşdur.

Ancaq böyük bir verilənlər bazası böyüməsi olduqda, dinamik sarsıntıda vedrə ünvanı cədvəlini qorumaq üçün bir xərc olacaq.

Verilənlərin aralığının alınması üçün üstünlük verilir, yəni müəyyən bir sıra üçün axtarış məlumatları olduqda, bu metod ən uyğun gəlir. Bu metod axtarış düyməsinə əsasən müəyyən bir qeyd almaq üçün əlverişlidir. Ancaq hash funksiyası axtarış düyməsində deyilsə daha yaxşı nəticə verməyəcəkdir.

Şərh yaz

Translate »