1. Dasturiy ta’minot va uning turlari

Xesh funksiya (Xesh funksiya, turlari, kalit hosil qiluvchi xesh funksiyalar, kolliziya muammosi)

Xeshing-ma'lum bir xususiyatga ega bo'lmagan pastki to'plamlarda (elementlarning to'plamlari) bir nechta kalitlarni (odatda saqlash elementlarini va odatda matn satrlari yoki raqamlar shaklida taqdim etilgan) ajratish. Bu xususiyat xeshing funktsiyasi yoki xesh funktsiyasi bilan tavsiflanadi va xesh manzili deb ataladi. Teskari muammoni hal qilish Xesh-tuzilmaga (Xesh-jadval) beriladi: Xesh-manzilda ular kerakli elementga tezkor kirish imkonini beradi. Ideal holda, qidirish vazifalari uchun xesh manzili yagona kalit (ideal xesh funktsiyasi) bilan tavsiflangan elementga kirish uchun yagona manzil bo'lishi kerak. Biroq, amalda, ideal kelishuv bilan almashtirilishi va bir xil Xesh manziliga ega bo'lgan to'plamlar bir nechta elementni o'z ichiga olishi kerak. Keyinchalik, Xesh funktsiyalarining asosiy turlari va ularning ayrim modifikatsiyalari, to'qnashuvlarni hal qilish usullari, Xesh jadvalidagi elementlarni olib tashlash muammolari, shuningdek, xeshingni qo'llash uchun ba'zi variantlar ko'rib chiqiladi.Xesh funktsiyasi k kalitini olgan va k bilan bog'liq ma'lumotlarni olish uchun xesh jadvalida qidirilayotgan manzilni qaytaradigan h(K) funktsiyasidir, masalan, k abonentning telefon raqami va kerakli ma'lumot uning nomi. Bu holda funktsiya bizga kerakli manzilni topish uchun aniq ma'lumot beradi. Telefon daftariga misol, taqdim etilgan CDda demo dasturi bilan tasvirlangan.Qarama-qarshilik h(K1) = h(K2), K1 K K2 esa. Bunday holda, aniq ma'lumot saqlash uchun yangi joy topish kerak. Shubhasiz, to'qnashuvlar sonini kamaytirish kerak. Quyidagi alohida bo'lim to'qnashuvlarni hal qilish usullariga bag'ishlanadi. Xesh funktsiyasi ikki talabni qondirishi kerak:uning hisob-kitoblari juda tez bajarilishi kerak; bu to'qnashuvlar sonini kamaytirish kerak.
Shunday qilib, yaxshi Xesh funktsiyasining birinchi xususiyati kompyuterga, ikkinchisi esa ma'lumotlarga bog'liq. Agar barcha ma'lumotlar tasodifiy bo'lsa, unda Xesh funktsiyalari juda oddiy (masalan, bir nechta kalit) bo'ladi. Biroq, amalda, tasodifiy ma'lumotlar juda kam uchraydi va siz butun kalitga bog'liq bo'lgan funktsiyani yaratishingiz kerak.