डबल हैशिंग

डबल हैशिंग एक कंप्यूटर प्रोग्रामिंग तकनीक है जिसका उपयोग कोलिजन होने पर ऑफसेट के रूप में कुंजी के द्वितीयक हैश का उपयोग करके, हैश कोलिजन को हल करने के लिए हैश तालिकाओं में विवर्त पते के साथ संयोजन में किया जाता है। विवर्त संबोधन के साथ डबल हैशिंग एक टेबल पर एक मौलिक डेटा संरचना $T$ है .

डबल हैशिंग तकनीक तालिका में एक सूचकांक के रूप में एक हैश मान का उपयोग करती है और तब तक बार-बार एक अंतराल को आगे बढ़ाती है जब तक कि वांछित मान स्थित न हो जाए, एक रिक्त स्थान न पहुंच जाए, या पूरी तालिका खोज न ली जाए; किंतु यह अंतराल एक दूसरे, स्वतंत्र हैश फंकशन द्वारा निर्धारित किया जाता है। रैखिक जांच और द्विघात जांच के वैकल्पिक कोलिजन-रिज़ॉल्यूशन विधियों के विपरीत, अंतराल डेटा पर निर्भर करता है, जिससे एक ही स्थान पर मैपिंग मानों में अलग-अलग बकेट अनुक्रम होंता है ; जिसमे यह बार-बार होने वाले कोलिजनों और क्लस्टरिंग के प्रभावों को कम करता है।

दो यादृच्छिक, समान और स्वतंत्र हैश फ़ंक्शंस $h_{1}$ और $h_{2}$, को देखते हुए, $|T|$ की हैश तालिका में मान $k$ के लिए बकेट अनुक्रम में $i$ स्थान बकेट है: $h(i,k)=(h_{1}(k)+i\cdot h_{2}(k)){\bmod {|}}T|.$ समान्यत:, $h_{1}$ और $h_{2}$ को सार्वभौमिक हैश फ़ंक्शंस के एक सेट से चुना जाता है; $\{0,|T|-1\}$ की सीमा के लिए $h_{1}$ का चयन किया जाता है और $\{1,|T|-1\}$ की सीमा के लिए$h_{2}$ का चयन किया जाता है। डबल हैशिंग एक यादृच्छिक वितरण का अनुमान लगाता है; अधिक स्पष्ट रूप से, जोड़ी-वार स्वतंत्र हैश फ़ंक्शन $(n/|T|)^{2}$ की संभावना उत्पन्न करते हैं कि कुंजियों की कोई भी जोड़ी समान बकेट अनुक्रम का पालन करेगी।

h₂(k) का चयन

द्वितीयक हैश फ़ंक्शन $h_{2}(k)$ कई विशेषताएं होनी चाहिए:

• इससे कभी भी शून्य का सूचकांक प्राप्त नहीं होना चाहिए
• इसे पूरी मेज पर घूमना चाहिए
• यह गणना करने में बहुत तेज़ होना चाहिए
• यह जोड़ी-वार $h_{1}(k)$ से स्वतंत्र होना चाहिए।
• $h_{2}$ की वितरण विशेषताएँ अप्रासंगिक हैं। यह एक यादृच्छिक-संख्या जनरेटर के समान है।
• सभी $h_{2}(k)$ |T| के लिए अपेक्षाकृत अभाज्य बनें हो।

वास्तव में:

• यदि विभाजन हैशिंग का उपयोग दोनों कार्यों के लिए किया जाता है, तो भाजक को अभाज्य के रूप में चुना जाता है।
• यदि टी 2 की शक्ति है, तो पहली और अंतिम आवश्यकताएं समान्यत: $h_{2}(k)$को सदैव एक विषम संख्या देकर संतुष्ट की जाती हैं। इसका दुष्परिणाम यह है कि एक व्यर्थ बिट के कारण कोलिजन की संभावना दोगुनी हो जाती है।

विश्लेषण

मान लीजिए कि $T$ में संग्रहीत तत्वों की संख्या $n$ है, तो $T$ का लोड कारक $\alpha =n/|T|$ है। अर्थात्, एक डबल हैशिंग तालिका $T$ बनाने के लिए दो सार्वभौमिक हैश फ़ंक्शन $h_{1}$ और $h_{2}$ का चयन करके यादृच्छिक रूप से, समान रूप से और स्वतंत्र रूप से प्रारंभ करें। सभी तत्वों को$h_{1}$ और $h_{2}$. का उपयोग करके डबल हैशिंग द्वारा $T$ में रखा गया है। एक कुंजी $k$ देते हुए, $(i+1)$ हैश स्थान की गणना निम्न द्वारा की जाती है:

$$h(i,k)=(h_{1}(k)+i\cdot h_{2}(k)){\bmod {|}}T|.$$

मान लें कि $T$ का लोड कारक $\alpha :1>\alpha >0$ है। ब्रैडफोर्ड और कटेहाकिस ने $T$ में असफल खोज के लिए जांचों की अपेक्षित संख्या दिखाई, फिर भी इन आरंभिक रूप से चुने गए हैश फ़ंक्शंस का उपयोग करते हुए, इसकी परवाह किए बिना ${\tfrac {1}{1-\alpha }}$ है इनपुट का वितरण. हैश फ़ंक्शंस की जोड़ी-वार स्वतंत्रता पर्याप्त है।

