Fan Ma’lumotlar tuzilmasi mustaqil ish mavzu: Kalitlarni akslantirish (Heshlashtirish) usuli, samaradorligi xamda reheshlash usuli Guruh: 216-20 Bajardi: Valijonov n tekshirdi: Akbarova M

Zanjirband qilish va ochiq manzillar

Zanjirband qilish	Ochiq manzil
Elementlarni stol tashqarisida saqlash	Ochiq manzil elementlari faqat jadval
mumkin	ichida saqlanishi kerak
Istalgan vaqtda zanjirlashda xash	Ochiq manzilda xash jadvalidagi
jadvalidagi elementlarning soni xash
jadvalining kattaligidan kattaroq bo'lishi	elementlar soni xash jadvalidagi indekslar
mumkin	sonidan oshmaydi.
	Agar o'chirish talab qilinmasa. Faqat
Yo'q qilishda zanjir eng yaxshi usul	qo'shish va qidirish kerak, agar ochiq
hisoblanadi	manzil bo'lsa yaxshi bo'ladi
	Ochiq adreslash zanjirga qaraganda
Zanjirband qilish ko'proq joy talab qiladi	kamroq joy talab qiladi.

Kolliziya xolati.

Kolliziya ro‘y berishini butunlay oldini oladigan, yaxshi xesh-funksiyani qurish mumkinmi?
Aniqki, butunlay kolliziyaga uchramasligi uchun xesh-funksiyaning har bir natijaviy qiymati unikal bo‘lishi kerak.
Kolliziya muammosini echish uchun turli usullarni qo‘llash mumkin. Ulardan biri “reheshlash” metodi hisoblanadi.

Bu metodga ko‘ra, A element uchun xesh-funksiya orqali hisoblangan h(A) adresi band bo‘lgan yacheykani ko‘rsatsa, unda n₁=h₁(A) funksiya qiymatini hisoblash zarur va n₁ adresga tegishli yacheykani bandligini tekshirish kerak. Agar n₁ ham band bo‘lsa, unda h₂(A) qiymat hisoblanadi, shu tariqa bo‘sh yacheyka to’lguncha yoki h_i(A) navbatdagi qiymat h(A) bilan mos kelgunga qadar davom etadi. Oxirgi holatda identifikatorlar jadvali to‘lgan va bo‘sh joy boshqa yo‘q, degan xatolik to‘g‘risida ma’lumot beradi.

h_i(A) funksiyani hisoblashning eng oddiy metodi, uni

h_i(A)=(h(A)+p_i)modN_m asosida qurishdir, bu erda p_i qandaydir

bir hisoblangan butun son, N_m –identifikatorlar jadvalidagi

elementlarning maksimal soni. O‘z o‘rnida eng oddiy usul p_i ni
o‘rniga i ni qo‘yish bo‘ladi. Unda quyidagi formulani olamiz

h_i(A)=(h(A)+i)modN_m. Bu holda xesh-funksiyaning bir xil

qiymatlariga mos kelgan identifikatorlarni joylash uchun bo‘sh
yacheykani qidirish mantiqan hesh-funksiya h(A) ko‘rsatgan
joydan boshlanadi.

C ++ da xeshlash dasturi
Quyida C ++ da xeshlash yoki xash jadvali amalga oshiriladi:
Dastur:
#include
#include
using namespace std;
/*

Bu ochiq manzilda chiziqli tekshirish uchun kod. Agar siz kvadrat probirovka qilishni va ikkilamchi xashlashni xohlasangiz, ular ham mavjud

xash funktsiyasidan foydalanganda (kod + 1)% hFn-ni boshqa funktsiya bilan almashtirganimda ushbu koddagi manzilni ochish usullari. */

