कुक्कू हैशिंग

कुक्कू हैशिंग उदाहरण। तीर प्रत्येक कुंजी का वैकल्पिक स्थान दिखाते हैं। A के स्थान में नई वास्तु प्रविष्ट की जाती है, A को उसके वैकल्पिक स्थान पर ले जाया जाता है, जो वर्तमान में B द्वारा अधिकृत कर लियाजाता है, और B को उसके वैकल्पिक स्थान पर ले जाया जाता है जो वर्तमान में विवृत होता है। H के स्थान पर किसी नई वास्तु का सम्मिलन सफल नहीं होता है: चूँकि H चक्र का भाग होता है (W के साथ), नई वास्तु पुनः बाहर हो हो जाती है।

कुक्कू हैशिंग कंप्यूटर प्रोग्रामिंग में एक हैश टेबल में हैश फंक्शन के मूल्यों के हैश कलिसिओं (कोलिजन ) को हल करने के लिए योजना होती है, जिसमें सबसे व्यर्थ स्थिति में निरंतर समय लुकअप समय होता है। यह नाम कुक्कू की कुछ प्रजातियों के व्यवहार से लिया जाता है, जहां कुक्कू का चूजा (बच्चा) अंडे सेते समय अन्य अंडों या बच्चों को घोंसले से बाहर प्रेरित कर देता है, इस व्यवहार में भिन्नता होती है जिसे ब्रूड परजीवीवाद कहा जाता है; समान रूप से, कुक्कू हैशिंग टेबल में नई कुंजी प्रयुक्त करने से पुरानी कुंजी को टेबल में किसी भिन्न स्थान पर प्रेरित किया जा सकता है।

इतिहास

कुक्कू हैशिंग का वर्णन सबसे पहले 2001 के कॉन्फ्रेंस पेपर में रासमस पाघ और फ्लेमिंग फ्रिचे रोडलर द्वारा किया गया था। पेपर को 2020 में कलन विधि समय का परीक्षण पुरस्कार पर यूरोपीय संगोष्ठी से सम्मानित किया गया था।

संचालन

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

अन्वेषण

कुक्कू हैशिंग दो हैश टेबलओं $T_{1}$ और $T_{2}$का उपयोग करती है। यह मानते हुए $r$ प्रत्येक टेबलओं की लंबाई होती है, दो टेबलओं के लिए हैश फंक्शन को इस प्रकार $h_{1},\ h_{2}\ :\ \cup \rightarrow \{0,...,r-1\}$और $\forall x\in S$ द्वारा परिभाषित किया जाता है, जहाँ $x$ कुंजी और $S$ वह समुच्चय बनें जिसकी कुंजियाँ $h_{1}(x)$ के $T_{1}$में और $h_{2}(x)$ के $T_{2}$ में संग्रहीत होती हैं। लुकअप संचालन इस प्रकार होता है:

function lookup(x) is return $T_{1}[h_{1}(x)]\ =\ x\vee T_{2}[h_{2}(x)]=x$ end function

तार्किक या ($\vee$) प्रदर्शित करता है कि, कुंजी $x$ का मान या तो $T_{1}$ या तो $T_{2}$ में पाया जाता है , जो $O(1)$ सबसे व्यर्थ स्थिति में होता है।

विलोपन

विलोपन $O(1)$ में किया जाता है चूंकि इसमें जांच में कोई सहकारिता नहीं होती है - यदि टेबल बहुत कम है तो दबाव संचाल के मूल्य पर विचार नहीं किया जाता है।

प्रविष्टि

