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.
bet7/9
Sana15.11.2022
Hajmi62,22 Kb.
#866865
1   2   3   4   5   6   7   8   9
Bog'liq
Mavzu Xesh jadvallari va funktsiyalari

Juft aralashgan manzil
Ushbu zanjir tanlash algoritmi chiziqli manzil uchun algoritmga juda o'xshaydi, lekin h1(K) va h2(K) ikkita Xesh funktsiyasidan foydalanib, jadvalni biroz boshqacha tekshiradi. Ikkinchisi 1 dan m – 1 oralig'ida qiymatlarni hosil qilishi kerak, m bilan o'zaro oddiy.
O'rnatish i = h1 (K)
Jadval [i] bo'sh bo'lsa, 6 bosqichiga o'ting, aks holda bu manzil kerakli bo'lsa, algoritm tugaydi.
C = h2(K) ni o'rnating)
I = i – c ni o'rnating, agar i < 0, keyin i = i +M bo'lsa.

Agar jadval [i] bo'sh bo'lsa, u holda 6 qadamiga o'ting. Istalgan manzil ushbu manzilda joylashgan bo'lsa, algoritm tugaydi, aks holda 4 bosqichiga qaytadi.

Qo'shish. 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.

Shubhasiz, bu variant ancha yaxshi taqsimlash va mustaqil zanjirlar beradi. Biroq, qo'shimcha funktsiyani kiritish tufayli biroz sekinroq.

Donald Knut ([3], p.566) qo'shimcha funktsiyani tanlash uchun turli xil variantlarni taklif etadi. Agar m – asosiy raqam va h1(K) = k mod M bo'lsa, siz h2(K) = 1 + (K mod (M – 1)) ni qo'yishingiz mumkin; biroq, Agar m – 1 hatto (boshqacha aytganda, m har doim asosiy sonlar uchun bajariladigan g'alati) bo'lsa, h2(K) = 1 + (k mod (M – 2)) ni qo'yish yaxshi bo'ladi.

Bu erda ikkala funktsiya ham mustaqildir. Gari Knott (Gary Knott) 1968 da oddiy m bilan quyidagi funksiyadan foydalanishni taklif qildi:


h2(K) = 1, agar h1(K) = 0 va h2(K) = m – h1 (K) aks holda(ya'ni h1 (K) > 0).
Ushbu usul qayta bo'linishdan ko'ra tezroq amalga oshiriladi, lekin ikki yoki undan ortiq kalitlarning bir xil yo'ldan borishi ehtimolini oshirishi tufayli namunalar sonining ko'payishiga olib keladi.

Xesh-jadval elementlarini olib tashlash
Ko'pgina dasturchilar algoritmlarga ko'r-ko'rona ishonadilar, hatto ular qanday ishlashi haqida o'ylashga harakat qilmaydilar. Ular uchun Xesh jadvalidagi yozuvlarni o'chirishning aniq usuli ishlamayapti, chunki ular uchun yoqimsiz ajablanib bo'ladi. Misol uchun, agar siz ochiq manzildan foydalanib qidiruv algoritmini ishlatadigan zanjirda joylashgan kalitni olib tashlasangiz, unda barcha keyingi elementlar yo'qoladi, chunki algoritm birinchi band bo'lmagan elementga qo'ng'iroq qiladi.

Umuman aytganda, elementni bo'sh emas, balki masofadan turib belgilash orqali olib tashlash mumkin. Shunday qilib, jadvaldagi har bir hujayra uchta qiymatdan birini o'z ichiga oladi: bo'sh, band, uzoq. Qidirilganda, o'chirilgan elementlar band sifatida muomala qilinadi va qo'shilganda – bo'sh, navbati bilan.

Biroq, u ochiq-oydin emas, bu usul faqat kamdan-kam hollarda ishlaydi, chunki bir marta band joy endi bepul bo'lishi mumkin, va, shuning uchun, qo'shimchalari va olib tashlash uzoq ketma-ketlikdan so'ng, barcha bepul postlar yo'qoladi ,va muvaffaqiyatsiz izlash m cheklar talab qilinadi (qaerda m, biz xesh stol hajmini eslang). Bu juda uzoq jarayon bo'ladi, har bir qadam sifatida №4 qidiruv algoritm (qarang.er-xotin aralashgan bilan manzil bo'limda) o'zgaruvchilar i qiymati tekshiriladi.
Lineer manzilda i elementini olib tashlash algoritmini ko'rib chiqing.
Jadval[i] ni bo'sh hujayra sifatida belgilang va j = i ni o'rnating
i = i – 1 yoki i = i + m, agar salbiy bo'lsa

Jadval [i] bo'sh bo'lsa, algoritm tugaydi, chunki unga kirish uchun ko'proq elementlar yo'q. Aks holda, biz R = h(key[i]) ni o'rnatamiz, bu erda key[i] TABLE [i] da saqlanadigan kalit. Bu bizga asl xesh manzilini beradi. Agar i ≤ r < j yoki r < j < i yoki j < i ≤ r (boshqacha qilib aytganda, r bu ikki o'zgaruvchining orasidagi davriy bo'lsa, bu element yuqorida ko'rsatilgan zanjirda ekanligini ko'rsatadi), qadam 1 ga qayting.

Jadval[j] = jadval[i] yozuvini ko'chirish va birinchi qadamga qaytish kerak.

Ushbu algoritm ishlashning pasayishiga olib kelmasligini ko'rsatish mumkin ([3], p.570). Shu bilan birga, algoritmning to'g'riligi xesh jadvalining chiziqli tekshiruvi qo'llanilishiga juda bog'liq, shuning uchun er-xotin xeshing uchun shunga o'xsxesh algoritm yo'q.

Ushbu algoritm sizga jadvalning ba'zi elementlarini ko'chirishga imkon beradi, bu esa istalmagan bo'lishi mumkin (masalan, Xesh jadvalining elementlariga tashqi havolalar mavjud bo'lsa). Olib tashlash muammosiga yana bir yondashuv axlatni yig'ishda ishlatiladigan ba'zi g'oyalarni uyg'unlashtirishga asoslangan: har bir kalit bilan bog'lanish sonini qancha boshqa kalitlarga duch kelishi haqida gapirish mumkin. Keyin taymerni qayta tiklashda siz bunday hujayralarni bo'sh joyga aylantira olasiz. Jadvalda harakatlanishni oldini olish va har qanday Xesh texnologiyasi bilan ishlaydigan boshqa o'chirish usullari [16] da taklif qilingan.


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