Xesh funktsiyasi nima? Kriptografik xesh funktsiyalari

Shakl 14.1.

0 dan 1 gacha bo'lgan suzuvchi nuqta raqamlarini o'lchamlari 97 ga teng jadval indekslariga aylantirish uchun biz bu raqamlarni 97 ga ko'paytiramiz. Ushbu misolda uchta to'qnashuv yuz berdi: 17, 53 va 76 ga teng bo'lgan indekslar uchun. kalit raqamlar, pastki raqamlar hech qanday rol o'ynamaydi. Hash funktsiyasini ishlab chiqishning maqsadlaridan biri bu nomutanosiblikni bartaraf etishdir, shunda hisoblash paytida har bir bit hisobga olinadi.

Agar kalitlar w-bit sonlari bo'lsa, ularni suzuvchi nuqta raqamlariga aylantirish mumkin va 0 dan 1 gacha bo'lgan suzuvchi nuqtali raqamlarni olish uchun 2 w ga bo'linadi va keyin oldingi paragrafdagi kabi M ga ko'paytiriladi. Agar suzuvchi nuqta bilan ishlash ko'p vaqtni talab qilsa va sonlar oshib ketishiga olib keladigan darajada katta bo'lmasa, butun arifmetik operatsiyalar yordamida bir xil natijani olish mumkin: kalitni M ga ko'paytirish kerak, so'ngra o'ng tomonga o'tish va w raqamlari bilan 2 ga bo'lish kerak. w (yoki, agar ko'paytirish toshib ketishga olib keladigan bo'lsa, siljishni bajaring va keyin ko'paytiring). Bunday usullar xeshlar uchun foydasiz, agar kalitlar diapazon bo'yicha bir tekis taqsimlanmasa, hash qiymati faqat kalitning etakchi raqamlari bilan belgilanadi.

W bitli butun sonlar uchun sodda va samaraliroq usul hashing usullaridan biri hisoblanadi - M o'lchamidagi eng katta stolni tanlash va M ga bo'linishni qolgan qismini hisoblash. h (k) \u003d k mod M har qanday k butun son uchun. Bunday funktsiya modulli xesh funktsiyasi deb ataladi. Hisoblash juda oson (C ++ da k% M) va u M qiymatidan kichik bo'lgan qiymatlar o'rtasida asosiy qiymatlarning teng taqsimlanishiga erishish uchun samaralidir. Kichik misol sek. 14.2.