नए नाम-मूल्य जोड़े को सम्मिलित करने के पहले चरण में यह जांचना आवश्यक होता है कि क्या स्लॉट $h_{1}(x)$ टेबल के $T_{1}$ भरा हुआ हैं; यदि ऐसा नहीं है, तो आइटम उस सेल में प्रविष्टि कराया जाता है। यघपि, यदि स्थान पर अधिकार कर लिया जाता है, तो पहली वस्तु हटा दी जाती है - इसे रहने दें $x'$-और $x$ को $T_{1}[h_{1}(x)]$ पर प्रविष्ट किया गया है । हटाई गई वस्तु $x'$ को टेबल $T_{2}$ में प्रविष्ट किया जाता है। प्रक्रिया का निरंतर पालन किया जाता है; प्रक्रिया तब तक जारी रहती है जब तक कुंजी प्रविष्ट करने के लिए कोई रिक्त स्थान नहीं प्राप्त हो जाता है। प्रक्रिया लूप में संभावित अनंत पुनरावृत्ति से बचने के लिए, a ${\text{Max-Loop}}$ इस प्रकार निर्दिष्ट किया जाता है कि यदि पुनरावृत्तियाँ निश्चित क्रिटिकल वैल्यू से अधिक हो जाती हैं, तो हैश टेबलएँ दोनों $T_{1}$ और $T_{2}$- नए हैश फंक्शनो के साथ पुनः दोहराया जाता है और प्रविष्टि प्रक्रिया दोहराई जाती है। सम्मिलन के लिए छद्म कोड निम्नलिखित होता है:

1 function insert(x) is 2 if lookup(x) then 3 return 4 end if 5 loop Max-Loop times 6 if $T_{1}[h_{1}(x)]$ = $\bot$ then 7 $T_{1}[h_{1}(x)]$ := x 8 return 9 end if 10 x $\leftrightarrow T_{1}[h_{1}(x)]$ 11 if $T_{2}[h_{2}(x)]$ = $\bot$ then 12 $T_{2}[h_{2}(x)]$ := x 13 return 14 end if 15 x $\leftrightarrow T_{2}[h_{2}(x)]$ 16 end loop 17 rehash() 18 insert(x) 19 end function

पंक्ति 10 और 15 पर, अन्य कुंजियो को किक करने का 'कुक्कू दृष्टिकोण' - जो कि पहले से $T_{1,2}[h_{1,2}(x)]$में अधिकृत था। तब तक होता है जब तक कि प्रत्येक कुंजी का अपना घोंसला अर्थात वस्तु $x$ को दो टेबलओं में से किसी पर स्थान में प्रविष्ट किया जाता है; संकेतन $\leftrightarrow$ विक्षनरी:स्वैप की प्रक्रिया को व्यक्त करता है।

सिद्धांत

सम्मिलन अपेक्षित स्थिर समय में सफल होते है, यहां तक ​​कि टेबल के पुनर्निर्माण की संभावना पर भी विचार करते हुए, जब तक कि कुंजियों की संख्या हैश टेबल की क्षमता के आधे से कम रखी जाती है, अर्थात्, लोड फैक्टर 50% से निम्न होता है।

इसे सिद्ध करने की एक विधि यादृच्छिक ग्राफ के सिद्धांत का उपयोग करती है: कोई भी एक अप्रत्यक्ष ग्राफ बना सकता है जिसे "कुक्कू ग्राफ़" कहा जाता है जिसमें प्रत्येक हैश टेबल स्थान के लिए शीर्ष होता है, और प्रत्येक हैशेड मान के लिए सीमांत होता है, किनारे के अंतिम बिंदु के दो संभावित मूल्य के स्थान होते हैं। फिर, कुक्कू हैश टेबल में मानों का समुच्चय जोड़ने के लिए लालची स्वार्थी एल्गोरिथ्म सफल होता है यदि और मात्र यदि मूल्यों के इस समुच्चय के लिए कुक्कू ग्राफ छद्मवन होता है, तो इसके प्रत्येक जुड़े घटक में अधिकतम एक चक्र वाला ग्राफ होता है। शीर्षों से अधिक सीमा वाला कोई भी शीर्ष-प्रेरित सबग्राफ कुंजियों के समुच्चय के समरूप होता है जिसके लिए हैश टेबल में अपर्याप्त संख्या में स्लॉट उपस्थित होते हैं। जब हैश फंक्शन को यादृच्छिक रूप से चयन किया जाता है, तो कुक्कू ग्राफ एर्दो-रेनी मॉडल में एक यादृच्छिक ग्राफ होता है। उच्च संभावना के साथ, 1/2 से कम लोड फैक्टर के लिए ( यादृच्छिक ग्राफ के अनुरूप जिसमें किनारों की संख्या और कोने की संख्या का अनुपात 1/2 से नीचे घिरा हुआ होता है), इस प्रकार ग्राफ छद्म वन और कुक्कू हैशिंग एल्गोरिदम सभी कुंजिया रखने में सफल हो जाता है। वही सिद्धांत यह भी सिद्ध करता है कि कुक्कू ग्राफ के सम्बद्ध घटक का अपेक्षित आकृति छोटी होती है, यह सुनिश्चित करता है कि प्रत्येक प्रविष्टि में निरंतर अपेक्षित समय लगता है। यघपि, उच्च संभावना के साथ, 1/2 से अधिक लोड फैक्टर दो या दो से अधिक चक्रों वाले विशाल घटक को जन्म देता है, जिससे डेटा संरचना विफल हो जाती है और आकृति बदलने की आवश्यकता होती है।

