Muhammad Al-Xorazmiy nomidagi
Toshkent axborot texnologiyalari universiteti
“Ma’lumotlar tuzilmasi va algoritmlar”
Mustaqil ish
Bajardi:
Mavzu: Hesh jadvallari va funksiyalari
Reja:
Kirish qism
Asosiy qism:
1.Xesh jadval nima
2. Xesh-funksiya turlari va qo’llanishi.
3. Xesh-funksiya va uning hossalari
Xulosa
Foydalanilgan adabiyotlar
"Xesh" so'zi ingliz tilidagi «hash» so’zidan olingan bo’lib, uning ma'nosi “shovqin” yoki “aralash” kabi ta'riflanadi. Aslida, bular atamaning haqiqiy ma'nosini to'liq ifodalaydi. Odatda “xeshlash” – bu jarayon bo’lib, ingliz tilida - chopish, aralashtirish kabi ma’nolarni anglatadi.
• Xeshlash – bu ma'lum bir turdagi va ixtiyoriy uzunlikdagi kirish ma'lumotlari massivini fiksirlangan uzunlikdagi chiquvchi bitlar qatoriga (butun son) aylantirish. Bunday akslantirish (aylantirish) xesh-funksiya deb ham ataladi. Xeshfunksiya – bu kirish ma’lumotlarini sonlarga aylantiruvchi funksiya bo’lib, bir xil ma’lumotlar to’plami hamma vaqt bir xil natija beradi.
•Xesh-jadval – bu elementlari “kalit-qiymat” juftliklari bo'lgan assotsiativ massiv shaklidagi ma'lumotlar tuzilmas
• Xeshlash assotsiativ massivlarni tashkil qilish uchun qo’llaniladi, bunda indekslari sonlar emas, balki ixtiyoriy qiymatlar bo’ladi. Xeshlashdan odatda matnlardan nusxalarning takrorlanishini qidirishda, ya'ni xesh-funksiyalarining bir xil qiymatiga ega bo'laklarni qidirishda foydalaniladi. Bundan tashqari, xeshlash ko'pincha parollarni saqlash uchun ishlatiladi; shu bilan birgalikda noyob identifikatorlarni yaratish uchun, masalan, agar fayl o'ziga xos nomni talab qilsa, siz ushbu faylni xeshlash natijasini hisoblab chiqishingiz va natijani faylga nom sifatida ishlatishingiz mumkin. Shuningdek, bu matnlarning nazorat summasini hisoblash uchun juda muhimdir. Aytaylik, foydalanuvchi tarmoq orqali bir nechta matn yuborishi kerak. Tekshirish summasi matn bilan birga uzatiladi, olinganidan keyin asl nusxasi bilan tekshiriladi. Agar summasi mos kelmasa, demak matnni uzatishda qandaydir xatolik bo’lganligi haqida xulosa qilish mumkin bo’ladi.
• Biroq, ko'pincha kirishdagi turli uzunlikdagi bir nechta turli xil ma'lumotlar, chiqishda bir xil ma'lumotlarga mos kelishi mumkin. Turli xil ma'lumotlar bir xil xesh qiymatiga ega bo'lgan holatlar kolliziya (to'qnashuv) deb ataladi (2-rasm). Bunday holda, xeshlash algoritmi har xil ma'lumotlarning har xil qiymatga ega bo'lishini ta'minlashga intilishi kerak. Kamdan kam hollarda kolliziyalarning oldini olish mumkin
2-rasm. Kolliziyaga misol: xeshlash natijasida xesh funksiya K2 va K3 kalitlar uchun bir xil qiymat bergan.
• Xesh-jadval – assotsiativ massivni tatbiq etish uchun qo’llaniladigan interfeys hisoblanadi. Unda kalitlar va xeshlangan kalitlardan tashkil topgan juftliklar saqlanadi. Xesh-jadval unga yangi juftlik qo’shish, kaliti bo’yicha juftliklarni qidirish va o’chirish imkonini beradi. Xesh-jadval xesh-funksiya tomonidan ma’lum bir tartibda shakllanadi.
• Xesh-jadvallari ko'pincha ma'lumotlar bazalarida, ayniqsa, kompilyatorlar va assemblerlar kabi til protsessorlarida qo'llaniladi, bu yerda ular identifikatorlar jadvalini qayta ishlash tezligini oshiradi.
Xesh-jadvallarni tatbiq qilish va xesh-funksiyani tanlash
• Xesh-jadvallar quyidagi xossalarga mos kelishi shart:
• Xesh-jadvalida amallarni bajarishdan oldin, kalitning xesh-funksiyasi hisoblanadi, natijada kirish massivdagi indeks hosil bo’ladi.
• Xesh jadvalini to'ldirish koeffitsienti - bu saqlanadigan massiv elementlari soni, xesh funksiyasining mumkin bo'lgan qiymatlari soniga bo'linadi. Bu operatsiyalarning o'rtacha bajarilish vaqti bog'liq bo'lgan muhim parametr hisoblanadi.
• Odatda yaxshi xesh-funksiya quyidagi shartlarni qonatlantiradigan funksiya ekanligi qabul qilinadi. Funktsiya: hisoblash nuqtai nazaridan sodda bo'lishi kerak (bu kompyuterning xususiyatlariga bog'liq), xesh jadvalga kalitlar iloji boricha teng taqsimlanishi (ma'lumotlar qiymatiga qarab), kolliziyalar sonini kamaytirishga harakat qilishi kerak. Funksiya asosiy kalitlar qiymatlari orasidagi bog'liqlikni manzil qiymatlari o'rtasidagi munosabat bilan taqqoslamasligi kerak.
Xeshlash funksiyasini hosil qilishga misollar
• Xeshlash uchun matn berilgan bo’lsin. U belgilar ketma-ketligidan iborat va berilgan matn uchun unikal (yagona) natija beruvchi xesh-funksiyani ishlab chiqish talab qilingan bo’lsin.
• Soddalik uchun 3-rasmda berilganidek bir nechta belgilar ketma-ketligini olamiz. Har bir belgining ost qismida ASCII jadvali bo’yicha mos kodi berilgan.
• Ushbu ketma-ketlikdagi har bir belgining sonli qiymatlari bo’yicha xeshfunksiyaning qiymatlarini tashkil qilish kerak. Bu qiymatlarni hosil qilish bilan belgilar to’plamini qayta ishlash mexanizmini o’ylash kerak bo’lgan xeshfunksiya shug’ullanadi
• Yoddan chiqarmaslik kerakki, xeshlangan kalit fiksirlangan uzunlikka ega bo’ladi, imkoni boricha kichik bo’lishi kerak. Xeshlashdan keyin kalit 8 razryaddan tashkil topgan bo’lsin, ya’ni 0 yoki 1 qiymatni qabul qiluvchi 8 bit uzunlikka ega deb olamiz. Shunga mos ravishda xesh-funksiyaning turli xil qiymatlari soni 28=256 ta (0 dan 255 gacha) variantda bo’lishi mumkin Kolliziya aniqligi
• Kolliziyalarni hal qilish kerak, chunki ularning buzilishi xesh-jadvaldan foydalanishda ma'lumotlar va ularning xeshlangan anologlari o'rtasidagi bir qiymatlilikni aniqlashni murakkablashtiradi.
• Buning uchun xesh-jadvalning yacheykalariga ilgari qo’shilgan kalit lar egallab turgan joyga davogarlik qiladigan kalitlarni saqlash uchun joy ajratilgan. Ushbu mexanizm zanjirlash usuli deb ataladi. Yoki, agar elementlarning barcha kalitlari oldindan aniqlangan bo’lsa, mos ravishda jadvalga qo'shilish jarayonida
elementlarni to'g'ridan-to'g'ri kataklarga taqsimlashning hojati yo'q, kalitlarni xeshjadvalning yacheykalari kolliziyasiz taqsimlaydigan ba’zi in’ektiv xesh funksiyani yaratish mumkin bo’ladi. Kolliziyani hal qilish mexanizmiga zarurat bo'lmagan bunday xesh- jadvallar, to'g'ridan-to'g'ri yoki ochiq adreslangan xeshjadvallar deb nomlanadi.
• Uning xususiy maydonlari va funksiyalaridan boshlaymiz. Faraz qilaylik, jadval maksimal yacheykalari soni bilan o’lchanadigan fiksirlangan o’lchamga ega bo’lsin.
• Tavsiya etiladigan ikkita usulni batafsil ko’rib chiqamiz.
Zanjirlash usuli:
Massivning har bir yacheykasi bir xil kalitning xesh-qiymatiga mos keladigan kalit-qiymat juftliklarining bog’langan ro’yxati (zanjir)ga ko’rsatkich hisoblanadi (6-rasm). Bir nechta element uzunligidagi zanjirlar paydo bo'lganda kolliziyalar kelib chiqadi.
• Shuning uchun, agar bittadan ko’p elementlardan tashkil topgan zanjirlarning har biri uchun elementlarni hisoblasak, bunday har bir yig'indidan bittasini ayirib, so'ngra bu natijalarning hammasini qo'shsak, kolliziyalarning umumiy sonini olamiz.
• Jadvalga ma'lumotlarni kiritish uchun xesh-funksiyaning oldindan topilgan qiymati bilan tegishli xesh-qiymatni zanjirning oxiridan yoki boshidan qo’shish kerak.
• Jadvaldan qandaydir ma’lumotlarni topish yoki o’chirish uchun, kirish ma’lumotining xesh qiymati bilan mos keladigan xesh qiymatli elementlar zanjirini topish yetarli bo’ladi. Keyin agar zanjir bitta elementdan iborat bo’lsa, butun zanjirni o’chirish mumkin, aks holda, zanjirning o'zida oldindan xeshlangan ma'lumotlar bilan emas, balki kalit orqali qidirishni tashkil qilish va elementni o'chirish kerak bo’ladi.
Xeshlash - bu ma’lumotlarning kirishdagi massivini determenistik algoritm bo’yicha chekli uzunlikdagi chiqish satriga aylantirishdir. Boshqacha aytganda, xeshlash - bu shunday jarayonki, uning kirishidagi massiv maxsus algoritm asosida chiqishda bitlar ketma-ketligiga almashtiriladi. Bunday almashtirish xesh-funksiya yoki o’rash funksiyasi deyiladi. Almashtirish natijasi esa xesh yoki xesh-kod yoki xabarlar qisqa izohi (o’rami) deb ataladi. Ikki massiv yoki satrning xesh-kodlari har xil bo’lishidan bu massivlar bir xil emas degan xulosa qilish mumkin. Xesh-kodlari bir xil bo’lishi esa massivlar bir xil bo’lishi muminligini ( ehtimoli borligini) bildiradi.
Xeshlash qo’llaniladigan holatlarga misollar:
· har bir elementi o’zoro biriktirilgan ikki qismdan iborat massivlar (masalan, lug’at shaklidagi massiv) hosil qilishda;
· ma’lumotlar to’plamida takrorlanuvchi elementlarni izlash uchun;
· ma’lumotlar to’plami uchun o’ziga xos takrorlanmaydigan ism (identifikator) topish uchun;
· ma’lumot saqlash yoki uzatishdagi tasodifiy yoki ataylab qilingan xatolarni aniqlash maqsadida nazorat uchun yig’indilarni hisoblashda;
· himoya tizimlarida parollarni saqlash uchun (bunda parol saqlanayotgan xotira sohasiga murojat paytida parolni bilib olish mumkin bo’lmaydi);
elektron imzoni ishlab chiqishda (amalda xabarlarning o’zi emas ularning xesh-shakli imzolanadi).
Umuman olganda, boshlang’ich ma’lumotlar va ularning xesh-kodlari o’rtasida o’zoro bir qiymatli moslik yo’q. Chunki xesh-funksiyasi qiymatlari soni kirish massivi variantlari sonidan kichik. Quyidagi jadvalda massivning turli variantlari va ularga mos nazorat yig’indilar keltirilgan (bunda xesh-funksiya qiymati massiv elementlari yig’indisidan iborat
|
T.n.
|
Massiv variantlari
|
Xesh-kod(nazorat yig’indi)
| |
1.
|
1;2
|
3
| |
2.
|
2;1
|
3
| |
3.
|
0;3
|
3
| |
4.
|
3;0
|
3
| |
5.
|
1;3
|
4
|
Bu jadvaldan ko’rinadiki, massivning turli variantlari bir xil xesh-kodga ega bo’lishi mumkin ekan.
Xesh-jadval - bu assotsiativ massiv interfeysini amalga oshiradigan ma’lumotlar tuzilmasi, ya'ni har bir elementi juftliklar (kalit, qiymat)ni saqlovchi tuzilma bo’lib, unda uchta operatsiyani bajarish imkoni mavjud: yangi juftlikni qo'shish, qidirish va kalit yordamida juftlikni o’chrish.
Turli xil tarkibga ega bo’lib, xesh –kodlari bir xil bo’lgan massivlar to’plami kolliziya deyiladi . Kolliziyalar yuzaga kelish ehtimoli tanlangan xesh-funksiyaning sifatini baholashda muhim ro’l o’ynaydi. Bu ehtimol miqdori qanchalik kichik bo’lsa, tanlangan xesh-funksiya shunchalik yaxshi bo’ladi.
Xesh-funksiya xossalari
Xeshlash algoritmlarining xossalari turlicha bo’lishi mumkin: masalan, razryadlilik, hisoblash murakkabligi, kriptomustahkamlik va hokozo. Boshqacha aytganda, ba’zi xesh-algoritmlarning asosiy xususyati unda ishlatilayotgan razryadlar soni bilan, ba’zilariniki hisoblashning murakkablik darajasi bilan bog’liq bo’ladi. Xesh-funksiya tanlashda yechilayotgan masalaning o’ziga xos xususiyatlari hisobga olinadi.
“Yaxshi” xesh-funksiya ikki xossaga ega bo’lishi kerak:
1) yuqori hisoblash tezligi;
2) kam miqdordagi “kolliziyalar”.
Quyidagi belgilashlarni olamiz:
K – “kalitlar” (kiritiladigan ma’lumotlar) soni;
h(k) - M dan katta bo’lmagan sondagi turli xil qiymatlarga ega bo’lgan xesh-funksiya, ya’ni ixtiyoriy k ϵ (0;K):h(k)“Yomon” xesh-funksiyaga misol keltiramiz: M=1000 bo’lib, o’n raqamli K natural songa uning kvadratiga teng yigirma raqamli son yozuvining o’rtasidan olingan uchta raqamdan iborat ketma-ketlikni mos qo’yuvchi funksiya. Bir qarashda bu funksiya uchun xesh-kodlar “000” va “999” lar o’rtasida tekis taqsimlanadi deb o’ylash mumkin. Lekin, agar berilgan son yozuvida chapda yoki o’ngdagi nollar soni juda katta bo’lgan hollar uchun tekis taqsimot buziladi.
Xesh-funksiya turlari
1)Bo’lish amaliga asoslangan xesh-funksiyalar
a) Mumkin bo’lgan barcha “xesh”lar soniga bo’lishda hosil bo’ladigan qoldiqni “xesh-kod” sifatida olish.
Kirishdagi ma’lumot qiymati M soniga bo’linib, hosil bo’gan qoldiq “xesh-funksiya” qiymati (“xesh”) deb olinadi, ya’ni h(k)=k mod M, bu yerda M-barcha mumkin bo’lgan “xesh”lar soni. Bu holda ko’rinib turibdiki, M juft bo’lib, k ham juft bo’lsa, xesh-funksiya qiymati juft bo’ladi. M juft bo’lib, k toq bo’lsa, funksiya qiymati toq bo’ladi. Kompyuter sanoq tizimining asosini M soni sifatida olish tavsiya qilinmaydi, chunki bunda xesh-kod k soni yozuvi o’ng tomonida joylashgan bir necha raqamlardangina bog’liq bo’lib qoladi va natijada kolliziyalar soni juda katta bo’ladi. Amaliyotda, odatda, M sifatida oddiy natural son olinadi va bu ko’p hollarda batamom qoniqarli tanlov hisoblanadi.
b) Xesh-kod sifatida xosil bo’ladigan ko’phad koeffitsientlari to’plamini olish.
Xesh-funksiyada kiritilgan ma’lumotlarni moduli 2 bo’lgan ko’phadga bo’lish amali bajariladi. Bu usulda M soni 2 ning biron darajasiga teng bo’lishi kerak. Kalitlar (K=kn-1kn-2…k0) ko’phad shakliga keltiriladi. Bu holda xesh-kod sifatida K ni ilgaridan tanlab olingan m-darajali P ko’phadga bo’lishda qoldiq sifatida hosil bo’lgan ko’phadning koeffitsientlarining qiymatlari olinadi:
K(x) mod P(x)=hm-1xm-1+…+h1x+h0
h(x)=hm-1hm-2…h1h0.
Bu usul P(x) ko’phad to’g’ri tanlanganda deyarli bir xil kalitlar o’rtasida kolliziyalar bo’lmasligini ta’minlaydi.
2) Xeshlashning mul’tiplikativ sxemasi.
Bu usul w coni bilan o’zaro tub bo’lgan A butun sonni tanlashdan iborat (w-mashina so’zida joylanishi mumkin bo’lgan eng kata butun son; IBM PC komp’yuterlar uchun w=232). Xesh-funksiya quyidagi ko’rinishda olinadi:
h(K)=[M[K*A/w]].
Bu holda, ikkilik sanoq tizimidagi kompyuterga, M soni 2 ning biron darajasiga teng va h(K) esa A*K ko’paytmaning o’ng yarmidagi kata nomerli bitlardan iborat bo’ladi.
3)O’zgaruvchan uzunlikdagi satrlarni xeshlash.
Yuqorida tavsiflangan usullar kalitlar bir necha so’zlardan tarkib topgan hollar hamda kalitlar uzunligi o’zgaruvchan bo’lgan xollar uchun ham o’rinli. Misol uchun so’zlarni w modul bo’yicha qo’shish yoki “istisno qiluvchi yoki“ amali yordamida bittaga birlashtirish mumkin. Shunday tamoyil asosida ishlaydigan algoritmlardan biri Pirson xesh-funksiyasidir. Pirson xeshlashi – bu Pirson tomonidan 8-bitli registrlarga ega bo’lgan protsessorlar uchun taklif qilgan algoritm bo’lib, uning vazifasi o’zgaruvchan uzunlikdagi satrlar uchun xesh-kodni yuqori tezlik bilan hisoblashdir.
Xesh-funksiya kirishiga har biri bir baytli n ta simvoldan iborat W so’z beriladi va chiqishida 0 dan 255 gacha diapozondagi qiymat olinadi. Xesh-kod qiymati kirishdagi so’zning har bir simvolidan bog’liq bo’ladi.
Kirishda W satrni qabul qiluvchi va o’rin almashtirishlar jadvali Tni ishlatadigan algoritmni quyidagicha tasvirlash mumkin:
h:=0
for each c in W loor
index: = h xor c
h:= T[index]
end loop
return h
Bu algoritmning afzalliklari:
· hisoblashlar oddiyligi;
· kolliziyalar ehtimoli eng kata bo’lgan kiruvchi ma’lumotlarning mavjud emasligi;
· o’zgartirib ideal xesh-funksiyalar olish imkoniyati.
Simvollardan (l ta) iborat K=x1x2…xl kalitlarni xeshlashning muqobil usuli sifatida h(K)=(h1(x1)+h2(x2)+…+hl(xl)) mod M formula bo’yicha hisoblashlarni olish mumkin.
4) Ideal xeshlash
Ideal xesh-funksiya deb shunday funksiyaga aytiladiki, u kalitlarning S naborining har bir kalitini butun sonlar to’plamiga kolliziyalarsiz akslantiradi. Matematik terminlar bilan aytilsa bu in’ektiv akslantirishdir.
Tafsifi:
1. h(k):U→[m] funksiya S€U uchun ideal xesh-funksiya deyiladi, agar u Sda in’ektiv bo’lsa.
2. h(k):U→[m] funksiya S€U uchun minimal xesh-funksiya deyiladi, agar u ideal xesh-funksiya bo’lib , hamda m=n=|S| bo’lsa.
3. Butun k≥1 uchun h(k):U→[m] funksiya S€U uchun k-ideal xesh–funksiya deyiladi, agar har bir j ϵ[m] uchun
│{x ϵ S}|h(x)=j}│≤k tengcizlik o’rinli bo’lsa.
Ideal xeshlash kalit xaqida xech qanday axborot saqlab qolmasdan unga takrorlanmas identifikatorlar berish zaruriyati paydo bo’lganda ishlatiladi.
Faraz qilaylik, hajmi kichik tezkor xotira mavjud va unda xeshlar saqlanadi. Xeshlar esa katta hajmli sekin xotiradagi malumotlar bilan bog’langan. Ushbu vaziyat ideal xeshlash ishlatishiga yaqqol misol bo’la oladi. Bundan tashqari, ideal xeshlash usuli grafni asosiy xotiraga joylashning imkoni bo’lmagan hollarda graf bilan ishlaydigan algoritmlarning tezkorligini oshirish uchun xam qo’llaniladi.
5) Universal xeshlash
Universal xeshlash deb shunday xeshlashga aytiladiki, unda bitta konkret xesh funksiya emas, balki berilgan to’plamdan tasodifiy algoritm asosida tanlab olingan xesh-funksiya ishlatiladi. Universal xeshlash odatda kolliziyalar sonining kichik bo’lishini ta’minlaydi.
Tavsifi:
Faraz qilaylik, kalitlarning U fazosidan olingan kalitlarni [m] sonlarga akslantirish kerak bo’lsin. Algoritm kirishiga n o’lchamli S U ma’lumotlar nabori berilgan. Xeshlashda kolliziyalar soni minimal bo’lishi talab qilinadi. Bunga ilgaridan belgilab qo’yilgan konkret bir xesh-funksiya bilan erishish mumkin emas. Bu muammo universal H={h:Uà[m]} oila deb ataladigan xesh-funksiyalarning to’plamidan xesh-funksiyani tasodifiy ravishda tanlab olish bilan hal qilinadi.
Kolliziyalar bilan kurashish usullari
Dastlabki paytlarda xesh–funksiyalar katta fayllarda izlashni tashkillashtirish uchun ishlatilar edi va shuning uchun xeshlashga oid dastlabki adabiyotlarda xesh–jadvallarda kolliziyalar bilan kurashish usullari bayon etilgan. Xesh-jadvallar uchun ikki usul mavjud:
1) zanjirsimon bog’lanish usuli;
2) ochiq adresslash usuli.
Birinchi usul xesh funksiyaning har bir qiymatiga bittadan Mta bog’lamli ro’yxat tashkillashtirishga asoslangan. Ro’yxatlarda bir xil qiymatli xesh-kod beruvchi kalitlar saqlanadi. Umumiy xolda, agar Nta kalitlar va Mta ro’yxatlar bor bo’lsa, xesh-jadvalning o’rtacha o’lchami N/M bo’ladi va xeshlash ishning o’rtacha miqdorini ketma-ket izlash algoritmiga nisbatan M marta kamayishiga olib keladi.
Ikkinchi usul jadval masssivida kalit–qiymat juftliklar saqlanishiga asoslangan. Bu xolda xavolalardan to’liq voz kechib, kerakli K kalit yoki bo’sh pozitsiya topilgunga qadar jadvalning yozuvlari birin-ketin qarab chiqiladi. Jadval yacheykalarini qarab chiqish ketma-ketligi tasodifiy urinishlar ketma ketligi deyiladi.
Xesh funksiyalarning qo’llanishi
Xesh funksiyalar kriptografiyaga juda ko’p ishlatiladi. Ulardan, shuningdek, turli ma’lumotlar strukturalarini (xesh-jadvallar, Blum fil’trlari kabi) tashkillashtirishda ham foydalinadi.
Kriptografiya xesh funksiyalariga qo’yiladigan asosiy talab -ularning kriptomustahkamligidir. Bu funksiyalar uchun argumentning kichik o’zgarishlarida funksiya qiymatining keskin (katta miqdorda) o’zgarishi juda muhimdir. Xususan, xeshning qiymati axborotning oqib chiqib ketishiga umuman yo’l qo’yilmasligi kerak, ya’ni argumentning hatto alohida olingan bitlari haqidagi axborot ham tashqariga chiqishi mumkin emas. Bu talab kalitni olish uchun foydalanuvchi parollarini xeshlash algoritmilarining kriptomustahkamligining garovidir.
Xeshlash, ko’pincha, elektron-raqamli imzo algoritmlarida ishlatiladi. Bu algoritmlarda xabarning o’zi emas, balki xesh-kodi shifrlanadi. Buning natijasida hisoblash vaqti kamayib, kriptomustahkamlik oshadi. Ko’p hollarda parollarning o’rniga ularning xesh-kodi saqlanadi.
“Nazorat yig’indilar” deb ataluvchi xesh-funksiyalar ma’lumot uzatish va saqlashda xatolarni oshkor qilish uchun ishlatiladi. Bu funksiyalar sifatida qiymatlarning yoki ularning bir qismining yig’indisini nazorat kodi sifatida oladi. Algoritmi esa murakkab bo’lmay, tezkorligi juda yuqori va uni amalga oshirish oson. Tasodifiy xatoliklarni, shu jumladan, apparatura xatoliklaridan himoyalanishda foydalaniladi.
Nazorat yig’indi xesh-funksiyalarida yuqori tezkorlikka erishish evaziga kriptomustahkamlik xususiyatidan boy beriladi. Bunda ilgaridan ma’lum yig’indiga moslab ma’lumot tuzib olish imkoniyati bor. Bundan tashqari kalliziyalar yuzaga kelish ehtimoli ham yuqori. Bunday algoritmga eng oddiy misol sifatida kirishdagi ma’lumotni 32 yoki 16 bitli so’zlarga bo’lish va ularning yig’indisini xisoblash algoritmini keltirish mumkin.
Nazorat yig’indi aloqa kanali orqali asosiy matn bilan birgalikda uzatiladi. Qabul qiluvchi tugunda nazorat yig’indi qaytadan hisoblanadi va uzatilgan nazorat yig’indi qiymati bilan solishtiriladi. Agar qiymatlar teng bo’lmasa, demak, ma’lumot uzatishda xato bor va uni qaytadan bajarish zarur degan xulosa chiqariladi.
Ma’lumot izlash algoritmini tezlashtirish uchun xesh-jadval tashkil qilinadi. Xesh-jadval - bu ma’lumotlar strukturasi bo’lib, unda “kalit - xesh-kod” juftliklari saqlanib, element izlash, yangi element kiritish va o’chirib tashlash amallari bajarilishi mumkin. Xesh-jadval ma’lumot izlash jarayonini tezlashtirishga xizmat qiladi. Ma’lumotlar bazasiga matnli maydonlar yozishda, dastlab, xesh – kod hisoblanadi va, keyin, ma’lumotlar bazasining ushbu xesh-kodga mos keluvchi bo’limiga matn joylashtiriladi. “Bo’lim kodi - xesh-kod” juftlik xesh-jadvaliga yozib qo’yiladi. Ma’lumotlar bazasida izlashni bajarish uchun, dastlab, izlanayotgan matn xesh-kodi hisoblanadi, xesh-jadvaldan unga mos bo’lim kodi aniqlanadi, keyin, ushbu bo’lim ichida izlash amalga oshiriladi. Shunday qilib, izlash butun ma’lumotlar bazasida emas, balki uning faqat bir bo’limida bajariladi. Natijada izlashga sarflanadigan vaqt kamayadi. Lug’atda so’zlarni alfavit tartibida joylashtirish bunga misol bo’la oladi. So’zning birinchi harfi uning xesh–kodi bo’lib xizmat qiladi. So’zni lug’atdan izlashda biz lug’atni to’liq boshdan oxirigacha ko’rib chiqmasdan, faqat birinchi harfga mos keluvchi bo’limdan izlaymiz
Xulosa:
Men ushbu xulosa yozishimdan maqsadim. Xesh funksiyalar va xesh algoritmlarini tuzish va haqida o’zimga ma’lumotlar oldim. Heshlash o’zi nima uni qanday amalga oshiriladi. Jadval lar qanday yaratiladi. Zanjirlash usuli nima ochiq adreslar usuli nima ekan degan savollarga javob oldim. Yetarli ko’nikma va malaka menda paydo bo’ldi.
|
