डबल हैशिंग: Difference between revisions

From Vigyanwiki
(Created page with "डबल हैशिंग एक कंप्यूटर प्रोग्रामिंग तकनीक है जिसका उपयोग टकराव...")
 
No edit summary
Line 1: Line 1:
डबल हैशिंग एक [[कंप्यूटर प्रोग्रामिंग]] तकनीक है जिसका उपयोग टकराव होने पर ऑफसेट के रूप में कुंजी के द्वितीयक हैश का उपयोग करके, हैश टकराव को हल करने के लिए [[हैश तालिका]]ओं में खुले पते के साथ संयोजन में किया जाता है। [[ खुला संबोधन ]] के साथ डबल हैशिंग एक टेबल पर एक शास्त्रीय डेटा संरचना है <math>T</math>.
'''डबल हैशिंग''' एक [[कंप्यूटर प्रोग्रामिंग]] तकनीक है जिसका उपयोग कोलिजन होने पर ऑफसेट के रूप में कुंजी के द्वितीयक हैश का उपयोग करके, हैश कोलिजन को हल करने के लिए [[हैश तालिका]]ओं में विवर्त पते के साथ संयोजन में किया जाता है। [[ खुला संबोधन | विवर्त  संबोधन]] के साथ डबल हैशिंग एक टेबल पर एक मौलिक डेटा संरचना <math>T</math> है .


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


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


== एच का चयन<sub>2</sub>(के)==
== h<sub>2</sub>(k) का चयन==
द्वितीयक हैश फ़ंक्शन <math>h_2(k)</math> कई विशेषताएं होनी चाहिए:
द्वितीयक हैश फ़ंक्शन <math>h_2(k)</math> कई विशेषताएं होनी चाहिए:
*इससे कभी भी शून्य का सूचकांक प्राप्त नहीं होना चाहिए
*इससे कभी भी शून्य का सूचकांक प्राप्त नहीं होना चाहिए
*इसे पूरी मेज पर घूमना चाहिए
*इसे पूरी मेज पर घूमना चाहिए
*यह गणना करने में बहुत तेज़ होना चाहिए
*यह गणना करने में बहुत तेज़ होना चाहिए
*यह जोड़ी-वार स्वतंत्र होना चाहिए <math>h_1(k)</math>
*यह जोड़ी-वार <math>h_1(k)</math> से स्वतंत्र होना चाहिए।
*की वितरण विशेषताएँ <math>h_2</math> अप्रासंगिक हैं. यह एक यादृच्छिक-संख्या जनरेटर के समान है।
*<math>h_2</math> की वितरण विशेषताएँ अप्रासंगिक हैं। यह एक यादृच्छिक-संख्या जनरेटर के समान है।
* सभी <math>h_2(k)</math> |T| के लिए अपेक्षाकृत अभाज्य बनें।
* सभी <math>h_2(k)</math> |T| के लिए अपेक्षाकृत अभाज्य बनें हो।


व्यवहार में:
वास्तव में:
* यदि विभाजन हैशिंग का उपयोग दोनों कार्यों के लिए किया जाता है, तो भाजक को अभाज्य के रूप में चुना जाता है।
* यदि विभाजन हैशिंग का उपयोग दोनों कार्यों के लिए किया जाता है, तो भाजक को अभाज्य के रूप में चुना जाता है।
* यदि टी 2 की शक्ति है, तो पहली और आखिरी आवश्यकताएं आमतौर पर बनाकर पूरी की जाती हैं <math>h_2(k)</math> हमेशा विषम संख्या लौटाएं. इसका दुष्परिणाम यह है कि एक बर्बाद बिट के कारण टकराव की संभावना दोगुनी हो जाती है।<ref name=Dillinger04/>
*यदि टी 2 की शक्ति है, तो पहली और अंतिम आवश्यकताएं समान्यत: <math>h_2(k)</math>को सदैव एक विषम संख्या देकर संतुष्ट की जाती हैं। इसका दुष्परिणाम यह है कि एक व्यर्थ बिट के कारण कोलिजन की संभावना दोगुनी हो जाती है।<ref name="Dillinger04">{{cite conference
 
|title=Bloom Filters in Probabilistic Verification
 
|first1=Peter C. |last1=Dillinger  |first2=Panagiotis |last2=Manolios
|conference=5h International Conference on Formal Methods in Computer Aided Design (FMCAD 2004)
|location=Austin, Texas |date=November 15–17, 2004
|doi=10.1007/978-3-540-30494-4_26 |citeseerx=10.1.1.119.628
|url=https://www.khoury.northeastern.edu/~pete/pub/bloom-filters-verification.pdf
}}</ref>
== विश्लेषण ==
== विश्लेषण ==


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


