Mavzu: Xesh jadvallari va funktsiyalari

Minimal mukammal xeshing

Yuqorida aytib o'tilganidek, ideal xesh funktsiyasi tez ishlashi va to'qnashuvlar sonini kamaytirish kerak. Ushbu funktsiyani ideal (perfect xesh function) [12] deb ataymiz. Bunday funktsiya bilan to'qnashuvlarni hal qilish mexanizmidan foydalanmaslik mumkin, chunki har bir so'rov muvaffaqiyatli bo'ladi. Lekin siz yana bir shartni qo'yishingiz mumkin: Xesh funktsiyasi bo'shliqlarsiz xesh stolini to'ldirishi kerak. Bu funktsiya minimal ideal xesh funktsiyasi deb ataladi. Bu xotira iste'moli va ish tezligi jihatidan ideal holat. Shubhasiz, bunday xususiyatlarni izlash juda ahamiyatsiz vazifadir.

Ideal xesh xususiyatlarini topish uchun algoritmlardan biri R. Chichelli tomonidan taklif qilingan [13]. Minimal ideal xesh funktsiyasini yaratish kerak bo'lgan ba'zi so'zlar to'plamini ko'rib chiqing. Bu C++tilining ba'zi kalit so'zlari bo'lsin. Bu ba'zi bir funktsiya bo'lsin, qaysi har bir belgi ma'lum bir raqamli kodi bog'liq, uning holati va uzunligi. Keyin funktsiyani yaratish vazifasi belgilar kodlari jadvalini yaratishga olib keladi, masalan, funktsiya minimal va ideal. Algoritm juda oddiy, lekin ish uchun juda ko'p vaqt talab etadi. Jadvalda barcha qiymatlarni to'liq qidirish, agar kerak bo'lsa, barcha qiymatlarni tanlash uchun, hech qanday to'qnashuv bo'lmasligi uchun orqaga qaytish bilan amalga oshiriladi.