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.