ओपन एड्रेसिंग के अन्य सभी रूपों की तरह, डबल हैशिंग रैखिक हो जाती है क्योंकि हैश तालिका अधिकतम क्षमता तक पहुंचती है। सामान्य अनुमान टेबल लोडिंग को क्षमता के 75% तक सीमित करना है। अंततः अन्य सभी ओपन एड्रेसिंग योजनाओं की अनुरूप बड़े आकार में पुनः प्रयास करना आवश्यक होगा।

वेरिएंट

पीटर डिलिंजर की पीएचडी थीसिस बताते हैं कि डबल हैशिंग अवांछित समतुल्य हैश फ़ंक्शन उत्पन्न करता है जब हैश फ़ंक्शन को एक सेट के रूप में माना जाता है, जैसा कि ब्लूम फिल्टर में होता है: यदि $h_{2}(y)=-h_{2}(x)$ और $h_{1}(y)=h_{1}(x)+k\cdot h_{2}(x)$, तब $h(i,y)=h(k-i,x)$ और हैश के सेट $\left\{h(0,x),...,h(k,x)\right\}=\left\{h(0,y),...,h(k,y)\right\}$ समरूप हैं। इससे कोलिजन की संभावना अपेक्षा से $1/|T|^{2}$ दोगुनी हो जाती है .

इसके अतिरिक्त बड़ी संख्या में अधिकतर ओवरलैपिंग हैश सेट भी हैं; यदि $h_{2}(y)=h_{2}(x)$ और $h1(y)=h_{1}(x)\pm h_{2}(x)$, तब $h(i,y)=h(i\pm 1,x)$, और अतिरिक्त हैश मानों की तुलना करना (सीमा का विस्तार करना)। $i$) कोई सहायता नहीं है.

ट्रिपल हैशिंग

हैश फ़ंक्शन में एक द्विघात शब्द $i^{2},$ $i(i+1)/2$ (एक त्रिकोणीय संख्या) या यहां तक ​​कि $i^{2}\cdot h_{3}(x)$ (ट्रिपल हैशिंग) जोड़ने से हैश फ़ंक्शन में कुछ हद तक सुधार होता है किंतु यह समस्या ठीक नहीं होती है; यदि :

$h_{1}(y)=h_{1}(x)+k\cdot h_{2}(x)+k^{2}\cdot h_{3}(x),$

$h_{2}(y)=-h_{2}(x)-2k\cdot h_{3}(x),$ और

$h_{3}(y)=h_{3}(x).$

तब

${\begin{aligned}h(k-i,y)&=h_{1}(y)+(k-i)\cdot h_{2}(y)+(k-i)^{2}\cdot h_{3}(y)\\&=h_{1}(y)+(k-i)(-h_{2}(x)-2kh_{3}(x))+(k-i)^{2}h_{3}(x)\\&=\ldots \\&=h_{1}(x)+kh_{2}(x)+k^{2}h_{3}(x)+(i-k)h_{2}(x)+(i^{2}-k^{2})h_{3}(x)\\&=h_{1}(x)+ih_{2}(x)+i^{2}h_{3}(x)\\&=h(i,x).\\\end{aligned}}$

उन्नत डबल हैशिंग

एक घन शब्द $i^{3}$ या $(i^{3}-i)/6$ (एक चतुष्फलकीय संख्या) जोड़ने से समस्या हल हो जाती है, एक तकनीक जिसे एन्हांस्ड डबल हैशिंग के रूप में जाना जाता है। इसकी गणना फॉरवर्ड डिफरेंसिंग द्वारा कुशलतापूर्वक की जा सकती है:

struct key;	/// Opaque
/// Use other data types when needed. (Must be unsigned for guaranteed wrapping.)
extern unsigned int h1(struct key const *), h2(struct key const *);

/// Calculate k hash values from two underlying hash functions
/// h1() and h2() using enhanced double hashing.  On return,
///     hashes[i] = h1(x) + i*h2(x) + (i*i*i - i)/6.
/// Takes advantage of automatic wrapping (modular reduction)
/// of unsigned types in C.
void ext_dbl_hash(struct key const *x, unsigned int hashes[], unsigned int n)
{
	unsigned int a = h1(x), b = h2(x), i;

	for (i = 0; i < n; i++) { 
		hashes[i] = a;
		a += b;	// Add quadratic difference to get cubic
		b += i;	// Add linear difference to get quadratic
		       	// i++ adds constant difference to get linear
	}
}

कोलिजन की समस्या को सुधारने के अतिरिक्त, बढ़ी हुई डबल हैशिंग $h_{2}(x)$ के गुणों पर डबल-हैशिंग के संख्यात्मक प्रतिबंधों को भी हटा देती है, जिससे संपत्ति के समान हैश फ़ंक्शन को $h_{1}$ के समान (किंतु फिर भी स्वतंत्र) होने की अनुमति मिलती है। जिससे इसका उपयोग किया गया है।

यह भी देखें

• कुक्कू हैशिंग
• 2-विकल्प हैशिंग

बाहरी संबंध

• How Caching Affects Hashing by Gregory L. Heileman and Wenbin Luo 2005.
• Hash Table Animation
• klib a C library that includes double hashing functionality.