void Insert(int ary[],int hFn, int Size){

int element,pos,n=0;

cout<<"Qo'shish uchun asosiy elementni kiriting\n"; cin>>element;

pos = element%hFn;

while(ary[pos]!= INT_MIN) { // INT_MIN va INT_MAX hujayralar bo'shligini bildiradi. Agar hujayra bo'sh bo'lsa, tsikl buzilib, elementning qo'shilishi uchun pastdan pastga tushadi if(ary[pos]== INT_MAX)

break;
pos = (pos+1)%hFn;
n++;
if(n==Size)
break; // Agar jadval to'la bo'lsa, biz sindirishimiz kerak, agar buni tekshirmasak,
pastadir cheksiz ko'chaga o'tadi.
}
if(n==Size)
cout<<"Xash jadvali elementlarga to'la edi\n Bu elementni kiritish uchun joy yo'q\n\n";
else
ary[pos] = element; //Element qo'shilmoqda
}

void Delete(int ary[],int hFn,int Size){

/*
o'chirish paytida juda ehtiyotkorlik bilan kuzatish talab etiladi. Ushbu o'chirish funktsiyasining kodini tushunish uchun dastur oxiridagi yozuvga qarang */

int element,n=0,pos;

cout<<"O'chirish uchun elementni kiriting\n"; cin>>element;
pos = element%hFn;
while(n++ != Size){
if(ary[pos]==INT_MIN){
cout<<"Element xash jadvalda topilmadi\n"; break;
}
else if(ary[pos]==element){
ary[pos]=INT_MAX;
cout<<"Element o'chirildi\n\n";
break;
}
else{
pos = (pos+1) % hFn;
}
}

if(--n==Size)

cout<<"Element xash jadvalda topilmadi\n";
}
void Search(int ary[],int hFn,int Size){
int element,pos,n=0;

cout<<"Qidirmoqchi bo'lgan elementni kiriting\n"; cin>>element;

pos = element%hFn;
while(n++ != Size){
if(ary[pos]==element){
cout<<"Element indeksda topildi "<

break;
}

else

if(ary[pos]==INT_MAX ||ary[pos]!=INT_MIN)

pos = (pos+1) %hFn;
}
if(--n==Size)
cout<<"Element xash jadvalda topilmadi\n";
}
void display(int ary[],int Size){
int i;
cout<<"Indeks\tQiymat\n";
for(i=0;icout<}
int main(){
int Size,hFn,i,choice;
cout<<"Xash jadvalining hajmini kiriting\n";
cin>>Size;
int ary[Size];

cout<<"Xash funktsiyasini kiriting[if mod 10 enter 10]\n"; cin>>hFn;

for(i=0;iary[i]=INT_MIN; //INT_MINni tayinlash katakning bo'shligini bildiradi
do{
cout<<"O'zingizning tanlovingizni kiriting\n";
cout<<" 1-> Kiritmoq\n 2-> O'chirish\n 3-> Displey\n 4-> Qidirilmoqda\n 0-> Chiqish\n";

cin>>choice;

switch(choice){
case 1:
Insert(ary,hFn,Size);
break;
case 2:
Delete(ary,hFn,Size);
break;
case 3:
display(ary,Size);
break;
case 4:
Search(ary,hFn,Size);
break;
default:
cout<<"To'g'ri tanlovni kiriting\n";
break;
}
}while(choice);
return 0;
}
/*
Izoh: O'chirish funktsiyasi va qidirish funktsiyasi uchun tushuntirish
xash jadvalida 22, 32, 42 elementlari 2, 3, 4 indeks holatlarida bo'lsa deylik.
Endi o'chirib tashlang (22). Belgilangan xash funktsiyasi bo'yicha biz avval 2-indeksni tekshiramiz. Topildi, shuning uchun o'chirildi. Va bu ko'rsatkichni nillga aylantiring. Keyin o'chirishni qo'llang (32). Bu safar u birinchi navbatda 2-indeksni tekshirdi, ammo uning hech narsasi yo'qligini aniqladi, keyin biz to'xtab, 32-element emas deymiz
xash jadvalda topilgan. Ammo u 3-indeksda mavjud. Ammo boshqa indeksni tekshirishni yoki qilmaslikni qanday bilishimiz kerak? Buning uchun
har qanday elementni o'chirib tashlaganimizda, INT_MAX bilan belgilaymiz, bu esa ilgari ba'zi bir elementlar hozirda mavjudligini bildiradi

u o'chirildi. Shuning uchun bu erda to'xtamang, kerakli element keyingi indeksda

ko'rsatilishi mumkin.
*/
Natija: