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



Download 62,22 Kb.
bet6/9
Sana15.11.2022
Hajmi62,22 Kb.
#866865
1   2   3   4   5   6   7   8   9
Bog'liq
Mavzu Xesh jadvallari va funktsiyalari

Chiziqli manzil
Lineer manzil (lineer Study, linear probing) deb nomlanadigan eng oddiy ochiq manzil sxemasi davriy tekshiruv ketma-ketligini qo'llaydi
h(K), h(K - 1), …, 0, M – 1, M – 2, …, h(K) + 1
va quyidagi algoritm bilan tavsiflanadi ([3], p. 562). M elementlaridan jadvalda K kalitini qidiradi. Agar jadval to'liq bo'lmasa va kalit yo'q bo'lsa, u qo'shiladi.

Jadval xujayralari jadval[i] deb nomlanadi, bu erda 0 ≤ i < m va bo'sh yoki band bo'lishi mumkin. N yordamchi o'zgaruvchisi band bo'lgan tugunlar sonini kuzatish uchun ishlatiladi. Har bir qo'shimchada 1 tomonidan oshiriladi.


O'rnatish i = h (K)
Jadval [i] bo'sh bo'lsa, 4-bosqichga o'ting, aks holda bu manzil kerakli bo'lsa, algoritm tugaydi.

I = i-1 ni o'rnating, agar i < 0 bo'lsa, keyin i = i +M. 2 bosqichiga qaytish.

Qo'shish, chunki qidiruv muvaffaqiyatsiz bo'ldi. Agar n = M – 1 bo'lsa, unda algoritm toshib ketadi. Aks holda, N ni oshiring, jadval[i] hujayrasini band qilib belgilang va unga K kalitining qiymatini o'rnating.

Tajribalar ([3], p. 564) algoritm jadvalni to'ldirishning boshida yaxshi ishlayotganini ko'rsatadi, ammo to'ldirish jarayoni sekinlashadi va uzoq namunalar seriyasi tez-tez uchraydi.



Kvadrat va o'zboshimchalik bilan manzillash
Birlikda doimiy o'zgarish o'rniga, chiziqli manzilda bo'lgani kabi, quyidagi formuladan foydalanishingiz mumkin [15]
h = h + a2,
qaerda a-bu harakat raqami. Ushbu turdagi manzil juda tez va oldindan taxmin qilinadi (u har doim bir xil yo'llardan o'tadi 1, 4, 9, 16, 25, 36 va hokazo). Jadvaldagi to'qnashuvlar qanchalik ko'p bo'lsa, bu yo'l qanchalik uzoq. Bir tomondan, bu usul jadvalga ko'ra yaxshi taqsimot beradi, ikkinchisi esa noto'g'ri hisoblash uchun ko'proq vaqt talab etadi.

O'zboshimchalik manzil ketma-ketlikni olish uchun tasodifiy sonlar oldindan hosil ro'yxatini foydalanadi [15]. Bu tezlik bilan g'alaba qozonadi, lekin dasturchi vazifasini biroz murakkablashtiradi.



Download 62,22 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8   9




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