HESH JADVALLAR VA ULARNI TASHKIL ETISH
![21
mda kiruvchi ma ’lumotning uzunligi 264 bitdan kichik bo ‘lib, xesh qiymat uzun-
ligi 160 bit bo ‘ladi. Kiritilayotgan ma ’lumot 512 bitlik blok larga ajratilib qayta
ishlanadi .
3.2. Sonlar uchun hesh -funksiyasi
Kalitlar: fayl hajmi - raqam.
Lug'atda saqlanadigan qiymat: fayl nomi.
Hash funktsiyasini ishlab chiqish talab qilinadi:
ℎ???????????? ℎ(�????????????�??????????????????� → [0 … 1023 ].](/data/documents/1bee1d5d-4c11-4f87-9572-3fcccea54ebd/page_21.png)
![24
#include <iostream>
#include <string.h>
using namespace std;
long long Heshlash(char s[])
{
long long h = 0;
int base = 37;
for(int i=0; i<=strlen(s); i++)
{
h = h* base + s[i] - 61 +1;
}
return h;
}
int main()
{
char s[100];
for(int i=1; i<10; i++)
{
cin.getline(s,100);
cout<<s<<" "<<Heshlash(s);
cout<<endl;
}}](/data/documents/1bee1d5d-4c11-4f87-9572-3fcccea54ebd/page_24.png)
1 O’ZBEKISTON RESPUBLIKASI OLIY VA O’RTA -MAXSUS TA’LIM VAZIRLIGI SAMARQAND DAVLAT UNIVERSITETI RAQAMLI TEXNOLOGIYALAR FAKULTETI DASTURIY INJINIRING YO`NALISHI 107 -GURUH TALABASI YO`LDOSHEV DAVRONBEKNING “ALGORITM VA MA’LUMOTLAR STRUKTURASI” FANIDAN “HESH JADVALLAR VA ULARNI TASHKIL ETISH” MAVZU- SIDA TAYYORLAGAN KURS ISHI Topshirdi: Yo‘ldoshev D Tekshirdi: Abdusalomova G .
2 Mundari ja KIRISH ................................ ................................ ................................ ................................ ................................ .. 3 I BOB. HESH JADVALLA RI ASOSLARI ................................ ................................ ................................ ......... 4 1.1.HESH TUSHUNCHASI ................................ ................................ ................................ ........................... 4 1.2. HESH ALGORITMLA RI ................................ ................................ ................................ ...................... 7 II BOB . KOLLIZIYA TUSHUNCH ASI ................................ ................................ ................................ ............ 10 2.1 KOLLIZIYA HAQID A TUSHUNCHA ................................ ................................ ............................... 10 2.2. KOLLIZIYA ANIQL IGI (COLLISION RESOL UTION) ................................ ................................ . 11 2.3 . OCHIQ ADRESLASH ................................ ................................ ................................ .......................... 16 III BOB. AMALIY MASA LALAR ................................ ................................ ................................ .................... 19 3.1.SATRLI FUNKSIYAL AR UCHUN HESH -FUNKSI YASINI QO ’LLASH ................................ ...... 19 3.2. SONLAR UCHUN HE SH -FUNKSIYASI ................................ ................................ ........................... 21 3.3.IKKILIK DARAXTLA RDA IZLASH VA HESH J ADVALLAR ................................ ...................... 22 HESH JADVALNI REALIZ ATSIYA QILISH ................................ ................................ ................................ . 22 XULOSA ................................ ................................ ................................ ................................ .............................. 28 ADABIYOTLAR ................................ ................................ ................................ ................................ ................. 29
3 Kirish Hozirgi kunda amaliy matematika va kibernetika fanining asosiy yo`nalishlaridan biri – tasvirlarni aniqlash masalasidir. Bu yo`nalishning muhimligi avvalo shu bilan asoslanadiki juda ko`pgina amaliy masalalar mavjudki, ularni to`liq matematik qa’tiylik bilan asoslangan metodlar bilan yechish qiyin yoki yechib bo`lmaydi. Bunday masalalarga, masalan, geologiya, texnika va tibbiyotda uchraydigan diagnost ika va bashorat qilish masalalari misol bo`la oladi. Tasvirlarni aniqlash masalalasi metodlarining bu sohalarda keng tarqalishing sabablarirdan yana biri, ularni tadbiqida bu sohalardagi boshlang`ich ma`lumotlarni yuqori darajada formallash talab qilinmayd i. Tasvirlarni aniqlash nazariyasi optimal yechimni axtarish muammosini diskret analogidir. Bu masalaga nafaqat eng yaxshi yechimni sintezi masalasi, balki boshqa muammoli amaliy masalalar sinfi ham keltiriladi. Hesh jadvali - bu assotsiativ massiv interfeysini amalga oshiruvchi ma'lumotlar tuzilmasi, ya'ni juftlarni saqlashga (kalit, qiymat) va uchta operatsiyani bajarishga imkon beradi: yangi juftlikni qo'shish, qidirish operatsiyasi va juftlikni kalit bilan o'chirish. Hesh jadvallarining ikkita asosiy varianti mavjud: zanjirli va ochiq adreslash. H esh jadvali ba'zi bir ?????? massivini o'z ichiga oladi, ularning elementlari juftliklar (ochiq adreslash bilan hesh jadvali) yoki juftliklar ro'yxati (zanjir bilan hesh jadvali). Hes hlash – bu ixtiyori uzunlikdagi kirish ma'lumotlari majmuasini ma'lum bir algoritm tomonidan bajarilgan, belgilangan o'lchamdagi chiqish massiviga aylantirish jarayoni. Bunday algoritmni amalga oshiruvchi funksiya hesh funktsiya , transformatsiya natijasi x ash yoki xash yig'indisi deyiladi. Hesh funktsiyasi quyidagi xususiyatlarga ega: - bir xil ma'lumotlar bir xil xashni beradi; - "deyarli har doim" turli xil ma'lumotlar boshqacha hesh beradi.
4 I BOB. Hesh jadvallari asoslari 1.1.Hesh tushunchasi Katta hajmdagi ma'lumotlarda ma'lumotlarni izlash jarayoni ko'p vaqt talab etadi, bu esa qidiruv kaliti yordamida sezilarli miqdordagi elementlarni ko'rish va taqqoslash zarurati bilan bog'liq. Ko'rish oynasini mahalliylashtirish orqali qidiruvni qisqartirish mu mkin. Misol uchun, ma'lumotlarni qidirish kaliti bo'yicha tartiblang, ularni biron bir guruh atributiga ko'ra bir -biriga mos kelmaydigan bloklarga bo'ling yoki haqiqiy ma'lumotlarni qidirish jarayonini soddalashtiradigan kod bilan moslang. Heshlash (yoki he shlash , inglizcha hashing ) - ma'lum turdagi va ixtiyoriy uzunlikdagi kirish ma'lumotlar massivini belgilangan uzunlikdagi chiqish bit qatoriga aylantirish. Bunda transformatsiyalar ham deyiladi. Hesh funktsiya- lari yoki konvolyutsiya funksiyalari va ularnin g natijalari deyiladi. Hash, hash kodi, hash jadvali yoki hazm qilish xabarlar (inglizcha) xabar dayjesti ). Hesh jadvali - bu ma'lumotlar tuzilishi, bu assotsiativ massiv interfeysini amalga oshiradi, ya'ni kalit -qiymat juftlarini saqlash va uchta amalni bajarish im- konini beradi: yangi juft qo'shish operatsiyasi, qidirish operatsiyasi va kalit bo'yi- cha juftlikni o'chirish operatsiyasi. Hesh -jadval - bu hesh funktsiyasi tomonidan ma'lum tartibda tuzilgan massiv. funksiya hisoblash uchun oddiy bo'lishi kerak; funksiya hesh -jadvaldagi kalitlarni iloji boricha bir tekis taqsimlashi kerak; funktsiya kalit qiymatlar o'rtasidagi hech qanday munosabatni manzil qiymatlari o'rtasidagi munosabatlarga moslashtirmasligi kerak; funktsiya to'qnashuvlar sonini minimal lashtirishi kerak, ya'ni turli tugmalar bitta hesh qiymatiga to'g'ri keladigan vaziyatlar (bu holda kalitlar deyiladi. si- nonimlar ). Bunda yaxshi hesh funksiyasining birinchi xossasi kompyuterning xususiyatlariga, ikkinchisi esa ma'lumotlar qiymatlariga bog 'liq. Agar barcha ma'lumotlar tasodifiy bo'lsa, hesh funktsiyalari juda oddiy bo'lar edi (kalitning bir necha bitlari kabi). Biroq, amalda tasodifiy ma'lumotlar
5 juda kam uchraydi va siz butun kalitga bog'liq bo'lgan funktsiyani yaratishingiz kerak. Agar he sh funksiyasi aholini taqsimlasa mumkin bo'lgan kalitlar indekslar to'plami ustidan bir xilda, keyin xeshlash kalitlar to'plamini samarali ravishda ajratadi. Eng yomoni, barcha kalitlar bitta indeksga xeshlanganda. To'qnashuvlar sodir bo'lganda, bir xil hesh jadvali katagiga da'vo qiluvchi kalitlarni saqlash uchun yangi joy topish kerak. Bundan tashqari, agar to'qnashu- vlarga ruxsat berilsa, u larning sonini kamaytirish kerak. Ba'zi maxsus holatlarda to'qnashuvlardan butunlay qochish mumkin. Misol uchun, agar barcha element kalitlari oldindan ma'lum bo'lsa (yoki juda kamdan -kam hollarda o'zgartirilsa), ular uchun ba'zi in'dektsion hesh funktsiya sini topish mumkin, bu ularni hesh jadvalining katakchalari o'rtasida to'qnashuvsiz taqsimlaydi. Hesh jadvallari quyidagilarga mos kelishi kerak xususiyatlari . Hesh -jadvalda operatsiyani bajarish kalitning hesh funktsiyasini hisoblashdan boshlanadi. Olingan hesh qiymati asl massivning indeksidir. Saqlangan massiv elementlari soni mumkin bo'lgan hesh qiymatlari soniga bo'linadi va bo'ladigan m uhim parametr , bu operatsiyalarning o'rtacha bajarilishi vaqtini belgilaydi. Qidiruv, kiritish va oʻchirish operatsiyalari oʻrtacha O(1) vaqtni olishi kerak. Biroq, bu taxmin massiv o'lchami qiymatini oshirish va hesh jadvaliga yangi juft- lik qo'shish bilan bog'liq bo'lgan hesh jadvali indeksini qayta tiklash uchun mum- kin bo'lgan apparat xarajatlarini hisobga olmaydi. To'qnashuvni hal qilish mexanizmi har qanday hesh jadvalining muhim qismidir. Heshing, mumkin bo'lgan qiymatlarning keng doirasi kichik hajmdagi xo- tirada saqlanishi kerak bo'lganda foydali bo'ladi va tez, deyarli tasodifiy kirish usuli kerak bo'ladi. Hesh -jadvallar ko'pincha ma'lumotlar bazalarida va ayniqsa, ma'lumotlar bazalarida qo'llaniladi til protsessorlari identifikatorlar jadvalini qayta ishlash tezligini oshiradigan kompilyatorlar va assemblerlar kabi. Kundalik hayotda xeshlashdan foydalanishga misollar kutubxonadagi kitoblarni tematik kataloglar bo'yicha taqsimlash, lug'atl arda so'zlarning birinchi harflari bo'yicha