Kommunikatsiyalarni rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti
Download 0.68 Mb. Pdf ko'rish
|
MTvaA Mustaqil Ish1
|
O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARNI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
Ma’lumotlar tuzilmasi
Mavzu: Kalitlarni akslantirish (Heshlashtirish) usuli, samaradorligi xamda reheshlash usuli Guruh: 416 - 19 Bajardi: Shexnazarov Umar Tekshirdi: Akbarova Marg’uba Toshkent-2020 Kalitlarni akslantirish (Heshlashtirish) usuli, samaradorligi xamda reheshlash usuli 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.
Hesh so’zi ingliz tilidagi hash so’zidan olingan bo’lib, chalkash ( putanisa) yoki aralashma (meshanina) ma’nosini anglatadi
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.
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, 0 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
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.
“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 1 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.
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.
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.
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
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.
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. */
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; }
ary[pos]=INT_MAX; cout<<"Element o'chirildi\n\n"; break; }
} }
pos = (pos+1) % hFn; if(--n==Size) cout<<"Element xash jadvalda topilmadi\n"; }
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 "< } else
} break;
if(ary[pos]==INT_MAX ||ary[pos]!=INT_MIN) pos = (pos+1) %hFn; if(--n==Size) cout<<"Element xash jadvalda topilmadi\n"; }
int i; cout<<"Indeks\tQiymat\n"; for(i=0;i cout< }
cout<<"Xash jadvalining hajmini kiriting\n";
int ary[Size]; cout<<"Xash funktsiyasini kiriting[if mod 10 enter 10]\n"; cin>>hFn;
for(i=0;i
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; }
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. */
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 1 Qo'shish uchun asosiy elementni kiriting 12 O'zingizning tanlovingizni kiriting 1-> Kiritmoq 2-
> O'chirish 3-
> Displey 4-
> Qidirilmoqda 0-> Chiqish 1 Qo'shish uchun asosiy elementni kiriting 22 O'zingizning tanlovingizni kiriting 1-> Kiritmoq 2-
> O'chirish 3-
> Displey 4-
> Qidirilmoqda 0-> Chiqish 1 Qo'shish uchun asosiy elementni kiriting 32 O'zingizning tanlovingizni kiriting 1-> Kiritmoq 2-
> O'chirish 3-
> Displey 4-
> Qidirilmoqda 0-> Chiqish 3 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 2 O'chirish uchun elementni kiriting 12 Element o'chirildi
1-> Kiritmoq 2-
> O'chirish 3-
> Displey 4-
> Qidirilmoqda 0-> Chiqish 4 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 0
Xulosa Man Shexnazarov Umar Hesh jadvallari va funksiyalari mavzusida mustaqil ishladim va kerakli ma’lumotlarni topib o’rgandim va amalda qo’llab ko’rdim.Man bu mavzudan o’zimga kerakli xulosalarni chiqardim. E’tiboringiz uchun raxmat. Download 0.68 Mb. Do'stlaringiz bilan baham: 
|