Jizzax filiali amaliy matematika fakulteti «kompyuter ilmlari va dasturlashtirish»

OʻZBEKISTON RESPUBLIKASI OLIY VA O‘RTA MAXSUS TA’LIM VAZIRLIGI
MIRZO ULUG‘BEK NOMIDAGI MILLIY UNIVERSITETININIG
JIZZAX FILIALI



AMALIY MATEMATIKA FAKULTETI

«KOMPYUTER ILMLARI VA DASTURLASHTIRISH» kafedrasi

“ALGORITMLAR VA BERILGANLAR STRUKTURASI” FANIDAN

MUSTAQIL ISH

Mavzu: Satrlarni xeshlash masalasi

Bajardi: ’’ Komputer ilmlari va dasturlash texnologiyalari’’ yoʻnalishi 2-kurs 10-21-guruh talabasi Xolbo’tayev Kamoliddin

Tekshirdi: Tojiyev Maruf

Jizzax – 2023
Mavzu:Satrlarni heshlash masalasi

Reja:
1.Xeshlash

2.Xesh jadval va unga doir masalalar
3.Xesh funksiyalar
"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.
1.Xesh jadvalni tashkil etish: asosiy tushunchalar
Xeshlash – bu ma'lum bir turdagi va ixtiyoriy uzunlikdagikirishma'lumotlari massivini fiksirlangan uzunlikdagi chiquvchi bitlar qatoriga (butun son) aylantirish. Bunday akslantirish (aylantirish) xesh-funksiya deb ham ataladi. Xeshfunksiya – bukirishma’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. 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 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.
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 birtartibdashakllanadi.
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. 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.
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.
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 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 A1, A2, A3 identifikatorlar uchun mos ravishda n1, n2, n3 xesh-funksiya qiymatlari to‘g‘ri kelsin. n1, n2, n3 adreslarga mos yacheykalarda A1, A2, A3 identifikatorlar haqida ma’lumot joylanadi. A3 identifikatorni qidirishda n3 adres qiymati hisoblanadi va tegishli jadval yacheykasidan ma’lumotlar tanlanadi.
Turli A1, A2, A3 identifikatorlar uchun mos ravishda n1, n2, n3 xesh-funksiya qiymatlari to‘g‘ri kelsin. n1, n2, n3 adreslarga mos yacheykalarda A1, A2, A3 identifikatorlar haqida ma’lumot joylanadi. A3 identifikatorni qidirishda n3 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 metod juda effektiv, elementlarni jadvalga joylash vaqti ham, qidiruv vaqti ham faqat xesh-funksiyani hisoblashga ketadi.
Bu usulning 2 ta yaqqol kamchiligi bor:
1) 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.
2) mos keluvchi xesh-funksiyani tanlay bilish.
Xesh-funksiyadan natija olish - “xeshlash” simvollar zanjiri ustida oddiy arifmetik va mantiqiy amallarni bajarish hisobiga erishiladi.
Xesh-funksiyadan natija olish - “xeshlash” simvollar zanjiri ustida oddiy arifmetik va mantiqiy amallarni bajarish hisobiga erishiladi.
Xesh-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 A1 va A2larning xesh-funksiya qiymatlari n1 va n2 bir xil (n1=n2) bo‘lishi hisoblanadi.
Kolliziya xolati
Kolliziya ro‘y berishini butunlay oldini oladigan, yaxshi xesh-funksiyani qurish mumkinmi?
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 “rexeshlash” metodi hisoblanadi.
Bu metodga ko‘ra, A element uchun xesh-funksiya orqali hisoblangan h(A) adresi band bo‘lgan yacheykani ko‘rsatsa, unda n1=h1(A) funksiya qiymatini hisoblash zarur va n1 adresga tegishli yacheykani bandligini tekshirish kerak. Agar n1 ham band bo‘lsa, unda h2(A) qiymat hisoblanadi, shu tariqa bo‘sh yacheyka to’lguncha yoki hi(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.Bu metodga ko‘ra, A element uchun xesh-funksiya orqali hisoblangan h(A) adresi band bo‘lgan yacheykani ko‘rsatsa, unda n1=h1(A) funksiya qiymatini hisoblash zarur va n1 adresga tegishli yacheykani bandligini tekshirish kerak. Agar n1 ham band bo‘lsa, unda h2(A) qiymat hisoblanadi, shu tariqa bo‘sh yacheyka to’lguncha yoki hi(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.
hi(A) funksiyani hisoblashning eng oddiy metodi, uni hi(A)=(h(A)+pi)modNm asosida qurishdir, bu erda pi qandaydir bir hisoblangan butun son, Nm –identifikatorlar jadvalidagi elementlarning maksimal soni. O‘z o‘rnida eng oddiy usul pi ni o‘rniga i ni qo‘yish bo‘ladi. Unda quyidagi formulani olamiz hi(A)=(h(A)+i)modNm. Bu holda xesh-funksiyaning bir xil qiymatlariga mos kelgan identifikatorlarni joylash uchun bo‘sh yacheykani qidirish mantiqan xesh-funksiya h(A) ko‘rsatgan joydan boshlanadi.
hi(A) funksiyani hisoblashning eng oddiy metodi, uni hi(A)=(h(A)+pi)modNm asosida qurishdir, bu erda pi qandaydir bir hisoblangan butun son, Nm –identifikatorlar jadvalidagi elementlarning maksimal soni. O‘z o‘rnida eng oddiy usul pi ni o‘rniga i ni qo‘yish bo‘ladi. Unda quyidagi formulani olamiz hi(A)=(h(A)+i)modNm. Bu holda xesh-funksiyaning bir xil qiymatlariga mos kelgan identifikatorlarni joylash uchun bo‘sh yacheykani qidirish mantiqan xesh-funksiya h(A) ko‘rsatgan joydan boshlanadi.


C# dagi kodi
TmpHash bayt massivi endi manba ma'lumotlaringiz uchun hisoblangan xesh qiymatini (128-bit qiymati = 16 bayt) saqlaydi. Ko'pincha bunday qiymatni quyidagi kod amalga oshiradigan o'n oltilik qator sifatida ko'rsatish yoki saqlash foydali bo'ladi:
Console.WriteLine(ByteArrayToString(tmpHash));
static string ByteArrayToString(byte[] arrInput)
{
int i;
StringBuilder sOutput = new StringBuilder(arrInput.Length);
for (i=0;i < arrInput.Length; i++)
{
sOutput.Append(arrInput[i].ToString("X2"));
}
return sOutput.ToString();
}
Ikki bayt massivini solishtirishning eng oddiy usuli har bir alohida elementni ikkinchi qiymatdagi hamkasbi bilan taqqoslab, massivlar bo'ylab aylanishdir. Agar biron bir element boshqacha bo'lsa yoki ikkita massiv bir xil o'lchamda bo'lmasa, ikkita qiymat teng emas.
bool bEqual = false;
if (tmpNewHash.Length == tmpHash.Length)
{
int i=0;
while ((i < tmpNewHash.Length) && (tmpNewHash[i] == tmpHash[i]))
{
i += 1;
}
if (i == tmpNewHash.Length)
{
bEqual = true;
}
}


if (bEqual)
Console.WriteLine("Ikki hash qiymat bir hil");
else
Console.WriteLine("Ikki hash qiymat bir hil emas");
Console.ReadLine();
Xulosa.
Xeshlash va unga doir masalalar va jadvalllar haqida malumotlar
Foydalanilgan adabiyotlar.
1. A.P. Alferov, Kriptografiya asoslari.
Bryus Shnayer, amaliy kriptografiya.
2.https://learn.microsoft.com/en-us/troubleshoot/developer/visualstudio/csharp/language-compilers/compute-hash-value