Mustaqil ish mavzu: Xesh jadval va xesh funksiyalari

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.

Foydalanilgan adabiyotlar:

1. 
   [RU] Алфред В. Ахо., Джон Э. Хопкрофт, Джефри Д. Ульман. Структура данных и алгоритмы. //Учеб.пос., М.: Изд.дом: "Вильямс", 2000, — 384 с.
   
2. 
   [EN] Adam Drozdek. Data structures and algorithms in C++. Fourth edition.Cengage Learning, 2013.
   
3. 
   [UZ] Narzullaev U.X., Qarshiev A.B., Boynazarov I.M. Ma’lumotlar tuzilmasi va algoritmlar. //O’quv qo’llanma. Toshkent: Tafakkur nashriyoti, 2013 y. – 192 b.
   
4. 
   [RU] Лойко В.И. Структуры и алгоритмы обработки данных. Учебное пособие для вузов. - Краснодар: КубГАУ. 2000. - 261 с., ил.