<math display=block> h(i,k) = ( h_1(k) + i \cdot h_2(k) ) \bmod |T|.</math>
<math display=block> h(i,k) = ( h_1(k) + i \cdot h_2(k) ) \bmod |T|.</math>
होने देना <math>T</math> निश्चित लोड फैक्टर है <math>\alpha: 1 > \alpha > 0</math>.
मान लें कि <math>T</math> का लोड कारक  <math>\alpha: 1 > \alpha > 0</math> है। ब्रैडफोर्ड और कटेहाकिस<ref>{{citation
ब्रैडफोर्ड और माइकल एन. कटेहाकिस<ref>{{citation
  | last1 = Bradford | first1 = Phillip G.
  | last1 = Bradford | first1 = Phillip G.
  | last2 = Katehakis | first2 = Michael N. | author2-link = Michael N. Katehakis
  | last2 = Katehakis | first2 = Michael N. | author2-link = Michael N. Katehakis
Line 41: Line 43:
  | archive-url = https://web.archive.org/web/20160125172602/http://phillipbradford.com/papers/AProbStudyExpandersAndHashing.pdf
  | archive-url = https://web.archive.org/web/20160125172602/http://phillipbradford.com/papers/AProbStudyExpandersAndHashing.pdf
  | archive-date = 2016-01-25
  | archive-date = 2016-01-25
}}.</ref>
}}.</ref> ने <math>T</math> में असफल खोज के लिए जांचों की अपेक्षित संख्या दिखाई, फिर भी इन आरंभिक रूप से चुने गए हैश फ़ंक्शंस का उपयोग करते हुए, इसकी परवाह किए बिना <math>\tfrac{1}{1-\alpha}</math> है इनपुट का वितरण. हैश फ़ंक्शंस की जोड़ी-वार स्वतंत्रता पर्याप्त है।
में असफल खोज के लिए जांचों की अपेक्षित संख्या दिखाई गई <math>T</math>, अभी भी इन प्रारंभिक रूप से चुने गए हैश फ़ंक्शंस का उपयोग कर रहा है <math>\tfrac{1}{1-\alpha}</math> इनपुट के वितरण की परवाह किए बिना। हैश फ़ंक्शंस की जोड़ी-वार स्वतंत्रता पर्याप्त है।


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


== वेरिएंट ==
== वेरिएंट ==
Line 56: Line 57:
  |pages=93–112
  |pages=93–112
  |url=http://peterd.org/pcd-diss.pdf#page=93
  |url=http://peterd.org/pcd-diss.pdf#page=93
}}</ref> बताते हैं कि डबल हैशिंग अवांछित समतुल्य हैश फ़ंक्शन उत्पन्न करता है जब हैश फ़ंक्शन को एक सेट के रूप में माना जाता है, जैसा कि [[ब्लूम फिल्टर]] में होता है: यदि <math>h_2(y) = -h_2(x)</math> और <math>h_1(y) = h_1(x) + k\cdot h_2(x)</math>, तब <math>h(i, y) = h(k - i, x)</math> और हैश के सेट <math>\left\{h(0, x), ..., h(k, x)\right\} = \left\{h(0, y), ..., h(k, y)\right\}</math> समरूप हैं। इससे टकराव की संभावना अपेक्षा से दोगुनी हो जाती है <math>1/|T|^2</math>.
}}</ref> बताते हैं कि डबल हैशिंग अवांछित समतुल्य हैश फ़ंक्शन उत्पन्न करता है जब हैश फ़ंक्शन को एक सेट के रूप में माना जाता है, जैसा कि [[ब्लूम फिल्टर]] में होता है: यदि <math>h_2(y) = -h_2(x)</math> और <math>h_1(y) = h_1(x) + k\cdot h_2(x)</math>, तब <math>h(i, y) = h(k - i, x)</math> और हैश के सेट <math>\left\{h(0, x), ..., h(k, x)\right\} = \left\{h(0, y), ..., h(k, y)\right\}</math> समरूप हैं। इससे कोलिजन की संभावना अपेक्षा से <math>1/|T|^2</math> दोगुनी हो जाती है .


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


