डबल हैशिंग

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

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

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

एच का चयन₂(के)

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

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

व्यवहार में:

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

विश्लेषण

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

$$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.