|
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.
Do'stlaringiz bilan baham: |