=== ट्रिपल हैशिंग ===
=== ट्रिपल हैशिंग ===
एक द्विघात पद जोड़ना <math>i^2,</math><ref name=Kirsch08>{{cite journal
हैश फ़ंक्शन में एक द्विघात शब्द <math>i^2,</math><ref name="Kirsch08">{{cite journal
  |title=Less Hashing, Same Performance: Building a Better Bloom Filter
  |title=Less Hashing, Same Performance: Building a Better Bloom Filter
  |first1=Adam |last1=Kirsch  |first2=Michael |last2=Mitzenmacher |authorlink2=Michael Mitzenmacher
  |first1=Adam |last1=Kirsch  |first2=Michael |last2=Mitzenmacher |authorlink2=Michael Mitzenmacher
Line 67: Line 68:
  |date=September 2008 |doi=10.1002/rsa.20208 |citeseerx=10.1.1.152.579
  |date=September 2008 |doi=10.1002/rsa.20208 |citeseerx=10.1.1.152.579
  |url=https://www.eecs.harvard.edu/~michaelm/postscripts/rsa2008.pdf
  |url=https://www.eecs.harvard.edu/~michaelm/postscripts/rsa2008.pdf
}}</ref> <math>i(i+1)/2</math> (एक [[त्रिकोणीय संख्या]]) या सम <math>i^2 \cdot h_3(x)</math> (ट्रिपल हैशिंग)<ref>Alternatively defined with the triangular number, as in Dillinger 2004.</ref> हैश फ़ंक्शन में हैश फ़ंक्शन में कुछ हद तक सुधार होता है<ref name=Kirsch08/>लेकिन इस समस्या को ठीक नहीं करता; अगर:
}}</ref> <math>i(i+1)/2</math> (एक त्रिकोणीय संख्या) या यहां तक ​​कि <math>i^2 \cdot h_3(x)</math> (ट्रिपल हैशिंग)<ref>Alternatively defined with the triangular number, as in Dillinger 2004.</ref> जोड़ने से हैश फ़ंक्शन में कुछ हद तक सुधार होता है<ref name=Kirsch08/> किंतु यह समस्या ठीक नहीं होती है; यदि :
: <math>h_1(y) = h_1(x) + k \cdot h_2(x) + k^2 \cdot h_3(x),</math>
: <math>h_1(y) = h_1(x) + k \cdot h_2(x) + k^2 \cdot h_3(x),</math>
: <math>h_2(y) = -h_2(x) - 2k \cdot h_3(x),</math> और
: <math>h_2(y) = -h_2(x) - 2k \cdot h_3(x),</math> और
Line 84: Line 85:
=== उन्नत डबल हैशिंग ===
=== उन्नत डबल हैशिंग ===


एक घन फ़ंक्शन जोड़ना <math>i^3</math><ref name=Kirsch08/>या <math>(i^3-i)/6</math> (एक [[चतुष्फलकीय संख्या]]),<ref name=Dillinger04>{{cite conference
एक घन शब्द  <math>i^3</math><ref name=Kirsch08/> या <math>(i^3-i)/6</math> (एक चतुष्फलकीय संख्या) जोड़ने से<ref name="Dillinger04" /> समस्या हल हो जाती है, एक तकनीक जिसे एन्हांस्ड डबल हैशिंग के रूप में जाना जाता है। इसकी गणना फॉरवर्ड डिफरेंसिंग द्वारा कुशलतापूर्वक की जा सकती है:
|title=Bloom Filters in Probabilistic Verification
|first1=Peter C. |last1=Dillinger  |first2=Panagiotis |last2=Manolios
|conference=5h International Conference on Formal Methods in Computer Aided Design (FMCAD 2004)
|location=Austin, Texas |date=November 15–17, 2004
|doi=10.1007/978-3-540-30494-4_26 |citeseerx=10.1.1.119.628
|url=https://www.khoury.northeastern.edu/~pete/pub/bloom-filters-verification.pdf
}}</ref> समस्या का समाधान करता है, एक तकनीक जिसे एन्हांस्ड डबल हैशिंग के रूप में जाना जाता है। इसकी गणना [[ आगे का अंतर ]] द्वारा कुशलतापूर्वक की जा सकती है:
<syntaxhighlight lang="c">
<syntaxhighlight lang="c">
struct key; /// Opaque
struct key; /// Opaque
Line 114: Line 108:
}
}
</syntaxhighlight>
</syntaxhighlight>
टकराव की समस्या को सुधारने के अलावा, बढ़ी हुई डबल हैशिंग भी डबल-हैशिंग के संख्यात्मक प्रतिबंधों को हटा देती है <math>h_2(x)</math>के गुण, एक हैश फ़ंक्शन को संपत्ति के समान अनुमति देता है (लेकिन अभी भी स्वतंत्र है) <math>h_1</math> इस्तेमाल किया जाएगा।<ref name=Dillinger04/>
कोलिजन की समस्या को सुधारने के अतिरिक्त , बढ़ी हुई डबल हैशिंग भी डबल-हैशिंग के संख्यात्मक प्रतिबंधों को हटा देती है <math>h_2(x)</math>के गुण, एक हैश फ़ंक्शन को संपत्ति के समान अनुमति देता है (किंतु  अभी भी स्वतंत्र है) <math>h_1</math> इस्तेमाल किया जाएगा।<ref name=Dillinger04/>
 