चूँकि सैद्धांतिक यादृच्छिक हैश फंक्शन को व्यावहारिक उपयोग के लिए बहुत अधिक स्थान की आवश्यकता होती है, महत्वपूर्ण सैद्धांतिक प्रश्न यह है कि कुक्कू हैशिंग के लिए कौन सा व्यावहारिक हैश फंक्शन पर्याप्त होता है। दृष्टिकोण k-स्वतंत्र हैशिंग का उपयोग करता है। 2009 में इसे दिखाया गया था की $O(\log n)$-स्वतंत्रता पर्याप्त है, और कम से कम 6-स्वतंत्रता की आवश्यकता होती है। अन्य दृष्टिकोण सारणीकरण हैशिंग का उपयोग करता है, जो 6-स्वतंत्र नहीं है, यघपि 2012 में दिखाया गया था की इसमें कुक्कू हैशिंग के लिए पर्याप्त अन्य गुण उपस्थित होते है । 2014 से एक तीसरा दृष्टिकोण तथाकथित स्टैश के साथ कुक्कू हैशटेबल को थोड़ा संशोधित करता है, जो 2-स्वतंत्र हैश फंक्शनो से अधिक कुछ भी उपयोग करना संभव नहीं बनाता है।

अभ्यास

व्यवहार में, कुक्कू हैशिंग रैखिक जांच की तुलना में लगभग 20-30% धीमें होते है, जो सामान्य विधियों में सबसे शीघ्र होता है।इसका कारण यह है कि कुक्कू हैशिंग सामान्यतः प्रति अन्वेषण दो कैश मिस का कारण बनती है, उन दो स्थानों की जांच करने के लिए जहां कुंजी संग्रहीत की जा सकती है, जबकि रैखिक जांच के कारण समानतः अन्वेषण मात्र कैश मिस होता है। यघपि, खोज समय पर इसकी सबसे अनुपयुक्त स्थिति की आश्वासन के कारण, वास्तविक समय प्रतिक्रिया दरों की आवश्यकता होने पर कुक्कू हैशिंग अभी भी मूल्यवान हो सकती है। कुक्कू हैशिंग का लाभ इसकी लिंक-लिस्ट मुक्त गुण होता है, जो जीपीयू प्रोसेसिंग के लिए अच्छी तरह से उपयुक्त होता है।

उदाहरण

निम्नलिखित हैश फंक्शन दिए गए हैं:

$h\left(k\right)=k{\bmod {1}}1$
$h'\left(k\right)=\left\lfloor {\frac {k}{11}}\right\rfloor {\bmod {1}}1$

निम्नलिखित दो टेबलएँ कुछ उदाहरण तत्वों का सम्मिलन प्रदर्शित करती हैं। प्रत्येक कॉलम समय के साथ दो हैश टेबलओं की स्थिति के समरूप होता है। प्रत्येक नए मान के लिए संभावित प्रविष्टि स्थानों पर प्रकाश को प्रदर्शित किया जाता है।

1. table for h(k)

		Key inserted
k		20	50	53	75	100	67	105	3	36	39
h(k)		9	6	9	9	1	1	6	3	3	6
Hash table entries	0
	1					100	67	67	67	67	100
	2
	3								3	36	36
	4
	5
	6		50	50	50	50	50	105	105	105	39
	7
	8
	9	20	20	20	75	75	75	53	53	53	75
	10

2. table for h′(k)

		Key inserted
