Kriptografik xesh funksiyasi. Xesh nima va u nima uchun

Guruch. 14.1.
0 va 1 oralig'idagi suzuvchi nuqtali raqamlarni hajmi 97 bo'lgan jadval indekslariga aylantirish uchun bu raqamlar 97 ga ko'paytiriladi. Bu misolda uchta to'qnashuv yuz berdi: 17, 53 va 76 indekslari uchun. Xesh qiymatlari ​kalitning eng yuqori bitlari bilan belgilanadi, eng kam ahamiyatli bitlar hech qanday rol o'ynamaydi. Xesh-funktsiyani ishlab chiqishning maqsadlaridan biri bu nomutanosiblikni to'g'irlashdir, shunda hisob-kitob paytida har bir bit hisobga olinadi.
Agar kalitlar w-bitli tamsayılar bo'lsa, ularni suzuvchi nuqtali raqamlarga aylantirish va 0 va 1 o'rtasidagi suzuvchi nuqta raqamlarini olish uchun 2 v ga bo'linishi mumkin, so'ngra oldingi xatboshidagi kabi M ga ko'paytiriladi. Agar suzuvchi nuqta operatsiyalari uzoq vaqt talab qilsa va raqamlar to'lib ketishiga olib keladigan darajada katta bo'lmasa, xuddi shunday natijani butun arifmetik amallar yordamida olish mumkin: siz kalitni M ga ko'paytirishingiz kerak, so'ngra w raqamlariga o'ngga siljitish kerak. 2 w ga bo'linadi (yoki ko'paytirish to'lib ketgan bo'lsa, siljishni va keyin ko'paytirishni bajaring). Bunday usullar xeshlash uchun foydasiz, agar kalitlar diapazon bo'ylab teng taqsimlanmasa, xesh qiymati faqat kalitning etakchi raqamlari bilan belgilanadi.
W-bitli butun sonlar uchun oddiyroq va samaraliroq usul, ehtimol, eng ko'p qo'llaniladigan xeshlash usullaridan biri - M o'lchami sifatida asosiy jadvalni tanlash va k ning qolgan qismini M ga hisoblash, ya'ni. h (k) = k mod M har qanday butun k kalit uchun. Bu funksiya modulli xesh funksiyasi deb ataladi. Hisoblash juda oson (C++ da k% M) va asosiy qiymatlarni M dan kichikroq qiymatlar orasida teng taqsimlashga erishish uchun samarali. Kichik misol rasmda ko'rsatilgan. 14.2.

Guruch. 14.2.
O'ng tomondagi uchta ustun chap tomonda keltirilgan 16-bitli kalitlarni quyidagi funktsiyalardan foydalangan holda xeshlash natijasini ko'rsatadi:
v% 97 (chapda)
v% 100 (markazda) va
(int) (a * v)% 100 (o'ngda),
bu erda a = .618033. Bu funksiyalar uchun jadval oʻlchamlari mos ravishda 97, 100 va 100. Qiymatlar tasodifiy koʻrinadi (chunki tugmalar tasodifiy). Ikkinchi funktsiya (v% 100) tugmachalarning faqat ikkita eng o'ng raqamidan foydalanadi va shuning uchun tasodifiy bo'lmagan tugmalar uchun yomon ishlashni ko'rsatishi mumkin.
Modulli xeshlash suzuvchi nuqtali kalitlarga ham tegishli. Agar tugmachalar kichik diapazonda bo'lsa, w-bitli butun sonlarni olish uchun ularni 0 dan 1,2 w gacha bo'lgan raqamlarga masshtablashtirib, modulli xesh funksiyasidan foydalanishingiz mumkin. Yana bir variant - modulli xesh funktsiyasi uchun operand sifatida kalitning ikkilik ko'rinishini oddiygina ishlatish (agar mavjud bo'lsa).
Modulli xeshlash kalitlarni tashkil etuvchi bitlarga kirish imkoni mavjud bo'lganda, ular mashina so'zining butun sonlari, so'z bilan to'ldirilgan belgilar ketma-ketligi yoki boshqa mumkin bo'lgan variant bo'ladimi, foydalaniladi. Mashina so'ziga to'plangan tasodifiy belgilar ketma-ketligi tasodifiy butun son kalitlari bilan bir xil emas, chunki kodlash uchun barcha bitlar ishlatilmaydi. Ammo bu ikkala turdagi (va mashina so'ziga moslash uchun kodlangan kalitlarning boshqa har qanday turi) kichik jadvaldagi tasodifiy indekslar kabi ko'rinishi mumkin.
Modulli xeshlash uchun M o'lchami sifatida asosiy xesh jadvalini tanlashning asosiy sababi rasmda ko'rsatilgan. 14.3. 7 bitli belgilar ma'lumotlarining ushbu misoli kalitni 128 ta asosiy raqam sifatida ko'rib chiqadi - kalitdagi har bir belgi uchun bitta raqam. Bu so'z endi 1816567 raqamiga to'g'ri keladi, uni shunday yozish ham mumkin
chunki ASCII da n, o va w belgilari 1568 = 110, 1578 = 111 va 1678 = 119 raqamlariga mos keladi. Ushbu turdagi kalit uchun jadval o'lchami M = 64 ni tanlash muvaffaqiyatsiz tugadi, chunki x ga 64 (yoki 128) ga karrali qiymatlarni qo'shish x mod 64 qiymatini o'zgartirmaydi - har qanday kalit uchun, qiymati xesh funksiyasi bu kalitning oxirgi 6 bitining qiymati. Albatta, yaxshi xesh funksiyasi kalitning barcha raqamlarini hisobga olishi kerak, ayniqsa belgilar kalitlari uchun. M 2 ning darajali koeffitsientini o'z ichiga olganida shunga o'xshash vaziyatlar yuzaga kelishi mumkin. Bunga yo'l qo'ymaslikning eng oddiy usuli M sifatida tub sonni tanlashdir.