कोलिजन की समस्या को सुधारने के अतिरिक्त, बढ़ी हुई डबल हैशिंग <math>h_2(x)</math> के गुणों पर डबल-हैशिंग के संख्यात्मक प्रतिबंधों को भी हटा देती है, जिससे संपत्ति के समान हैश फ़ंक्शन को <math>h_1</math> के समान (किंतु फिर भी स्वतंत्र) होने की अनुमति मिलती है। जिससे इसका उपयोग किया गया है।<ref name="Dillinger04" />





Revision as of 13:36, 19 July 2023

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

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

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

h2(k) का चयन

द्वितीयक हैश फ़ंक्शन कई विशेषताएं होनी चाहिए:

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

वास्तव में:

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

विश्लेषण

मान लीजिए कि में संग्रहीत तत्वों की संख्या है, तो का लोड कारक है। अर्थात्, एक डबल हैशिंग तालिका बनाने के लिए दो सार्वभौमिक हैश फ़ंक्शन और का चयन करके यादृच्छिक रूप से, समान रूप से और स्वतंत्र रूप से प्रारंभ करें। सभी तत्वों को और . का उपयोग करके डबल हैशिंग द्वारा में रखा गया है। एक कुंजी देते हुए, हैश स्थान की गणना निम्न द्वारा की जाती है:

मान लें कि का लोड कारक है। ब्रैडफोर्ड और कटेहाकिस[2] ने में असफल खोज के लिए जांचों की अपेक्षित संख्या दिखाई, फिर भी इन आरंभिक रूप से चुने गए हैश फ़ंक्शंस का उपयोग करते हुए, इसकी परवाह किए बिना है इनपुट का वितरण. हैश फ़ंक्शंस की जोड़ी-वार स्वतंत्रता पर्याप्त है।

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

वेरिएंट

पीटर डिलिंजर की पीएचडी थीसिस[3] बताते हैं कि डबल हैशिंग अवांछित समतुल्य हैश फ़ंक्शन उत्पन्न करता है जब हैश फ़ंक्शन को एक सेट के रूप में माना जाता है, जैसा कि ब्लूम फिल्टर में होता है: यदि और , तब और हैश के सेट समरूप हैं। इससे कोलिजन की संभावना अपेक्षा से दोगुनी हो जाती है .

इसके अतिरिक्त बड़ी संख्या में अधिकतर ओवरलैपिंग हैश सेट भी हैं; यदि और , तब , और अतिरिक्त हैश मानों की तुलना करना (सीमा का विस्तार करना)। ) कोई सहायता नहीं है.

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

हैश फ़ंक्शन में एक द्विघात शब्द [4] (एक त्रिकोणीय संख्या) या यहां तक ​​कि (ट्रिपल हैशिंग)[5] जोड़ने से हैश फ़ंक्शन में कुछ हद तक सुधार होता है[4] किंतु यह समस्या ठीक नहीं होती है; यदि :

और

तब


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

एक घन शब्द [4] या (एक चतुष्फलकीय संख्या) जोड़ने से[1] समस्या हल हो जाती है, एक तकनीक जिसे एन्हांस्ड डबल हैशिंग के रूप में जाना जाता है। इसकी गणना फॉरवर्ड डिफरेंसिंग द्वारा कुशलतापूर्वक की जा सकती है:

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
	}
}

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

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


यह भी देखें

संदर्भ

  1. 1.0 1.1 1.2 1.3 Dillinger, Peter C.; Manolios, Panagiotis (November 15–17, 2004). Bloom Filters in Probabilistic Verification (PDF). 5h International Conference on Formal Methods in Computer Aided Design (FMCAD 2004). Austin, Texas. CiteSeerX 10.1.1.119.628. doi:10.1007/978-3-540-30494-4_26.
  2. Bradford, Phillip G.; Katehakis, Michael N. (April 2007), "A Probabilistic Study on Combinatorial Expanders and Hashing" (PDF), SIAM Journal on Computing, 37 (1): 83–111, doi:10.1137/S009753970444630X, MR 2306284, archived from the original (PDF) on 2016-01-25.
  3. Dillinger, Peter C. (December 2010). Adaptive Approximate State Storage (PDF) (PhD thesis). Northeastern University. pp. 93–112.
  4. 4.0 4.1 4.2 Kirsch, Adam; Mitzenmacher, Michael (September 2008). "Less Hashing, Same Performance: Building a Better Bloom Filter" (PDF). Random Structures and Algorithms. 33 (2): 187–218. CiteSeerX 10.1.1.152.579. doi:10.1002/rsa.20208.
  5. Alternatively defined with the triangular number, as in Dillinger 2004.


बाहरी संबंध