12-mavzu. Xeshlash va xesh jadvallar Reja

---

12-mavzu. Xeshlash va xesh jadvallar 

 

Reja: 

      1      To‘g‘ridan to‘g‘ri adreslash jadvallari.  

 2      Xesh jadvallar.  

 3      Xesh funksiyalar 

Xeshlash 

Yuqorida biz mijoz dasturiga ma'lumotlarni qidirish va olish imkonini 

beradigan bir qator ro'yxat tuzilmalarini qo'lga kiritdik. Har bir bunday strukturada 

Find uslubi ro'yxatni kesib o'tishni amalga oshiradi va kalitga mos keladigan 

ma'lumotlar elementini qidiradi. Shu bilan birga, qidiruv samaradorligi ro'yxat 

tuzilishiga bog'liq. Oddiy ro'yxatga kiritilganda, Find (Oddiy) metodi O (n) 

elementlariga qarash uchun kafolatlanadi, ikkilik qidiruv daraxti va ikkilik qidiruv 

sharoitida esa, O (log2n) samaradorligi yuqori bo'ladi. 

Ideal holda biz O (1) vaqtida ma'lumotlarni tanlashni xohlaymiz. Bunday 

holda, zarur taqqoslashlar soni ma'lumotlar elementlarining soniga bog'liq emas. 

Bir element katalogda indeks sifatida foydalanilganda element (1) vaqtida namuna 

olinadi. Misol uchun, aktsiyadagi menyudan taomlar buxgalteriyani soddalashtirish 

uchun raqamlar bilan soddalashtiriladi. "Aralashtirilgan basturma" turidagi har 

qanday nozikligi ma'lumotlar bazasida faqat 2 raqami bilan ko'rsatilgan. 

Go'shtning egasi faqatgina 2-tugma bilan ro'yxatga kiritilishi mumkin (25-rasm). 

Hashing yoki hashing (inglizcha hashing) - o'ziga xos algoritm bilan 

bajarilgan ma'lum uzunlikdagi tasodifiy uzunlikdagi boshlang'ich registrini 

(chiqish) bit majmuasiga aylantirish. Algoritmni bajaradigan va ishlashni amalga 

oshiradigan vazifaga "xash funktsiyasi" yoki "konvolution funktsiyasi" deb 

nomlanadi. Resurslar ma'lumotlariga kirish majmuasi, "kalit" yoki "xabar" deb 

ataladi. Konvertatsiya (chiqdi) natijalariga "xash", "xash kodi", "xash summasi", 

"xabar xulosasi" deb nomlanadi. 

Misol uchun, biz 128-bitli hash funksiyasining kiritilishini o'n oltinchi sonda 

yoki 1 raqami bilan Leo Tolstoyning romaniga yuborishimiz mumkin. Natijada, 

har ikkala holatda ham biz "s4ca4238a0b923820dcc509a6f75849b" kabi pseudo-

tasodifiy o'n olti raqamli qatorlarni olamiz. 

Agar manba matnini bir karra o'zgartirsa, xash funktsiyasining natijasi 

butunlay o'zgartiriladi. 

Hash funksiyalarining bu xususiyati ularni quyidagi hollarda qo'llashingizga 

imkon beradi: 

assotsiativ majmualar qurishda; 

bir qator ma'lumotlar to'plamida takroriy matnlarni qidirishda; 

ma'lumotlar to'plamlari uchun noyob identifikatorlarni yaratishda; 

ma'lumotlarni saqlash va / yoki uzatish jarayonida yuzaga keladigan xatolarni 

(tasodifiy yoki qasddan kelib chiqadigan) aniqlash uchun ma'lumotlar (signal) 

summalarini hisoblashda; 

---

parollarni xavfsizlik tizimlarida xesh kodi shaklida saqlashda (xash kodi 

yordamida parolni tiklash uchun foydalaniladigan xash funktsiyasiga teskari 

funksiya kerak); 

elektron imzo yaratishda (amalda, ko'pincha imzolangan xabarning o'zi emas, 

balki uning "xash rasmi"); 

va boshq. 

