1 mustaqil ish mavzu: Ma’lumotlarni tashkil qilishning kalitlarni akslantirish usuli (xeshlashtirish). Xesh funksiyani tanlash qoidalari Bajardi

O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI
VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

kafedrasi
Ma’lumotlar tuzilmasi va algoritmlar fani bo’yicha

№1 MUSTAQIL ISH

Mavzu: Ma’lumotlarni tashkil qilishning kalitlarni akslantirish usuli (xeshlashtirish). Xesh funksiyani tanlash qoidalari
Bajardi: 216.20 – guruh talabasi Aliqulov Suhrob Dilshod o’g’li
Tekshirdi: Akbarova M.
Toshkent – 2021
REJA

1. 
   Kirish
   
2. 
   Heshlashtirish
   
3. 
   Hesh funksiyalarini tanlash qoidalari
   
4. 
   Amaliy qism
   
5. 
   Xulosa
   

Tasavvur qiling sizda katta ma’lumotlar tuzilmasi bor. Va ular tartiblangan yoki tartiblanmagan. Siz bu ikki xil holda ham ma’lumotlarni saralashingiz(qidirishingiz) kerak. Va bunda agar ma’lumotlar saralangan bo’lsa Binary search metodini qo’llashingiz maqsadga muvofiq. Ammo Binary search uchun O(log₂N). Yani siz ro’yxatdan sizga kerakli ma’lumotni topishingiz uchun log₂N amal bajarasiz. Hashlash - bu katta hajmdagi ma'lumotlar elementini xeshlash funktsiyasi yordamida kichikroq jadvalga solish jarayoni. Hashlash orqali O(1)ga erishishimiz mumkin. Bu bir qator kalit qiymatlarni massiv indekslari diapazoniga aylantirish texnikasi. U chiziqli yoki ikkilik qidiruv bilan solishtirganda keyingi darajadagi qidiruv usulini osonlashtirish uchun ishlatiladi. Xeshlash har qanday ma'lumotni doimiy vaqt ichida yangilash va olish imkonini beradi O(1). Doimiy vaqt O(1) operatsiya ma'lumotlar hajmiga bog'liq emasligini bildiradi. Elementlarni tezroq olish imkonini berish uchun ma'lumotlar bazasi bilan xeshlash qo'llaniladi.
Hash funktsiyasi - ruxsat etilgan jarayon kalitni xesh-kalitga aylantiradi, bu Xesh funktsiyasi deb nomlanadi. Bu funktsiya kalitni oladi va uni Xesh qiymati yoki Xesh deb ataladigan ma'lum uzunlikdagi qiymatga moslashtiradi. Xesh qiymati asl belgilar qatorini ifodalaydi, lekin u odatda asl nusxadan kichikroq.
Hash jadvali - Xesh jadvali yoki xesh xaritasi kalit-qiymat juftlarini saqlash uchun ishlatiladigan ma'lumotlar strukturasidir. Bu keyinchalik ularni topishni osonlashtirish uchun saqlangan narsalar to'plamidir. U indeksni kerakli qiymatni topish mumkin bo'lgan busket lar yoki slot lar qatoriga hisoblash uchun xesh funktsiyasidan foydalanadi. Bu har bir ro’yxat busket sifatida tanilgan ro'yxatlar qatoridir. U kalitga asoslangan qiymatni o'z ichiga oladi. Xesh jadvali xarita interfeysini amalga oshirish uchun ishlatiladi va Lug'at sinfini kengaytiradi. Xesh jadvali sinxronlashtiriladi va faqat noyob elementlarni o'z ichiga oladi.

Yaxshi xesh funktsiyasi quyidagi xususiyatlarga ega bo'lishi kerak:

1. 
   Samarali hisoblash mumkin.
   
