pair_insert (keyvalue, mapvalue) - mapga yangi element qo'shiladi
erase (iterator position) - elementni iterator ko'rsatgan joydan olib
tashlaydi
erase (const g) - mapdan "g" kalit qiymatini olib tashlaydi
clear () - mapdagi barcha elementlarni olib tashlaydi
Kolliziya muammosi. Tabiiyki, savol tugʻiladi, nega biz bir qator
katakchaga ikki marta kirib olishimiz mumkin emas, chunki har bir
elementga mutlaqo boshqacha natural sonlarni taqqoslaydigan
funksiyani taqdim etish shunchaki mumkin emas. Kolliziya muammosi
xesh funksiyasi 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.
Mavzu yuzasidan savollar: 1. Xesh jadval nima?
2. Xesh jadvallardan foydalanish samaradorligini taqqoslang
3. Xesh funksiyasiga misol keltiring
4. Satrlar uchun xesh funksiyasini qoʻllang
166
5. Xesh funksiya ma‘lumotlar strukturasi qoʻllaniladigan sohalarga
qaysilar kiradi?
Mustaqil ishlash uchun masalalar: 1. C++ tilida xesh jadvallarni hosil qiling.
2. C++da xesh jadvallarning metodlarini qoʻllang
14-§. Xesh funksiya Xesh funksiyalar – ixtiyoriy uzunlikdagi kirish ma‘lumotini
chiqishda belgilangan uzunlikdagi xesh qiymatga aylantirib beruvchi bir
tomonlama funksiyalarga aytiladi. Xesh funksiyalar kriptografiya va
zamonaviy axborot xavfsizligi sohasida ma‘lumotlarni toʻlaligini
tekshirishda foydalaniladi. Elektron toʻlov tizimlari protokollarida ham
istemolchi kartasi ma‘lumotlarini bank-emitentga toʻliq yetkazish uchun
foydalaniladi.
Xesh funksiya – ixtiyoriy uzunlikdagi M-ma‘lumotni fiksirlangan
uzunlikga siqish yoki ikkilik sanoq sistemasi ifodalangan ma‘lumotlarni
fiksirlangan uzunlikdagi bitlar ko‗rinishidagi qandaydir kombinatsiyasi
(svertkasi) deb ataluvchi funksiya.
Ta‟rif. Xesh-funksiya deb, har qanday
h: X
Y
oson hisoblanuvchi va
M –ma‘lumot uchun h(M) = H fiksirlangan
uzunlikga ega bo‗lgan funksiyaga aytiladi.
Berilgan M-ma‘lumotning h(M) –xesh qiymatini topish uchun
avvalo ma‘lumot biror «m» -uzunlikdagi bloklarga ajratilib chiqiladi.
Agar M-ma‘lumot uzunligi «m» -ga karrali bo‗lmasa, u holda oxirgi
to‗lmay qolgan blok «m»- uzunlikga olindan kelishib olingan maxsus
usulda biror simvol yoki belgi (masalan ―0‖ yoki ―1‖) bilan to‗ldirilib
chiqiladi. Natijada hosil qilingan M-ma‘lumot bloklariga:
M= { M
1
, M
2
,.......M
n
)
quyidagicha siqishni (svertkani) hisoblash protsedurasi qo‗llaniladi:
H
0
=
,
H
i
= f ( M
i
, H
i-1
) , i =1,2,......n
167
h(M)= H
n
;
bu yerda
-qandaydir fiksirlangan boshlangʻich vektor.
Misol sifatida quyidagi keng tarqalgan:
f ( M
i
, H
i-1
) = E
k
( M
i
H
i-1
) i =1,2,......n
xesh-funksiyani keltirib o‗tish mumkin.
Bu yerda E-simmetrik shifrlash algoritmi (masalan DES, GOST
28147-87, AES –FIPS 197 va hakoza), k- esa shifrlash algoritmi maxfiy
kaliti, H
0
= 0,
- XOR (mod 2 bo‗yicha mos bitlarni qo‗shish) amali.