k		20	50	53	75	100	67	105	3	36	39
h′(k)		1	4	4	6	9	6	9	0	3	3
Hash table entries	0									3	3
	1				20	20	20	20	20	20	20
	2
	3
	4			53	53	53	53	50	50	50	53
	5
	6							75	75	75	67
	7
	8
	9						100	100	100	100	105
	10

चक्र

यदि आप अब तत्व 6 सम्मिलित करने का प्रयास करते हैं, तो आप एक चक्र में पहुँच जाते हैं, और असफल हो जाते हैं। टेबल की अंतिम पंक्ति में हमें फिर से वही आरंभिक स्थिति मिलती है जो आरंभ में थी।

$h\left(6\right)=6{\bmod {1}}1=6$
$h'\left(6\right)=\left\lfloor {\frac {6}{11}}\right\rfloor {\bmod {1}}1=0$

table 1	table 2
6 replaces 50 in cell 6	50 replaces 53 in cell 4
53 replaces 75 in cell 9	75 replaces 67 in cell 6
67 replaces 100 in cell 1	100 replaces 105 in cell 9
105 replaces 6 in cell 6	6 replaces 3 in cell 0
3 replaces 36 in cell 3	36 replaces 39 in cell 3
39 replaces 105 in cell 6	105 replaces 100 in cell 9
100 replaces 67 in cell 1	67 replaces 75 in cell 6
75 replaces 53 in cell 9	53 replaces 50 in cell 4
50 replaces 39 in cell 6	39 replaces 36 in cell 3
36 replaces 3 in cell 3	3 replaces 6 in cell 0
6 replaces 50 in cell 6	50 replaces 53 in cell 4

भिन्नताएँ

कुक्कू हैशिंग के कई रूपों का अध्ययन किया गया है, मुख्य रूप से लोड फैक्टर को बढ़ाकर इसके स्थानीय उपयोग में सुधार लाने के उद्देश्य से, जिसे यह मूल एल्गोरिदम की 50% सीमा से अधिक संख्या तक सहन कर सकता है। इनमें से कुछ विधियों का उपयोग कुक्कू हैशिंग की विफलता दर को कम करने के लिए भी किया जा सकता है, जिससे डेटा संरचना का पुनर्निर्माण बहुत कम होता है।

कुक्कू हैशिंग के सामान्यीकरण जो दो से अधिक वैकल्पिक हैश फंक्शनो का उपयोग करते हैं, उनसे कुछ लुकअप और प्रविष्टि गति का त्याग करते हुए हैश टेबल की क्षमता के बड़े भाग का कुशलतापूर्वक उपयोग करने की उम्मीद की जा सकती है। मात्र तीन हैश फंक्शनो का उपयोग करने से लोड 91% तक बढ़ जाता है।कुक्कू हैशिंग का अन्य सामान्यीकरण, जिसे ब्लॉक्ड कुक्कू हैशिंग कहा जाता है, में प्रति बकट से अधिक कुंजी का उपयोग करना सम्मिलित होता है। प्रति बकट मात्र 2 कुंजियों का उपयोग करने से 80% से अधिक लोड फैक्टर की अनुमति मिलती है।

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

कुछ लोग कुक्कू हैशिंग के सरलीकृत सामान्यीकरण की अनुशंसा करते हैं जिसे कुछ सीपीयू कैश में स्कूड-एसोसिएटिव कैश कहा जाता है।

कुक्कू हैश टेबल का और रूपांतर, जिसे कुक्कू निस्पंदन कहा जाता है, कुक्कू हैश टेबल की संग्रहीत कुंजियों को बहुत छोटे उंगलियों के निशान से बदल देता है, जिसकी गणना कुंजियों पर और हैश फंक्शन प्रयुक्त करके की जाती है। इन उंगलियों के चन्हो को कुक्कू फिल्टर के अंदर चारों ओर ले जाने की अनुमति देने के लिए, बिना यह जाने कि वे किस कुंजी से आए हैं, प्रत्येक फिंगरप्रिंट के दो स्थानों की गणना दूसरे से बिटवाइज़ एकमात्र फिंगरप्रिंट के साथ संचालन या हैश के साथ की जा सकती है। फिंगरप्रिंट का यह डेटा संरचना ब्लूम निस्पंदन के समान गुणों के साथ अनुमानित समुच्चय सदस्यता डेटा संरचना बनाती है: यह कुंजी के समुच्चय के सदस्यों को संग्रहीत कर सकती है, और परीक्षण कर सकती है कि क्वेरी कुंजी सदस्य है या नहीं, असत्य धनात्मक की कुछ संभावना के साथ (प्रश्न जो समुच्चय का भाग होने के रूप में अनैतिक विधि से रिपोर्ट किया गया है) यघपि कोई गलत ऋणात्मक सूचना नहीं होती है। यघपि, यह कई विधियों में ब्लूम निस्पंदन में सुधार करता है: इसकी मेमोरी का उपयोग स्थिर कारक से छोटा होता है, इसमें संदर्भ का उच्चतर स्थान होता है, और (ब्लूम निस्पंदन के विपरीत) यह बिना किसी अतिरिक्त मेमोरी दंड के समुच्चय तत्वों को शीघ्रता से हटाने की अनुमति देता है।

संबंधित संरचनाओं के साथ तुलना

ज़ुकोव्स्की एट अल द्वारा एक अध्ययन में दिखाया गया है कि आधुनिक प्रोसेसर पर छोटे, सीपीयू कैश-रेजिडेंट हैश टेबल के लिए कुक्कू हैशिंग चेन्ड हैशिंग की तुलना में बहुत श्रेष्ट होते है। केनेथ रॉस कुक्कू हैशिंग के बकेटाइज्ड संस्करणों को (वैरिएंट जो से अधिक कुंजी वाली बकट का उपयोग करते हैं) बड़े हैश टेबलओं के लिए पारंपरिक तरीकों की तुलना में श्रेष्ट दिखाया गया है, जब स्थान उपयोग अधिक होता है। बकेटाइज्ड कुक्कू हैश टेबल के प्रदर्शन की जांच एस्किटिस द्वारा की गई थी, इसके प्रदर्शन की तुलना वैकल्पिक हैशिंग योजनाओं से की गई थी।

माइकल मिटज़ेनमाचर का एक सर्वेक्षण2009 तक कुक्कू हैशिंग से संबंधित विवृत समस्याएं प्रस्तुत करता है।

अनुप्रयोग

एम्बेडिंग टेबल कलिसिओं (कोलिजन) की समस्या को हल करने के लिए टिकटोक की अनुशंसा प्रणाली में कूक्कू हैशिंग का उपयोग किया जाता है, जिसके परिणामस्वरूप मॉडल की गुणवत्ता कम हो सकती है।टिकटॉक अनुशंसा प्रणाली मोनोलिथ विभिन्न अवधारणाओं को एक ही सदिश में मानचित्र होने से रोकने के लिए कुक्कू हैशिंग के कलिसिओं स्थिरता का लाभ उठाती है।

यह भी देखें

• उत्तम हैशिंग
• डबल हैशिंग
• द्विघात जांच
• हॉप्सकॉच हैशिंग

बाहरी संबंध

• A cool and practical alternative to traditional hash tables, U. Erlingsson, M. Manasse, F. Mcsherry, 2006.
• Cuckoo Hashing for Undergraduates, 2006, R. Pagh, 2006.
• Cuckoo Hashing, Theory and Practice (Part 1, Part 2 and Part 3), Michael Mitzenmacher, 2007.
• Naor, Moni; Segev, Gil; Wieder, Udi (2008). "History-Independent Cuckoo Hashing". International Colloquium on Automata, Languages and Programming (ICALP). Reykjavik, Iceland. Retrieved 2008-07-21.
• Algorithmic Improvements for Fast Concurrent Cuckoo Hashing, X. Li, D. Andersen, M. Kaminsky, M. Freedman. EuroSys 2014.

उदाहरण

• समवर्ती उच्च-प्रदर्शन Cuckoo हैशटेबल C++ में लिखा गया है
• कुक्कू हैश मैप C++ में लिखा गया है
• C/C++ के लिए स्टेटिक कुक्कू हैशटेबल जेनरेटर
• कुक्कू हैश टेबल हास्केल में लिखी गई है
• गो के लिए कुक्कू हैशिंग

श्रेणी:खोज एल्गोरिदम श्रेणी:हैशिंग

pl:टैब्लिका मिस्ज़ाजाका#हस्ज़ोवानी कुकू.C5.82cze