3- mavzu. Xesh jadval va xesh funksiyalar. Xesh funksiyalarga misol

Kolliziyalar bilan kurashish usullari

Dastlabki paytlarda xesh–funksiyalar katta fayllarda izlashni tashkillashtirish uchun ishlatilar edi va shuning uchun xeshlashga oid dastlabki  adabiyotlarda  xesh–jadvallarda  kolliziyalar bilan kurashish usullari bayon etilgan. Xesh-jadvallar uchun ikki usul mavjud:

1) zanjirsimon bog’lanish usuli;

2) ochiq adresslash usuli.

Birinchi usul xesh funksiyaning har bir qiymatiga bittadan Mta bog’lamli ro’yxat tashkillashtirishga asoslangan. Ro’yxatlarda bir xil qiymatli xesh-kod beruvchi kalitlar saqlanadi. Umumiy xolda, agar Nta kalitlar va Mta ro’yxatlar bor bo’lsa, xesh-jadvalning o’rtacha o’lchami N/M bo’ladi va xeshlash ishning o’rtacha miqdorini  ketma-ket izlash algoritmiga nisbatan M marta kamayishiga olib keladi.

Ikkinchi usul jadval masssivida kalit–qiymat juftliklar saqlanishiga asoslangan. Bu xolda xavolalardan to’liq voz kechib, kerakli K kalit yoki bo’sh pozitsiya topilgunga qadar jadvalning yozuvlari birin-ketin qarab chiqiladi. Jadval yacheykalarini qarab chiqish ketma-ketligi tasodifiy urinishlar ketma ketligi deyiladi.