Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti telekomunikatsiya texnologiyalari fakulteti

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

TELEKOMUNIKATSIYA TEXNOLOGIYALARI FAKULTETI

413-20 GURUH TALABASI

Axmedov Abdunabi

“Ma`lumotlar tuzilmasi va algoritmlar“

fanidan

Mustaqil ish

Bajardi: Axmedov A.

Tekshirdi:Xojiyeva N.

Toshkent 2021

6-variant

Mavzu: Xesh funksiya va xeshlash algoritmlarini tuzish

Reja:

1.Xesh o`zi nima?

2. Xeshlash g’oyasining kelib chiqish tarixi.

3.Xesh funksiya deganda nima tushuniladi?

4. Xeshlash funktsiyasi xususiyatlarga nimalar kiradi?

5. Xesh funksiyaning axborot xavfsizlikdagi ahamiyati?

6. Xesh funksiya algoritmlarining tahlili.

7.Kolliziya holati.

Kalit so`zlar:Xesh-jadval, xesh funksiya, xeshlash,kolliziya

Maqsad: Ushbu mustaqil ishining maqsadi talabalar xesh funksiyalar va algoritmlari mavjudligini va ularning samaradorliklarini baholashni o’rganishlari kerak.

Vazifa: Talabalar topshiriq variantiga mos qidirish usuli yordamida masalani yechish dasturini yaratish ko’nikmasiga ega bo’lishlari kerak.

"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. • 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. Xesh-funksiya – 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 tuzilmasi.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.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 xush qiymatiga ega bo'lgan holatlar kolliziya (to'qnashuv) deb ataladi. 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.

1953-yilning yanvar oyida IBM firmasi hodimi Hans Peter Lun “xesh kodlash” g’oyasini taklif qildi. Keyinchalik Donald Knut Hansning g’oyasini sistematik qayta ishlab “xeshlash” deb e’lon qildi. 1956 yilda Angilyalik olim Arnold Dumi “Computers and automation”asarida “xeshlash” masalasiga e’tibor qaratdi. U programmistlarning ko’p ishlatiladigan belgilar tizimini avtomatlashtirish uchun “xeshlash” orqali “lug’at muammosini” yechishni, tub sonlarning bo’linishidan qolgan qoldiqlarni “xesh-addres”ga aylantirish orqali yechishni taklif qildi. 1957 yilda “IBM Journal of Research and Development” jurnalida Wesley Petersonning katta fayllardan matnlarni ishlash haqidagi maqolasi bosmadan chiqdi. Bu ilmiy ish “xeshlash” yo’nalishi bo’yicha “jiddiyish” deya e’tirof etildi. Wesley maqolasi “ochiq addres” deb nomlangan bo’lib, bu fayllardagi kiruvchi adreslar orqali chiquvchi adreslar natijasini solishtirishni anglatadi. Shu tariqa “xeshlash” prinsipi axborot kommunikatsiya texnalogiyalariga va axborot xavfsizligi sohalariga kirib boradi.

Xesh – funksiyaning ma’nosi, na’munaviy algoritmlar yordamida xesh funksiya qiymatini aniqlash bo’lib hisoblanadi. Odatda bu qiymat ikkilangan o’lchamda bo’ladi. Misol uchun, 64 bitlik xabar 128 bitlik xabarga aylanadi. Xesh kodni teskarisiga ixtiyoriy masalani yechish uchun tanlash mumkin. Bunda xeshlash xabarlarni solishtirish uchun ham qo’llaniladi.Xesh funksiya - Xeshlash funktsiyasi (xesh-funktsiyasi) shunday o’zgartirishki, kirish yo’liga uzunligi o’zgaruvchan xabar M berilganida chiqish yo’lida belgilangan uzunlikdagi qator h(M) hosil bo’ladi. Ya`ni 17 xesh-funktsiya h(.) argument sifatida uzunligi ixtiyoriy xabar (hujjat) ni qabul qiladi va belgilangan uzunlikdagi xesh – qiymat (xesh) H=H(M)ni qaytaradi.