द्विघात जांच

हैश तालिकाओं में हैश टकराव को हल करने के लिए कंप्यूटर प्रोग्रामिंग में द्विघात जांच एक खुला संबोधन योजना है। द्विघात जांच मूल हैश इंडेक्स को लेकर और एक खुले स्लॉट मिलने तक एक मनमाना द्विघात बहुपद के क्रमिक मूल्यों को जोड़कर संचालित होती है।

द्विघात जांच का उपयोग करने वाला एक उदाहरण अनुक्रम है:

$H+1^{2},H+2^{2},H+3^{2},H+4^{2},...,H+k^{2}$ द्विघात जांच एक खुली एड्रेसिंग टेबल में एक अधिक कुशल एल्गोरिदम हो सकती है, क्योंकि यह क्लस्टरिंग समस्या से बेहतर ढंग से बचाती है जो रैखिक जांच के साथ हो सकती है, हालांकि यह प्रतिरक्षा नहीं है। यह अच्छी मेमोरी कैशिंग भी प्रदान करता है क्योंकि यह संदर्भ के कुछ इलाके को संरक्षित करता है; हालाँकि, रैखिक जांच में अधिक स्थानीयता होती है और इस प्रकार, बेहतर कैश प्रदर्शन होता है।

द्विघात फलन

मान लीजिए h(k) एक हैश फंकशन है जो एक तत्व k को [0, m−1] में एक पूर्णांक पर मैप करता है, जहां m तालिका का आकार है। चलो मैं^{मान k के लिए जांच की स्थिति फ़ंक्शन द्वारा दी गई है}

$h(k,i)=h(k)+c_{1}i+c_{2}i^{2}{\pmod {m}}$

जहां सी₂ ≠ 0 (यदि सी₂ = 0, तो h(k,i) एक रैखिक जांच में अवक्रमित हो जाता है)। किसी दी गई हैश तालिका के लिए, c का मान₁ और सी₂ स्थिर रहना।

उदाहरण:

• अगर $h(k,i)=(h(k)+i+i^{2}){\pmod {m}}$, तो जांच क्रम होगा $h(k),h(k)+2,h(k)+6,...$
• एम = 2 के लिएⁿ, स्थिरांक के लिए एक अच्छा विकल्प c है₁ = सी₂ = 1/2, क्योंकि [0, m−1] में i के लिए h(k,i) के मान सभी अलग-अलग हैं (वास्तव में, यह [0, m−1] पर एक क्रमपरिवर्तन है)). इससे एक जांच क्रम बनता है $h(k),h(k)+1,h(k)+3,h(k)+6,...$ (त्रिकोणीय संख्याएँ) जहाँ मान 1, 2, 3, ... से बढ़ते हैं
• प्राइम एम > 2 के लिए, सी के अधिकांश विकल्प₁ और सी₂ [0, (m−1)/2] में i के लिए h(k,i) को अलग बना देगा। ऐसे विकल्पों में सी शामिल है₁ = सी₂ = 1/2, सी₁ = सी₂ = 1, और सी₁ = 0, सी₂ = 1. हालाँकि, किसी दिए गए तत्व के लिए केवल एम/2 अलग-अलग जांच हैं, यह गारंटी देने के लिए अन्य तकनीकों की आवश्यकता होती है कि लोड फैक्टर 1/2 से अधिक होने पर सम्मिलन सफल होगा।
• के लिए $m=n^{p}$, जहां एम, एन, और पी पूर्णांक 2 से बड़े या बराबर हैं (पी = 1 होने पर रैखिक जांच में गिरावट आती है), तो $h(k,i)=(h(k)+i+ni^{2}){\pmod {m}}$ सभी विशिष्ट जांचों का चक्र देता है। इसकी गणना लूप में इस प्रकार की जा सकती है: $h(k,0)=h(k)$, और $h(k,i+1)=(h(k,i)+2in+n+1){\pmod {m}}$
• किसी भी m के लिए, m को 2 की निकटतम शक्ति तक पूर्णांकित करके द्विघात जांच के साथ पूर्ण चक्र प्राप्त किया जा सकता है, जांच सूचकांक की गणना करें: $h(k,i)=h(k)+((i^{2}+i)/2){\pmod {roundUp2(m)}}$, और जब पुनरावृत्ति छोड़ें $h(k,i)>=m$. अधिकतम है $roundUp2(m)-m<m/2$ छोड़े गए पुनरावृत्तियाँ, और ये पुनरावृत्तियाँ मेमोरी को संदर्भित नहीं करती हैं, इसलिए यह अधिकांश आधुनिक प्रोसेसर पर तेज़ संचालन है। m को पूर्णांकित करने की गणना इस प्रकार की जा सकती है:

uint64_t roundUp2(uint64_t v){
	v--;
	v |= v >> 1;
	v |= v >> 2;
	v |= v >> 4;
	v |= v >> 8;
	v |= v >> 16;
	v |= v >> 32;
	v++;
	return v;
}

सीमाएँ

वैकल्पिक संकेत

यदि ऑफसेट का चिह्न वैकल्पिक है (जैसे +1, −4, +9, −16, आदि), और यदि बाल्टियों की संख्या एक अभाज्य संख्या है $p$ 3 मॉड्यूलो 4 (जैसे 3, 7, 11, 19, 23, 31, आदि) के अनुरूप, फिर पहला $p$ ऑफसेट अद्वितीय होंगे (modulo $p$). दूसरे शब्दों में, 0 से तक का क्रमपरिवर्तन $p-1$ प्राप्त की जाती है, और, परिणामस्वरूप, जब तक कम से कम एक बाल्टी मौजूद है तब तक एक मुफ़्त बाल्टी हमेशा मिलती रहेगी।

बाहरी संबंध

• Tutorial/quadratic probing