2-bosqich 731-23 guruh talabasining “MA’lumotlar tuzilmasi va algoritmlar” fanidan tayyorlagan mustaqil ishi bajardi: Nasridinov M

Download 0,63 Mb.
bet	6/8
Sana	07.10.2024
Hajmi	0,63 Mb.
	#273963

1 2 3 4 5 6 7 8

Bog'liq
Raqamli texnologiyalar vazirligi muhammad al-xorazmiy nomidagi t

Xesh jadvali - bu assotsiativ massiv interfeysini amalga oshiruvchi ma'lumotlar tuzilmasi, ya'ni juftlarni saqlashga (kalit, qiymat) va uchta amalni bajarishga imkon beradi: yangi juftlikni qo'shish, qidirish amali va juftlikni kalit bilan o'chirish.
Xesh jadvallarining ikkita asosiy varianti mavjud: zanjirli va ochiq adreslash. Xesh jadvali ba'zi bir massivini o'z ichiga oladi, ularning elementlari juftliklar (ochiq adreslash bilan xesh jadvali) yoki juftliklar ro'yxati (zanjir bilan xesh jadvali) boʻladi. Xeshlash – bu ixtiyoriy uzunlikdagi kirish ma'lumotlari majmuasini ma'lum bir algoritm tomonidan bajarilgan, belgilangan o'lchamdagi chiqish massiviga aylantirish jarayoni. Bunday algoritmni amalga oshiruvchi funksiya xesh funksiya, transformatsiya natijasi xesh yoki xesh yigʻindisi deyiladi. Xesh funksiyasi quyidagi xususiyatlarga
ega:

bir xil ma'lumotlar bir xil xeshni beradi;
"deyarli har doim" turli xil ma'lumotlar boshqacha xesh beradi.

Ikkinchi xususiyatdagi "deyarli har doim" izohi xeshlarning aniq o'lchamiga ega bo'lishidan kelib chiqadi, shu bilan birga kirish ma'lumotlari bu bilan cheklanmaydi. Natijada, biz xesh funktsiyasi kirish ma'lumotlari to'plamidan xeshlar to'plamiga
xaritalashni amalga oshiramiz, bu esa ularning kardinalligi ancha past bo'ladi. Dirixle prinsipiga ko'ra, har bir xesh uchun bir nechta turli xil ma'lumotlar to'plamlari bo'ladi. Bunday moslik kolliziya deb ataladi. Agar biron bir muammoni hal qilishda kirish ma'lumotlari cheklangan bo'lsa, siz bunday xeshlar to'plamini tanlashingiz mumkin, shunda uning aniqligi kirish ma'lumotlari to'plamining muhimligidan oshib ketadi. Bunday holda, biz inyeksion xaritalashni aniqlaydigan xesh funksiyasini qurishimiz mumkin (mukammal xeshlash). Biroq, umuman olganda, kolliziya muqarrar. Kolliziya ehtimoli xesh funksiyasi sifatini baholash uchun ishlatiladi. Yaxshi xesh funksiyasi quyidagicha ishlaydi:

mavjud bo'lgan barcha xesh oraligʻi maksimal darajada ishlatiladi;
kirish ma'lumotlarining ozgina o'zgarishi ham mutlaqo boshqacha xeshni berishi kerak, to'qnashuvlar faqat butunlay boshqacha ma'lumotlar uchun ro'y berishi kerak.

Xeshlash o'zi obyektga tasodifiy o'zgaruvchini xaritalashga o'xshaydi. Birinchi xususiyat natijasida xeshlar o'zlarini bir tekis taqsimlangan tasodifiy o'zgaruvchilar kabi tutishi kerak, bu butun diapazondan foydalanishni ta'minlaydi, bu foydali bo'lishi mumkin, masalan, xesh jadvalini tuzishda.

Download 0,63 Mb.

1 2 3 4 5 6 7 8

Download 0,63 Mb.