Algoritm tushunchasi

Xesh funksiyalarda kolliziya – ikkita har xil ma’lumotdan bir xil
xesh qiymat hosil boʻlib qolishi. Kolliziyaning oldini olish yoʻllaridan
biri bu xesh jadval hisoblanadi. Xeshlash algoritmlarining bardoshliligi
xa xavfsizliligi kolliziyaga chidamliligi bilan aniqlanadi.

49 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 qidiriladiChiziqli 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

50 Hesh funksiyasi va unga talablar

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.
Oddiy xesh funksiyalar: Adler-32, CRC, FNV, Murmur2, PJW-
32, TTH, Jenkins hash.
Kriptografik xesh funksiyalar: CubeHash, BLAKE, BMW,
ECHO, FSB, Fugue, Grøstl, JH, Hamsi, HAVAL, Keccak (SHA-3),
Kalit hosil qiluvchi xesh funksiyalar: bcrypt, PBKDF2, scrypt.
Kriptografik xesh funksiyalarning esa quyidagi turlari mavjud:
1) kalitli xesh funksiya; 2) kalitsiz xesh funksiya.
Odatda kalitsiz xesh funksiyalardan quyidagi xossalarni
qanoatlantirishi talab qilinadi:
1) bir tomonlilik;
2) kolliziyaga bardoshlilik;
3) xesh qiymatlari teng bo‘lgan ikkita ma’lumotni topishga
bardoshlilik.