12-mavzu. Xeshlash va xesh jadvallar Reja

Xeshlash funktsiyasi

Xeshlash funktsiyasi (xesh-funktsiyasi) shunday o’zgartirishki, kirish yo’liga uzunligi o’zgaruvchan xabar M berilganida chišish yo’lida belgilangan uzunlikdagi šator h(M) ќosil bo’ladi. Boshšacha aytganda, xesh-funktsiya h(.) argument sifatida uzunligi ixtiyoriy xabar (xujjat) M ni šabul šiladi va belgilangan uzunlikdagi xesh- šiymat (xesh) H=h(M)ni šaytaradi.

Xeshlash funktsiyasi šuyidagi xususiyatlarga ega bo’lishi lozim:

1. 
   Xesh-funktsiya ixtiyoriy o’lchamli argumentga šo’llanishi mumkin.
   
2. 
   Xesh-funktsiya chišish yo’lining šiymati belgilangan o’lchamga ega.
   
3. 
   Xesh-funktsiya h(x) ni ixtiyoriy "x" uchun yetarlicha oson ќisoblanadi. Xeshfunktsiyani ќisoblash tezligi shunday bo’lishi kerakki, xesh-funktsiya ishlatilganida elektron rašamli imzoni tuzish va tekshirish tezligi xabarning o’zidan foydalanilganiga šaraganda anchagina katta bo’lsin.
   
4. 
   Xesh-funktsiya matn M dagi orasiga šo’yishlar (vstavki), chišarib tashlashlar (vqbrosq), joyini o’zgartirishlar va ќ. kabi o’zgarishlarga sezgir bo’lishi lozim.
   
5. 
   Xesh-funktsiya šaytarilmaslik xususiyatiga ega bo’lishi lozim.
   
6. 
   Ikkita turli xujjatlar (ularning uzunligiga boђliš bo’lmagan ќolda) xeshfunktsiyalari šiymatlarining mos kelishi eќtimolligi juda kichkina bo’lishi shart,
   

ya’ni ќisoblash nuštai nazaridan h(x')=h(x) bo’ladigan x'≠ xni topish mumkin emas.

Xeshlash

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. Ushbu usulda ma’lumotlar kalitlari N akslantirish yordamida massiv indekslariga akslantiriladi. SHu sababli mazkur akslantirish «kalitlarni akslantirish» deb nomlanadi.

Elementni jadvalga qo’shishdan oldin uning adresi xesh-funktsiya orqali aniqlanadi: A = h(K), bu yerda K – kalit, A – jadvaldagi element adresi bo’lib,