|
8-amaliy mashg’ulot
Xeshlash algoritmlari,xesh funksiyani tanlash va ziddiyatlarni bartaraf etish usullari.Ularga doir misollarni yechish.
Joylashtirish usuli (xeshlashtirish) ma’lumotlar tuzilmasida element joylashgan o’rinni tez aniqlashga yo’naltirilgan usuldir. Joylashtirish usulida ma’lumotlar oddiy massiv sifatida ifodalangan bo’ladi. Elementni jadvalga qo’shishdan oldin uning adresi xesh-funksiya orqali aniqlanadi: A = h(K), bu yerda K – kalit, A – jadvaldagi element adresi bo’lib, 0 £ A £ N-1, shart o’rinli bo’ladi.
F xesh-funksiya deb R kiruvchi elementlar to’plamini manfiy bo’lmagan butun sonlar to’plami Z ga o’girishga aytiladi. Z:F(r)=n, rϵR, nϵZ. Xesh-adreslash bu xesh-funksiya qiymatlar soxasini qandaydir bir ma’lumotlar massivining yacheykasi adresi sifatida foydalanishdan iborat. U holda ma’lumotlar massivi o’lchami foydalanilayotgan xesh-funksiyaning qiymatlar soxasiga mos kelishi kerak.
Turli A1, A2, A3 identifikatorlar uchun mos ravishda n1, n2, n3 xesh-funksiya qiymatlari to’g’ri kelsin. n1, n2, n3 adreslarga mos yacheykalarda A1, A2, A3 identifikatorlar haqida ma’lumot joylanadi. A3 identifikatorni qidirishda n3 adres qiymati hisoblanadi va tegishli jadval yacheykasidan ma’lumotlar tanlanadi.
Bu metod juda effektiv, elementlari jadvalga joylash vaqti xam, qidiruv vaqti ham faqat xesh-funksiyani xisoblashga ketadi.
Bu usulning 2 ta yaqqol kamchiligi bor. Ulardan biri: identifikatorlar jadvalining xotira xajmidan unumsiz foydalanilishi. Massiv o’lchami xesh-funksiya qiymatlar soxasiga mos kelishi kerak, ayni vaqtda real xolatda jadvalda saqlanayotgan identifikatorlar ancha kam bo’lishi mumkin. Ikkinchi kamchiligi mos keluvchi xesh-funksiyani tanlay bilish.
Xesh-funksiyadan natija olish - “xeshlash” simvollar zanjiri ustida oddiy arifmetik va mantiqiy amallarni bajarish xisobiga erishiladi. xesh-adreslashda identifikatorlar jadvalining bir yacheykasiga 2 ta turli xil bo’lgan identifikatorlar joylashishi mumkin emas. Bu vaziyat, ya’ni 2 yoki undan ortiq identifikatorlar xesh funksiyaning bir xil qiymatiga ega bo’lish xodisasi kolliziya deb nomlanadi. Kolliziyaning yuzaga kelishi 2 ta xar xil identifikator A1 va A2larning xesh-funksiya qiymatlari n1 va n2 bir xil (n1=n2) bo’lishi xisoblanadi. Xesh-funksiyadan natija olish - “xeshlash” simvollar zanjiri ustida oddiy arifmetik va mantiqiy amallarni bajarish xisobiga erishiladi. xesh-adreslashda identifikatorlar jadvalining bir yacheykasiga 2 ta turli xil bo’lgan identifikatorlar joylashishi mumkin emas. Bu vaziyat, ya’ni 2 yoki undan ortiq identifikatorlar xesh funksiyaning bir xil qiymatiga ega bo’lish xodisasi kolliziya deb nomlanadi. Kolliziyaning yuzaga kelishi 2 ta xar xil identifikator A1 va A2larning xesh-funksiya qiymatlari n1 va n2 bir xil (n1=n2) bo’lishi xisoblanadi.
Bu metodga ko’ra, A element uchun xesh-funksiya orqali hisoblangan h(A) adresi band bo’lgan yacheykani ko’rsatsa, unda n1=h1(A) funksiya qiymatini hisoblash zarur va n1 adresga tegishli yacheykani bandligini tekshirish kerak. Agar n1 xam band bo’lsa, unda h2(A) qiymat hisoblanadi, shu tariqa bo’sh yacheyka torilguncha yoki hi(A) navbatdagi qiymat h(A) bilan mos kelgunga qadar davom etadi. Oxirgi xolatda identifikatorlar jadvali to’lgan va bo’sh joy boshqa yo’q degan xatolik to’g’risida ma’lumot beradi.
hi(A) funksiyani xisoblashni eng oddiy metodi, uni hi(A)=(h(A)+pi)modNm asosida qurishdir, bu yerda pi qandaydir bir xisoblangan butun son, Nm –identifikatorlar jadvalidagi elementlarning maksimal soni. O’z o’rnida eng oddiy usul pi ni o’rniga i ni qo’yish bo’ladi. Unda quyidagi formulani olamiz hi(A)=(h(A)+i)modNm. Bu holda xesh-funksiyaning bir xil qiymatlariga mos kelgan identifikatorlarni joylash uchun bo’sh yacheykani qidirish mantiqan xesh-funksiya h(A) ko’rsatgan joydan boshlanadi.
Massiv elementini indeks buyicha topish kerak bo’lsin. Buning uchun avval indeksni xesh adresning mos qiymatiga aylantirish lozim va shundan so’nggina qidiruvni amalga oshirish mumkin.
Xeshlashtirish misolida primary nomli tuzilmalar massividan foydalaniladi:
#define MAX 260
struct htype {
int index; /* mantiqiy indeks */
int val; /* malumotlar elementining xos qiymati */
struct htype *next; /* Shunday xesh-adresli keyingi elemntga ko’rsatkich */
} primary[MAX];
Bu massivdan foydalanishdan avval uni inisializasiya qilish zarur.Quyidagi funksiya index maydoniga -1 qiymatini beradi; Bu qiymat bo’sh elementni bildiradi. NULL qiymati next maydonidagi xeshlashtirishning bo’sh zanjiriga mos keladi.
/* xesh-massivni inisializasiya qilish. */
void init(void)
{
register int i;
for (i=0; i
primary[i].index = -1;
primary[i].next = NULL; /* bo’sh zanjir */
primary[i].val = 0;
}
}
store() prosedurasi yacheyka nomini birlamchi primary massividagi xesh adresga aylantiradi. Xesh adresda ko’rsatilgan pozisiya band bo’lsa, prosedura bu yozuvni avtomatik xolda slstore() fuknsiyaning modifikasiyalangan versiyasi yordamida kolliziya ro’yxatiga qo’shib qo’yadi. Bu funksiyalar quyida keltirilgan.
/* xesh-adresni xisoblash va qiymatini saqlash */
void store(char *cell_name, int v)
{
int h, loc;
struct htype *p;
/* xesh-adresni olish*/
loc = *cell_name - 'A'; /* ustun */
loc += (atoi(&cell_name[1])-1) * 26; /* qator * kenglik + ustun */
h = loc/10; /* hash */
/* agar olingan pozisiya band bo’lmasa, uni saqlash yoki mantiqiy indekslar ustma – ust tushgan xolda saqlash */
if(primary[h].index==-1 || primary[h].index==loc) {
primary[h].index = loc;
primary[h].val = v;
return;
}
/*aks xolda kolliziyalar ro’yxatini tuzish va unga xesh – adresni qo’shish */
p = (struct htype *) malloc(sizeof(struct htype));
if(!p) {
printf("xotira yetishmayapti\n");
return;
}
p->index = loc;
p->val = v;
slstore(p, &primary[h]);
}
/* Elementlarni kolliziya ro’yxatiga qo’shish. */
void slstore(struct htype *i,
struct htype *start)
{
struct htype *old, *p;
old = start;
/* ro’yxat oxirini topish */
while(start) {
old = start;
start = start->next;
}
/* yangi yozuv bilan bog’lash */
old->next = i;
i->next = NULL;
}
Elementning qiymatini olish uchun dastur avval xesh-adresni xisoblaydi va uni qidirilayotgan massiv elementi indeks bilan tengligini tekshiradi.Agar teng bo’lsa yacheyka qiymati qaytariladi, aks xolda kolliziyalar ro’yxatida qidiruv amalga oshiriladi. Bu vazifalarni bajaruvchi find(),quyida keltirilgan:
/* xesh-adresni xisoblash va qiymatini olish. */
int find(char *cell_name)
{
int h, loc;
struct htype *p;
/* xesh-adres qiymatini olish */
loc = *cell_name - 'A'; /* stolbes */
loc += (atoi(&cell_name[1])-1) * 26; /* qator * kenglik + ustun */
h = loc/10;
/* yacheyka topilsa,qiymatni qaytarish */
if(primary[h].index == loc) return(primary[h].val);
else { /* aks xolda kolliziyalar ro’yxatini ko’rish */
p = primary[h].next;
while(p) {
if(p->index == loc) return p->val;
p = p->next;
}
printf("Yacheyka massivda yo’q\n");
return -1;
}
}
Bu dasturga o’chirish funksiyasini qo’yish lozim.
Do'stlaringiz bilan baham: | 
