Kommunikatsiyalarni rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti


Download 1.23 Mb.
Pdf ko'rish
Sana28.11.2020
Hajmi1.23 Mb.
#154289
Bog'liq
Mustaqil Ish


O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA 

KOMMUNIKATSIYALARNI RIVOJLANTIRISH VAZIRLIGI 

 

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT 



TEXNOLOGIYALARI UNIVERSITETI 

 

Fan 

 Ma’lumotlar tuzilmasi

 va algoritmlar  



MUSTAQIL ISH 

Mavzu: 

Hesh jadvallari va funksiyalari

Guruh: 

416 - 19 

Bajardi:

 Zafar Kamolov 

Tekshirdi:  

Marg'uba Akbarova  

Toshkent-2020 

Hesh jadvallari va funksiyalari

 

Mustaqil ish maqsadi: 

Hesh jadvallari va funksiyalari



 

 

o’rganish hamda ularni 

tadqiq   qilish. C++ tilida hesh funksiyalarni e’lon qilish va uning ustida amal bajarish 

dasturini ishlab chiqish. 



Reja: 

 Heshlash(tirish) tushunchasi.

 Hesh-funksiya va uning hossalari.

 Ma'lumotlar tarkibida Heshlash

 Ziddiyatlarning yuzaga kelishi.

 Kolloziya holatini hal etish metodlari.

 C++ tilida dastur algoritmini ishlab chiqish.

 Xulosa.



Heshlash(tirish) tushunchasi. 

Hesh so’zi ingliz tilidagi hash so’zidan olingan bo’lib, chalkash ( 

putanisa) yoki aralashma (meshanina) ma’nosini anglatadi 

Ta’rif . Hesh-funksiya – bu kiruvchi ma’lumotlarning ixtiyoriy 

uzunlikdagi massivini  belgilangan aniq uzunlikdagi bitlar qatoriga 



biror bir algoritm orqali akslantiruvchi bir tomonlama funksiyadir 

(funksiya svyortki). 

Bunday amal -heshlash(+tirish) deyiladi. 

Amalning natijasi (bitlar qatori)ga hesh yoki hesh kod yoki hesh-

summa yoki ma’lumotlar yig’mi(cvodkasi ) deyiladi. 

Bunday funksiyalar  kriptografiya va axborot xavfsizlik 

masalalarida keng qo’llaniladi. 

Ma'lumotlar tarkibida Heshlash. 

Qidiruv har qanday ma'lumotlar tuzilmasidan ustunlik qiladi. 

Barcha operatsiyalarni kiritish, o'chirish, yangilash uchun ko'p holatlar 

avval qidirishni talab qiladi. Shunday qilib, ma'lumotlar tuzilmasining 

qidiruv ishi vaqt murakkabligini aniqlaydi. Agar biron bir ma'lumot 

strukturasini olsak, qidirish uchun eng yaxshi vaqt murakkabligi  

O (log n) AVL daraxtida va faqat tartiblangan massivda. Aksariyat 

hollarda O (n) vaqt talab etiladi. Ushbu qidiruv muammosini hal qilish 

uchun O (1) vaqtni talab qiladigan heshlash kontseptsiyasi taqdim 

etildi. Bu doimiy vaqt. 



Hesh funksiya hossalari : 

 



1.Teskari funksiyaning mavjud emasligi; 

 



2.Kollizia holatining yo’qligi ; 

 

3.DeterminanlanganIik 



 

4. Natijaning tasodifligi. 



Joylashtirish usuli (xeshlashtirish)

 ma’lumotlar tuzilmasida element 

joylashgan o‘rinni tez aniqlashga yo‘naltirilgan usuldir. Joylashtirish usulida 

ma’lumotlar oddiy massiv sifatida ifodalangan bo‘ladi.  

Elementni jadvalga qo‘shishdan oldin uning adresi xesh-funksiya orqali 

aniqlanadi: 



A = h(K),

 bu erda 

K

 – kalit, 



A

 – jadvaldagi element adresi bo‘lib,   



 A 



 N-1,


 shart o‘rinli bo‘ladi. 

F

 xesh-funksiya deb 



R

 kiruvchi elementlar to‘plamini manfiy 

bo‘lmagan butun sonlar to‘plami 

Z

 ga akslantirishga aytiladi: 



    

F(r)=n, rϵR, nϵZ.

 

Xesh-adreslash bu xesh-funksiya qiymatlar sohasini qandaydir bir 



ma’lumotlar massivining yacheykasi, adresi sifatida foydalanishdan iborat. 

U holda ma’lumotlar massivi 



o‘lchami 

foydalanilayotgan xesh-

funksiyaning  

qiymatlar sohasiga 

mos kelishi kerak. 

Turli 

A

1



, A

2

, A



3

 

identifikatorlar uchun mos ravishda 



n

1

, n



2

, n


3

 

xesh-



funksiya qiymatlari to‘g‘ri kelsin. 

n

1



, n

2

, n



3

 

adreslarga mos yacheykalarda 



A

1

, A



2

, A


3

 

identifikatorlar haqida ma’lumot joylanadi. 



A

3

 identifikatorni 



qidirishda 

n

3



 adres qiymati hisoblanadi va tegishli jadval yacheykasidan 

ma’lumotlar tanlanadi. 



Bu metod juda effektiv, elementlarni jadvalga joylash vaqti ham, 

qidiruv vaqti ham faqat xesh-funksiyani hisoblashga ketadi. 

Bu usulning 2 ta yaqqol kamchiligi bor: 

 identifikatorlar jadvalining xotira hajmidan unumsiz foydalanilishi.

Massiv o‘lchami xesh-funksiya qiymatlar sohasiga mos kelishi kerak,

ayni vaqtda real holatda jadvalda saqlanayotgan identifikatorlar

ancha kam bo‘lishi mumkin.

 mos keluvchi xesh-funksiyani tanlay bilish.

Hesh-funksiyadan natija olish - 

“heshlash” 

simvollar zanjiri ustida 

oddiy arifmetik va mantiqiy amallarni bajarish hisobiga erishiladi. 



Hesh-adreslashda identifikatorlar jadvalining bir yacheykasiga 2 

ta turli xil bo‘lgan identifikatorlar joylashishi mumkin emas. Bu 

vaziyat, ya’ni 2 yoki undan ortiq identifikatorlar xesh funksiyaning bir 

xil qiymatiga ega bo‘lish xodisasi kolliziya deb nomlanadi. 

Demak, kolliziyaning yuzaga kelishi 2 ta har xil identifikator 

A



va 

A

2



larning Hesh-funksiya qiymatlari 

n

1



 va 

n

2



 

 bir xil 

