Ajratkichlar va ajratish masalasi. Ajratkichlarning ko‘rinishlari. Chekli avtomatlar

Xesh-junksiya F deb R kiruvchi elementlaming to’plamini qandaydir butun
manfiy bo’Imagan Z: F(r) = n, reR, neZ sonlami akslantirishga aytiladi. «Xeshfunksiya» termini inglizcha «hash function» (hash — «meshatb», «smeshivatb»,
«putatb») terminidan kelib chiqadi, «xeshlash» termini o’miga ko’pincha
«randomizasiya», «qayta tartiblash» terminidan foydalaniladi.
R kiruvchi elementlaming mumkin bo’lgan to’plami xesh -funksiyaning
aniqlanish sohasi deb ataladi. F xesh-fimksiyaning qiymatlar to’plami deb Z: Me Z
151
butun manfiy bo’lmagan sonlar to’plamining barcha F: VreR: F(r) eM funksiya
qaytargan qiymatlami o’zida jamlovchi M qism to’plamiga aytiladi.
Xesh-funksiyaning aniqlanish sohasining qiymatlar to’plamiga aks ettirilishi
jarayoni «xeshlash» deb ataladi.
Identifikatorlar jadvali bilash ishlashda xesh-funksiya identifikatorlar ismlarini
butun manfiy bo’lmagan sonlar to’plamiga aks ettirishni bajarishi kerak.
Xesh-fiinksiyalaming aniqlanish sohasi identifikatorlar ismlarining barcha
mumkin bo’lgan to’plamidir.
Xesh-manzillash xesh funksiya tomonidan qaytarilgan qiymatni qandaydir
ma'lumotlar to’plamidan olingan yacheyka manzili sifatida foydalanishni
anglatadi. U holda ma'lumotlar to’plamining o’Ichami xesh funksiya foydalanayotgan
qiymatlar sohasiga mos kelishi kerak.
SHunday qilib, aniq kompilyatorda xesh iunksiyaning qiymatlari sohasi
komptyuteming mumkin bo’lgan manzillar fazosi o’lchamidan oshmasligi shart.
Xesh- manzillashdan foydalanib identifikatorlami tashkil etish usuli ushbu
element uchun hisoblangan xesh-fimksiya tomonidan qaytariladigan manzil bo’yicha
jadvalning har bir elementini yacheykagajoylashtirishdan iboratdir.
U holda, ideal holatda identifikatorlar jadvalining ixtiyoriy elementini
joylashtirish uchun uning xesh -funksiyasini hisoblash va ma'lumotlar to’plamining
kerakli yacheykasiga murojaat etish etarli bo’ladi.
Jadvalda elementni qidirish uchun element uchun xesh-funksiyani hisoblash va
to’plamning berilgan yacheykasi bo’sh emasligini tekshirish zamr (agar u bo’sh
bo’lmasa-element topildi, agar bo’sh bo’Isa-element topilmadi).
Quyidagi 28-rasmda xesh-manzillashdan foydalangan holda identifikatorlami
jadvalini tashkil etish usuli keltirilgan. Rasmda uchta turli Ajf A2, A3 identifikatorlarga

xesh-funksiyaning uchta ni n2, p3 qiymatlari mos keladi. nj n2,	manzillarda
joylashgan	yacheykalarga An A2, A3 identifikatorlar haqidagi ma'lumotlar

joylashtiriladi. A3 identifikatomi qidirishda p3 manzilning qiymati hisoblanadi va
jadvalning mos yacheykasidan ma'lumotlar olinadi.
Ushbu usul, elementni jadvalga joylashtirish vaqti va elementni qidirishga
ketadigan vaqt xesh-funksiyani hisoblashga ketadigan vaqt bilan aniqlanib, elementni
ko’p marta qidirishga ketadigan vaqtga nisbatan kam bo’lganligi sababli,
foydaliroqdir. Usulning ikkita ko’rinib turgan kamchiligi mavjud. Ulardan biri- xotira
hajmidan identifikatorlar jadvalini tashkil etishda foydasiz foydalanish: identifikatorlar
jadvalini saqlash uchun kerak bo’lgan to’plam o’Ichami, jadvaldagi identifikatorlar
soni juda kam bo’lsa ham, xesh-funksiyaning qiymatlar sohasiga mos kelishi shart.
152
Ikkinchi kamchiligi - xesh-funksiyaning aniq mos tanlovini amalga
oshirish zaruriyati.