Mustaqil ishi mavzu: Ma’lumotlarni xeshlash argoritmlari

Xeshlash(yoki xeshlash, ingliz xeshlash) - ma'lum turdagi va ixtiyoriy uzunlikdagi kirish ma'lumotlar massivini belgilangan uzunlikdagi chiqish bit qatoriga aylantirish. Bunday transformatsiyalar ham deyiladi hash funktsiyalari yoki konvolyutsiya funksiyalari va ularning natijalari deyiladi hash, hash kodi, hash jadvali yoki hazm qilish xabarlar (inglizcha) xabar dayjesti).
Xesh jadvali- bu ma'lumotlar tuzilishi, bu assotsiativ massiv interfeysini amalga oshiradi, ya'ni kalit-qiymat juftlarini saqlash va uchta amalni bajarish imkonini beradi: yangi juft qo'shish operatsiyasi, qidirish operatsiyasi va kalit bo'yicha juftlikni o'chirish operatsiyasi. Xesh-jadval - bu xesh funktsiyasi tomonidan ma'lum bir tartibda tuzilgan massiv.
funksiya hisoblash uchun oddiy bo'lishi kerak;
funksiya xesh-jadvaldagi kalitlarni iloji boricha bir tekis taqsimlashi kerak;
funktsiya kalit qiymatlar o'rtasidagi hech qanday munosabatni manzil qiymatlari o'rtasidagi munosabatlarga moslashtirmasligi kerak;
funktsiya to'qnashuvlar sonini minimallashtirishi kerak, ya'ni turli xil kalitlar bitta xesh qiymatiga mos keladigan vaziyatlar (bu holda kalitlar deyiladi. sinonimlar).
Bunda yaxshi xesh funksiyasining birinchi xossasi kompyuterning xususiyatlariga, ikkinchisi esa ma'lumotlar qiymatlariga bog'liq.
Agar barcha ma'lumotlar tasodifiy bo'lsa, xesh funktsiyalari juda oddiy bo'lar edi (kalitning bir necha bitlari kabi). Biroq, amalda tasodifiy ma'lumotlar juda kam uchraydi va siz butun kalitga bog'liq bo'lgan funktsiyani yaratishingiz kerak. Agar xesh funksiyasi aholini taqsimlasa mumkin bo'lgan kalitlar indekslar to'plami ustidan bir xilda, keyin xeshlash kalitlar to'plamini samarali ravishda ajratadi. Eng yomoni, barcha kalitlar bitta indeksga xeshlanganda.
To'qnashuvlar sodir bo'lganda, bir xil xesh jadvali katagiga da'vo qiluvchi kalitlarni saqlash uchun yangi joy topish kerak. Bundan tashqari, agar to'qnashuvlarga ruxsat berilsa, ularning sonini kamaytirish kerak. Ba'zi maxsus holatlarda to'qnashuvlardan butunlay qochish mumkin. Misol uchun, agar barcha element kalitlari oldindan ma'lum bo'lsa (yoki juda kamdan-kam hollarda o'zgartirilsa), ular uchun ba'zi in'ektsion xesh funktsiyasini topish mumkin, bu ularni xesh jadvalining katakchalari o'rtasida to'qnashuvsiz taqsimlaydi. Shu kabi xesh funksiyalaridan foydalanadigan xesh-jadvallar to'qnashuvni hal qilish mexanizmiga muhtoj emas va ular bilan xesh-jadvallar deb ataladi. to'g'ridan-to'g'ri murojaat qilish.
Xesh jadvallari quyidagilarga mos kelishi kerak xususiyatlari.
Xesh-jadvalda operatsiyani bajarish kalitning hash funktsiyasini hisoblashdan boshlanadi. Olingan xesh qiymati asl massivning indeksidir.
Saqlangan massiv elementlari soni mumkin bo'lgan xesh qiymatlari soniga bo'linadi xesh jadvalini to'ldirish omili (yuk koeffitsienti) va operatsiyalarning o'rtacha bajarilishi vaqti bog'liq bo'lgan muhim parametrdir.
Qidiruv, kiritish va oʻchirish operatsiyalari oʻrtacha O(1) vaqtni olishi kerak. Biroq, bu taxmin massiv o'lchami qiymatini oshirish va xesh jadvaliga yangi juftlik qo'shish bilan bog'liq bo'lgan xesh jadvali indeksini qayta tiklash uchun mumkin bo'lgan apparat xarajatlarini hisobga olmaydi.
To'qnashuvni hal qilish mexanizmi har qanday xesh jadvalining muhim qismidir.
Hashing, mumkin bo'lgan qiymatlarning keng doirasi kichik hajmdagi xotirada saqlanishi kerak bo'lganda foydali bo'ladi va tez, deyarli tasodifiy kirish usuli kerak bo'ladi. Xesh-jadvallar ko'pincha ma'lumotlar bazalarida va ayniqsa, ma'lumotlar bazalarida qo'llaniladi til protsessorlari identifikatorlar jadvalini qayta ishlash tezligini oshiradigan kompilyatorlar va assemblerlar kabi. Kundalik hayotda xeshlashdan foydalanishga misollar kutubxonadagi kitoblarni tematik kataloglar bo'yicha taqsimlash, lug'atlarda so'zlarning birinchi harflari bo'yicha tartiblash, universitetlarda mutaxassisliklarni shifrlash va boshqalar.
To'qnashuvlarni hal qilish usullari
To'qnashuvlar xesh-jadvallardan foydalanishni murakkablashtiradi, chunki ular xesh kodlari va ma'lumotlar o'rtasidagi birma-bir yozishmalarni buzadi. Biroq, yuzaga keladigan qiyinchiliklarni bartaraf etishning yo'llari mavjud:
zanjir usuli (tashqi yoki ochiq xeshlash);
ochiq adreslash usuli (yopiq xeshlash).
Zanjir usuli. Elementlarni ulash texnologiyasi shundan iborat elementlarni o'rnatish bir xil xesh qiymatiga mos keladigan , zanjir ro'yxatida bog'langan. Pozitsiya raqami i kalitning xesh qiymati i ga teng bo'lgan elementlar ro'yxatining boshiga ko'rsatgichni saqlaydi; agar to'plamda bunday elementlar bo'lmasa, i holatida NULL yoziladi. Shaklda. 38.1 to'qnashuvlarni hal qilishda zanjirlar usulini amalga oshirishni ko'rsatadi. 002 kaliti chiziqli ro'yxatda tashkil etilgan ikkita qiymat bilan da'vo qilinadi.
Har bir massiv yacheykasi bir xil kalit xesh qiymatiga mos keladigan kalit-qiymat juftlarining bog'langan ro'yxatiga (zanjir) ko'rsatgichdir. To'qnashuvlar shunchaki bitta elementdan uzunroq zanjirlarga olib keladi.
Ma'lumotlarni qidirish yoki o'chirish operatsiyalari unda berilgan kalitga ega elementni topish uchun tegishli zanjirning barcha elementlarini qidirishni talab qiladi. Ma'lumotlarni qo'shish uchun tegishli ro'yxatning oxiriga yoki boshiga element qo'shishingiz kerak va agar to'ldirish omili juda katta bo'lsa, massiv hajmini oshiring va jadvalni qayta tiklang.
Har bir element jadvalning istalgan pozitsiyasiga teng ehtimollik bilan tushishi mumkin deb faraz qilsak va boshqa element qayerda tugaganidan qat'i nazar,