O’zbekiston respublikasi oliy va o’rta maxsus ta’lim vazirligi toshkent axborot texnologiyalari universiteti


-ma’ruza. Kalitlarni akslantirish



Download 18,83 Mb.
bet103/225
Sana30.12.2021
Hajmi18,83 Mb.
#89889
1   ...   99   100   101   102   103   104   105   106   ...   225
Bog'liq
“MTA” fani boyicha oquv uslubiy qollanma

18-ma’ruza. Kalitlarni akslantirish (joylashtirish)

Reja:

  1. Kalitlarni akslantirish.

  2. Akslantirish funksiyasini tanlash.

  3. Ziddiyatni hal qilish algoritmlari

 

Kalit so’zlar: xeshlash, xesh funksiya, xesh algoritm, ziddiyatlarni xal qilish algoritmlari.
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.
Kolliziya xolati

Kolliziya ro’y berishini butunlay oldini oladigan, yaxshi xesh-funksiyani qurish mumkinmi?

Aniqki, butunlay kolliziyaga uchramasligi uchun xesh-funksiyaning xar bir natijaviy qiymati unikal bo’lishi kerak.

Kolliziya muammosini yechish uchun turli usullarni qo’llash mumkin. Ulardan biri “rexeshlash” metodi hisoblanadi.

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.






Download 18,83 Mb.

Do'stlaringiz bilan baham:
1   ...   99   100   101   102   103   104   105   106   ...   225




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish