Kriptografik xesh funksiyasi. Xesh nima va u nima uchun

Dastur 14.1. String kalitlari uchun xesh funksiyasi
M = 96 va a = 128 (yuqorida),
M = 97 va a = 128 (markazda) va
M = 96 va a = 127 (pastki)
Birinchi holatda notekis taqsimlanish harflarning notekis qo'llanilishi va notekislikning davom etishi natijasidir, chunki jadval o'lchami ham, ko'paytiruvchi ham 32 ga karrali bo'ladi. Qolgan ikkita misol tasodifiy ko'rinadi, chunki jadval hajmi va omili nisbatan tub sonlar.
14.1-dastur buni amalga oshirishning bir usulini ko'rsatadi: 2 ning darajasi o'rniga oddiy tayanch va satrning ASCII tasviriga mos keladigan butun sondan foydalanish. Shaklda. 14.5 rasm. 14.5-rasmda bu o'zgarish odatiy string kalitlari uchun taqsimotni qanday yaxshilashini ko'rsatadi. Nazariy jihatdan, dastur 14.1 tomonidan yaratilgan xesh qiymatlari 127 ga ko'payadigan jadval o'lchamlari uchun yomon natijalar berishi mumkin (garchi amalda bu deyarli ko'rinmas bo'lsa ham); tasodifiy algoritm yaratish uchun multiplikatorning qiymatini tasodifiy tanlash mumkin. Bundan ham samaraliroq yondashuv - hisoblashda koeffitsientlarning tasodifiy qiymatlari va har bir asosiy raqam uchun turli xil tasodifiy qiymatlardan foydalanish. Ushbu yondashuv universal xeshlash deb ataladigan tasodifiy algoritmni beradi.
Nazariy jihatdan ideal universal xesh funksiyasi M o‘lchamli jadvaldagi ikki xil kalit o‘rtasidagi to‘qnashuv ehtimoli aynan 1/M ga teng bo‘lgan funksiyadir. 14.1 Dasturda a koeffitsienti sifatida qat'iy belgilangan ixtiyoriy qiymat emas, balki tasodifiy turli xil qiymatlar ketma-ketligidan foydalanish modulli xeshlashni universal xesh funktsiyasiga aylantirishini isbotlash mumkin. Biroq, kalitdagi har bir belgi uchun yangi tasodifiy sonni yaratish narxi odatda qabul qilinishi mumkin emas. Amalda, 14.1-dasturda ko'rsatilgan kelishuvga har bir kalit belgisi uchun turli xil tasodifiy sonlar qatorini saqlamasdan, oddiy psevdo-tasodifiy ketma-ketlikni yaratish orqali koeffitsientlarni o'zgartirish orqali erishish mumkin.
Xulosa qilib aytadigan bo'lsak, mavhum belgilar jadvalini amalga oshirishda xeshlashdan foydalanish uchun avvalo mavhum turdagi interfeysni M jadvalining o'lchamidan kichikroq manfiy bo'lmagan butun sonlarga kalitlarni xaritalashadigan xesh operatsiyasini kiritish uchun kengaytirish kerak.
U