Mavzu: Xesh jadvallari va funktsiyalari

Xesh vazifalari

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.

Yaxshi 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.
Nazariy jihatdan haqiqiy tasodifiy bo'lmagan fayllardan tasodifiy ma'lumotlarni yaratish uchun Xesh funktsiyasini aniqlash mumkin emas. Biroq, amalda, oddiy arifmetik operatsiyalar yordamida juda yaxshi taqlid qilish mumkin. Bundan tashqari, u tez-tez (haqiqiy tasodifiy ma'lumotlarga nisbatan kam) to'qnashuvlar minimal soni bilan xesh vazifalarni yaratish uchun ma'lumotlar xususiyatlarini foydalanishingiz mumkin [3].
Ehtimol, xeshingning eng aniq va eng oddiy usullaridan biri kvadratning o'rta kvadrat usuli bo'lib, kalit kvadratga o'rnatiladi va o'rtada bir nechta raqam olinadi. Bu erda va bundan tashqari, kalit birinchi navbatda arifmetik operatsiyalarni bajarish uchun butun songa to'g'ri keladi deb taxmin qilinadi. Biroq, bu usul chap yoki o'ng tomonda juda ko'p nol bo'lmasa yaxshi ishlaydi. Ko'pgina testlar ikkita asosiy xeshing turini yaxshi ko'rsatdi, ulardan biri bo'linishga asoslangan, ikkinchisi esa ko'paytiriladi. Biroq, bu mavjud bo'lgan yagona usullar emas, bundan tashqari, ular har doim ham maqbul emas.
Bo'linish usuli
Bo'linish usuli juda oddiy - qolgan qismi m ga bo'linadi:
h(K) = K mod M
Ushbu o'zgarishni diqqat bilan tanlash kerak. Agar siz uni 100ga tenglashtirsangiz va kalit tug'ilgan yilga to'g'ri keladigan bo'lsa, unda tarqatish bir qator vazifalar uchun juda noaniq bo'ladi (masalan, yosh beysbol ligasi o'yinchilarini aniqlash). Bundan tashqari, funktsiya ham doimiy qiymati hatto k va g'alati bo'lsa ham bo'ladi - g'alati bilan, bu kiruvchi natija olib keladi. Bundan ham yomoni, Agar M kompyuterning raqamlash darajasi bo'lsa, natija faqat o'ngdagi kalitning bir nechta raqamlariga bog'liq bo'ladi. Xuddi shunday, m ning uchta ko'pligi bo'lmasligi ham mumkin, chunki harfli kalitlarda ularning ikkitasi faqat harflarni almashtirish bilan farqlanadi, uchta ko'paytma farq bilan raqamli qiymatlarni berishi mumkin (qarang: [3], p.552). Yuqoridagi fikrlashlar oddiy raqamni ishlatish yaxshiroq degan fikrga olib keladi. Aksariyat hollarda bunday tanlov juda qoniqarli.

Yana bir misol – kalit, bir belgi liniyasi C. Xesh funktsiyasi birinchi va oxirgi belgilarni to'plash va keyinchalik 101 (jadval kattaligi) tomonidan bo'linishdan qolgan qoldiqni hisoblash orqali bu qatorni tamsayıga ko'rsatadi. Bu Xesh funktsiyasi bir xil birinchi va oxirgi belgilar bilan to'qnashuvga olib keladi. Misol uchun, "start" va "slant" satrlari 29 indeksida ko'rsatiladi. Bundan tashqari, bir xesh vazifasini muomala, chiziq barcha belgilarni sarhisob. "Bad" va "dab" satrlari bir xil indeksga aylanadi. Eng yaxshi natijalar belgilar bit aralashtirish ishlab chiqarish xesh vazifasini beradi.

Amalda, bo'linish usuli eng keng tarqalgan [7].