2-amaliy topshiriq!

4 – Vazifa: Ma’lumotlarni xeshlash algoritmlari. Xesh jadval va xesh funksiyalari.

2-AMALIY ISH	Ma’lumotlarni xeshlash algoritmlari. Xesh jadval va xesh funksiyalari.
Ishning maqsadi:	Xeshlash algoritmlarini, xesh jadvalni tuzishni o’rganish va amalda qo’llash.
Ish tartibi:	Nazariy qismdagi ma’lumotlarni o’rganib chiqish. Amaliy qismda keltirilgan amaliyot ishini bajarish. Topshiriqlar bo’limida keltirilgan masalalarni yechish Amalga oshirilgan ish bo’yicha hisobot tayyorlash va topshirish

NAZARIY QISM VA AMALIY QISM

XESHLASH TUSHUNCHASI

Katta hajmli ma’lumotlarnda paydo bo’ladigan muammo bu qidirish. Agar ma’lumotlar tartibsiz joylashgan bo’lsa chiziqli qidirish qo’llaniladi, effektivligi O(n/2). Agar massiv tartiblangan bo’lsa ikkilik qidirish qo’llanilishi mumkin, effektivligi O(log₂n).
Tartiblangan ma’lumotlar va ikkilik daraxt bilan ishlashda qo’yish, o’chirish amallari qiyinchilik keltirib chiqaradi. Bunda daraxt balansni yo’qotadi keyin uni yana balansga olish kelishga to’g’ri keladi.
Bu holatlarda xeshlash algoritmi ishlatiladi. Bunda massiv ma’lumotlarini anglatuvchi kalit yaratiladi va uning asosida ma’lumotlar jadvalga yoziladi. Bu jadval xesh jadval deb ataladi. Kalit i=h(key) funksiyasi orqali aniqlanadi. Bu funksiya xesh-funksiya deb ataladi. Xeshlash algoritmi qidirilayotgan elementni uning kaliti bo’yicha xesh-jadvalda joylashuvini aniqlaydi.
Xeshlash bu katta ko’plikni kichik ko’rinish saqlash usuli.
Masalan, lug’at, bunda ma’lumotlar alifbo tartibida joylashadi, bu yerda alifbo kalit deb qabul qilinadi.
Dasturlashda xeshlash termini 1967 yili Xellerman tarafidan kiritilgan.
Haqiqatda xeshlash bu ma’lumotlarni kalitlari bo’yicha tez qidirish uchun adreslashning maxsus usuli.
Agar to’plam N ta elementdan iborat bo’lsa, uni 2^N ta har xil ko’pliklarga ajratish mumkin.
XESH FUNKSIYA VA XESH-JADVAL
Funksiya, kichik to’plamlar xosiyati belgilaydi, ma’lumotlar elementi kalitini jadval indeksiga (xeshjadval) shakllantiradi. Bu funksiya xesh-funksiya deb ataladi:
i = h(key)
key – kalit, i – jadval indeksi.
Funksiya natijasi bo’yicha bir necha kalit qiymatlari bir xil i indeksini berishi mumkin. Bu holat xeshlashda kolliziya deb ataladi.
Yaxshi funksiya bu kolliziyani minimallashtiradigan va jadval bo’yicha ma’lumotlarni tengday tarqatadigan funksiya bo’lib hisoblanadi.
Mukammal xesh-funksiya bu umuman kolliziya keltirib chiqarmaydigan funksiya.

Xesh-jadval bu oddiy massiv bo’lib, standart emas ko’rinishda adreslanadi.
Xeshlash usullari har xil bo’lib ular h(key) funksiyalari va konfliktlarni yechish usullari bilan farq qiladi.
Masalan, m uzunlikdagi simvolli n ta qator berilgan. Qatorlardan ikkitasini tengligina q marta tekshirish kerak. Buning uchun O(q * n * m) murakkablikda amal bajariladi. Buning o’rniga biz barcha qatorlar xeshlash, saqlash keyin ikki qator solishtirish o’rniga ikki sonni solishtirishimiz mumkin.

Xeshlanadigan obyektlar har xil bo’lishi mumkin. Simvolli qatorlar, rasm, graf, bitli fayllar.
Xesh funksiya faqat bir tarafga ishlaydi, ya’ni xeshlangan kalitni qayta tiklab bo’lmaydi.
XESH-FUNKSIYA METODLARI