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

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.

To'qnashuvlarni hal qilish
Xesh funktsiyasini tuzish-bu xeshing asosida qidiruvni amalga oshiruvchi dasturchi tomonidan bajarilishi kerak bo'lgan barcha ish emas. Bundan tashqari, to'qnashuvlarni hal qilish mexanizmini amalga oshirish kerak. Xesh funktsiyalari bilan bir qatorda, ularning afzalliklari va kamchiliklari mavjud bo'lgan bir nechta variantlar mavjud.

Zanjir usuli
Zanjir usuli-bu muammoni hal qilishning eng aniq usuli. Xesh funktsiyasini qaytargan indeks bilan jadval elementi allaqachon band bo'lsa, unga bog'langan ro'yxat qo'shiladi. Shunday qilib, agar bir necha xil kalit qiymatlari uchun Xesh funktsiyasining bir xil qiymati qaytarilsa, unda bu manzilda tegishli ro'yxat uchun ko'rsatgich mavjud, bu barcha qiymatlarni o'z ichiga oladi. Ushbu ro'yxatda qidirish oddiy qidirish orqali amalga oshiriladi, chunki har qanday ro'yxatning Xesh funktsiyasini to'g'ri tanlash juda qisqa. Lekin bu erda ham qo'shimcha optimallashtirish mumkin. O'tish: saytda harakatlanish, qidiruv 558) bu elementlar murojaat vaqtida ro'yxatini tartiblashtirish mumkin, deb qayd etadi. Boshqa tomondan, jadvalning katta o'lchamlari tezlikni oshirish uchun kerak bo'ladi, ammo bu xotirani bila turib bo'sh elementlarga keraksiz sarflashga olib keladi. Quyidagi rasmda to'qnashuv yuz berganda Xesh jadvalining tuzilishi va zanjirlar shakllanishi ko'rsatilgan.


Ochiq manzil
Qarama - qarshiliklar bilan bog'liq muammolarni hal qilishning yana bir usuli, k tugmachasi yoki bo'sh joy [3] topilgunga qadar, turli xil jadval yozuvlarini tartibda ko'rib chiqish orqali bog'lanishdan butunlay voz kechishdir. Fikr, ushbu kalit tomonidan "sinov ketma-ketligi", ya'ni jadval pozitsiyalarining ketma-ketligi bilan belgilanadigan qoidani shakllantirishdir, bu esa k kalitini kiritish yoki qidirish paytida ko'rish kerak. agar qidiruvda bo'sh hujayra mavjud bo'lsa, unda k jadvalda mavjud emas, chunki bu hujayra qo'shilganda ishg'ol qilinadi, chunki. algoritm bir xil zanjirdan o'tdi. Usullarning bu umumiy klassi [4] ochiq manzil deb ataladi.