logo

HESH JADVALLAR VA ULARNI TASHKIL ETISH

Yuklangan vaqt:

12.08.2023

Ko'chirishlar soni:

0

Hajmi:

1027.64453125 KB
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  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. 	 	  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	- 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  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.	 	  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	  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  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.	 	  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$	  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  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	. 	  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	  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	  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	  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  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- 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	]. 	
 	  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) );	 	
 }  23 	
 /// initsializatsiyalangan mapni ekranga chiqarish	 	
 for (auto it = mySecondMap.begin(); it != mySecondMap.end(); ++it)	 	
 { 
 cout << (*it).first << "	 : " << (*it).second << endl;	 	
 } 
 return 0;}	 	  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;	 	
 }}	 	
  25 	
Hesh funksiya	. Hesh jadvalni initsializatsiyalash	
Hesh jadvalga element qo’shish	 	
 	 	
//Ro	’yxatning boshiga kiriting	  26 	
Elementni 	izlash	 	
 
 	  27 	
Elementni o’chirish	 	
 
 	  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.	 	
 	 	  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

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