HESH JADVALLAR VA ULARNI TASHKIL ETISH
![1
O’ZBEKISTON RESPUBLIKASI
OLIY VA O’RTA -MAXSUS TA’LIM VAZIRLIGI
SAMARQAND DAVLAT UNIVERSITETI
RAQAMLI TEXNOLOGIYALAR FAKULTETI
DASTURIY INJINIRING YO`NALISHI
107 -GURUH TALABASI
YO`LDOSHEV DAVRONBEKNING
“ALGORITM VA MA’LUMOTLAR STRUKTURASI” FANIDAN
“HESH JADVALLAR VA ULARNI TASHKIL ETISH” MAVZU-
SIDA TAYYORLAGAN
KURS ISHI
Topshirdi: Yo‘ldoshev D
Tekshirdi: Abdusalomova G .](/data/documents/1bee1d5d-4c11-4f87-9572-3fcccea54ebd/page_1.png)
![2
Mundari ja
KIRISH ................................ ................................ ................................ ................................ ................................ .. 3
I BOB. HESH JADVALLA RI ASOSLARI ................................ ................................ ................................ ......... 4
1.1.HESH TUSHUNCHASI ................................ ................................ ................................ ........................... 4
1.2. HESH ALGORITMLA RI ................................ ................................ ................................ ...................... 7
II BOB . KOLLIZIYA TUSHUNCH ASI ................................ ................................ ................................ ............ 10
2.1 KOLLIZIYA HAQID A TUSHUNCHA ................................ ................................ ............................... 10
2.2. KOLLIZIYA ANIQL IGI (COLLISION RESOL UTION) ................................ ................................ . 11
2.3 . OCHIQ ADRESLASH ................................ ................................ ................................ .......................... 16
III BOB. AMALIY MASA LALAR ................................ ................................ ................................ .................... 19
3.1.SATRLI FUNKSIYAL AR UCHUN HESH -FUNKSI YASINI QO ’LLASH ................................ ...... 19
3.2. SONLAR UCHUN HE SH -FUNKSIYASI ................................ ................................ ........................... 21
3.3.IKKILIK DARAXTLA RDA IZLASH VA HESH J ADVALLAR ................................ ...................... 22
HESH JADVALNI REALIZ ATSIYA QILISH ................................ ................................ ................................ . 22
XULOSA ................................ ................................ ................................ ................................ .............................. 28
ADABIYOTLAR ................................ ................................ ................................ ................................ ................. 29](/data/documents/1bee1d5d-4c11-4f87-9572-3fcccea54ebd/page_2.png)
![3
Kirish
Hozirgi kunda amaliy matematika va kibernetika fanining asosiy
yo`nalishlaridan biri – tasvirlarni aniqlash masalasidir. Bu yo`nalishning
muhimligi avvalo shu bilan asoslanadiki juda ko`pgina amaliy masalalar
mavjudki, ularni to`liq matematik qa’tiylik bilan asoslangan metodlar bilan
yechish qiyin yoki yechib bo`lmaydi. Bunday masalalarga, masalan, geologiya,
texnika va tibbiyotda uchraydigan diagnost ika va bashorat qilish masalalari misol
bo`la oladi. Tasvirlarni aniqlash masalalasi metodlarining bu sohalarda keng
tarqalishing sabablarirdan yana biri, ularni tadbiqida bu sohalardagi boshlang`ich
ma`lumotlarni yuqori darajada formallash talab qilinmayd i.
Tasvirlarni aniqlash nazariyasi optimal yechimni axtarish muammosini
diskret analogidir. Bu masalaga nafaqat eng yaxshi yechimni sintezi masalasi,
balki boshqa muammoli amaliy masalalar sinfi ham keltiriladi.
Hesh jadvali - bu assotsiativ massiv interfeysini amalga oshiruvchi
ma'lumotlar tuzilmasi, ya'ni juftlarni saqlashga (kalit, qiymat) va uchta
operatsiyani bajarishga imkon beradi: yangi juftlikni qo'shish, qidirish
operatsiyasi va juftlikni kalit bilan o'chirish. Hesh jadvallarining ikkita asosiy
varianti mavjud: zanjirli va ochiq adreslash. H esh jadvali ba'zi bir ?????? massivini o'z
ichiga oladi, ularning elementlari juftliklar (ochiq adreslash bilan hesh jadvali)
yoki juftliklar ro'yxati (zanjir bilan hesh jadvali). Hes hlash – bu ixtiyori
uzunlikdagi kirish ma'lumotlari majmuasini ma'lum bir algoritm tomonidan
bajarilgan, belgilangan o'lchamdagi chiqish massiviga aylantirish jarayoni.
Bunday algoritmni amalga oshiruvchi funksiya hesh funktsiya , transformatsiya
natijasi x ash yoki xash yig'indisi deyiladi. Hesh funktsiyasi quyidagi
xususiyatlarga ega:
- bir xil ma'lumotlar bir xil xashni beradi;
- "deyarli har doim" turli xil ma'lumotlar boshqacha hesh beradi.](/data/documents/1bee1d5d-4c11-4f87-9572-3fcccea54ebd/page_3.png)
![4
I BOB. Hesh jadvallari asoslari
1.1.Hesh tushunchasi
Katta hajmdagi ma'lumotlarda ma'lumotlarni izlash jarayoni ko'p vaqt talab
etadi, bu esa qidiruv kaliti yordamida sezilarli miqdordagi elementlarni ko'rish va
taqqoslash zarurati bilan bog'liq. Ko'rish oynasini mahalliylashtirish orqali
qidiruvni qisqartirish mu mkin. Misol uchun, ma'lumotlarni qidirish kaliti bo'yicha
tartiblang, ularni biron bir guruh atributiga ko'ra bir -biriga mos kelmaydigan
bloklarga bo'ling yoki haqiqiy ma'lumotlarni qidirish jarayonini
soddalashtiradigan kod bilan moslang.
Heshlash (yoki he shlash , inglizcha hashing ) - ma'lum turdagi va ixtiyoriy
uzunlikdagi kirish ma'lumotlar massivini belgilangan uzunlikdagi chiqish bit
qatoriga aylantirish. Bunda transformatsiyalar ham deyiladi. Hesh funktsiya-
lari yoki konvolyutsiya funksiyalari va ularnin g natijalari deyiladi. Hash, hash
kodi, hash jadvali yoki hazm qilish xabarlar (inglizcha) xabar dayjesti ).
Hesh jadvali - bu ma'lumotlar tuzilishi, bu assotsiativ massiv interfeysini
amalga oshiradi, ya'ni kalit -qiymat juftlarini saqlash va uchta amalni bajarish im-
konini beradi: yangi juft qo'shish operatsiyasi, qidirish operatsiyasi va kalit bo'yi-
cha juftlikni o'chirish operatsiyasi. Hesh -jadval - bu hesh funktsiyasi tomonidan
ma'lum tartibda tuzilgan massiv.
funksiya hisoblash uchun oddiy bo'lishi kerak;
funksiya hesh -jadvaldagi kalitlarni iloji boricha bir tekis taqsimlashi kerak;
funktsiya kalit qiymatlar o'rtasidagi hech qanday munosabatni manzil
qiymatlari o'rtasidagi munosabatlarga moslashtirmasligi kerak;
funktsiya to'qnashuvlar sonini minimal lashtirishi kerak, ya'ni turli tugmalar
bitta hesh qiymatiga to'g'ri keladigan vaziyatlar (bu holda kalitlar deyiladi. si-
nonimlar ).
Bunda yaxshi hesh funksiyasining birinchi xossasi kompyuterning
xususiyatlariga, ikkinchisi esa ma'lumotlar qiymatlariga bog 'liq.
Agar barcha ma'lumotlar tasodifiy bo'lsa, hesh funktsiyalari juda oddiy
bo'lar edi (kalitning bir necha bitlari kabi). Biroq, amalda tasodifiy ma'lumotlar](/data/documents/1bee1d5d-4c11-4f87-9572-3fcccea54ebd/page_4.png)
![5
juda kam uchraydi va siz butun kalitga bog'liq bo'lgan funktsiyani yaratishingiz
kerak. Agar he sh funksiyasi aholini taqsimlasa mumkin bo'lgan kalitlar indekslar
to'plami ustidan bir xilda, keyin xeshlash kalitlar to'plamini samarali ravishda
ajratadi. Eng yomoni, barcha kalitlar bitta indeksga xeshlanganda.
To'qnashuvlar sodir bo'lganda, bir xil hesh jadvali katagiga da'vo qiluvchi
kalitlarni saqlash uchun yangi joy topish kerak. Bundan tashqari, agar to'qnashu-
vlarga ruxsat berilsa, u larning sonini kamaytirish kerak. Ba'zi maxsus holatlarda
to'qnashuvlardan butunlay qochish mumkin. Misol uchun, agar barcha element
kalitlari oldindan ma'lum bo'lsa (yoki juda kamdan -kam hollarda o'zgartirilsa),
ular uchun ba'zi in'dektsion hesh funktsiya sini topish mumkin, bu ularni hesh
jadvalining katakchalari o'rtasida to'qnashuvsiz taqsimlaydi.
Hesh jadvallari quyidagilarga mos kelishi kerak xususiyatlari .
Hesh -jadvalda operatsiyani bajarish kalitning hesh funktsiyasini hisoblashdan
boshlanadi. Olingan hesh qiymati asl massivning indeksidir.
Saqlangan massiv elementlari soni mumkin bo'lgan hesh qiymatlari soniga
bo'linadi va bo'ladigan m uhim parametr , bu operatsiyalarning o'rtacha bajarilishi
vaqtini belgilaydi.
Qidiruv, kiritish va oʻchirish operatsiyalari oʻrtacha O(1) vaqtni olishi kerak.
Biroq, bu taxmin massiv o'lchami qiymatini oshirish va hesh jadvaliga yangi juft-
lik qo'shish bilan bog'liq bo'lgan hesh jadvali indeksini qayta tiklash uchun mum-
kin bo'lgan apparat xarajatlarini hisobga olmaydi.
To'qnashuvni hal qilish mexanizmi har qanday hesh jadvalining muhim
qismidir.
Heshing, mumkin bo'lgan qiymatlarning keng doirasi kichik hajmdagi xo-
tirada saqlanishi kerak bo'lganda foydali bo'ladi va tez, deyarli tasodifiy kirish
usuli kerak bo'ladi. Hesh -jadvallar ko'pincha ma'lumotlar bazalarida va ayniqsa,
ma'lumotlar bazalarida qo'llaniladi til protsessorlari identifikatorlar jadvalini
qayta ishlash tezligini oshiradigan kompilyatorlar va assemblerlar kabi. Kundalik
hayotda xeshlashdan foydalanishga misollar kutubxonadagi kitoblarni tematik
kataloglar bo'yicha taqsimlash, lug'atl arda so'zlarning birinchi harflari bo'yicha](/data/documents/1bee1d5d-4c11-4f87-9572-3fcccea54ebd/page_5.png)
![6
tartiblash, universitetlarda mutaxassisliklarni shifrlash va boshqalar.
To'qnashuvlarni hal qilish usullari
To'qnashuvlar hesh -jadvallardan foydalanishni murakkablashtiradi, chunki
ular hesh kodlari va ma'lumotla r o'rtasidagi birma -bir yozishmalarni buzadi.
Biroq, yuzaga keladigan qiyinchiliklarni bartaraf etishning yo'llari mavjud:
zanjir usuli (tashqi yoki ochiq xeshlash);
ochiq adreslash usuli (yopiq xeshlash).
Zanjir usuli. Elementlarni ulash texnologiyasi shundan iborat elementlarni
o'r ta qiymatiga mos keladigan , zanjir ro'yxatida bog'langan. Pozitsiya raqami i
kalitning hesh qiymati i ga teng bo'lgan elementlar ro'yxatining boshiga ko'rsat-
gichni saqlaydi; agar to'plamda bunday elementlar bo'lmasa, i holat ida NULL
yoziladi.](/data/documents/1bee1d5d-4c11-4f87-9572-3fcccea54ebd/page_6.png)
![7
1.2. Hesh algoritmlari
Hozirda deyarli hech qanday kriptografiya ilovasi xeshlashdan foyda-
lanmasdan to'liq emas.
Hesh funksiyalari odatda ikkilik alifboda yozilgan ixtiyoriy xabar yoki
maʼlumotlar toʻplamini konvolyutsiya deb ataladi gan qatʼiy uzunlikdagi bit birk-
masiga “siqish ” uchun moʻljallangan funksiyalardir. Hesh -funksiyalar statistik
eksperimentlarni o'tkazishda, mantiqiy qurilmalarni sinovdan o'tkazishda, tezkor
qidiruv algoritmlarini yaratishda va ma'lumotlar bazalaridagi yoz uvlarning
yaxlitligini tekshirishda turli xil ilovalarga ega. Hesh -funksiyalar uchun asosiy
talab - bu argument qiymatlarini tasodifiy tanlash bilan ularning qiymatlarini
taqsimlashning bir xilligi.
Kriptografik hesh -funksiya - kriptografik jihatdan xavfsiz bo'lgan, ya'ni
kriptografik ilovalar uchun xos bo'lgan bir qator talablarni qondiradigan har
qanday hesh funksiyasi. Kriptografiyada hesh funksiyalari quyidagi muammo-
larni hal qilish uchun ishlatil adi:
- uzatish yoki saqlash vaqtida ma'lumotlar yaxlitligini nazorat qilish tizimlarini
yaratish;
- ma'lumotlar manbasini autentifikatsiya qilish.
Hesh funktsiyasi har qanday funktsiyadir h:X -> Y , oson hisoblash mumkin
va har qanday xabar uchun shunday M ma'nosi h(M) = H (konvolyutsiya) bel-
gilangan bit uzunligiga ega. X- barcha xabarlar to'plami, Y- belgilangan uzunlik-
dagi ikkilik vektorlar to'plami.
Qoidaga ko'ra, hesh funktsiyalari bir bosqichli qisqarish funktsiyalari aso-
sida qurilgan y \u003d f (x 1, x 2) ikkita o'zgaruvchi, bu erda x 1 , x2 va y- ikkilik
uzunlik vektorlari m va n mos ravishda va n konvolyutsiya uzunligi va m - xabar
blokining uzunligi.
Qiymatni olish uchun h(M) xabar avval uzunlikdagi bloklarga
bo'linadi m (shu bilan birga, agar xabarning uzunligi ko'p bo'lmasa m keyin oxirgi
blok qandaydir maxsus tarzda to'liq bloklarga to'ldiriladi), so'ngra olingan
bloklarga M 1 , M 2 ,.., M N konvolyutsiyani hisoblash uchun quyidagi ketma -](/data/documents/1bee1d5d-4c11-4f87-9572-3fcccea54ebd/page_7.png)
![8
ketlikni qo'llang:
H o \u003d v,
H i = f(M i ,H i -1), i = 1,.., N,
h(M) = H N
Bu yerda v- ba'zi doimiy, u ko'pincha initsializatsiya vektori deb ataladi. U
chiqadi turli sabablarga ko'ra va maxfiy doimiy yoki tasodifiy ma'lumotlar
to'plami bo'lishi mumkin (masalan, sana va vaqtni tanlash). Ushbu yondashuv bi-
la n hash funktsiyasining xususiyatlari bir bosqichli qisqarish funktsiyasining
xususiyatlari bilan to'liq aniqlanadi.
Kriptografik hesh -funktsiyalarning ikkita muhim turi mavjud - kalitli va
kalitsiz. Asosiy hesh funksiyalari xabar autentifikatsiya kodlari d eb ataladi. Ular
uchun imkoniyat yaratadi qo'shimcha mablag'lar o'zaro ishonchli foydalanuvchi-
lar bilan tizimlarda ma'lumotlar manbasining t o'g'riligini va ma'lumotlarning
yaxlitligini ta'minlash.
Kalitsiz hesh funksiyalari xatolarni aniqlash kodlari deb ataladi. Ular
qo'shimcha vositalar (masalan, shifrlash) yordamida ma'lumotlarning yaxlitligini
kafolatlash imkonini beradi. Ushbu hesh -funksi yalar ishonchli va ishonchsiz foy-
dalanuvchilarga ega tizimlarda ishlatilishi mumkin.
Statistik xususiyatlar va talablar haqida
Aytganimdek, hesh -funksiyalar uchun asosiy talab argument qiymatlarini
tasodifiy tanlash bilan ularning qiymatlarini bir xil taqsimlashdir. Kriptografik
hesh -funksiyalar uchun argumentning eng kichik o'zgarishi bilan funktsiyaning
qiymati sezilarli darajada o'zgarishi ham muhimdir. Bu ko'chki effekti deb ataladi.
H eshlash quyidagi talablarga ega:
- ishlab chiqarishning mumkin e masligi;
- o'zgartirishning mumkin emasligi.
Birinchi talab shuni anglatadiki, xabarni to'g'ri qatlama qiymatiga mos-
lashtirish juda qiyin. Ikkinchisi, ma'lum qatlama qiymatiga ega bo'lgan ma'lum
bir xabar uchun to'g'ri katlama qiymatiga ega boshqa xabarni moslashtirishning](/data/documents/1bee1d5d-4c11-4f87-9572-3fcccea54ebd/page_8.png)
![9
yuqori murakkabligi.
Kalitsiz funktsiyalarga qo'yiladigan talablar:
- bir tomonlama,
- to'qnashuvlarga qarshilik,
- ikkinchi prototipni topishga qarshilik.
Bir yo'nalishlilik deganda ma'lum konvolyutsiya qiymati bo'yicha xabarni
topishnin g yuqori murakkabligi tushuniladi. Shuni ta'kidlash kerakki bu
daqiqa isbotlangan bir tomonlama bilan ishlatiladigan hech qanday hash
funksiya lari.
To'qnashuvga qarshilik deganda bir xil katlama qiymatlari bo'lgan bir juft
xabarni topish qiyinligi tushuniladi. Odatda, algoritmning eskirganligi va uni
tezda almashtirish zarurati to'g'risida birinchi signal bo'lib xizmat qiladigan
kriptoanalitikl ar tomonidan to'qnashuvlarni qurish usulini topishdir.
Ikkinchi preimageni topishga qarshilik deganda ma'lum katlama qiymatiga
ega bo'lgan berilgan xabar uchun bir xil katlama qiymatiga ega ikkinchi xabarni
topish qiyinligi tushuniladi.](/data/documents/1bee1d5d-4c11-4f87-9572-3fcccea54ebd/page_9.png)
![10
II Bob. Kolliziya tushunchasi
2.1 Kolliziya haqida tushuncha
Kolliziya (lotincha collisio -qaramaqarshilik, to‘qnashish) -badiy asarda
harakterlararo hamda harakterlar bilan sharoit, muhit o‘rtasidagi ziddiyat.
Kolliziya konfikt atamasining sinonimi tarzda ham qo‘llaniladi. Kolliziya
atamasini birinchi bo‘lib Gagel estetika ilmiga olib kirgan. Uning aytishich
Kolliziya ziddiyatning ijtimoiy -tarixiy jihatdan keng ko‘lamligi, yirikligi va
konfiktning boshlanish nuqtasini, tugunini anglatadi. Kolliziya harakatga, mavzu
rivojig a, harakterning kurashga kirishishiga turtki beradi.
Kolliziya (Qarama -qarshi qarashlar, intilishlar yoki manfaatlar to’qnashuvi)
- bu ikki xil kalit uchun hesh funksiyasi qiymatlarining tasodifiyligi.
Hesh funksiyalarda kolliziya -ikkita har xil ma’lumotdan bir xesh qiymat hosil
bo‘lib qolishi. Kollizianing oldini olish yo‘llaridan biri bu xesh jadval hisoblanadi.
Xeshlash algoritmlarining bardoshliligi va xavfsizligi kolliziaga chidamliligi
bilan aniqlanadi.
fil
jirafa
Tulki
Bo ’ri
Fil
Bo ’ri
Hash funksiyasi Kalit Heshlar
To ’qnashuv](/data/documents/1bee1d5d-4c11-4f87-9572-3fcccea54ebd/page_10.png)
![11
2.2. Kolliziya aniqligi (Collision resolution)
Zanjirlash usuli (chaining) yopiq adreslash
Xuddi shu hesh qiymatiga ega bo'lg an narsalar bog'langan ro'yxatga
birlashtiriladi. Ro'yxat ko'rsatkichi hesh jadvalining mos yacheykalarida saqla-
nadi.
- Kolliziyada element ro'yxat boshiga qo'shiladi.
- Elementni topish va yo'q qilish uchun butun ro'yxatni ko'rib chiqish
kerak.
-
Jirafa
Fil
Tulki
Bo’ri
Tulki
Fil
Bo’r Ji-
Kal
it Hash funksiya Heshla
r](/data/documents/1bee1d5d-4c11-4f87-9572-3fcccea54ebd/page_11.png)
![12
Matematik modellashtirish bosqichlari .
Matematik modellashtirishning nazariy asoslari besh bosqichga bo’linib,
amalga oshiriladi.
Massivning har bir yacheykasi yuir xil kalitning xesh -qiymatiga mos
keladigan kalit -qiymat juftliklarining bog’langan ro’yxati (zanjir)ga ko’rsatkich
hisoblanadi (6 -rasm). Bir nechta element uzunligidagi zanjirlar paydo bo'lganda
kolliziyalar kelib chiqadi.
• Shuning uchun, agar bittadan ko’p elementlardan tashkil topgan zanjirlarning
har biri uchun elementlarni hisoblasak, bunday har bir yig'indidan bittasini ayirib,
so'ngra bu natijalarning hammasini qo'shsak, kolliziyalarning umumiy sonini
olamiz.
• Jadvalga ma'lumotlarni kiritish uchun xesh -funksiyaning oldindan topilgan
qiymati bilan tegishli xesh -qiymatni zanjirning oxiridan yoki boshidan qo’shish
kerak.
• Jadvaldan qandaydir ma’lumotlarni topish yoki o’chirish
uchun, kirish ma’lumotining xesh qiymati bilan mos keladigan xesh qiymatli
elementlar zanjirini topish yetarli bo’ladi. Keyin agar zanjir bitta elementdan
iborat bo’lsa, butun zanjirni o’chirish mumkin, aks holda, zanjirning o'zida
oldindan xeshlangan ma'lumo tlar bilan emas, balki kalit orqali qidirishni tashkil
qilish va elementni o'chirish kerak bo ’ladi.](/data/documents/1bee1d5d-4c11-4f87-9572-3fcccea54ebd/page_12.png)
![13
Kolliziya muammosi
Tabiiyki, savol tug'iladi, nega biz bir qator katakchaga ikki marta kirib
olishimiz mumkin emas, chunki har bir elementga mutlaqo boshqa cha natural
sonlarni taqqoslaydigan funktsiyani taqdim etish shunchaki mumkin emas. Kol-
liziya muammosi xash funktsiyasi turli elementlar uchun bir xil natural sonni hosil
qilganda paydo bo’ladigan muammo.
Ushbu muammoning bir nechta yechimlari mavjud: zanjirlash usuli va ikki
marta xeshlash usuli.
O'zingizni kichik do'konda sotuvchi ekanligingizni tasavvur qiling. Xaridor
mahsulot sotib olayotganda, siz ularning narxini kitob bilan tekshirasiz. Agar
kitobd agi yozuvlar alifbo tartibida tartiblanmagan bo'lsa, har bir satrda "apelsin"
so'zini topish juda uzoq vaqt talab etadi. Aslida, siz 1 -bobdan oddiy qidiruvni ba-
jarishingiz kerak va buning uchun har bir yozuvni tekshirishingiz kerak bo'ladi.
Unutmang, qanch a vaqt ketadi? O (n). Agar kitob alifbo tartibida saralangan
bo’lsa, ikkilik qidiruvdan foydalanishingiz mumkin, bu faqat O (log n) vaqtni
oladi.
Qidirish vaqti O(logn) qidirish vaqti O(n)
Shunga qaramay, sizga O (n) va O (log n) vaqtlari bir xil emasligini eslatib
qo'yay! Aytaylik, siz bir soniyada kitobdagi 10 ta yozuvni ko'rish ingiz mumkin.
Quyidagi jadvalda oddiy va ikkilik qidiruvlar qancha vaqt ketishi ko'rsatilgan.
Kitoblar soni O(n) O(log n)
100 10 s 1s log 2100=7
1000 1.66min 1s log 21000=10
Asal ….2.49$
Sut …1.99$
Tuxum …79$
Sut …1.99$
Asal …2.49$
Tuxum …79$](/data/documents/1bee1d5d-4c11-4f87-9572-3fcccea54ebd/page_13.png)
![14
10000 16.6min 2s log 210000=14
Ikkilik qidiruv juda tezligini allaqachon bilasiz. Ammo kitobdan
ma'lumotlarni topish kassir uchun bosh og'rig'i, hatto uning tarkibi saralangan
bo'lsa ham. Sahifalarni varaqla ganingizda, mijoz asta -sekin o'zini yo'qotishni
boshlaydi. Tovarlarning barcha nomlarini va narxlarini eslab turadigan
yordamchiga ega bo'lish ancha qulayroq bo'ladi. Keyin siz hech narsa
qidirishingiz shart emas: siz yordamchidan so'rasangiz, u darhol jav ob beradi.
Sizning yordamchingiz Meggi sizga kitobning hajmidan qat'i nazar, O (1)
vaqt ichida har qanday buyumning narxini aytib berishi mumkin. Ikkilik
qidiruvdan ham tezroq.
Kitoblar soni O(n) O(log n) O(1)
100 10 s 1s bir zumda
1000 1.66min 1s bir zumda
10000 16.6min 2s bir zumda
Faqatgina mo'jiza, qiz emas! Va bu Maggini qaerdan olish mumkin?
Ma'lumotlar tuzilmalariga murojaat qilaylik. Hozircha siz ikkita
ma' lumotlar tuzilishi bilan tanishasiz: massivlar va ro'yxatlar. (Steklar haqida
gapirmayapman, chunki oddiy stekni qidirish mumkin emas). Kitob massiv
sifatida amalga oshirilishi mumkin.
Asal, 2.49 sut, 1.49 tuxum, 0.79
Massivning har bir elementi as lida ikkita elementdan iborat: mahsulot nomi
va uning narxi. Agar siz massivni nomlari bo'yicha saralasangiz, unda buyumning
narxini aniqlash uchun ikkilik qidiruvni amalga oshirishingiz mumkin. Bu shuni
anglatadiki, qidirish O (log n) vaqtni oladi. Ammo b iz qidiruvni O (1) vaqt ichida
bajarilishini istaymiz (boshqacha aytganda, siz "Maggi" ni yaratmoqchisiz). Hesh
funktsiyalari sizga bu borada yordam beradi
Kolliziyalarni hal qilish kerak, chunki ularning buzilishi xesh -jadvaldan
foydalanishda ma'lumotlar va ularning xeshlangan anologlari o'rtasidagi bir
qiymatlilikni aniqlashni murakkablashtiradi.
• Buning uchun xesh -jadvalning yacheykalariga ilgari qo ’shilgan kalit lar](/data/documents/1bee1d5d-4c11-4f87-9572-3fcccea54ebd/page_14.png)
![15
egallab turgan joyga davogarlik qiladigan kalitlarni saqlash uchun joy
ajratilgan. Ushbu mexanizm zanjirlash usuli deb ataladi. Yoki, agar
elementlarning barcha kalitlari oldindan aniqlangan bo ’lsa, mos ravishda jadvalga
qo'shilish jarayonida elementlarni to'g'ridan -to'g'ri kataklarga taqsimlashning
hojati yo'q, kalitlarni xesh -jadvalning yacheykalari kolliziyasiz taqsimlaydigan
ba ’zi in ’ektiv xesh funksiyani yaratish mumkin bo ’ladi. Kolliziyani hal qilish
mexanizmiga zarurat bo'lmagan bunday xesh - jadvallar, to'g'ridan -to'g'ri yoki
ochiq adreslangan xesh -jadvallar deb nomlanadi.
• Uning xususiy maydonlari va funksiyalaridan boshlaymiz. Faraz qilaylik,
jadval maksimal yacheykalari soni bilan o ’lchanadigan fiksirlangan o ’lchamga
ega bo ’lsin.
• Tavsiya etiladigan ikkita usulni batafsil ko ’rib chiqamiz.
Zanjirlash usuli:
Massivning har bir yacheykasi yuir xil kalitning xesh -qiymatiga mos ke-
ladiga n kalit -qiymat juftliklarining bog ’langan ro ’yxati (zanjir)ga ko ’rsatkich
hisoblanadi. Bir nechta element uzunligidagi zanjirlar paydo bo'lganda kolliziya-
lar kelib chiqadi.
• Shuning uchun , agar bittadan ko ’p elementlardan tashkil topgan zan-
jirlarning har biri uchun elementlarni hisoblasak, bunday har bir yig'indidan bit-
tasini ayirib , so'ngra bu natijalarning hammasini qo'shsak, kolliziyalarning
umumiy sonini olamiz.
• Jadvalga ma'lumotlarni kiritish uchun xesh -funksiyaning oldindan topil-
gan qiymati bilan tegishli xesh -qiymatni zanjirning oxiridan yoki b oshidan
qo ’shish kerak.
• Jadvaldan qandaydir ma ’lumotlarni topish yoki o ’chirish
uchun, kirish ma ’lumotining xesh qiymati bilan mos keladigan xesh qiymatli ele-
mentlar zanjirini topish yetarli bo ’ladi. Keyin agar zanjir bitta elementdan iborat
bo ’lsa, butu n zanjirni o ’chirish mumkin, aks holda, zanjirning o'zida oldindan
xeshlangan ma'lumotlar bilan emas , balki kalit orqali qidirishni tashkil qilish va
elementni o'chirish kerak bo ’ladi .](/data/documents/1bee1d5d-4c11-4f87-9572-3fcccea54ebd/page_15.png)
![16
2.3 . Ochiq adreslash
Jadvalining har bir katakchasi bog'langan ro'yxatdagi ko'rsatkichni emas,
balki bitta elementni (kalit, qiymat) saqlaydi.
Agar hesh (kalit) indeksiga ega bo'lgan yacheyka egallab olingan bo'lsa,
unda bo'sh katak quyidagi jadval holatlarida qidiri ladi
Chiziqli heshlash (linear probing) - pozitsiyalar tekshiriladi:
hash(key) + 1, hash(key) + 2, ...,(hash(key) + i) mod h, ...
Agar bo'sh kataklar bo'lmasa, unda jadval to’ldiriladi
Masalan:
hash (D) = 3, lekin 3 -indeks band.
Xuddi shunday davom ettiramiz 4 -band, 5 -bo’sh
Hesh funksiyasiga talablar
Asosiy qiymat bo'yicha tezkor xash -kodni hisoblash
- Hesh kodini hisoblashning murakkabligi hesh jadvalidagi element-
laringn soniga bog'liq bo'lmasligi kerak
Element](/data/documents/1bee1d5d-4c11-4f87-9572-3fcccea54ebd/page_16.png)
![17
- Determinizm - berilgan kalit qiymati uchun hesh funksiyasi har doim
bir xil qiymatni qaytarishi kerak
Bir xil o’lchamlilik – hesh funksiyasi massiv indekslarini qaytarilgan
raqamlar bilan teng ravishda to'ldirishi kerak
Barcha hesh kodlari bir xil taqsimlangan ehti mollik bilan tuzilgan bo’lishi kerak.
Bir xil o’lchamga ega bo’lmagan
taqsimlanish
Element](/data/documents/1bee1d5d-4c11-4f87-9572-3fcccea54ebd/page_17.png)
![18
Bir xil o’lchamga ega bo’lgan taqsimlanish
Hesh -jadvallarning samaradorligi
Amal O'rtacha hisoblash murakka-
bligi
Eng yomon hisoblash mu-
rakkabligi
Element Yagona taqsimlash](/data/documents/1bee1d5d-4c11-4f87-9572-3fcccea54ebd/page_18.png)
![19
III Bob. AMALIY MASALALAR
3.1.Satrli funksiyalar uchun hesh -funksiyasini qo ’llash
Faqat bitli operatsiyalar qo'llaniladi (samaradorlik uchun)
CRC32 (Cyclic redundancy check – Davriy kamchilikni tekshiruvchi kod)
kompyuter qurilmalarida, ya ’ni tarmoq qurilmalari va doimiy xotiradagi
ma ’lumotlarni xavfsizligini ta ’minlashda ya ’ni oʻzgartirilmaganligini doimiy
ravishda tekshirib boradigan oddiy xes h funksiya hisoblanadi. CRC32 xalqaro
standarti CRC32 -IEEE 802. Bu algoritm juda tez ishlagani bilan,
kriptoxavfsizlikni toʻliq ta ’minlay olmaydi. Shunga qaramasdan keng qoʻllaniladi](/data/documents/1bee1d5d-4c11-4f87-9572-3fcccea54ebd/page_19.png)
![20
chunki, ishlatilishi juda oddiy va tez. 32 -bit xesh -kod odatda 8 ta simvo ldan iborat
16 lik sanoq sistemasida ifodalanadi. Bu algoritm kriptografik hisoblanmaydi.
MD4 xeshlash algoritmi RSA Data Security, Inc. Ronald L. Rivest tomoni-
dan ishlab chiqilgan. MD4 aralashgan algoritm hisoblanadi, Endi ishonchsiz
hisoblanadi. Bu alg oritm (32 -bit protsessorlari uchun) tez va peer -to -peer tar-
mogʻi edonkey 2000 Qo'shma Algoritm hash kodi 32 ta simvoldan iborat bo'lgan
belgilar bilan o'n oltilik soni RFC 1320. tasvirlangan hisoblash ishlatiladi.
MD5 xesh funksiyasi algoritmi Massachuset s texnologiya instituti profes-
sori Ronald Rivest tomonidan 1992 yilda ishlab chiqilgan. Bu 172 algoritmda kir-
uvchi ma ’lumot uzunligi ixtiyoriy bo ‘lib, xesh qiymat uzunligi 128 bit bo ‘ladi.
MD 5 xesh funksiyasi algoritmida kiruvchi ma ’lumot 512 bitlik blokl arga ajratilib,
ular 16 ta 32 bitlik qism bloklarga ajratiladi va bular ustida amallar bajariladi.
Faraz qilaylik, bizga uzunligi b bit bo ‘lgan, bu yerda b – ixtiyoriy nomanfiy butun
son, ma ’lumot berilgan bo ‘lsin va bu ma ’lumotning bitlari quyidagicha:
m0 m1 … m(b -1) .
SHA -1 xesh funksiyasi algoritmi. Kafolatlangan bardoshlilikka ega bo ‘lgan
xeshlash algoritmi SHA (Secure Hash Algorithm) AQShning standartlar va
texnologiyalar Milliy instituti (NIST) tomonidan ishlab chiqilgan bo ‘lib, 1992
yilda axborotni qayta ishlash federal standarti (RUB FIPS 180) ko ‘rinishida nashr
qilindi. 1995 yilda bu standart qaytadan ko ‘rib chiqildi va SHA -1 deb nomlandi
(RUB FIPS 180 -1). SHA algoritmi MD4 algoritmiga asoslanadi va uning tuzilishi
MD4 algoritmining tuzilishiga juda yaq in. Bu algoritm DSS standarti asosidagi
elektron raqamli imzo algoritmlarida ishlatish uchun mo ‘ljallangan. Bu algorit-](/data/documents/1bee1d5d-4c11-4f87-9572-3fcccea54ebd/page_20.png)
![21
mda kiruvchi ma ’lumotning uzunligi 264 bitdan kichik bo ‘lib, xesh qiymat uzun-
ligi 160 bit bo ‘ladi. Kiritilayotgan ma ’lumot 512 bitlik blok larga ajratilib qayta
ishlanadi .
3.2. Sonlar uchun hesh -funksiyasi
Kalitlar: fayl hajmi - raqam.
Lug'atda saqlanadigan qiymat: fayl nomi.
Hash funktsiyasini ishlab chiqish talab qilinadi:
ℎ???????????? ℎ(�????????????�??????????????????� → [0 … 1023 ].](/data/documents/1bee1d5d-4c11-4f87-9572-3fcccea54ebd/page_21.png)
![22
3.3.Ikkilik daraxtlarda izlash va hesh jadvallar
Hesh jadvalni realizatsiya qilish
#include <iostream>
#include <map> //map bilan ishlash uchun kutubxonani ulash
using namespace std;
int main()
{
///map oshkor initsializatsiyalash
map <string,int> myFirstMap = {{ "Mother", 37 },
{ "Father", 40 },
{ "Brother", 15 },
{ "Sister", 20 }};
/// initsializatsiyalangan mapni ekranga chiqarish
for (auto it = myFirstMap.begin(); it != myFirstMap.end(); ++it)
{
cout << it ->first << " : " << it ->second << endl;
}
char c;
map <char,in t> mySecondMap;
for (int i = 0,c = 'a'; i < 5; ++i,++c)
{
mySecondMap.insert ( pair<char,int>(c,i) );
}](/data/documents/1bee1d5d-4c11-4f87-9572-3fcccea54ebd/page_22.png)
![23
/// initsializatsiyalangan mapni ekranga chiqarish
for (auto it = mySecondMap.begin(); it != mySecondMap.end(); ++it)
{
cout << (*it).first << " : " << (*it).second << endl;
}
return 0;}](/data/documents/1bee1d5d-4c11-4f87-9572-3fcccea54ebd/page_23.png)
![24
#include <iostream>
#include <string.h>
using namespace std;
long long Heshlash(char s[])
{
long long h = 0;
int base = 37;
for(int i=0; i<=strlen(s); i++)
{
h = h* base + s[i] - 61 +1;
}
return h;
}
int main()
{
char s[100];
for(int i=1; i<10; i++)
{
cin.getline(s,100);
cout<<s<<" "<<Heshlash(s);
cout<<endl;
}}](/data/documents/1bee1d5d-4c11-4f87-9572-3fcccea54ebd/page_24.png)
![25
Hesh funksiya . Hesh jadvalni initsializatsiyalash
Hesh jadvalga element qo’shish
//Ro ’yxatning boshiga kiriting](/data/documents/1bee1d5d-4c11-4f87-9572-3fcccea54ebd/page_25.png)
![26
Elementni izlash](/data/documents/1bee1d5d-4c11-4f87-9572-3fcccea54ebd/page_26.png)
![27
Elementni o’chirish](/data/documents/1bee1d5d-4c11-4f87-9572-3fcccea54ebd/page_27.png)
![28
Xulosa
Xulosa sifatida shuni aytib o’tish mumkinki, bu kurs ishi 3 bo’limdan va 8
ta rejadan tashkil topgan. Bu kurs ishida hesh jadvallari haqida yoritilgan.
H esh jadvallari muvoffaqiyatli bajarilishida muhim rol o’ynovchi omil
hisoblanadi . Hesh jadvali - bu kalit -qiymat juftlarini saqlash uchun ma'lumotlar
struktura si hisoblanadi .
1) Elementlarga kalit orqali kirish mumkin
2) Kalitlar satrlar, raqamlar, ko'rsatkichlar bo'lishi mumkin
Hash jadvallar o'rtacha O(1) vaqt ichida elementlarni qo'shish, izlash va
o'chirishga imkon beradi . H esh algoritmi qidiruv algoritm hisoblanadi. Hesh
jadvallari katta katta ro’yxatlar ichidan bizga kerakli mahsulotni topadi.
Misol sifatida sabzavotlar degan ro’yxat olinsa va bu ro’yxatda heshdan
foydalanilsa, bu hesh orqali shu ro’yxatga mahsulot qo’shish, mahsulotni
o’chirish va mahsulotni qidirish kabi amallarni bajarish mumkin.
Bu kurs ishida hesh jadval haqida asosiy tu shunchlar va ularni tuzish bosqichlari
hamda usullari haqida yoritilgan. Amaliy masalalar va ularning algoritmlari c++
dasturlash tili yordamida tuzilgan.
Telefon kontaktlardan kerakli ismni topmoqchi bo’lsak, ka ntaktlar soni
qancha bo’lishidan qat’iy nazar bizga tezda biz kiritgan ism haqida ma’lumot
topib beradi( agar shu ism bo’lsa). Bunda ham hesh funksiyasining o’rni katta.
Googledan biror narsani qidirayotgan bo’lsangiz ham juda ko’p ma’lumotlar
ichidan siz kiritgan so’z yoki gap haqida ma’lumot topib beradi. O’sha paytning
o’zida googledan juda ko’p odam foydalanayotgan bo’lishi mumkin. Lekin
shunga qaramay sizga juda qisqa vaqt ichida kiritgan ma’lumotingiz haqida
ko’plab maqolalar va shunga o’xshash qo’llanmalarni topib beradi. Bu ham
yaxshi h eshning ishidir.](/data/documents/1bee1d5d-4c11-4f87-9572-3fcccea54ebd/page_28.png)
![29
ADABIYOTLAR
1. Горстко А.Б. Познакомьтесь с математическим моделированием. М., Знание,
1991.
2. Музафаров Х.А., Баклушин М.Б., Абдураимов М.Г. Математическое моде-
лирование. –Т., Университет. 2002. (эл.вар.)
3. А. А. Самарский, А. П. Михайлов. Математическое моделирование. М.,
Наука, 1997.
4. Ю.Ю.Тарасевич. Математическое и компьютерное моделирование. –М.,
УРСС, 2003.
5. Введение в математическое моделирование. Под ред. В. П. Трусова. -М., Ло-
гос, 2005.
6. Арнольд В.И. Жёсткие и мягкие математические модели. -М., - МЦНМО.
2000.
7. M. Mo’minov, I. Bozorov - Amaliy masalalarni m atematik modellashtirish.
8. Журавлев Ю.И. Экстремальные алгоритмы в математических моделях для
задач распознавания и классификации. ДАН АН Рос., т. 231, №3 .
Qidiruv saytlar :
www.Google.uz
www.hesh funksiya.uz
www.Yandex.uz](/data/documents/1bee1d5d-4c11-4f87-9572-3fcccea54ebd/page_29.png)
1 O’ZBEKISTON RESPUBLIKASI OLIY VA O’RTA -MAXSUS TA’LIM VAZIRLIGI SAMARQAND DAVLAT UNIVERSITETI RAQAMLI TEXNOLOGIYALAR FAKULTETI DASTURIY INJINIRING YO`NALISHI 107 -GURUH TALABASI YO`LDOSHEV DAVRONBEKNING “ALGORITM VA MA’LUMOTLAR STRUKTURASI” FANIDAN “HESH JADVALLAR VA ULARNI TASHKIL ETISH” MAVZU- SIDA TAYYORLAGAN KURS ISHI Topshirdi: Yo‘ldoshev D Tekshirdi: Abdusalomova G .
2 Mundari ja KIRISH ................................ ................................ ................................ ................................ ................................ .. 3 I BOB. HESH JADVALLA RI ASOSLARI ................................ ................................ ................................ ......... 4 1.1.HESH TUSHUNCHASI ................................ ................................ ................................ ........................... 4 1.2. HESH ALGORITMLA RI ................................ ................................ ................................ ...................... 7 II BOB . KOLLIZIYA TUSHUNCH ASI ................................ ................................ ................................ ............ 10 2.1 KOLLIZIYA HAQID A TUSHUNCHA ................................ ................................ ............................... 10 2.2. KOLLIZIYA ANIQL IGI (COLLISION RESOL UTION) ................................ ................................ . 11 2.3 . OCHIQ ADRESLASH ................................ ................................ ................................ .......................... 16 III BOB. AMALIY MASA LALAR ................................ ................................ ................................ .................... 19 3.1.SATRLI FUNKSIYAL AR UCHUN HESH -FUNKSI YASINI QO ’LLASH ................................ ...... 19 3.2. SONLAR UCHUN HE SH -FUNKSIYASI ................................ ................................ ........................... 21 3.3.IKKILIK DARAXTLA RDA IZLASH VA HESH J ADVALLAR ................................ ...................... 22 HESH JADVALNI REALIZ ATSIYA QILISH ................................ ................................ ................................ . 22 XULOSA ................................ ................................ ................................ ................................ .............................. 28 ADABIYOTLAR ................................ ................................ ................................ ................................ ................. 29
3 Kirish Hozirgi kunda amaliy matematika va kibernetika fanining asosiy yo`nalishlaridan biri – tasvirlarni aniqlash masalasidir. Bu yo`nalishning muhimligi avvalo shu bilan asoslanadiki juda ko`pgina amaliy masalalar mavjudki, ularni to`liq matematik qa’tiylik bilan asoslangan metodlar bilan yechish qiyin yoki yechib bo`lmaydi. Bunday masalalarga, masalan, geologiya, texnika va tibbiyotda uchraydigan diagnost ika va bashorat qilish masalalari misol bo`la oladi. Tasvirlarni aniqlash masalalasi metodlarining bu sohalarda keng tarqalishing sabablarirdan yana biri, ularni tadbiqida bu sohalardagi boshlang`ich ma`lumotlarni yuqori darajada formallash talab qilinmayd i. Tasvirlarni aniqlash nazariyasi optimal yechimni axtarish muammosini diskret analogidir. Bu masalaga nafaqat eng yaxshi yechimni sintezi masalasi, balki boshqa muammoli amaliy masalalar sinfi ham keltiriladi. Hesh jadvali - bu assotsiativ massiv interfeysini amalga oshiruvchi ma'lumotlar tuzilmasi, ya'ni juftlarni saqlashga (kalit, qiymat) va uchta operatsiyani bajarishga imkon beradi: yangi juftlikni qo'shish, qidirish operatsiyasi va juftlikni kalit bilan o'chirish. Hesh jadvallarining ikkita asosiy varianti mavjud: zanjirli va ochiq adreslash. H esh jadvali ba'zi bir ?????? massivini o'z ichiga oladi, ularning elementlari juftliklar (ochiq adreslash bilan hesh jadvali) yoki juftliklar ro'yxati (zanjir bilan hesh jadvali). Hes hlash – bu ixtiyori uzunlikdagi kirish ma'lumotlari majmuasini ma'lum bir algoritm tomonidan bajarilgan, belgilangan o'lchamdagi chiqish massiviga aylantirish jarayoni. Bunday algoritmni amalga oshiruvchi funksiya hesh funktsiya , transformatsiya natijasi x ash yoki xash yig'indisi deyiladi. Hesh funktsiyasi quyidagi xususiyatlarga ega: - bir xil ma'lumotlar bir xil xashni beradi; - "deyarli har doim" turli xil ma'lumotlar boshqacha hesh beradi.
4 I BOB. Hesh jadvallari asoslari 1.1.Hesh tushunchasi Katta hajmdagi ma'lumotlarda ma'lumotlarni izlash jarayoni ko'p vaqt talab etadi, bu esa qidiruv kaliti yordamida sezilarli miqdordagi elementlarni ko'rish va taqqoslash zarurati bilan bog'liq. Ko'rish oynasini mahalliylashtirish orqali qidiruvni qisqartirish mu mkin. Misol uchun, ma'lumotlarni qidirish kaliti bo'yicha tartiblang, ularni biron bir guruh atributiga ko'ra bir -biriga mos kelmaydigan bloklarga bo'ling yoki haqiqiy ma'lumotlarni qidirish jarayonini soddalashtiradigan kod bilan moslang. Heshlash (yoki he shlash , inglizcha hashing ) - ma'lum turdagi va ixtiyoriy uzunlikdagi kirish ma'lumotlar massivini belgilangan uzunlikdagi chiqish bit qatoriga aylantirish. Bunda transformatsiyalar ham deyiladi. Hesh funktsiya- lari yoki konvolyutsiya funksiyalari va ularnin g natijalari deyiladi. Hash, hash kodi, hash jadvali yoki hazm qilish xabarlar (inglizcha) xabar dayjesti ). Hesh jadvali - bu ma'lumotlar tuzilishi, bu assotsiativ massiv interfeysini amalga oshiradi, ya'ni kalit -qiymat juftlarini saqlash va uchta amalni bajarish im- konini beradi: yangi juft qo'shish operatsiyasi, qidirish operatsiyasi va kalit bo'yi- cha juftlikni o'chirish operatsiyasi. Hesh -jadval - bu hesh funktsiyasi tomonidan ma'lum tartibda tuzilgan massiv. funksiya hisoblash uchun oddiy bo'lishi kerak; funksiya hesh -jadvaldagi kalitlarni iloji boricha bir tekis taqsimlashi kerak; funktsiya kalit qiymatlar o'rtasidagi hech qanday munosabatni manzil qiymatlari o'rtasidagi munosabatlarga moslashtirmasligi kerak; funktsiya to'qnashuvlar sonini minimal lashtirishi kerak, ya'ni turli tugmalar bitta hesh qiymatiga to'g'ri keladigan vaziyatlar (bu holda kalitlar deyiladi. si- nonimlar ). Bunda yaxshi hesh funksiyasining birinchi xossasi kompyuterning xususiyatlariga, ikkinchisi esa ma'lumotlar qiymatlariga bog 'liq. Agar barcha ma'lumotlar tasodifiy bo'lsa, hesh funktsiyalari juda oddiy bo'lar edi (kalitning bir necha bitlari kabi). Biroq, amalda tasodifiy ma'lumotlar
5 juda kam uchraydi va siz butun kalitga bog'liq bo'lgan funktsiyani yaratishingiz kerak. Agar he sh funksiyasi aholini taqsimlasa mumkin bo'lgan kalitlar indekslar to'plami ustidan bir xilda, keyin xeshlash kalitlar to'plamini samarali ravishda ajratadi. Eng yomoni, barcha kalitlar bitta indeksga xeshlanganda. To'qnashuvlar sodir bo'lganda, bir xil hesh jadvali katagiga da'vo qiluvchi kalitlarni saqlash uchun yangi joy topish kerak. Bundan tashqari, agar to'qnashu- vlarga ruxsat berilsa, u larning sonini kamaytirish kerak. Ba'zi maxsus holatlarda to'qnashuvlardan butunlay qochish mumkin. Misol uchun, agar barcha element kalitlari oldindan ma'lum bo'lsa (yoki juda kamdan -kam hollarda o'zgartirilsa), ular uchun ba'zi in'dektsion hesh funktsiya sini topish mumkin, bu ularni hesh jadvalining katakchalari o'rtasida to'qnashuvsiz taqsimlaydi. Hesh jadvallari quyidagilarga mos kelishi kerak xususiyatlari . Hesh -jadvalda operatsiyani bajarish kalitning hesh funktsiyasini hisoblashdan boshlanadi. Olingan hesh qiymati asl massivning indeksidir. Saqlangan massiv elementlari soni mumkin bo'lgan hesh qiymatlari soniga bo'linadi va bo'ladigan m uhim parametr , bu operatsiyalarning o'rtacha bajarilishi vaqtini belgilaydi. Qidiruv, kiritish va oʻchirish operatsiyalari oʻrtacha O(1) vaqtni olishi kerak. Biroq, bu taxmin massiv o'lchami qiymatini oshirish va hesh jadvaliga yangi juft- lik qo'shish bilan bog'liq bo'lgan hesh jadvali indeksini qayta tiklash uchun mum- kin bo'lgan apparat xarajatlarini hisobga olmaydi. To'qnashuvni hal qilish mexanizmi har qanday hesh jadvalining muhim qismidir. Heshing, mumkin bo'lgan qiymatlarning keng doirasi kichik hajmdagi xo- tirada saqlanishi kerak bo'lganda foydali bo'ladi va tez, deyarli tasodifiy kirish usuli kerak bo'ladi. Hesh -jadvallar ko'pincha ma'lumotlar bazalarida va ayniqsa, ma'lumotlar bazalarida qo'llaniladi til protsessorlari identifikatorlar jadvalini qayta ishlash tezligini oshiradigan kompilyatorlar va assemblerlar kabi. Kundalik hayotda xeshlashdan foydalanishga misollar kutubxonadagi kitoblarni tematik kataloglar bo'yicha taqsimlash, lug'atl arda so'zlarning birinchi harflari bo'yicha