12-mavzu. Xeshlash va xesh jadvallar Reja

0  A  N-1, shart o’rinli bo’ladi.
Ushbu usuldan ko’pincha daraxtlarda hamda uni tadbiq etish muvoffaqiyat keltiruvchi masalalarda foydalaniladi.
Kalitlarni akslantirish bilan bog’liq bo’lgan asosiy muammo bu kalitlarni qabul qilishi mumkin bo’lgan qiymatlar to’plamini xotira adresi (massiv indekslari) qabul qilishi mumkin bo’lgan to’plamdan ancha kengligidir. Quyidagicha misol ko’rib chiqaylik. Faraz qilaylik, 1000 ta odam bor. Har bir odamni aniqlash (identifikatsiya qilish) uchun kalit sifatida ismlarini qaraylik. Faraz qilaylik har bir ism 16 tagacha harfdan tashkil topgan bo’lsin. U holda biz bo’lishi mumkin bo’lgan kalit qiymatlari to’plamini (bu yerda bo’lishi mumkin bo’lgan kalitlar to’plami 26¹⁶ ta elmentdan iborat bo’ladi, agar alifbo 26 ta xarfdan iborat bo’lsa), 10³ ta indeksli massivga akslantirish lozim bo’ladi. Yuqoridagi misoldan ko’rinib turibdiki, N funktsiya ichiga akslantiruvchi akslantirish bo’ladi, ya’ni «ko’pgina qiymat bir qiymatga akslantiriladi». Agar biror bir kalit berilgan bo’lsa, u holda qidiruv amalining birinchi qadami - kalit bilan bog’langan indeksni hisoblash, ya’ni h = H(k), ikkinchi va asosiysi – tekshirish bo’lib hisoblanadi, ya’ni bunda haqiqatdan ham h funktsiya T massivda (jadvalda) k kalitli elementni identifikatsiya qilayotgani tekshiriladi.

Akslantirish funktsiyasini tanlash

O’z-o’zidan ma’lumki, akslantirishning ixtiyoriy yaxshi funktsiyasi kalitlarni berilgan indekslar oralig’iga iloji boricha teng taqsimlaydi. Agarda ushbu talab o’rinli bo’lsa, u holda qo’shimcha shart va cheklanishlar bo’lmaydi. Agarda akslantirish mutlaqo tasodifiy bo’lsa yana ham yaxshiroq bo’ladi. Mazkur usulga “maydalash” (xeshlashtirish), ya’ni argumentni bo’laklash deb ataladi. N funktsiya esa “joylashtirish funktsiyasi” deb ataladi. Ravshanki, N funktsiya iloji boricha samarali xisoblanishi lozim, ya’ni uncha ko’p bo’lmagan asosiy arifmetik amallardan tashkil topgan bo’lishi lozim.
Faraz qilaylik, k kalit tartib raqamini barcha mumkin bo’lgan kalitlar to’plamida ifodalovchi ORD(k) funktsiya berilgan bo’lsin. Bundan tashqari, i massiv indeksi 0 ... N — 1 oraliqda joylashgan deb faraz qilamiz, bu yerda N — massiv o’lchami. Bunday holda “joylashtirish funktsiyasi” sifatida quyidagi funktsiyani olish mumkin:
H(k) = ORD(k) MOD N
Agarda “joylashtirish funktsiyasi” yuqoridagi kabi aniqlanadigan bo’lsa, u holda kalit qiymatlari indekslar o’zgarishi oralig’iga tekis taqsimlanadi. SHu sababli, kalitlarni akslantirish amalga oshirilayotgan vaqtda ko’pincha uni asos qilib olishadi. Bundan tashqari, agar masiv uzunligi N ikkining qandaydir darajasiga teng bo’lsa, u holda funktsiya samarali hisoblanadi. Lekin, agar kalit xarflar ketmaketligidan tashkil topgan bo’lsa, u holda aynan bunday funktsiyadan voz kechishga to’g’ri keladi. Sababi, bunday holatda barcha kalitlar tengextimollikga ega deb qarash noto’g’ri bo’ladi. Natijada, faqatgina bir necha belgilar bilan farqlanuvchi so’zlarni bitta indeksga akslantirish extimolligi yuqori bo’ladi, bu esa kalitlarni notekis taqsimlanishiga olib kelishi mumkin. SHu sababli, amaliy masallar hal qilinayotganda N sifatida tub sonlarni olish tavsiya etiladi.