Fan Ma’lumotlar tuzilmasi mustaqil ish mavzu: Kalitlarni akslantirish (Heshlashtirish) usuli, samaradorligi xamda reheshlash usuli Guruh: 216-20 Bajardi: Valijonov n tekshirdi: Akbarova M

Ta’rif . 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.

Ma'lumotlar tarkibida Heshlash.

Qidiruv har qanday ma'lumotlar tuzilmasidan ustunlik qiladi. Barcha operatsiyalarni kiritish, o'chirish, yangilash uchun ko'p holatlar avval qidirishni talab qiladi. Shunday qilib, ma'lumotlar tuzilmasining qidiruv ishi vaqt murakkabligini aniqlaydi. Agar biron bir ma'lumot strukturasini olsak, qidirish uchun eng yaxshi vaqt murakkabligi

O (log n) AVL daraxtida va faqat tartiblangan massivda. Aksariyat hollarda O (n) vaqt talab etiladi. Ushbu qidiruv muammosini hal qilish uchun O (1) vaqtni talab qiladigan heshlash kontseptsiyasi taqdim etildi. Bu doimiy vaqt.


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.

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.

6. 
   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 A₁, A₂, A₃ identifikatorlar uchun mos ravishda n₁, n₂, n₃ xesh-funksiya qiymatlari to‘g‘ri kelsin. n₁, n₂, n₃ adreslarga mos yacheykalarda A₁, A₂, A₃ identifikatorlar haqida ma’lumot joylanadi. A₃ identifikatorni qidirishda n₃ 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 usulning 2 ta yaqqol kamchiligi bor:

• 
  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.
  

• 
  mos keluvchi xesh-funksiyani tanlay bilish.
  

Hesh-funksiyadan natija olish - “heshlash” simvollar zanjiri ustida oddiy arifmetik va mantiqiy amallarni bajarish hisobiga erishiladi.

Hesh-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 A₁ va A₂larning Hesh-funksiya qiymatlari n₁ va n₂ bir xil (n₁=n₂) bo‘lishi hisoblanadi.

Hash jadvali va xash funktsiyasi
Ilgari ushbu kontseptsiyada dasturchilar "To'g'ridan-to'g'ri manzillar jadvali" ni yaratishda foydalanganlar. To'g'ridan-to'g'ri manzillar jadvali "n" sonli noyob tugmachalarga ega bo'lsak, biz "n" uzunlikdagi qator hosil qilamiz va massivning indeksiga "i" elementini kiritamiz. Ushbu qator Hash Table deb nomlanadi. Ammo ushbu usul tufayli bizda har bir diapazonning 10 ta elementi etishmayapti, biz faqatgina 10 ta element uchun 1 o'lchamdagi jadvalni yaratishimiz kerak. Qaysi biri xotirani behuda sarflaydi.
Ushbu muammoga duch kelmaslik uchun biz xash jadvali (massivi) hajmini aniqlaymiz va shu jadvalga elementlarimizni Hash funktsiyasi deb nomlangan funktsiya yordamida xaritamiz. Ushbu funktsiya ushbu elementga berilgan elementni qaerga qo'yishni hal qiladi. Agar biz qidirishni xohlasak, avval xash funktsiyasini qo'llang, xash jadvalidagi elementning mavjudligini yoki yo'qligini hal qiling.

Misol

Bizda 1 dan 100 gacha raqamlar va 10 o'lchamdagi xash jadvali bor. Hash funktsiyasi 10-mod. Demak, 23 raqami (23 mod 10 = 3) 3-xash jadvalining indeksiga tenglashtiriladi.