Va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi

Shakl 14.3.
Ushbu jadvalning har bir satrida quyidagilar ko'rsatilgan: 3 harfdan iborat so'z, ASCII kodidagi ushbu so'zning sakkizburchak va o'nlik shakllardagi 21 bitli raqami va 64 va 31-jadvallarning o'lchamlari uchun standart modulli xesh funktsiyalari (ikkita o'ng ustun). 64-jadvalning o'lchami istalmagan natijalarga olib keladi, chunki hash qiymatini olish uchun faqat kalitning o'ng tomonidagi bitlar ishlatiladi va umumiy til so'zlaridagi harflar teng taqsimlanmagan. Masalan, y harfi bilan tugaydigan barcha so'zlarning xesh qiymati 57 ga teng. Aksincha, 31 ning oddiy qiymati jadvalda hajmning yarmidan ko'prog'iga kamroq to'qnashuvlarga olib keladi.
Modulli xeshni amalga oshirish juda oddiy, stolning kattaligi bosh raqam bo'lishi kerak. Ba'zi bir amaliy dasturlar uchun siz ozgina ma'lum bo'lgan tub sonlar bilan qoniqishingiz yoki jadvalning kerakli hajmiga yaqin bo'lgan tub sonlar ro'yxatiga qarashingiz mumkin. Masalan, 2 t - 1 ga teng bo'lgan raqamlar juda muhimdir t \u003d 2, 3, 5, 7, 13, 17, 19 va 31 (va t ning boshqa qiymatlari yo'qligi uchun)< 31 ): это известные простые числа Мерсенна. Чтобы динамически распределить таблицу нужного размера, нужно вычислить простое число, близкое к этому значению. Такое вычисление нетривиально (хотя для этого и существует остроумный алгоритм, который будет рассмотрен в части 5), поэтому на практике обычно используют таблицу заранее вычисленных значений (см. рис. 14.4). Использование модульного хеширования - не единственная причина, по которой размер таблицы стоит сделать простым числом; еще одна причина рассматривается в разделе 14.4.


Shakl 14.4.
Ikki n dan kam tub sonlarning jadvali , stolning o'lchami bosh bo'lishi uchun zarur bo'lganda, hash stolni dinamik ravishda tarqatish uchun ishlatilishi mumkin. Berilgan diapazondagi har qanday ijobiy qiymat uchun ushbu jadvaldan undan 2 martaga kam farq qiluvchi ko'payishni aniqlash uchun foydalanish mumkin.
Butun sonli tugmachalarni qayta ishlashning yana bir varianti multiplikativ va modulli usullarni birlashtirishdir: siz kalitni 0 va 1 oralig'idagi doimiyga ko'paytirishingiz kerak, keyin M. bo'linish modulini bajaring. Boshqacha aytganda, siz funktsiyadan foydalanishingiz kerak. Nazariy jihatdan g'ayritabiiy xatti-harakatlarga olib kelishi mumkin bo'lgan qadriyatlar, M va kalitlarni raqamlash tizimining samarali bazasi o'rtasida bog'liqlik mavjud, ammo agar siz a-ning ixtiyoriy qiymatidan foydalansangiz, haqiqiy dasturda har qanday muammo bo'lmaydi. Ko'pincha f \u003d 0.618033 ... (oltin nisbat) ning qiymati a sifatida tanlanadi.
Ushbu mavzudagi boshqa ko'plab o'zgarishlar o'rganildi, xususan, siljitish va niqobni tanlash kabi samarali mashina ko'rsatmalaridan foydalanib bajarilishi mumkin bo'lgan hash funktsiyalari (bog'lanishlar bo'limiga qarang).
Belgilar jadvalidan foydalanadigan ko'plab dasturlarda kalitlar raqam emas va ular qisqa bo'lishi shart emas; tez-tez bu juda uzun bo'lishi mumkin bo'lgan alfanumerik raqamlardir. Averylongkey kabi so'z uchun hash funktsiyasini qanday hisoblash mumkin?
7 bitli ASCII kodida bu so'z 84 bitli raqamga to'g'ri keladi \\ boshlash (tekislang *) 97 \\ cdot 128 ^ (11) va + 118 \\ cdot 128 ^ (10) + 101 \\ cdot 128 ^ (9) + 114 \\ ^ (3) \\\\ & + 107 \\ cdot 128 ^ (2) + 101 \\ cdot 128 ^ (1) + 121 \\ cdot 128 ^ (0), \\ end (tekislang *),
ko'pgina kompyuterlar bilan odatiy arifmetik funktsiyalarni bajarish uchun juda katta. Va ko'pincha siz uzoqroq tugmachalarni qayta ishlashingiz kerak.
Uzoq tugmachalar uchun modulli hash funktsiyasini hisoblash uchun ular qismlarga bo'laklarga aylantiriladi. Modul funktsiyasining arifmetik xususiyatlaridan foydalanishingiz va Horner algoritmidan foydalanishingiz mumkin (4.9 "Mavhum ma'lumot turlari" bo'limiga qarang). Ushbu usul tugmachalarga mos keladigan raqamlarni yozishning boshqa usuliga asoslangan. Ko'rib chiqilayotgan misol uchun biz quyidagi ifodani yozamiz: \\ boshlamoq (tekislang *) (((((((((((((((97) cdot 128 ^ (11)) 128) (+) 118) \\ cdot 128 ^ (10) + 101)) 9) + 114) \\ cdot 128 ^ (8) + 121) \\ cdot 128 ^ (7) \\\\ & + 108) \\ cdot 128 ^ (6) + 111) \\ cdot 128 ^ (5) + 110) \\ cdot 128 ^ (4) + 103) \\ cdot 128 ^ (3) \\\\ & + 107) \\ cdot 128 ^ (2) + 101) \\ cdot 128 ^ (1) + 121. \\ end (tekislang *)
Ya'ni, satrni belgilar kodlashiga mos keladigan o'nlik raqamni chapdan o'ngga qarab ko'rib chiqishda, to'plangan qiymatni 128 ga ko'paytirganda va keyingi belgining kod qiymatini qo'shganda hisoblash mumkin. Uzun simli holatda bu hisoblash usuli oxir-oqibat umuman kompyuterda namoyish etilishi mumkin bo'lganidan kattaroq songa olib keladi. Ammo bu raqam kerak emas, chunki uning M.ga bo'linishidan faqat kichik (kichik) qismi talab qilinadi.Natijani katta to'plangan qiymatni saqlamasdan olish mumkin, chunki hisoblash paytida istalgan vaqtda, siz M ga ko'paygan sonni tashlab yuborishingiz mumkin - har safar ko'paytirsangiz va qo'shsangiz, siz M. bo'linish modulining faqat qolgan qismini saqlashingiz kerak bo'ladi, natijada biz uzoq raqamni hisoblash va keyin bo'linishni amalga oshirish imkoniga ega bo'lgandek bo'lamiz (qarang). mashq 14.10). Ushbu kuzatish uzun simlar uchun modulli xesh funktsiyalarini hisoblash uchun to'g'ridan-to'g'ri arifmetik usulga olib keladi - 14.1 dasturiga qarang. Ushbu dasturda yana bitta, oxirgi hiyla qo'llaniladi: baza 128 o'rniga, u 127 raqamini ishlatadi. Ushbu o'zgarish sababi keyingi paragrafda muhokama qilinadi.
Horner (Horner) usuli yordamida modulli xeshlash bilan bir xil narxda xesh funktsiyalarini hisoblashning ko'p usullari mavjud (har bir belgi uchun bitta yoki ikkita arifmetik amallar). Tasodifiy kalitlar uchun ushbu usullar deyarli bir-biridan farq qilmaydi, ammo haqiqiy kalitlar kamdan-kam hollarda tasodifiydir. Kichkina narxga haqiqiy kalitlarni tasodifiy ko'rish qobiliyati tasodifiy xeshlash algoritmlarini ko'rib chiqishga olib keladi, chunki biz kalitlarning taqsimlanishidan qat'i nazar, tasodifiy jadval indekslarini yaratadigan hash funktsiyalariga muhtojmiz. Tasodifiylashtirishni tashkil qilish qiyin emas, chunki modulli hashing ta'rifiga so'zma-so'z rioya qilish shart emas - faqat M dan kichik bo'lmagan butun sonni hisoblashda kalitning barcha raqamlari ishlatilishi kerak.
M \u003d 96 va a \u003d 128 (yuqorida),
M \u003d 97 va a \u003d 128 (markazda) va
M \u003d 96 va a \u003d 127 (pastki)
Birinchi holda notekis taqsimlash bu harflarning notekis ishlatilishi va jadvalning kattaligi ham, omil ham 32 ga ko'payganligi sababli notekislikni saqlashning natijasidir. Boshqa ikkita misol tasodifiy ko'rinadi, chunki stol kattaligi va omil - bu nusxa raqamlari.
14.1-dastur buni amalga oshirishning bitta usulini ko'rsatadi: 2-quvvat o'rniga oddiy bazadan va ASCII-ning mag'lubiyatiga mos keladigan butun sondan foydalanish. Shaklda 14.5 rasm. 14.5-rasmda ushbu o'zgarish odatiy simli tugmalar uchun taqsimlashni qanday yaxshilaganligi ko'rsatilgan. Nazariy jihatdan, 14.1 dasturi tomonidan yaratilgan xash qiymatlari jadval jadvallari uchun 127 ga teng bo'lgan yomon natijalar berishi mumkin (garchi amalda bu deyarli ko'rinmas bo'lishi mumkin); Tasodifiy algoritmni yaratish uchun multiplikatorning qiymatini tasodifiy tanlash mumkin. Keyinchalik samaraliroq usul - bu hisoblashda koeffitsientlarning tasodifiy qiymatlari va kalitning har bir raqami uchun turli xil tasodifiy qiymatlardan foydalanish. Ushbu yondashuv universal hashing deb nomlangan tasodifiy algoritmni taqdim etadi.
Nazariy jihatdan ideal universal hash funktsiyasi - bu M o'lchamidagi jadvalda ikkita turli xil kalitlarning to'qnashuvi ehtimoli to'liq 1 / M bo'lgan funktsiya. 14.1 dasturida a koeffitsienti sifatida foydalanish qat'iy belgilangan qiymat emas, balki tasodifiy turli xil qiymatlar ketma-ketligi modulli xeshni universal xesh funktsiyasiga o'zgartirishi isbotlanishi mumkin. Biroq, kalitdagi har bir belgi uchun yangi tasodifiy raqamni yaratish qiymati odatda qabul qilinishi mumkin emas. Amalda, 14.1 dasturida ko'rsatilgan murosaga har bir kalit belgisi uchun turli xil tasodifiy raqamlar qatorini saqlash bilan emas, balki oddiy soxta tasodifiy tartib yaratish orqali koeffitsientlarni o'zgartirish orqali erishish mumkin.
Xulosa qilish uchun: mavhum belgilar jadvalini amalga oshirish uchun xeshdan foydalanish uchun avval siz M-jadval jadvalidan kichikroq manfiy bo'lmagan butun sonlarga kalitlarni joylashtiradigan xesh-operatsiyani kiritish uchun mavhum tipli interfeysni kengaytirish kerak.
Ushbu maqolaning bir qismi sifatida sizga aytaman