Xesh funktsiyasi nima? Kriptografik xesh funktsiyalari

Xesh funktsiyasi nima? Kriptografik xesh funktsiyalari

Bizning qidiruv algoritmlarimiz odatda mavhum taqqoslash operatsiyasiga asoslangan. Ushbu ketma-ket, "Belgilar jadvallari va ikkilik qidirish daraxtlari" da tavsiflangan tarqatishni qidirish usuli ajralib turadi, unda i kaliti bo'lgan element to'g'ridan-to'g'ri kirishga imkon beradigan jadvalning i-pozitsiyasida saqlanadi. Distributiv qidirishda taqqoslash operatsiyalari emas, asosiy ko'rsatkichlar massiv ko'rsatkichlari sifatida ishlatiladi; Usulning o'zi kalitlarning jadval indekslari bilan bir xil diapazondagi turli xil sonlar ekanligiga asoslanadi. Ushbu bobda biz hashing usulini ko'rib chiqamiz, bunda kalitlar bunday qulay xususiyatlarga ega bo'lmagan odatdagi qidirish dasturlarida ishlatiladigan tarqatish qidiruvining ilg'or variantidir. Ushbu yondashuvni qo'llashning yakuniy natijasi taqqoslashga asoslangan usullardan mutlaqo farq qiladi - qidirish tugmachalarini elementlardagi kalitlar bilan taqqoslash orqali lug'at ma'lumotlari tuzilmalari bo'ylab harakatlanish o'rniga, kalitlarni jadval manzillariga arifmetik ravishda o'zgartirish orqali jadvaldagi elementlarga kirishga harakat qilamiz.

Xeshni ishlatadigan qidirish algoritmlari ikkita alohida qismdan iborat. Birinchi qadam qidirish kalitini jadvaldagi manzilga o'zgartiradigan hash funktsiyasini hisoblashdir. Ideal holda, turli xil tugmachalarni turli manzillarga solishtirish kerak edi, lekin ko'pincha ikkita yoki undan ko'p turli xil kalitlar jadvalda bir xil manzilni berishi mumkin. Shuning uchun, xesh qidirishning ikkinchi qismi bu kabi tugmachalarni qayta ishlaydigan to'qnashuvni hal qilish jarayoni. Ushbu bobda muhokama qiladigan mojarolarni hal qilish usullaridan biri bog'langan ro'yxatlardan foydalanadi, shuning uchun qidiruv kalitlari sonini oldindan taxmin qilish qiyin bo'lgan holatlarda dinamik vaziyatlarda darhol qo'llanilishini topadi. To'qnashuvlarni hal qilishning qolgan ikkita usuli yuqori natijalarga erishadi ishlash  qidirish, chunki narsalar sobit massivda saqlanadi. Ushbu usullarni takomillashtirish usulini ko'rib chiqamiz, bu esa jadval hajmini oldindan aniqlashning iloji bo'lmagan hollarda ulardan foydalanishga imkon beradi.

Hashing - vaqt va xotira o'rtasidagi muvozanatning yaxshi namunasidir. Agar ishlatilgan xotira hajmida hech qanday cheklov bo'lmasa, har qanday qidirishni faqat bitta xotiraga kirish bilan amalga oshirish mumkin, shunchaki kalitni xotira manzili sifatida tarqatish qidiruvidagi kabi ishlatish mumkin. Biroq, bu ideal holat odatda amalga oshirilmaydi, chunki uzun kalitlar juda ko'p xotirani talab qilishi mumkin. Boshqa tomondan, agar cheklovlar bo'lmasa qo'rg'oshin vaqti, ketma-ket qidirish usulidan foydalanib, minimal xotira bilan bajarish mumkin edi. Hashing - bu xotira va vaqtning maqbul miqdoridan foydalanish va ushbu ikkita haddan tashqari talablar o'rtasidagi muvozanatga erishishdir. Xususan, kodni qayta yozish va boshqa algoritmlarni tanlamaslik o'rniga jadvalning hajmini o'zgartirish orqali har qanday muvozanatni saqlashingiz mumkin.

Hashing - bu kompyuter fanining klassik vazifalaridan biri: uning turli xil algoritmlari sinchkovlik bilan o'rganilgan va keng qo'llanilmoqda. Biz shunchaki qat'iy taxminlar bilan emas, jadvalning o'lchamidan qat'i nazar, doimiy bajarilish vaqti bo'lgan belgilar jadvalini topish va kiritish uchun operatsiyalarni qo'llab-quvvatlashiga umid qilamiz.

Kutilayotgan qiymat ramzlar jadvalini har qanday amalga oshirish uchun eng maqbul nazariy samaradorlikdir, ammo hashing hali ham ikkita asosiy sababga ko'ra davo emas. Birinchidan, qo'rg'oshin vaqti  haqiqiy dasturlarda uzun tugmalarni ishlatishda ahamiyatli bo'lishi mumkin bo'lgan kalit uzunligiga bog'liq. Ikkinchidan, hashing boshqa belgi yoki saralash kabi belgilar jadvallari bilan boshqa operatsiyalarni samarali bajarilishini ta'minlamaydi. Ushbu bobda biz ushbu va boshqa masalalarni batafsil ko'rib chiqamiz.

Hash funktsiyalari

Avvalo, kalitlarni stol manzillariga o'zgartiradigan xesh funktsiyasini hisoblash muammosini hal qilish kerak. Odatda bu arifmetik hisob-kitobni amalga oshirish qiyin emas, lekin har xil nozik chuqurlarga tushmaslik uchun ehtiyot bo'lish kerak. Agar sizda M elementlari bo'lgan jadval mavjud bo'lsa, sizga klavishlarni butun sonlarga o'zgartiradigan funktsiya kerak. Ideal xesh funktsiyani hisoblash oson va tasodifiy funktsiyaga o'xshab ko'rinishi kerak: har qanday argumentlar uchun natijalar, ma'lum ma'noda, ehtimol teng bo'lishi kerak.

Xesh funktsiyasi kalit turiga bog'liq. To'g'ri aytganda, har bir mumkin bo'lgan kalit turi uchun alohida hash funktsiyasi talab qilinadi. Samaradorlikni oshirish uchun, odatda, arifmetik hisob-kitoblarda ishlatilishi mumkin bo'lgan mashina so'zlaridagi kalitlarning ikkilik tasvirini butun son sifatida ko'rib chiqish g'oyasiga murojaat qilish o'rniga, aniq turdagi konversiyani oldini olish maqsadga muvofiqdir. Hashing yuqori darajadagi tillar oldida paydo bo'ldi - dastlabki kompyuterlarda qiymatni simli kalit yoki butun son sifatida ko'rib chiqish odatiy hol edi. Ba'zi bir yuqori darajadagi tillarda ma'lum bir kompyuterda kalitlarning tasvirlanishiga bog'liq bo'lgan dasturlarni yaratish juda qiyin, chunki bunday dasturlar asosan mashinaga bog'liq va shuning uchun boshqa kompyuterga o'tish qiyin. Odatda, hash funktsiyalari kalitlarni butun sonlarga o'tkazish jarayoniga bog'liq, shuning uchun hash dasturlarida bir vaqtning o'zida ham mashinaning mustaqilligi, ham samaradorligini ta'minlash qiyin bo'lishi mumkin. Odatda, oddiy sonlar yoki suzuvchi nuqta tugmachalari faqat bitta mashinaning ishlashi bilan o'zgartirilishi mumkin, ammo simli tugmalar va boshqa turdagi kompozit kalitlar qimmatroq va samaradorlikka ko'proq e'tibor qaratadi.

Ehtimol, eng oddiy, bu tugmachalar belgilangan diapazondagi raqamlarni o'zgartirish paytida bo'ladi. Masalan, agar kalitlar 0 dan katta bo'lsa va 1 dan kichik bo'lsa, siz ularni M ga ko'paytirib, natijani kichikroq butun songa aylantirib, 0 va M - 1 oralig'ida manzil olishingiz mumkin; bunday misol Fig. 14.1. Agar kalitlar s dan kattaroq va t dan kichik bo'lsa, ularni s sonini ajratish va t-s ga bo'lish orqali o'lchash mumkin, natijada ular 0 dan 1 gacha bo'lgan qiymatlar oralig'iga tushadi va keyin M ga ko'payadi va jadvalda manzilni oladi.

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.

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.