Mavzu: Xesh jadvallari va funktsiyalari

To'qnashuvlarni hal qilish

Xesh funktsiyasini tuzish-bu xeshing asosida qidiruvni amalga oshiruvchi dasturchi tomonidan bajarilishi kerak bo'lgan barcha ish emas. Bundan tashqari, to'qnashuvlarni hal qilish mexanizmini amalga oshirish kerak. Xesh funktsiyalari bilan bir qatorda, ularning afzalliklari va kamchiliklari mavjud bo'lgan bir nechta variantlar mavjud.

Zanjir usuli

Zanjir usuli-bu muammoni hal qilishning eng aniq usuli. Xesh funktsiyasini qaytargan indeks bilan jadval elementi allaqachon band bo'lsa, unga bog'langan ro'yxat qo'shiladi. Shunday qilib, agar bir necha xil kalit qiymatlari uchun Xesh funktsiyasining bir xil qiymati qaytarilsa, unda bu manzilda tegishli ro'yxat uchun ko'rsatgich mavjud, bu barcha qiymatlarni o'z ichiga oladi. Ushbu ro'yxatda qidirish oddiy qidirish orqali amalga oshiriladi, chunki har qanday ro'yxatning Xesh funktsiyasini to'g'ri tanlash juda qisqa. Lekin bu erda ham qo'shimcha optimallashtirish mumkin. O'tish: saytda harakatlanish, qidiruv 558) bu elementlar murojaat vaqtida ro'yxatini tartiblashtirish mumkin, deb qayd etadi. Boshqa tomondan, jadvalning katta o'lchamlari tezlikni oshirish uchun kerak bo'ladi, ammo bu xotirani bila turib bo'sh elementlarga keraksiz sarflashga olib keladi. Quyidagi rasmda to'qnashuv yuz berganda Xesh jadvalining tuzilishi va zanjirlar shakllanishi ko'rsatilgan.

Ochiq manzil

Qarama - qarshiliklar bilan bog'liq muammolarni hal qilishning yana bir usuli, k tugmachasi yoki bo'sh joy [3] topilgunga qadar, turli xil jadval yozuvlarini tartibda ko'rib chiqish orqali bog'lanishdan butunlay voz kechishdir. Fikr, ushbu kalit tomonidan "sinov ketma-ketligi", ya'ni jadval pozitsiyalarining ketma-ketligi bilan belgilanadigan qoidani shakllantirishdir, bu esa k kalitini kiritish yoki qidirish paytida ko'rish kerak. agar qidiruvda bo'sh hujayra mavjud bo'lsa, unda k jadvalda mavjud emas, chunki bu hujayra qo'shilganda ishg'ol qilinadi, chunki. algoritm bir xil zanjirdan o'tdi. Usullarning bu umumiy klassi [4] ochiq manzil deb ataladi.

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.