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.