(n

1

=n



2

bo‘lishi hisoblanadi



Hash jadvali va xash funktsiyasi 

Ilgari ushbu kontseptsiyada dasturchilar "To'g'ridan-to'g'ri 

manzillar jadvali" ni yaratishda foydalanganlar. To'g'ridan-to'g'ri 

manzillar jadvali "n" sonli noyob tugmachalarga ega bo'lsak, biz 

"n" uzunlikdagi qator hosil qilamiz va massivning indeksiga "i" 

elementini kiritamiz. Ushbu qator Hash Table deb nomlanadi. 

Ammo ushbu usul tufayli bizda har bir diapazonning 10 ta 

elementi etishmayapti, biz faqatgina 10 ta element uchun 1 

o'lchamdagi jadvalni yaratishimiz kerak. Qaysi biri xotirani 

behuda sarflaydi. 

Ushbu muammoga duch kelmaslik uchun biz xash jadvali 

(massivi) hajmini aniqlaymiz va shu jadvalga elementlarimizni 

Hash funktsiyasi deb nomlangan funktsiya yordamida xaritamiz. 

Ushbu funktsiya ushbu elementga berilgan elementni qaerga 

qo'yishni hal qiladi. Agar biz qidirishni xohlasak, avval xash 

funktsiyasini qo'llang, xash jadvalidagi elementning mavjudligini 

yoki yo'qligini hal qiling. 


Misol 

Bizda 1 dan 100 gacha raqamlar va 10 o'lchamdagi xash jadvali 

bor. Hash funktsiyasi 10-mod. Demak, 23 raqami (23 mod 10 = 3) 3-

xash jadvalining indeksiga tenglashtiriladi. 



 Mod10 

Hesh funksiya 

  Hesh jadval 

Ammo muammo shundaki, agar elementlarni (masalan, 2, 12, 

22, 32) kiritish kerak bo'lsa, ular faqat 2 indeksiga kiritishga harakat 

qilishadi. Ushbu muammo to'qnashuv deb ataladi. Ushbu to'qnashuv 

muammosini hal qilish uchun biz har xil xash funktsiyalari 

texnikasidan foydalanamiz.  

Ular quyida keltirilgan. 

 Zanjirband qilish 

 Ochiq manzil 



















1,2,3,4,….,100 

Elementlar. 


 Lineer zondlash 

 Kvadratik zondlash 

 Ikki marta xeshlash 

Ular to'qnashuvni hal qilish texnikasi deb ham ataladi. 



Zanjirband qilish

 

Xash jadvalda bitta elementni indeksga qo'yish o'rniga biz 

bog'langan ro'yxatni saqlaymiz. To'qnashuv sodir bo'lganda, biz 

ushbu elementni tegishli bog'langan ro'yxatga joylashtiramiz. Bu 

erda ko'rsatgichlar tufayli bo'sh joy behuda ketmoqda. 

Ochiq manzil 

Agar to'qnashuv bo'lsa, biz xash qiymatini yana mos 

keladigan xesh funktsiyasi yordamida hisoblaymiz. Ammo bu 

safar biz ushbu ma'lumotga ba'zi bir kichik o'zgartirishlar 

kiritamiz. 

"Probing" 

deb nomlangan elementni kiritish uchun 

bo'sh joyni qidirish jarayoni. 



Xash funktsiyasini tekshirish: h (k, i) 

bu erda k - kiritilishi kerak 

bo'lgan asosiy qiymat. Va men bu element bilan to'qnashuv soni.

 

Misol:


 Agar biz 2 ni qo'shsak, uning xash qiymatini 

h (2, 0) 

yordamida topamiz, chunki bu birinchi to'qnashuv. Deylik, ushbu 

funktsiya indeksiga javob (indeks) allaqachon ishg'ol qilingan bo'lsa, 

biz yana 

h (2, 1) 

xash funktsiyasiga murojaat qilishimiz kerak. 


Lineer zondlash

 

Xash funktsiyasi h ga teng, xash jadvali 

0

 dan 


n-1 

gacha bo'lgan 

bo'shliqlarni o'z ichiga oladi. 

Endi biz k elementini kiritmoqchimiz. 

H (k)

 ni qo'llang. Agar u "



x

" ga 


olib kelsa va 

"x" 


indeksida allaqachon qiymat mavjud bo'lsa, biz yana  

h (k, 1


) ning 

(h (k) + 1) 

mod n ga teng bo'lgan xash funktsiyasini qo'llaymiz. 

Umumiy shakli: 

h1 (k, j) = (h (k) + j) mod n

 

Masalan: funktsiyasi 5 bo'lgan 5 o'lchamdagi xash jadvali 0, 2, 3 



pozitsiyalarida to'ldirilgan bo'lsin. 

Endi yangi 10-element kiritishga harakat qiladi. 10 mod 5 = 0. Ammo 

indeks 0 allaqachon egallab olingan. Shunday qilib, keyingi (indeks 1) 

holatini tekshiradi (problar). Shunday qilib, 10 indeks 1 ga qo'shiladi. 

Endi 11-element kiritishga harakat qiladi. 11 mod 5 = 1. Ammo indeks 

1 allaqachon ishg'ol qilingan, u ham egallagan 2-indeksni tekshiring 

(ma'lumotlar berilgan), 3-band ham mavjud. Shunday qilib, u bo'sh 4 

indeksiga qo'shiladi. 

Keyingi bo'sh joyni chiziqli ravishda tekshirayotganini kuzatishimiz 

mumkin. Shunday qilib, bu 

chiziqli probing 

deb ataladi. 



Lineer probirovka bilan bog'liq muammolar:

 Boshlang'ich klasterlash: 

doimiy hujayralarni egallash imkoniyati mavjud, keyin yangi element 

kiritish ehtimoli kamayadi. Ushbu muammo birlamchi klasterlash deb 

nomlanadi 

Ikkilamchi klasterlash

: Agar ikkita xash funktsiyasida ikkita element 

bir xil qiymatga ega bo'lsa, ular bir xil problar ketma-ketligini bajaradilar. 



Kvadratik zondlash

 

Bu chiziqli tekshiruv bilan bir xil. Ammo to'qnashuv sodir 

bo'lganda biz turli funktsiyalardan foydalanamiz. Agar to'qnashuv 

sodir bo'lsa, bu element chiziqli masofa o'rniga kvadratik masofani 

egallashga harakat qiladi. 

Shu sababli "

Birlamchi klasterlash

" qisqartiriladi. Ammo 

ikkilamchi klasterlash bekor qilinmaydi. 

Ikki karra xashlash 

Bu erda ikkita xash funktsiyasidan foydalanamiz. 

h1 (k) = (h1 (k) + i h2 (k)) mod n. Bu erda h1 va h2 ikkita xash 

funktsiyasidir. 

Bu erda keyingi prob pozitsiyasi h1 va h2 ikkita funktsiyaga 

bog'liq bo'ladi. 


Ushbu usulning afzalliklari birlamchi klasterlash imkoniyati yo'q. 

Ikkilamchi klasterlash ham bekor qilindi. 



Zanjirband qilish va ochiq manzillar 

Zanjirband qilish 

Ochiq manzil 

Elementlarni stol tashqarisida saqlash 

mumkin 

Ochiq manzil elementlari faqat jadval 



ichida saqlanishi kerak 

Istalgan vaqtda zanjirlashda xash 

jadvalidagi elementlarning soni xash 

jadvalining kattaligidan kattaroq bo'lishi 

mumkin 

Ochiq manzilda xash jadvalidagi 



elementlar soni xash jadvalidagi indekslar 

sonidan oshmaydi. 

Yo'q qilishda zanjir eng yaxshi usul 

hisoblanadi 

Agar o'chirish talab qilinmasa. Faqat 

qo'shish va qidirish kerak, agar ochiq 

manzil bo'lsa yaxshi bo'ladi 

Zanjirband qilish ko'proq joy talab qiladi 

Ochiq adreslash zanjirga qaraganda 

kamroq joy talab qiladi. 



Kolliziya xolati. 

Kolliziya

 ro‘y berishini butunlay oldini oladigan, yaxshi xesh-

funksiyani qurish mumkinmi? 

Aniqki, butunlay kolliziyaga uchramasligi uchun xesh-

funksiyaning har bir natijaviy qiymati  

unikal


 bo‘lishi kerak. 

Kolliziya muammosini echish uchun turli usullarni qo‘llash 

mumkin. Ulardan biri 

“reheshlash” 

metodi hisoblanadi.  


Bu metodga ko‘ra, 

A

 element uchun xesh-funksiya orqali 



hisoblangan 

h(A) 


adresi band bo‘lgan yacheykani ko‘rsatsa, 

unda 


n

1

=h



1

(A) 


funksiya qiymatini hisoblash zarur va 

n

1



 adresga 

tegishli yacheykani bandligini tekshirish kerak. Agar 

n

1

 ham 



band bo‘lsa, unda 

h

2



(A) 

qiymat hisoblanadi, shu tariqa bo‘sh 

yacheyka to’lguncha yoki 

h

i



(A) 

navbatdagi qiymat 

h(A) 

bilan 


mos kelgunga qadar davom etadi. Oxirgi holatda 

identifikatorlar jadvali to‘lgan va bo‘sh joy boshqa yo‘q, degan 

xatolik to‘g‘risida ma’lumot beradi.  

h

i



(A) 

funksiyani hisoblashning eng oddiy metodi, uni 

h

i

(A)=(h(A)+p



i

)modN


m

 

asosida qurishdir, bu erda p



i

 qandaydir 

bir hisoblangan butun son

, N


m

 

–identifikatorlar jadvalidagi 



elementlarning maksimal soni. O‘z o‘rnida eng oddiy usul 

p

i



 

ni 


o‘rniga 

i

 ni qo‘yish bo‘ladi. Unda quyidagi formulani olamiz  



h

i

(A)=(h(A)+i)modN



m

.

 Bu holda xesh-funksiyaning bir xil 



qiymatlariga mos kelgan identifikatorlarni joylash uchun bo‘sh 

yacheykani qidirish mantiqan  hesh-funksiya 

h(A) 

ko‘rsatgan 



joydan boshlanadi.

 


 

 

 



 

 

C ++ da xeshlash dasturi 



Quyida C ++ da xeshlash yoki xash jadvali amalga oshiriladi:

  

Dastur: 

#include 

#include 

  

using namespace std; 



  

/* 


Bu ochiq manzilda chiziqli tekshirish uchun kod. Agar siz kvadrat probirovka qilishni va 

ikkilamchi xashlashni xohlasangiz, ular ham mavjud 

xash funktsiyasidan foydalanganda (kod + 1)% hFn-ni boshqa funktsiya bilan 

almashtirganimda ushbu koddagi manzilni ochish usullari. 

*/ 

void Insert(int ary[],int hFn, int Size){ 



    int element,pos,n=0; 

 cout<<"Qo'shish uchun asosiy elementni kiriting\n"; 

 cin>>element; 

 pos = element%hFn; 

 while(ary[pos]!= INT_MIN) {  // INT_MIN va INT_MAX hujayralar bo'shligini bildiradi. Agar 

hujayra bo'sh bo'lsa, tsikl buzilib, elementning qo'shilishi uchun pastdan pastga tushadi 

if(ary[pos]== INT_MAX) 

    break; 

pos = (pos+1)%hFn; 

n++; 


if(n==Size) 

    break;      // Agar jadval to'la bo'lsa, biz sindirishimiz kerak, agar buni tekshirmasak, 

pastadir cheksiz ko'chaga o'tadi. 

 } 


 if(n==Size) 

        cout<<"Xash jadvali elementlarga to'la edi\n Bu elementni kiritish uchun joy yo'q\n\n"; 

 else 

        ary[pos] = element;    //Element qo'shilmoqda 



void Delete(int ary[],int hFn,int Size){ 

 /* 

 o'chirish paytida juda ehtiyotkorlik bilan kuzatish talab etiladi. Ushbu o'chirish 



funktsiyasining kodini tushunish uchun dastur oxiridagi yozuvga qarang 

 */ 


 int element,n=0,pos; 

  

 cout<<"O'chirish uchun elementni kiriting\n"; 



 cin>>element; 

  

 pos = element%hFn; 



  

 while(n++ != Size){ 

   if(ary[pos]==INT_MIN){ 

    


cout<<"Element xash jadvalda topilmadi\n"; 

    


break; 

   } 


   else if(ary[pos]==element){ 

    


ary[pos]=INT_MAX; 

    


cout<<"Element o'chirildi\n\n"; 

    


break; 

   } 


   else{ 

    


pos = (pos+1) % hFn; 

   } 


 } 

 if(--n==Size) 

        cout<<"Element xash jadvalda topilmadi\n"; 

  



void Search(int ary[],int hFn,int Size){ 

 int element,pos,n=0; 

  

 cout<<"Qidirmoqchi bo'lgan elementni kiriting\n"; 



 cin>>element; 

  

 pos = element%hFn; 



  

 while(n++ != Size){ 

   if(ary[pos]==element){ 

    


cout<<"Element indeksda topildi "<

break; 

else 



    if(ary[pos]==INT_MAX ||ary[pos]!=INT_MIN) 

   pos = (pos+1) %hFn; 

 } 

 if(--n==Size) 



        cout<<"Element xash jadvalda topilmadi\n"; 

void display(int ary[],int Size){ 



 int i; 

 cout<<"Indeks\tQiymat\n"; 

 for(i=0;i

        cout<

int main(){ 



 int Size,hFn,i,choice; 

 cout<<"Xash jadvalining hajmini kiriting\n"; 

 cin>>Size; 

 int ary[Size]; 

    cout<<"Xash funktsiyasini kiriting[if mod 10 enter 10]\n"; 

 cin>>hFn; 

 for(i=0;i

        ary[i]=INT_MIN; //INT_MINni tayinlash katakning bo'shligini bildiradi 

 do{ 

cout<<"O'zingizning tanlovingizni kiriting\n"; 



cout<<" 1-> Kiritmoq\n 2-> O'chirish\n 3-> Displey\n 4-> Qidirilmoqda\n 0-> Chiqish\n"; 

cin>>choice; 

switch(choice){ 

case 1: 

Insert(ary,hFn,Size); 

break; 

case 2: 


Delete(ary,hFn,Size); 

break; 


case 3: 

display(ary,Size); 

break; 

case 4: 


Search(ary,hFn,Size); 

break; 


default: 

cout<<"To'g'ri tanlovni kiriting\n"; 

break; 

   } 


 }while(choice); 

 return 0; 

/* 


Izoh: O'chirish funktsiyasi va qidirish funktsiyasi uchun tushuntirish 

xash jadvalida 22, 32, 42 elementlari 2, 3, 4 indeks holatlarida bo'lsa deylik. 

Endi o'chirib tashlang (22). Belgilangan xash funktsiyasi bo'yicha biz avval 2-indeksni 

tekshiramiz. Topildi, shuning uchun o'chirildi. Va bu ko'rsatkichni nillga aylantiring. 

Keyin o'chirishni qo'llang (32). Bu safar u birinchi navbatda 2-indeksni tekshirdi, ammo 

uning hech narsasi yo'qligini aniqladi, keyin biz to'xtab, 32-element emas deymiz 

xash jadvalda topilgan. Ammo u 3-indeksda mavjud. Ammo boshqa indeksni tekshirishni 

yoki qilmaslikni qanday bilishimiz kerak? Buning uchun 

har qanday elementni o'chirib tashlaganimizda, INT_MAX bilan belgilaymiz, bu esa ilgari 

ba'zi bir elementlar hozirda mavjudligini bildiradi 



u o'chirildi. Shuning uchun bu erda to'xtamang, kerakli element keyingi indeksda 

ko'rsatilishi mumkin. 

*/ 

 

Natija: 

 


Xash jadvalining hajmini kiriting 

10 


Xash funktsiyasini kiriting[if mod 10 enter 10]

 

10 



O'zingizning tanlovingizni kiriting 

 1-> Kiritmoq 

 2-> O'chirish 

 3-> Displey 

 4-> Qidirilmoqda 


 0-> Chiqish 

Qo'shish uchun asosiy elementni kiriting 



12 

O'zingizning tanlovingizni kiriting 

 1-> Kiritmoq 

 2-> O'chirish 

 3-> Displey 

 4-> Qidirilmoqda 

 0-> Chiqish 

Qo'shish uchun asosiy elementni kiriting 



22 

O'zingizning tanlovingizni kiriting 

 1-> Kiritmoq 

 2-> O'chirish 

 3-> Displey 

 4-> Qidirilmoqda 

 0-> Chiqish 

Qo'shish uchun asosiy elementni kiriting 



32 

O'zingizning tanlovingizni kiriting 

 1-> Kiritmoq 

 2-> O'chirish 

 3-> Displey 

 4-> Qidirilmoqda 

 0-> Chiqish 

Indeks  Qiymat 



0       -2147483648 

1       -2147483648

2     12 

3     22 

4     32 

5  


-2147483648

6       -2147483648 

7       -2147483648 

8       -2147483648 

9       -2147483648 

O'zingizning tanlovingizni kiriting 

 1-> Kiritmoq 

 2-> O'chirish 

 3-> Displey 

 4-> Qidirilmoqda 

 0-> Chiqish 

O'chirish uchun elementni kiriting 



12 

Element o'chirildi 

O'zingizning tanlovingizni kiriting 

 1-> Kiritmoq 

 2-> O'chirish 

 3-> Displey 

 4-> Qidirilmoqda 

 0-> Chiqish 

Qidirmoqchi bo'lgan elementni kiriting 



32 

Element indeksda topildi 4 

O'zingizning tanlovingizni kiriting 

 1-> Kiritmoq 

 2-> O'chirish 

 3-> Displey 

 4-> Qidirilmoqda 

 0-> Chiqish 



To'g'ri tanlovni kiriting 



Download 1.23 Mb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling