Mustaqil ishi mavzu: Ma’lumotlarni xeshlash argoritmlari

Muhammad al-Xorazmiy nomidagi
Toshkent Axborot texnologiyalari Universiteti
Samarqand filiali
“Telekammunikatsiya texnologiyalari va kasb
ta’limi” fakulteti
21-01 guruh 2-bosqich talabasi
Sharipov Ruslanning
Ma’lumotlar tuzilmasi va algoritmlar fanidan

Mustaqil ishi


MAVZU: Ma’lumotlarni xeshlash argoritmlari








REJA:

1. 
   Xeshlash nima?
   
2. 
   Xesh funksiyalar
   
3. 
   Xesh-jadvallardagi to'qnashuvlarni bartaraf etish usullar
   

Xeshlash yoki xeshlash(ing. xeshlash) - ixtiyoriy uzunlikdagi kirish ma'lumotlari massivini ma'lum bir algoritm yordamida amalga oshiriladigan belgilangan uzunlikdagi (chiqish) bit qatoriga aylantirish. Algoritmni amalga oshiradigan va o'zgartirishni amalga oshiradigan funktsiya deyiladi. hash funktsiyasi "yoki" konvolyutsiya funktsiyasi ". Asl ma'lumotlar kirish massivi deb ataladi " kalit"yoki" xabar ". Transformatsiyaning natijasi (chiqish) " hash », « hash kodi », « hash summasi ”, “xabar xulosasi”.
Hashing quyidagi hollarda qo'llaniladi:
assotsiativ massivlarni qurishda;
bir qator ma'lumotlar to'plamida dublikatlarni qidirishda;
ma'lumotlar to'plami uchun noyob identifikatorlarni qurishda;
ma'lumotlardan (signaldan) nazorat summalarini hisoblashda ma'lumotlarni saqlash va (yoki) uzatish paytida yuzaga keladigan xatolarni (tasodifiy yoki qasddan kiritilgan) keyinchalik aniqlash uchun;
parollarni saqlashda himoya tizimlarida xesh-kod ko'rinishida (xesh-kod yordamida parolni tiklash uchun ishlatiladigan xesh funktsiyasiga teskari funktsiya talab qilinadi);
elektron imzoni ishlab chiqishda (amalda ko'pincha xabarning o'zi emas, balki uning "xesh tasviri" imzolanadi);
va boshq.
"Xesh funktsiyalari" turlari
"Yaxshi" xesh funktsiyasi ikkitani qondirishi kerak xususiyatlari:
tez hisoblash;
minimal "to'qnashuvlar" soni.
Keling, belgi bilan tanishtiramiz:
∀ k ∈ (0 ; K) : h (k)< M {\displaystyle \forall k\in (0;\,K):h(k)<="" span="" >.
"Yomon" xesh-funktsiyaga misol bilan funksiya hisoblanadi M = 1000 (\displaystyle M=1000), bu o'n xonali natural son K (\displaystyle K) solishtiradi uch sonning yigirma xonali kvadratining o'rtasidan tanlangan raqamlar K (\displaystyle K). Ko'rinishidan, "xesh kodlari" qiymatlari bo'lishi kerak teng ravishda orasida taqsimlanadi 000 "va" 999 ", lekin " uchun haqiqiy» ma’lumotlar, bu faqat “ kalitlari” ning “koʻp” soni chap yoki oʻng nollari yoʻq.
Keling, "xesh-funksiyalar" ning oddiy va ishonchli amalga oshirilishini ko'rib chiqaylik.
Bo'linishga asoslangan "xesh funktsiyalari"
1. "Xesh kodi" barcha mumkin bo'lgan "xeshlar" soniga bo'linishning qolgan qismi sifatida
Xesh funktsiyasi "xesh" ni kiritilgan ma'lumotlarni bo'lishning qolgan qismi sifatida hisoblashi mumkin M (\displaystyle M):
h (k) = k mod M (\ displaystyle h (k) = k \ mod M)
qayerda M (\displaystyle M)- barcha mumkin bo'lgan "xeshlar" soni (chiqish ma'lumotlari).
Bu holda, bu bir tekis uchun, deb ochiq-oydin bo'ladi M (\displaystyle M) funksiyaning qiymati hatto bo'lsa ham bo'ladi k (\displaystyle k) va g'alati - g'alati bilan k (\displaystyle k). sifatida ham ishlatilmasligi kerak M (\displaystyle M) kompyuterning raqam tizimining asos darajasi, chunki "xesh-kod" faqat bog'liq bo'ladi bir nechta raqamning raqamlari k (\displaystyle k) o'ng tomonda joylashgan bo'lib, bu ko'p sonli to'qnashuvlarga olib keladi. Amalda, odatda oddiyni tanlaydi M (\displaystyle M); ko'p hollarda bu tanlov juda qoniqarli.
2. “Xesh-kod” hosil bo‘lgan ko‘phadning koeffitsientlari to‘plami sifatida
Xesh-funktsiya kirish ma'lumotlarini polinom tomonidan modul-ikki bo'linishni amalga oshirishi mumkin. Ushbu usulda M (\displaystyle M) ikkining kuchi bo'lishi kerak va ikkilik kalitlar ( K = k n - 1 k n - 2. . . k 0 (\displaystyle K=k_(n-1)k_(n-2)...k_(0))) shaklida taqdim etiladi polinomlar, "xesh-kod" sifatida koeffitsientlarning qiymatlari "qabul qilinadi" polinom, kirishni bo'lishning qolgan qismi sifatida olinadi K (\displaystyle K) oldindan tanlangan polinomga P (\displaystyle P) daraja m (\displaystyle m):
K (x) mod P (x) = hm − 1 xm − 1 + ⋯ + h 1 x + h 0 (\displaystyle K(x)\mod P(x)=h_(m-1)x^(m- 1)+\nuqtalar +h_(1)x+h_(0)) h (x) = h m - 1 . . . h 1 h 0 (\displaystyle h(x)=h_(m-1)...h_(1)h_(0))
To'g'ri tanlov bilan P (x) (\displaystyle P(x)) deyarli bir xil kalitlar o'rtasida to'qnashuvlar yo'qligi kafolatlangan.
Ko'paytirishga asoslangan "xesh funktsiyalari"
Belgi bilan belgilang w (\displaystyle w) mashina so'zi bilan ifodalanishi mumkin bo'lgan sonlar soni. Masalan, IBM PC bilan mos keladigan 32 bitli kompyuterlar uchun, w = 2 32 (\displaystyle w=2^(32)).
Keling, bir necha doimiyni tanlaylik A (\displaystyle A) Shuning uchun; ... uchun; ... natijasida A (\displaystyle A) bilan ustun edi w (\displaystyle w). Keyin ko'paytirishdan foydalanadigan xesh funktsiyasi quyidagicha ko'rinishi mumkin:
h (K) = [ M ⌊ A w ∗ K ⌋ ] (\displaystyle h(K)=\chap)
Bunda ikkilik sanoq sistemasiga ega kompyuterda M (\displaystyle M) ikkining kuchi va h (K) (\displaystyle h(K)) mahsulotning o'ng yarmining yuqori bitlaridan iborat bo'ladi A ∗ K (\displaystyle A*K).
Bo'lish va ko'paytirishga asoslangan xesh funktsiyalarining afzalliklari orasida haqiqiy kalitlarning tasodifiy bo'lmaganligidan foydali foydalanishni ta'kidlash kerak. Misol uchun, agar tugmalar arifmetik progressiya bo'lsa (masalan, "Ism 1", "Ism 2", "Ism 3" ketma-ketligi), ko'paytirishdan foydalanadigan xesh funktsiyasi arifmetik progressiyani taxminan arifmetik progressiya bilan taqqoslaydi. turli xil xesh qiymatlari, bu tasodifiy vaziyatga nisbatan to'qnashuvlar sonini kamaytiradi.
Ko'paytirishdan foydalanadigan xesh funksiyalaridan biri Fibonachchi xeshini ishlatadigan xesh funktsiyasidir. Fibonachchi xashing oltin nisbatning xususiyatlariga asoslanadi. Doimiy sifatida A (\displaystyle A) bu erda eng yaqin butun son ph − 1 ∗ w (\displaystyle \varphi ^(-1)*w) va bilan tenglashing w (\displaystyle w), qayerda ph (\displaystyle \varphi) oltin nisbat hisoblanadi.
O'zgaruvchan uzunlikdagi satrlarni xeshlash
Yuqoridagi usullar bir nechta so'zlardan iborat kalitlarni yoki o'zgaruvchan uzunlikdagi kalitlarni ko'rib chiqish zarur bo'lganda ham qo'llaniladi. Masalan, modul qo'shilishidan foydalanib, so'zlarni birlashtira olasiz w (\displaystyle w) yoki "eksklyuziv yoki" operatsiya. Ushbu printsip asosida ishlaydigan algoritmlardan biri Pearson xesh funktsiyasidir.
Universal xeshlash
To'qnashuvlarni bartaraf etish usullari
To'qnashuv (ba'zan to'qnashuv yoki to'qnashuv) turli xil kirish bloklari uchun bitta xesh funktsiyasi bir xil xesh kodlarini qaytaradigan holatdir.
Xesh-jadvallardagi to'qnashuvlarni bartaraf etish usullari
Hashingni tavsiflovchi birinchi maqolalarning ko'pchiligi xesh jadvallaridagi to'qnashuvlarni bartaraf etish usullari bilan bog'liq. Keyinchalik katta fayllardagi matnni qidirishda xesh funksiyalaridan foydalanilgan. Xesh-jadvallardagi to'qnashuvlarni bartaraf etishning ikkita asosiy usuli mavjud:
zanjir usuli (to'g'ridan-to'g'ri bog'lanish usuli);
ochiq manzil usuli.
Zanjir usulidan foydalanganda, xesh jadvali kalitlarning "bog'langan" ro'yxati - "xesh-kod" juftlarini saqlaydi. Har bir kalit uchun xesh-kod hash funktsiyasi bilan hisoblanadi; agar xesh-kod ilgari olingan bo'lsa (boshqa kalit uchun), kalit xesh-kod bilan bog'langan kalitlarning mavjud ro'yxatiga qo'shiladi; aks holda, yangi juftlik "kalitlar ro'yxati" - "xesh-kod" yaratiladi va kalit yaratilgan ro'yxatga qo'shiladi. Umuman olganda, agar mavjud bo'lsa N (\displaystyle N) kalitlari va M (\displaystyle M) ro'yxatlar, o'rtacha hash jadval hajmi N M (\displaystyle (\frac (N)(M))). Bunday holda, jadval orqali qidirishda, qidiruv ketma-ket amalga oshiriladigan holatga nisbatan, o'rtacha ish hajmi taxminan kamayadi. M (\displaystyle M) bir marta.
Ochiq adreslash usulidan foydalanganda, xesh jadvali "kalit" - "xesh-kod" juftlarini saqlaydi. Har bir kalit uchun xesh-kod hash funktsiyasi bilan hisoblanadi; "kalit" juftligi - "xesh-kod" jadvalda saqlanadi. Bunday holda, jadval bo'ylab qidirishda, bog'langan ro'yxatlar qo'llaniladigan, havolalar ishlatilmaydigan holatga nisbatan, "kalit" - "xesh-kod" juftlarini ketma-ket sanash amalga oshiriladi, sanab o'tish kerakli kalitdan keyin to'xtaydi. topiladi. Jadvalning kataklarini skanerlash ketma-ketligi zondlar ketma-ketligi deyiladi.
Kriptografik tuz
Xesh funksiyalarini qo'llash
Xesh funktsiyalari kriptografiyada, shuningdek, ko'plab ma'lumotlar tuzilmalarida - xesh jadvallarida, Bloom filtrlarida va Dekart daraxtlarida keng qo'llaniladi.
Kriptografik xesh funksiyalari
Ko'pgina mavjud xesh funktsiyalari orasida alohida ajratib ko'rsatish odatiy holdir