Umumiy holatda (Dirkichlet printsipiga ko'ra) manba (kirish) ma'lumotlari va 

xash kodi (chiqish ma'lumotlari) o'rtasida hech qanday bog'lovchilik yo'q. Xash 

funktsiyasi (chiqishi) tomonidan qaytarilgan qiymatlar kiritish qatoridan (kirish 

ma'lumotlari) kamroq farq qiladi. Xash funktsiyasi bir nechta turli xil xabarlarni bir 

xil xabarlarga aylantiradigan holatga "to'qnashuv" deb ataladi. Qarama-qarshiliklar 

ehtimolligi xash funktsiyalarining sifatini baholash uchun ishlatiladi. 

Turli xil xususiyatlarga ega ko'plab xash algoritmlari mavjud. Xususiyatlar 

namunalari: 

raqamli quvvat; 

hisoblash murakkabligi; 

kriptografik kuch. 

Bir yoki bir nechta xash funktsiyasini tanlash muammoni hal etishning o'ziga 

xos xususiyati bilan belgilanadi. Xash funktsiyasining eng oddiy namunasi 

ma'lumotlarning "takrorlanishi" - takroriy takrorlash kodi (ingliz CRC, takroriy 

takrorlash kodi). 

Tarix [tahrir | tahrirlash kodi] 

Yanvar 1953da Hans Peter Lun (german: Hans Peter Luhn) (IBMning 

xodimi) "xash kodlash" ni taklif qildi. Donald Knut "Hashing" deb nomlangan 

sistematik g'oyani ilgari surgan birinchi Hans edi. 

1956-yili Arnold Dumey "Kompyuterlar va avtomatlashtirish" asarida eng 

ko'p programmuvchilar buni bilganligi uchun "hashing" g'oyasini birinchi bo'lib 

tasvirlab bergandi. Dumi, "lug'at muammosiga" yechim sifatida "hashing" ni ko'rib 

chiqdi, qolgan raqamni "hash manzil" (1) sifatida ajratishni taklif qildi. 

1957-yilda Wesley Peterson (W. Wesley Peterson) tomonidan yirik 

fayllardagi matnni qidirish bo'yicha "IBM Journal of Research and Development 

Journal" jurnalida chop etilgan maqola chop etildi. Ushbu ish "xashlash" bo'yicha 

birinchi "jiddiy" ish deb hisoblanadi. Maqolada, Wesley, "ochiq manzil" deb 

nomlangan bo'lib, uni o'chirish vaqtida ishlashning pasayishiga ishora qilmoqda. 

Olti yil o'tib, Verner Buchholz (Germaniya Verner Buchholz) asarining nashri 

chop etildi, unda "xash funktsiyalari" ni keng qamrovli o'rganish o'tkazildi. 

Keyingi bir necha yillar davomida "xashing" keng tarqalgan bo'lib ishlatilgan, 

biroq muhim ishlar chop etilmadi. 

1967 yilda "Zamonaviy ma'noda" xirgoyi "kitobida Herbert Hellerman" 

Raqamli hisoblash tizimlari tamoyillari "deb nomlangan [2]. 1968 yilda Robert 

Morris "ACM kommunikatsiyasi" jurnalida "xashlash" haqida keng ma'lumot 

tarqatdi. Ushbu asar ilmiy saralashga "xashing" tushunchasini kiritib, ilgari faqat 

mutaxassislar (jargon) tomonidan qo'llaniladigan "xash" atamasini kuchaytirishga 

qaratilgan "kalit" nashr. 

---

1990-yillarning boshiga qadar rus tilidagi adabiyotda Andrey Petrovich 

Ershovning asarlari natijasida "tartibga solish" so'zi "xashing" atamasi bilan 

tenglashtirildi va "to'qnashuv" atamasi "to'qnashuvlar" uchun ishlatilgan (A.P. 

Ershov 1956 yildan beri "kelishuv" dan foydalangan) ). 1989 yilda Niklaus 

Wirthning algoritmlari va ma'lumotlar tuzilmalari rus tilidagi nashriga "to'siq" 

atamasi ham ishlatilgan. Shuningdek, bu usulni boshqa ruscha so'z bilan ham 

aytish mumkin: okroshka. Biroq, bu variantlarning hech biri ildiz otgan va rus 

adabiyotida "xashing" atamasi asosan ishlatiladi [3]. 

"Xash funktsiyalarining turlari" [tahrirlash tahrirlash kodi] 

"Yaxshi" xash funktsiyasi ikki xususiyatni qondirishi kerak: 

tezkor hisoblash; 

eng kam "to'qnashuv" soni. 

Biz quyidagilarni bildiramiz: 

{\ displaystyle K} K - "tugmachalar" soni (kirish ma'lumotlari); 

{\ displaystyle h (k)} h (k) - {\ displaystyle M} M boshqa qiymatlari (chiqish 

ma'lumotlari) ko'p bo'lmagan xash funktsiyasi. 

Ya'ni: 

{\ displaystyle \ forall k \ in (0; \, K): h (k) 

(0; \, K): h (k)

"Yomon" xash funktsiyasiga misol sifatida {\ displaystyle M = 1000} M = 

1000 funktsiyasidan foydalanib, {\ displaystyle K} K raqamining yigirma xonali 

raqami ortidan tanlangan o'nta raqamli tabiiy raqam bilan {\ displaystyle K} K 

"Hash kodlari" qiymatlari "000" va "999" orasida bir xil taqsimlanishi kerak, lekin 

"haqiqiy" ma'lumot uchun bu "tugmachalar" chap yoki o'ngdagi "katta" sonli nolga 

ega bo'lmasa [ 3]. 

«Xash funktsiyalarini» bir necha oddiy va ishonchli amalga oshirishni ko'rib 

chiqing. 

"Xash funktsiyalari" bo'limi [tahrirlash tahrirlash kodi] 

1. "Xesh kodi" - mumkin bo'lgan barcha "xesh" larning soniga bo'linadi 

tahrirlash kodi] 

Xash funktsiyasi "xash" ni kirish ma'lumotlarini {\ displaystyle M} M: 

h(k)=k\mod M}  

{\ displaystyle M} M barcha mumkin xostlarning soni (chiqishi). 

Ko'rinib turibdiki, {\ displaystyle M} M uchun funktsiyaning qiymati ham {\ 

displaystyle k} k va odd - odatdagi {\ displaystyle k} k uchun ham bo'ladi. Bundan 

tashqari, "xash kodi" o'ng tomonda joylashgan {\ displaystyle k} k sonining bir 

nechta raqamiga bog'liq bo'lgani uchun, siz {\ displaystyle M} M komponentining 

raqam tizimining darajasini ishlatmasligingiz kerak, bu juda ko'p to'qnashuvlarga 

olib keladi. Amalda odatda oddiy {\ displaystyle M} M ni tanlashadi; Aksariyat 

hollarda bu tanlov juda qoniqarli. 

2. "Xash kodi" - natijada olingan polinomning koeffitsientlari to'plami 

tahrirlash kodi] 

Xash funktsiyasi kirish ma'lumotlarini polinom moduliga bo'linishi mumkin. 

Ushbu usulda {\ displaystyle M} M ikkitadan kuch bo'lishi kerak va ikkilik 

tugmalar ({\ displaystyle K=k_{n-1}k_{n-2}...k_{0}} K=k_{{n-1}}k_{{n-

---

2}}...k_{{0}})  polinomlar sifatida ifodalanadi, qolgan ma'lumotlarning qolgan 

qismi sifatida olingan polinomning koeffitsientlarining qiymatlari "displaystyle" 

"xash kodi" K} k oldindan tanlangan polinom {\ displaystyle P} P darajasiga {\ 

displaystyle m} m: 

{\ displaystyle K (x) \ mod P (x) = h_ {m-1} x ^ {m-1} + \ nuqtalar + h_ {1} 

x + h_ {0}} 

{\ displaystyle h (x) = h_ {m-1} ... h_ {1} h_ {0}} {\ displaystyle h (x) = h_ 

{m-1} ... h_ {1} h_ {0 }} 

{\ Displaystyle P (x)} P (x) to'g'ri tanlovi bilan deyarli bir xil tugmalar [3] 

o'rtasida to'qnashuv mavjud emas.