Mavzu: Xesh jadvallari va funktsiyalari

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.