Va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi

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.

Shakl 14.2.
O'ng tarafdagi uchta ustun chap tomonda ko'rsatilgan 16 bitli tugmachalarni quyidagi funktsiyalardan foydalanib yutish natijasini ko'rsatadi:
v% 97 (chapda)
v% 100 (markazda) va
(int) (a * v)% 100 (o'ngda),
bu erda a \u003d .618033. Ushbu funktsiyalar uchun jadval o'lchamlari mos ravishda 97, 100 va 100 bo'lib, qiymatlar tasodifiy ko'rinadi (chunki tugmalar tasodifiydir). Ikkinchi funktsiya (v% 100) faqat ikkita tugmachaning o'ng raqamlaridan foydalanadi va shuning uchun tasodifiy bo'lmagan tugmachalar uchun u yomon ishlashi mumkin.
Modulli hashing, shuningdek, suzuvchi nuqta tugmachalariga ham tegishli. Agar kalitlar kichik diapazonga tegishli bo'lsa, siz ularni 0 va 1, 2 w oralig'idagi raqamlarga w-bit sonlarini olish uchun o'lchashingiz mumkin va modulli hash funktsiyasidan foydalanishingiz mumkin. Yana bir variant - modulli hash funktsiyasining operandasi sifatida (agar mavjud bo'lsa) ikkilik kalitlarning vakili sifatida foydalanish.
Modulli xeshlash barcha holatlarda, kalitlarni tashkil etuvchi bitlarga kirish imkoniyati mavjud bo'lganda, ular mashinalar so'zi bilan ifodalangan butun sonlar, mashina so'zida keltirilgan belgilar ketma-ketligi yoki boshqa mumkin bo'lgan variantlardan qat'iy nazar foydalaniladi. Mashina so'ziga kiritilgan tasodifiy belgilar ketma-ketligi tasodifiy butun sonlar bilan bir xil emas, chunki kodlashda hamma bitlardan foydalanilmaydi. Ammo bu ikkala turni (va har qanday boshqa turdagi mashina so'ziga sig'adigan kodlangan) kichkina jadvalda tasodifiy indekslarga o'xshash qilish mumkin.
Modulli xeshlar uchun asosiy raqamni tanlashning asosiy sababi M hash jadvali sifatida sek. 14.3. 7-bitli kodlash bilan belgilar haqidagi ma'lumotlarning ushbu misolida, kalit bazasi bo'lgan raqam sifatida izohlanadi - kalitdagi har bir belgi uchun bitta raqam. Endi so'z 1816567 raqamiga mos keladi, uni ham shunday yozish mumkin
chunki ASCII kodida n, o va w belgilari 1568 \u003d 110, 1578 \u003d 111 va 1678 \u003d 119 raqamlariga mos keladi. Ushbu turdagi kalit uchun M \u003d 64 jadval o'lchamini tanlash muvaffaqiyatsiz tugadi, chunki 64 (yoki 128) ga ko'paytiriladigan x qiymatlarga qo'shish x mod 64 qiymatini o'zgartirmaydi - har qanday kalit uchun, hash funktsiyasining qiymati bu kalitning oxirgi 6 raqamining qiymati. Albatta, yaxshi hash funktsiyasi tugmachaning barcha raqamlarini, ayniqsa belgilar tugmachalarini hisobga olishi kerak. Shunga o'xshash vaziyatlar M darajasining 2-faktorini o'z ichiga olganda yuzaga kelishi mumkin. Buning oldini olishning eng oson yo'li M kabi bosh tanlamoqdir.