2. 
   Kalitlarni bir xilda taqsimlash kerak (har bir jadval pozitsiyasi har bir kalit uchun bir xil bo'lishi mumkin)
   

Masalan: Telefon raqamlari uchun yomon xesh funksiyasi birinchi uchta raqamni olishdir. Eng yaxshi funksiya oxirgi uchta raqam hisoblanadi. E'tibor bering, bu eng yaxshi xesh funksiyasi bo'lmasligi mumkin. Yaxshiroq usullar bo'lishi mumkin.
Hash funksiyaning yaxshi ishlayotganini ikki holatga qarab belgilaymiz:

1. 
   Bir kalitga har doim bir qiymat qaytarganda
   
2. 
   Xar hil kalitga har doim xar hil qiymat qaytarganda
   

Amalda, biz tez-tez yaxshi bajaradigan hash funktsiyasini yaratish uchun evristik usullardan foydalanishimiz mumkin. Kalitlarni taqsimlash haqidagi sifatli ma'lumotlar ushbu dizayn jarayonida foydali bo'lishi mumkin. Umuman olganda, xesh funktsiyasi kalitning har bir bitiga bog'liq bo'lishi kerak, shuning uchun ikkita kalit faqat bitta bit yoki bitta bit guruhida farqlanadi (guruh kalitning boshida, oxirida yoki o'rtasida bo'lishidan qat'i nazar). kalit bo'ylab mavjud) turli qiymatlarga xesh. Shunday qilib, kalitning bir qismini oddiygina ajratib oladigan xesh funktsiyasi mos kelmaydi. Xuddi shunday, agar ikkita kalit oddiy raqamlangan bo'lsa yoki bir-birining belgilar almashinuvi (masalan, 139 va 319), ular ham turli qiymatlarga xeshlanishi kerak.
Ikkita evristik usul - bo'linish va ko'paytirish yo'li bilan xeshlash, ular quyidagicha:
Mod usuli:
Xesh-funksiyalarni yaratishning ushbu usulida biz kalitning qolgan qismini table_size ga bo'lingan holda olib, jadvalning uyalaridan biriga kalitni joylashtiramiz. Ya'ni, hash funktsiyasi
h(kalit) = kalit mod table_size ya'ni % table_size kaliti
Bu faqat bitta bo'linish operatsiyasini talab qilganligi sababli, bo'linish orqali xeshlash juda tezdir.
Bo'lish usulidan foydalanganda biz odatda table_size ning ma'lum qiymatlaridan qochamiz, masalan table_size r sonining darajasi bo'lmasligi kerak, chunki agar table_size = r^p bo'lsa, h(kalit) kalitning eng past tartibli p bitlari bo'ladi. Agar biz barcha past tartibli p-bit naqshlarining bir xil ehtimoli borligini bilmasak, biz kalitning barcha bitlariga bog'liq holda xesh funktsiyasini loyihalashtirganimiz ma'qul. Ma'lum bo'lishicha, bo'linish usuli bilan eng yaxshi natijalarga jadval o'lchami asosiy bo'lganda erishiladi. Biroq, table_size asosiy bo'lsa ham, qo'shimcha cheklov talab qilinadi. Agar r kompyuterdagi mumkin boʻlgan belgilar kodlari soni boʻlsa va jadval_sizi r % jadval_sizi 1 ga teng boʻlgan tub son boʻlsa, h(key) = kalit % table_size xesh-funksiyasi shunchaki belgilarning ikkilik koʻrinishining yigʻindisidir. asosiy mod table_size.
Faraz qilaylik, r = 256 va table_size = 17, bunda r % table_size, ya'ni 256 % 17 = 1. Shunday qilib, kalit = 37599 uchun, uning hashi 37599 % 17 = 12 Lekin kalit = 573 uchun uning hash funktsiyasi ham 573 % 17 = 12 Demak, ushbu xesh funktsiyasi orqali ko'plab kalitlar bir xil xeshga ega bo'lishi mumkinligini ko'rish mumkin. Bu to'qnashuv deb ataladi. 2 ning aniq darajasiga unchalik yaqin boʻlmagan asosiy koʻrsatkich table_size uchun yaxshi tanlovdir.
Ko'paytirish usuli:
Ko'paytirish usulida k kalitini 0 < c < 1 oralig'ida c doimiy haqiqiy songa ko'paytiramiz va k * c ning kasr qismini ajratamiz. Keyin bu qiymatni table_size m ga ko'paytiramiz va natijaning butunlayni olamiz. Sifatida ifodalanishi mumkin
h(k) = round (m * (k * c mod 1)) yoki h(k) = round(m * frac (k * c))
Bu yerda math.h standart kutubxonasida mavjud round(x) funksiyasi x haqiqiy sonning butun qismini, frac(x) esa kasr qismini beradi. [frac(x) = x – qavat(x)]
Ko'paytirish usulining afzalligi shundaki, m qiymati kritik emas, biz odatda uni 2 daraja sifatida tanlaymiz (ba'zi bir butun p uchun m = 2p), chunki biz bu funktsiyani aksariyat kompyuterlarda osongina amalga oshirishimiz mumkin.

Amaliy qism

Bizda quyidagicha list bor:

1. 
   Olma – 10000
   
2. 
   Banan – 18000
   
3. 
   Apelsin – 25000
   
4. 
   Uzum – 7000
   
5. 
   Anor – 8000
   
6. 
   Xurmo – 5000
   

Hesh funksiya yordamida biz yaatgan tuzilmamizga osongina o’zgarishlar kirita olishimiz va undan ma’lumotlar ola olishimiz zarur.
Python-da Lug'at ma'lumotlar turlari xesh-jadvallarni amalga oshirishni ifodalaydi. Lug'atdagi kalitlar quyidagi talablarga javob beradi.

1. 
   Lug'atning kalitlari xeshlangan, ya'ni xesh funksiyasiga berilgan har bir noyob qiymat uchun noyob natijani yaratuvchi xesh funktsiyasi orqali yaratilgan.
   
2. 
   Lug'atdagi ma'lumotlar elementlarining tartibi aniqlanmagan.
   

Shunday qilib, biz quyida ko'rsatilgan lug'at ma'lumotlar turlaridan foydalangan holda xesh jadvalini amalga oshirishni ko'ramiz.

Lug’atda ma’lumotlarni e’lon qilish

Lug'atdagi qiymatlarga kirish
Lug'at elementlariga kirish uchun uning qiymatini olish uchun kalit bilan birga to‘rtburchak kvadrat qavslardan foydalanishingiz mumkin.

Kiritilgan kalitlar uchun qiymatlarni to‘g’ri chiqardi.
Ma’lumotlarga o’zgartirishlar kiritish


Xeshlashdan maqsad O(1) murakkabligidagi elementni qidirish, qo'shish va o'chirishdir. Xesh funktsiyasi kalitlarni xesh jadvali bo'ylab bir xilda taqsimlash uchun mo'ljallangan. Xesh jadvalidagi yuklanish omili a xesh jadvalidagi uyalar soni kiritiladigan kalitlar soni sifatida aniqlanishi mumkin. Ochiq adreslash uchun yuk koeffitsienti a har doim birdan kichik bo'ladi. Ochiq adreslash yordamida kiritish, oʻchirish va qidirishning murakkabligi 1/(1-a). Zanjirlash usuli yordamida kiritish, oʻchirish va qidirishning murakkabligi (1+a).