कुक्कू हैशिंग: Difference between revisions

Revision as of 11:43, 19 July 2023

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

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

इतिहास

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

संचालन

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

अन्वेषण

कुक्कू हैशिंग दो हैश तालिकाओं $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}$ में संग्रहीत होती हैं। लुकअप संचालन इस प्रकार होता है:^[1]^: 124

 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)$ सबसे व्यर्थ स्थिति में होता है।^[1]^: 123

विलोपन

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

प्रविष्टि

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

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$ विक्षनरी:स्वैप की प्रक्रिया को व्यक्त करता है।^[1]^: 124-125

सिद्धांत

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

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

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

अभ्यास

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

उदाहरण

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

$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% तक बढ़ जाता है।^[7]कुक्कू हैशिंग का अन्य सामान्यीकरण, जिसे ब्लॉक्ड कुक्कू हैशिंग कहा जाता है, में प्रति बकट से अधिक कुंजी का उपयोग करना सम्मिलित होता है। प्रति बकट मात्र 2 कुंजियों का उपयोग करने से 80% से अधिक लोड फैक्टर की अनुमति मिलती है।^[8]

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

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

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

अनुप्रयोग

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

यह भी देखें

संदर्भ

↑ ^1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 ^1.6 ^1.7 ^1.8 ^1.9 Pagh, Rasmus; Rodler, Flemming Friche (2001). "Cuckoo Hashing". Algorithms — ESA 2001. Lecture Notes in Computer Science. Vol. 2161. CiteSeerX 10.1.1.25.4189. doi:10.1007/3-540-44676-1_10. ISBN 978-3-540-42493-2.
↑ "ESA - European Symposium on Algorithms: ESA Test-of-Time Award 2020". esa-symposium.org. Award committee: Uri Zwick, Samir Khuller, Edith Cohen. Archived from the original on 2021-05-22. Retrieved 2021-05-22.{{cite web}}: CS1 maint: others (link)
↑ Kutzelnigg, Reinhard (2006). द्विदलीय यादृच्छिक ग्राफ़ और कोयल हैशिंग (PDF). Fourth Colloquium on Mathematics and Computer Science. Discrete Mathematics and Theoretical Computer Science. Vol. AG. pp. 403–406.
↑ Cohen, Jeffrey S., and Daniel M. Kane. "Bounds on the independence required for cuckoo hashing." ACM Transactions on Algorithms (2009).
↑ Pǎtraşcu, Mihai, and Mikkel Thorup. "The power of simple tabulation hashing." Journal of the ACM (JACM) 59.3 (2012): 1-50.
↑ Aumüller, Martin, Martin Dietzfelbinger, and Philipp Woelfel. "Explicit and efficient hash families suffice for cuckoo hashing with a stash." Algorithmica 70.3 (2014): 428-456.
↑ ^7.0 ^7.1 Mitzenmacher, Michael (2009-09-09). "कुक्कू हैशिंग से संबंधित कुछ खुले प्रश्न" (PDF). Proceedings of ESA 2009. Retrieved 2010-11-10.
↑ Dietzfelbinger, Martin; Weidling, Christoph (2007). "Balanced allocation and dictionaries with tightly packed constant size bins". Theoret. Comput. Sci. 380 (1–2): 47–68. doi:10.1016/j.tcs.2007.02.054. MR 2330641.
↑ Kirsch, Adam; Mitzenmacher, Michael D.; Wieder, Udi (2010). "More robust hashing: cuckoo hashing with a stash". SIAM J. Comput. 39 (4): 1543–1561. doi:10.1137/080728743. MR 2580539.
↑ Aumüller, Martin; Dietzfelbinger, Martin; Woelfel, Philipp (2014). "Explicit and efficient hash families suffice for cuckoo hashing with a stash". Algorithmica. 70 (3): 428–456. arXiv:1204.4431. doi:10.1007/s00453-013-9840-x. MR 3247374. S2CID 1888828.
↑ "Micro-Architecture".
↑ Fan, Bin; Andersen, Dave G.; Kaminsky, Michael; Mitzenmacher, Michael D. (2014), "Cuckoo filter: Practically better than Bloom", Proc. 10th ACM Int. Conf. Emerging Networking Experiments and Technologies (CoNEXT '14), pp. 75–88, doi:10.1145/2674005.2674994
↑ Zukowski, Marcin; Heman, Sandor; Boncz, Peter (June 2006). "वास्तुकला-जागरूक हैशिंग" (PDF). Proceedings of the International Workshop on Data Management on New Hardware (DaMoN). Retrieved 2008-10-16.
↑ Ross, Kenneth (2006-11-08). आधुनिक प्रोसेसर पर कुशल हैश जांच (PDF) (Research Report). IBM. RC24100. Retrieved 2008-10-16.
↑ Askitis, Nikolas (2009). "Fast and Compact Hash Tables for Integer Keys". Proceedings of the 32nd Australasian Computer Science Conference (ACSC 2009) (PDF). Vol. 91. pp. 113–122. ISBN 978-1-920682-72-9. Archived from the original (PDF) on 2011-02-16. Retrieved 2010-06-13.
↑ "Monolith: The Recommendation System Behind TikTok". gantry.io (in English). Retrieved 2023-05-30.

बाहरी संबंध

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.

उदाहरण

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

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

[Cuckoo-1] 1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 ^1.6 ^1.7 ^1.8 ^1.9 Pagh, Rasmus; Rodler, Flemming Friche (2001). "Cuckoo Hashing". Algorithms — ESA 2001. Lecture Notes in Computer Science. Vol. 2161. CiteSeerX 10.1.1.25.4189. doi:10.1007/3-540-44676-1_10. ISBN 978-3-540-42493-2.

[2] "ESA - European Symposium on Algorithms: ESA Test-of-Time Award 2020". esa-symposium.org. Award committee: Uri Zwick, Samir Khuller, Edith Cohen. Archived from the original on 2021-05-22. Retrieved 2021-05-22.{{cite web}}: CS1 maint: others (link)

[3] Kutzelnigg, Reinhard (2006). द्विदलीय यादृच्छिक ग्राफ़ और कोयल हैशिंग (PDF). Fourth Colloquium on Mathematics and Computer Science. Discrete Mathematics and Theoretical Computer Science. Vol. AG. pp. 403–406.

[4] Cohen, Jeffrey S., and Daniel M. Kane. "Bounds on the independence required for cuckoo hashing." ACM Transactions on Algorithms (2009).

[5] Pǎtraşcu, Mihai, and Mikkel Thorup. "The power of simple tabulation hashing." Journal of the ACM (JACM) 59.3 (2012): 1-50.

[6] Aumüller, Martin, Martin Dietzfelbinger, and Philipp Woelfel. "Explicit and efficient hash families suffice for cuckoo hashing with a stash." Algorithmica 70.3 (2014): 428-456.

[mitzenmacher2009survey-7] 7.0 ^7.1 Mitzenmacher, Michael (2009-09-09). "कुक्कू हैशिंग से संबंधित कुछ खुले प्रश्न" (PDF). Proceedings of ESA 2009. Retrieved 2010-11-10.

[8] Dietzfelbinger, Martin; Weidling, Christoph (2007). "Balanced allocation and dictionaries with tightly packed constant size bins". Theoret. Comput. Sci. 380 (1–2): 47–68. doi:10.1016/j.tcs.2007.02.054. MR 2330641.

[9] Kirsch, Adam; Mitzenmacher, Michael D.; Wieder, Udi (2010). "More robust hashing: cuckoo hashing with a stash". SIAM J. Comput. 39 (4): 1543–1561. doi:10.1137/080728743. MR 2580539.

[10] Aumüller, Martin; Dietzfelbinger, Martin; Woelfel, Philipp (2014). "Explicit and efficient hash families suffice for cuckoo hashing with a stash". Algorithmica. 70 (3): 428–456. arXiv:1204.4431. doi:10.1007/s00453-013-9840-x. MR 3247374. S2CID 1888828.

[11] "Micro-Architecture".

[12] Fan, Bin; Andersen, Dave G.; Kaminsky, Michael; Mitzenmacher, Michael D. (2014), "Cuckoo filter: Practically better than Bloom", Proc. 10th ACM Int. Conf. Emerging Networking Experiments and Technologies (CoNEXT '14), pp. 75–88, doi:10.1145/2674005.2674994

[13] Zukowski, Marcin; Heman, Sandor; Boncz, Peter (June 2006). "वास्तुकला-जागरूक हैशिंग" (PDF). Proceedings of the International Workshop on Data Management on New Hardware (DaMoN). Retrieved 2008-10-16.

[14] Ross, Kenneth (2006-11-08). आधुनिक प्रोसेसर पर कुशल हैश जांच (PDF) (Research Report). IBM. RC24100. Retrieved 2008-10-16.

[15] Askitis, Nikolas (2009). "Fast and Compact Hash Tables for Integer Keys". Proceedings of the 32nd Australasian Computer Science Conference (ACSC 2009) (PDF). Vol. 91. pp. 113–122. ISBN 978-1-920682-72-9. Archived from the original (PDF) on 2011-02-16. Retrieved 2010-06-13.

[16] "Monolith: The Recommendation System Behind TikTok". gantry.io (in English). Retrieved 2023-05-30.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

@@ Line 1: / Line 1: @@
 {{Short description|Data structure hashing scheme}}
-[[Image:Cuckoo hashing example.svg|thumb|कुक्कू   हैशिंग उदाहरण. तीर प्रत्येक कुंजी का वैकल्पिक स्थान दिखाते हैं। A के स्थान में  नया आइटम डाला जाएगा, A को उसके वैकल्पिक स्थान पर ले जाया जाएगा, जो वर्तमान में B द्वारा कब्जा कर लिया गया है, और B को उसके वैकल्पिक स्थान पर ले जाया जाएगा जो वर्तमान में खाली है। H के स्थान पर किसी नए आइटम का सम्मिलन सफल नहीं होगा: चूँकि H  चक्र का हिस्सा है (W के साथ), नया आइटम फिर से बाहर हो जाएगा।]]कुक्कू हैशिंग [[कंप्यूटर प्रोग्रामिंग]] में एक [[हैश तालिका]] में [[हैश फंकशन|हैश फलन]] के मूल्यों के हैश टकराव को हल करने के लिए  योजना होती है, जिसमें सबसे व्यर्थ स्थिति में [[निरंतर समय]] लुकअप समय होता है। यह नाम [[कोयल|कुक्कू]]   की कुछ प्रजातियों के व्यवहार से लिया जाता है, जहां कुक्कू   का चूजा अंडे सेते समय अन्य अंडों या बच्चों को घोंसले से बाहर प्रेरित कर देता है, इस व्यवहार में भिन्नता होती है जिसे ब्रूड परजीवीवाद कहा जाता है; समान रूप से, कुक्कू हैशिंग तालिका में  नई कुंजी प्रयुक्त करने से पुरानी कुंजी को तालिका में किसी भिन्न स्थान पर प्रेरित किया  जा सकता है।
+[[Image:Cuckoo hashing example.svg|thumb|कुक्कू हैशिंग उदाहरण। तीर प्रत्येक कुंजी का वैकल्पिक स्थान दिखाते हैं। A के स्थान में नई वास्तु प्रविष्ट की जाती है, A को उसके वैकल्पिक स्थान पर ले जाया जाता है, जो वर्तमान में B द्वारा अधिकृत कर लियाजाता है, और B को उसके वैकल्पिक स्थान पर ले जाया जाता है जो वर्तमान में विवृत होता है। H के स्थान पर किसी नई वास्तु का सम्मिलन सफल नहीं होता है: चूँकि H चक्र का भाग होता है (W के साथ), नई वास्तु पुनः बाहर हो हो जाती है।]]'''कुक्कू हैशिंग''' [[कंप्यूटर प्रोग्रामिंग]] में एक [[हैश तालिका]] में [[हैश फंकशन|हैश फलन]] के मूल्यों के हैश टकराव (कोलिजन ) को हल करने के लिए योजना होती है, जिसमें सबसे व्यर्थ स्थिति में [[निरंतर समय]] लुकअप समय होता है। यह नाम [[कोयल|कुक्कू]] की कुछ प्रजातियों के व्यवहार से लिया जाता है, जहां कुक्कू का चूजा (बच्चा) अंडे सेते समय अन्य अंडों या बच्चों को घोंसले से बाहर प्रेरित कर देता है, इस व्यवहार में भिन्नता होती है जिसे ब्रूड परजीवीवाद कहा जाता है; समान रूप से, कुक्कू हैशिंग तालिका में नई कुंजी प्रयुक्त करने से पुरानी कुंजी को तालिका में किसी भिन्न स्थान पर प्रेरित किया जा सकता है।
 ==इतिहास==
-कुक्कू हैशिंग का वर्णन सबसे पहले 2001 के  कॉन्फ्रेंस पेपर में [[रासमस पाघ]] और [[फ्लेमिंग फ्रिचे रोडलर]] द्वारा किया गया था।<ref name="Cuckoo">{{Cite book |last1=Pagh |first1=Rasmus |author1-link=Rasmus Pagh |last2=Rodler |first2=Flemming Friche| chapter=Cuckoo Hashing |doi=10.1007/3-540-44676-1_10 |title=Algorithms — ESA 2001 |series=Lecture Notes in Computer Science |volume=2161| year=2001 |isbn=978-3-540-42493-2 |citeseerx=10.1.1.25.4189}}</ref> पेपर को 2020 में कलन विधि समय का परीक्षण पुरस्कार पर यूरोपीय संगोष्ठी से सम्मानित किया गया था।<ref>{{Cite web |others=Award committee: [[Uri Zwick]], [[Samir Khuller]], [[Edith Cohen]]|title=ESA - European Symposium on Algorithms: ESA Test-of-Time Award 2020|url=http://esa-symposium.org/test-of-time-award.php |url-status=deviated |access-date=2021-05-22 |website=esa-symposium.org|archive-url=http://web.archive.org/web/20210522135306/http://esa-symposium.org/test-of-time-award.php |archive-date=2021-05-22}}</ref>{{rp|p=122}}
+कुक्कू हैशिंग का वर्णन सबसे पहले 2001 के कॉन्फ्रेंस पेपर में [[रासमस पाघ]] और [[फ्लेमिंग फ्रिचे रोडलर]] द्वारा किया गया था।<ref name="Cuckoo">{{Cite book |last1=Pagh |first1=Rasmus |author1-link=Rasmus Pagh |last2=Rodler |first2=Flemming Friche| chapter=Cuckoo Hashing |doi=10.1007/3-540-44676-1_10 |title=Algorithms — ESA 2001 |series=Lecture Notes in Computer Science |volume=2161| year=2001 |isbn=978-3-540-42493-2 |citeseerx=10.1.1.25.4189}}</ref> पेपर को 2020 में कलन विधि समय का परीक्षण पुरस्कार पर यूरोपीय संगोष्ठी से सम्मानित किया गया था।<ref>{{Cite web |others=Award committee: [[Uri Zwick]], [[Samir Khuller]], [[Edith Cohen]]|title=ESA - European Symposium on Algorithms: ESA Test-of-Time Award 2020|url=http://esa-symposium.org/test-of-time-award.php |url-status=deviated |access-date=2021-05-22 |website=esa-symposium.org|archive-url=http://web.archive.org/web/20210522135306/http://esa-symposium.org/test-of-time-award.php |archive-date=2021-05-22}}</ref>{{rp|p=122}}
 ==संचालन==
-कुक्कू हैशिंग [[ खुला संबोधन |विवृत संबोधन]] का एक रूप होता है जिसमें हैश तालिका के प्रत्येक गैर-विवृत सेल में  [[अद्वितीय कुंजी]] या कुंजी-मूल्य जोड़ी होती है। प्रत्येक कुंजी के लिए स्थान निर्धारित करने के लिए  हैश फलन का उपयोग किया जाता है, और तालिका में इसकी उपस्थिति (या इसके साथ जुड़े मूल्य) को तालिका के उस सेल की जांच करके पाया जा सकता है। यघपि, ओपन एड्रेसिंग हैश टकराव से संबद्ध होते है, जो तब सेल में  से अधिक कुंजी मानचित्र की जाती हैं। कुक्कू  हैशिंग का मूल विचार मात्र के अतिरिक्त दो हैश फलन का उपयोग करके टकराव को हल करता है। यह प्रत्येक कुंजी के लिए हैश तालिका में दो संभावित स्थान प्रदान करता है। कलन विधि को सामान्यतः उपयोग किए जाने वाले वेरिएंट में से एक में, हैश तालिका को समान आकार की दो छोटी तालिकाओं में विभाजित किया जाता है, और प्रत्येक हैश फलन इन दो तालिकाओं में से एक में अनुक्रमणिका प्रदान करता है। दोनों हैश फलनो के लिए  ही तालिका में अनुक्रमणिका प्रदान करना भी संभव होता है।{{r|Cuckoo|p=121-122}}
+कुक्कू हैशिंग [[ खुला संबोधन |विवृत संबोधन]] का एक रूप होता है जिसमें हैश तालिका के प्रत्येक गैर-विवृत सेल में [[अद्वितीय कुंजी]] या कुंजी-मूल्य जोड़ी होती है। प्रत्येक कुंजी के लिए स्थान निर्धारित करने के लिए हैश फलन का उपयोग किया जाता है, और तालिका में इसकी उपस्थिति (या इसके साथ जुड़े मूल्य) को तालिका के उस सेल की जांच करके पाया जा सकता है। यघपि, ओपन एड्रेसिंग हैश टकराव से संबद्ध होते है, जो तब सेल में से अधिक कुंजी मानचित्र की जाती हैं। कुक्कू हैशिंग का मूल विचार मात्र के अतिरिक्त दो हैश फलन का उपयोग करके टकराव को हल करता है। यह प्रत्येक कुंजी के लिए हैश तालिका में दो संभावित स्थान प्रदान करता है। कलन विधि को सामान्यतः उपयोग किए जाने वाले वेरिएंट में से एक में, हैश तालिका को समान आकृति की दो छोटी तालिकाओं में विभाजित किया जाता है, और प्रत्येक हैश फलन इन दो तालिकाओं में से एक में अनुक्रमणिका प्रदान करता है। दोनों हैश फलनो के लिए ही तालिका में अनुक्रमणिका प्रदान करना भी संभव होता है।{{r|Cuckoo|p=121-122}}
 ===अन्वेषण===
-कुक्कू  हैशिंग दो हैश तालिकाओं  <math>T_1</math> और <math>T_2</math>का उपयोग करती है। यह मानते हुए <math>r</math> प्रत्येक तालिकाओं की लंबाई होती है, दो तालिकाओं के लिए हैश फलन को इस प्रकार <math>h_1,\ h_2\ :\ \cup \rightarrow \{0, ..., r-1\}</math>और <math>\forall x \in S</math> द्वारा परिभाषित किया जाता है, जहाँ <math>x</math> कुंजी  और <math>S</math> वह समुच्चय बनें जिसकी कुंजियाँ  <math>h_1(x)</math> के <math>T_1</math>में और <math>h_2(x)</math> के <math>T_2</math> में संग्रहीत होती हैं। लुकअप संचालन इस प्रकार होता है:{{r|Cuckoo|p=124}}
+कुक्कू हैशिंग दो हैश तालिकाओं <math>T_1</math> और <math>T_2</math>का उपयोग करती है। यह मानते हुए <math>r</math> प्रत्येक तालिकाओं की लंबाई होती है, दो तालिकाओं के लिए हैश फलन को इस प्रकार <math>h_1,\ h_2\ :\ \cup \rightarrow \{0, ..., r-1\}</math>और <math>\forall x \in S</math> द्वारा परिभाषित किया जाता है, जहाँ <math>x</math> कुंजी और <math>S</math> वह समुच्चय बनें जिसकी कुंजियाँ <math>h_1(x)</math> के <math>T_1</math>में और <math>h_2(x)</math> के <math>T_2</math> में संग्रहीत होती हैं। लुकअप संचालन इस प्रकार होता है:{{r|Cuckoo|p=124}}
 {|
 |- style="vertical-align:top"
 |
    '''function''' lookup(x) '''is'''
-   '''return''' <math>T_1[h_1(x)]\ =\ x \vee T_2[h_2(x)] = x</math>
+  '''return''' <math>T_1[h_1(x)]\ =\ x \vee T_2[h_2(x)] = x</math>
    '''end function'''
 |}
-[[तार्किक या]] (<math>\vee</math>) प्रदर्शित करता है कि, कुंजी <math>x</math> का मान या तो  <math>T_1</math> या तो <math>T_2</math> में पाया जाता है , जो <math>O(1)</math> सबसे व्यर्थ स्थिति में होता है।{{r|Cuckoo|p=123}}
+[[तार्किक या]] (<math>\vee</math>) प्रदर्शित करता है कि, कुंजी <math>x</math> का मान या तो <math>T_1</math> या तो <math>T_2</math> में पाया जाता है , जो <math>O(1)</math> सबसे व्यर्थ स्थिति में होता है।{{r|Cuckoo|p=123}}
 ===विलोपन===
 विलोपन <math>O(1)</math> में किया जाता है चूंकि इसमें जांच में कोई सहकारिता नहीं होती है - यदि तालिका बहुत कम है तो दबाव संचाल के मूल्य पर विचार नहीं किया जाता है।{{r|Cuckoo|p=124-125}}
-===सम्मिलन===
+===प्रविष्टि===
-नए नाम-मूल्य जोड़े को सम्मिलित करने के पहले चरण में यह जांचना आवश्यक होता है कि क्या स्लॉट  <math>h_1(x)</math> तालिका के <math>T_1</math> भरा हुआ हैं; यदि ऐसा नहीं है, तो आइटम उस सेल में डाला जाता है। यघपि, यदि स्थान पर अधिकार कर लिया जाता है, तो पहले से अधिकृत वस्तु हटा दी जाती है - <math>x'</math>को स्थित रहने देते है  -और <math>x</math> को  <math>T_1[h_1(x)]</math> में प्रविष्ट कर देते है। हटाई गई वस्तु <math>x'</math>को <math>T_2</math> तालिका में प्रविष्ट किया जाता है  इस प्रक्रिया का निरंतर पालन किया जाता; प्रक्रिया तब तक निरंतर रहती है जब तक कुंजी प्रविष्ट कराने के लिए कोई रिक्त स्थान नहीं प्राप्त होता है।{{r|Cuckoo|p=124-125}} प्रक्रिया लूप में संभावित [[अनंत पुनरावृत्ति]] से बचने के लिए, एक  <math>\text{Max-Loop}</math> इस प्रकार निर्दिष्ट किया जाता है कि यदि पुनरावृत्तियाँ निश्चित महत्वपूर्ण मूल्य से अधिक हो जाती हैं, तो हैश तालिकाएँ - दोनों <math>T_1</math> और <math>T_2</math>- नए हैश फलन के साथ दोबारा दोहराया जाता है और प्रविष्टि प्रक्रिया दोहराई जाती है। सम्मिलन के लिए छद्म कोड निम्नलिखित होता है:{{r|Cuckoo|p=125}}
+नए नाम-मूल्य जोड़े को सम्मिलित करने के पहले चरण में यह जांचना आवश्यक होता है कि क्या स्लॉट <math>h_1(x)</math> तालिका के <math>T_1</math> भरा हुआ हैं; यदि ऐसा नहीं है, तो आइटम उस सेल में प्रविष्टि कराया जाता है। यघपि, यदि स्थान पर अधिकार कर लिया जाता है, तो पहली वस्तु हटा दी जाती है - इसे रहने दें <math>x'</math>-और <math>x</math> को <math>T_1[h_1(x)]</math> पर प्रविष्ट किया गया है । हटाई गई वस्तु <math>x'</math> को तालिका <math>T_2</math> में प्रविष्ट किया जाता है। प्रक्रिया का निरंतर पालन किया जाता है; प्रक्रिया तब तक जारी रहती है जब तक कुंजी प्रविष्ट करने के लिए कोई रिक्त स्थान नहीं प्राप्त हो जाता है।{{r|Cuckoo|p=124-125}} प्रक्रिया लूप में संभावित [[अनंत पुनरावृत्ति]] से बचने के लिए, a <math>\text{Max-Loop}</math> इस प्रकार निर्दिष्ट किया जाता है कि यदि पुनरावृत्तियाँ निश्चित क्रिटिकल वैल्यू से अधिक हो जाती हैं, तो हैश तालिकाएँ दोनों <math>T_1</math> और <math>T_2</math>- नए हैश फलनो के साथ पुनः दोहराया जाता है और प्रविष्टि प्रक्रिया दोहराई जाती है। सम्मिलन के लिए छद्म कोड निम्नलिखित होता है:{{r|Cuckoo|p=125}}
 {|
 |- style="vertical-align:top"
 |
 '''function''' insert(x) '''is'''
-  '''if''' lookup(x) '''then'''
+'''if''' lookup(x) '''then'''
-   '''return'''
+'''return'''
-  '''end if'''
+'''end if'''
-  '''loop''' Max-Loop '''times'''
+'''loop''' Max-Loop '''times'''
-   '''if''' <math>T_1[h_1(x)]</math> = <math>\bot</math> '''then'''
+'''if''' <math>T_1[h_1(x)]</math> = <math>\bot</math> '''then'''
-    <math>T_1[h_1(x)]</math> := x
+  <math>T_1[h_1(x)]</math> := x
-    '''return'''
+  '''return'''
-   '''end if'''
+'''end if'''
-   x <math>\leftrightarrow T_1[h_1(x)]</math>
+x <math>\leftrightarrow T_1[h_1(x)]</math>
-   '''if''' <math>T_2[h_2(x)]</math> = <math>\bot</math> '''then'''
+'''if''' <math>T_2[h_2(x)]</math> = <math>\bot</math> '''then'''
-    <math>T_2[h_2(x)]</math> := x
+  <math>T_2[h_2(x)]</math> := x
-    '''return'''
+  '''return'''
-   '''end if'''
+'''end if'''
-   x <math>\leftrightarrow T_2[h_2(x)]</math>
+x <math>\leftrightarrow T_2[h_2(x)]</math>
-  '''end loop'''
+'''end loop'''
-  rehash()
+rehash()
-  insert(x)
+insert(x)
 '''end function'''
 |}
-पंक्ति 10 और 15 पर, अन्य चाबियों को लात मारने का कुक्कू   दृष्टिकोण - जो कि व्यस्त था <math>T_{1,2}[h_{1,2}(x)]</math>-तब तक होता है जब तक कि प्रत्येक कुंजी का अपना घोंसला यानी आइटम न हो जाए <math>x</math> दो तालिकाओं में से किसी  पर  स्थान में डाला गया है; संकेतन <math>\leftrightarrow</math> विक्षनरी:स्वैप की प्रक्रिया को व्यक्त करता है।{{r|Cuckoo|p=124-125}}
+पंक्ति 10 और 15 पर, अन्य कुंजियो को किक करने का 'कुक्कू दृष्टिकोण' - जो कि पहले से <math>T_{1,2}[h_{1,2}(x)]</math>में अधिकृत था। तब तक होता है जब तक कि प्रत्येक कुंजी का अपना घोंसला अर्थात वस्तु <math>x</math> को दो तालिकाओं में से किसी पर स्थान में प्रविष्ट किया जाता है; संकेतन <math>\leftrightarrow</math> विक्षनरी:स्वैप की प्रक्रिया को व्यक्त करता है।{{r|Cuckoo|p=124-125}}
 ==सिद्धांत==
-सम्मिलन अपेक्षित स्थिर समय में सफल होता है,<ref name="Cuckoo" />यहां तक कि तालिका को पुनः निर्माण करने की संभावना पर भी विचार किया जाता है, जब तक कि कुंजियों की संख्या हैश तालिका की क्षमता के आधे से कम रखी जाती है, अर्थात्, [[लोड फैक्टर (कंप्यूटर विज्ञान)|लोड फैक्टर]]  50% से नीचे होता है।
+सम्मिलन अपेक्षित स्थिर समय में सफल होते है,<ref name="Cuckoo" />यहां तक कि तालिका के पुनर्निर्माण की संभावना पर भी विचार करते हुए, जब तक कि कुंजियों की संख्या हैश तालिका की क्षमता के आधे से कम रखी जाती है, अर्थात्, [[लोड फैक्टर (कंप्यूटर विज्ञान)|लोड फैक्टर]] 50% से निम्न होता है।
-इसे सिद्ध करने की विधि में [[यादृच्छिक ग्राफ]] के सिद्धांत का उपयोग किया जाता है: कोई [[अप्रत्यक्ष ग्राफ]] का निर्माण कर सकता है जिसे कुक्कू  ग्राफ़ भी कहा जाता है जिसमें प्रत्येक हैश तालिका स्थान के लिए शीर्ष होता है, और प्रत्येक हैशेड मान के लिए किनारा होता है, किनारे के अंतिम बिंदु दो संभावित मूल्य के स्थान होते हैं। फिर, कुक्कू  हैश तालिका में मानों का समुच्चय जोड़ने के लिए स्वार्थी सम्मिलन एल्गोरिथ्म सफल होता है यदि और मात्र  यदि मूल्यों के इस समुच्चय के लिए कुक्कू  ग्राफ [[छद्मवन]] होता है, तो इसके प्रत्येक जुड़े घटक में अधिकतम चक्र वाला ग्राफ (ग्राफ सिद्धांत) )एस। शीर्षों से अधिक किनारों वाला कोई भी शीर्ष-प्रेरित सबग्राफ कुंजियों के  समुच्चय के समरूप होता है जिसके लिए हैश तालिका में अपर्याप्त संख्या में स्लॉट उपस्थित होते हैं। जब हैश फलन को यादृच्छिक रूप से चुना जाता है, तो कुक्कू  ग्राफ एर्दो-रेनी मॉडल में यादृच्छिक ग्राफ होता है। उच्च संभावना के साथ, 1/2 से कम लोड फैक्टर के लिए ( यादृच्छिक ग्राफ के अनुरूप जिसमें किनारों की संख्या और कोने की संख्या का अनुपात 1/2 से नीचे घिरा हुआ है), ग्राफ  छद्म वन और कुक्कू   हैशिंग एल्गोरिदम है सभी चाबियाँ रखने में सफल हो जाता है। वही सिद्धांत यह भी साबित करता है कि कुक्कू   ग्राफ के कनेक्टेड घटक (ग्राफ सिद्धांत) का अपेक्षित आकार छोटा है, यह सुनिश्चित करता है कि प्रत्येक प्रविष्टि में लगातार अपेक्षित समय लगता है। यघपि , उच्च संभावना के साथ, 1/2 से अधिक लोड फैक्टर दो या दो से अधिक चक्रों वाले  [[विशाल घटक]] को जन्म देगा, जिससे डेटा संरचना विफल हो जाएगी और आकार बदलने की आवश्यकता होगी।<ref>{{Cite conference|first=Reinhard|last=Kutzelnigg|url=https://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/viewFile/dmAG0133/1710.pdf|conference=Fourth Colloquium on Mathematics and Computer Science|title=द्विदलीय यादृच्छिक ग्राफ़ और कोयल हैशिंग|series=Discrete Mathematics and Theoretical Computer Science|year=2006|volume=AG|pages=403–406}}</ref>
+इसे सिद्ध करने की एक विधि [[यादृच्छिक ग्राफ]] के सिद्धांत का उपयोग करती है: कोई भी एक [[अप्रत्यक्ष ग्राफ]] बना सकता है जिसे "कुक्कू ग्राफ़" कहा जाता है जिसमें प्रत्येक हैश तालिका स्थान के लिए शीर्ष होता है, और प्रत्येक हैशेड मान के लिए सीमांत होता है, किनारे के अंतिम बिंदु के दो संभावित मूल्य के स्थान होते हैं। फिर, कुक्कू हैश तालिका में मानों का समुच्चय जोड़ने के लिए लालची स्वार्थी एल्गोरिथ्म सफल होता है यदि और मात्र यदि मूल्यों के इस समुच्चय के लिए कुक्कू ग्राफ [[छद्मवन]] होता है, तो इसके प्रत्येक जुड़े घटक में अधिकतम एक चक्र वाला ग्राफ होता है। शीर्षों से अधिक सीमा वाला कोई भी शीर्ष-प्रेरित सबग्राफ कुंजियों के समुच्चय के समरूप होता है जिसके लिए हैश तालिका में अपर्याप्त संख्या में स्लॉट उपस्थित होते हैं। जब हैश फलन को यादृच्छिक रूप से चयन किया जाता है, तो कुक्कू ग्राफ एर्दो-रेनी मॉडल में एक यादृच्छिक ग्राफ होता है। उच्च संभावना के साथ, 1/2 से कम लोड फैक्टर के लिए ( यादृच्छिक ग्राफ के अनुरूप जिसमें किनारों की संख्या और कोने की संख्या का अनुपात 1/2 से नीचे घिरा हुआ होता है), इस प्रकार ग्राफ छद्म वन और कुक्कू हैशिंग एल्गोरिदम सभी कुंजिया रखने में सफल हो जाता है। वही सिद्धांत यह भी सिद्ध करता है कि कुक्कू ग्राफ के सम्बद्ध घटक का अपेक्षित आकृति छोटी होती है, यह सुनिश्चित करता है कि प्रत्येक प्रविष्टि में निरंतर अपेक्षित समय लगता है। यघपि, उच्च संभावना के साथ, 1/2 से अधिक लोड फैक्टर दो या दो से अधिक चक्रों वाले [[विशाल घटक]] को जन्म देता है, जिससे डेटा संरचना विफल हो जाती है और आकृति बदलने की आवश्यकता होती है।<ref>{{Cite conference|first=Reinhard|last=Kutzelnigg|url=https://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/viewFile/dmAG0133/1710.pdf|conference=Fourth Colloquium on Mathematics and Computer Science|title=द्विदलीय यादृच्छिक ग्राफ़ और कोयल हैशिंग|series=Discrete Mathematics and Theoretical Computer Science|year=2006|volume=AG|pages=403–406}}</ref>
-चूँकि  सैद्धांतिक यादृच्छिक हैश फलन को व्यावहारिक उपयोग के लिए बहुत अधिक स्थान की आवश्यकता होती है,  महत्वपूर्ण सैद्धांतिक प्रश्न यह है कि कुक्कू   हैशिंग के लिए कौन सा व्यावहारिक हैश फलन पर्याप्त है।  दृष्टिकोण k-स्वतंत्र हैशिंग का उपयोग करना है। 2009 में इसे दिखाया गया था<ref>Cohen, Jeffrey S., and Daniel M. Kane. "Bounds on the independence required for cuckoo hashing." ACM Transactions on Algorithms (2009).</ref> वह <math>O(\log n)</math>-स्वतंत्रता पर्याप्त है, और कम से कम 6-स्वतंत्रता की आवश्यकता है।  अन्य दृष्टिकोण [[सारणीकरण हैशिंग]] का उपयोग करना है, जो 6-स्वतंत्र नहीं है, लेकिन 2012 में दिखाया गया था<ref>Pǎtraşcu, Mihai, and Mikkel Thorup. "The power of simple tabulation hashing." Journal of the ACM (JACM) 59.3 (2012): 1-50.</ref> कुक्कू   हैशिंग के लिए पर्याप्त अन्य गुण होना।
-से तीसरा दृष्टिकोण<ref>Aumüller, Martin, Martin Dietzfelbinger, and Philipp Woelfel. "Explicit and efficient hash families suffice for cuckoo hashing with a stash." Algorithmica 70.3 (2014): 428-456.</ref> कुक्कू   हैशटेबल को तथाकथित स्टैश के साथ थोड़ा संशोधित करना है, जो 2-स्वतंत्र हैश फलनो  से अधिक कुछ भी उपयोग करना संभव नहीं बनाता है।
+चूँकि सैद्धांतिक यादृच्छिक हैश फलन को व्यावहारिक उपयोग के लिए बहुत अधिक स्थान की आवश्यकता होती है, महत्वपूर्ण सैद्धांतिक प्रश्न यह है कि कुक्कू हैशिंग के लिए कौन सा व्यावहारिक हैश फलन पर्याप्त होता है। दृष्टिकोण k-स्वतंत्र हैशिंग का उपयोग करता है। 2009 में इसे दिखाया गया था<ref>Cohen, Jeffrey S., and Daniel M. Kane. "Bounds on the independence required for cuckoo hashing." ACM Transactions on Algorithms (2009).</ref> की <math>O(\log n)</math>-स्वतंत्रता पर्याप्त है, और कम से कम 6-स्वतंत्रता की आवश्यकता होती है। अन्य दृष्टिकोण [[सारणीकरण हैशिंग]] का उपयोग करता है, जो 6-स्वतंत्र नहीं है, यघपि 2012 में दिखाया गया था<ref>Pǎtraşcu, Mihai, and Mikkel Thorup. "The power of simple tabulation hashing." Journal of the ACM (JACM) 59.3 (2012): 1-50.</ref> की इसमें कुक्कू हैशिंग के लिए पर्याप्त अन्य गुण उपस्थित होते है । 2014 से एक तीसरा दृष्टिकोण<ref>Aumüller, Martin, Martin Dietzfelbinger, and Philipp Woelfel. "Explicit and efficient hash families suffice for cuckoo hashing with a stash." Algorithmica 70.3 (2014): 428-456.</ref> तथाकथित स्टैश के साथ कुक्कू हैशटेबल को थोड़ा संशोधित करता है, जो 2-स्वतंत्र हैश फलनो से अधिक कुछ भी उपयोग करना संभव नहीं बनाता है।
 ==अभ्यास==
-व्यवहार में, कुक्कू   हैशिंग [[रैखिक जांच]] की तुलना में लगभग 20-30% धीमी है, जो सामान्य तरीकों में सबसे तेज़ है।<ref name="Cuckoo"/>इसका कारण यह है कि कुक्कू हैशिंग अक्सर प्रति खोज दो कैश मिस का कारण बनती है, उन दो स्थानों की जांच करने के लिए जहां  कुंजी संग्रहीत की जा सकती है, जबकि रैखिक जांच के कारण आमतौर पर प्रति खोज मात्र   कैश मिस होता है।
+व्यवहार में, कुक्कू हैशिंग [[रैखिक जांच]] की तुलना में लगभग 20-30% धीमें होते है, जो सामान्य विधियों में सबसे शीघ्र होता है।<ref name="Cuckoo"/>इसका कारण यह है कि कुक्कू हैशिंग सामान्यतः प्रति अन्वेषण दो कैश मिस का कारण बनती है, उन दो स्थानों की जांच करने के लिए जहां कुंजी संग्रहीत की जा सकती है, जबकि रैखिक जांच के कारण समानतः अन्वेषण मात्र कैश मिस होता है। यघपि, खोज समय पर इसकी सबसे अनुपयुक्त स्थिति की आश्वासन के कारण, [[वास्तविक समय कंप्यूटिंग|वास्तविक]] समय प्रतिक्रिया दरों की आवश्यकता होने पर कुक्कू हैशिंग अभी भी मूल्यवान हो सकती है। कुक्कू हैशिंग का लाभ इसकी लिंक-लिस्ट मुक्त गुण होता है, जो जीपीयू प्रोसेसिंग के लिए अच्छी तरह से उपयुक्त होता है।
-यघपि , खोज समय पर इसकी सबसे खराब स्थिति की गारंटी के कारण, [[वास्तविक समय कंप्यूटिंग]] | वास्तविक समय प्रतिक्रिया दरों की आवश्यकता होने पर कुक्कू   हैशिंग अभी भी मूल्यवान हो सकती है। कुक्कू हैशिंग का  फायदा इसकी लिंक-लिस्ट मुक्त संपत्ति है, जो जीपीयू प्रोसेसिंग के लिए अच्छी तरह से फिट बैठती है।
 ==उदाहरण==
@@ Line 65: / Line 64: @@
 <math>h\left(k\right)=k\bmod 11</math><br/>
 <math>h'\left(k\right)=\left\lfloor\frac{k}{11}\right\rfloor\bmod 11</math>
-निम्नलिखित दो तालिकाएँ कुछ उदाहरण तत्वों का सम्मिलन दिखाती हैं। प्रत्येक कॉलम समय के साथ दो हैश तालिकाओं की स्थिति से मेल खाता है। प्रत्येक नए मान के लिए संभावित प्रविष्टि स्थानों पर प्रकाश डाला गया है।
+निम्नलिखित दो तालिकाएँ कुछ उदाहरण तत्वों का सम्मिलन प्रदर्शित करती हैं। प्रत्येक कॉलम समय के साथ दो हैश तालिकाओं की स्थिति के समरूप होता है। प्रत्येक नए मान के लिए संभावित प्रविष्टि स्थानों पर प्रकाश को प्रदर्शित किया जाता है।
 <div शैली=फ्लोट:बाएँ; मार्जिन-दाएं:1em >
@@ Line 164: / Line 164: @@
 |}
 </div>
-===साइकिल===
+===चक्र ===
-यदि आप अब तत्व 6 सम्मिलित करने का प्रयास करते हैं, तो आप  चक्र में पहुँच जाते हैं, और असफल हो जाते हैं। तालिका की अंतिम पंक्ति में हमें फिर से वही आरंभिक स्थिति मिलती है जो आरंभ में थी।
+यदि आप अब तत्व 6 सम्मिलित करने का प्रयास करते हैं, तो आप एक चक्र में पहुँच जाते हैं, और असफल हो जाते हैं। तालिका की अंतिम पंक्ति में हमें फिर से वही आरंभिक स्थिति मिलती है जो आरंभ में थी।
 <math>h\left(6\right)=6\bmod 11=6</math><br/>
@@ Line 199: / Line 199: @@
 ==भिन्नताएँ==
-कुक्कू  हैशिंग के कई रूपों का अध्ययन किया गया है, मुख्य रूप से लोड फैक्टर (कंप्यूटर विज्ञान) को बढ़ाकर इसके अंतरिक्ष उपयोग में सुधार लाने के उद्देश्य से, जिसे यह मूल कलन विधि की 50% सीमा से अधिक संख्या तक सहन कर सकता है। इनमें से कुछ विधियों का उपयोग कुक्कू हैशिंग की विफलता दर को कम करने के लिए भी किया जा सकता है, जिससे डेटा संरचना का पुनर्निर्माण बहुत कम होता है।
+कुक्कू हैशिंग के कई रूपों का अध्ययन किया गया है, मुख्य रूप से लोड फैक्टर को बढ़ाकर इसके स्थानीय उपयोग में सुधार लाने के उद्देश्य से, जिसे यह मूल एल्गोरिदम की 50% सीमा से अधिक संख्या तक सहन कर सकता है। इनमें से कुछ विधियों का उपयोग कुक्कू हैशिंग की विफलता दर को कम करने के लिए भी किया जा सकता है, जिससे डेटा संरचना का पुनर्निर्माण बहुत कम होता है।
-कुक्कू  हैशिंग के सामान्यीकरण जो दो से अधिक वैकल्पिक हैश फलनो  का उपयोग करते हैं, उनसे कुछ लुकअप और प्रविष्टि गति का त्याग करते हुए हैश तालिका की क्षमता के बड़े भाग का कुशलतापूर्वक उपयोग करने की उम्मीद की जा सकती है। मात्र तीन हैश फलनो का उपयोग करने से लोड 91% तक बढ़ जाता है।<ref name="mitzenmacher2009survey">{{cite journal | last=Mitzenmacher | first=Michael | author-link=Michael Mitzenmacher |title=कुक्कू हैशिंग से संबंधित कुछ खुले प्रश्न|journal=Proceedings of ESA 2009 | date=2009-09-09 |url=http://www.eecs.harvard.edu/~michaelm/postscripts/esa2009.pdf | access-date=2010-11-10 }}</ref>कुक्कू  हैशिंग का अन्य सामान्यीकरण, जिसे ब्लॉक्ड कुक्कू  हैशिंग कहा जाता है, में प्रति बकट से अधिक कुंजी का उपयोग करना सम्मिलित होता  है। प्रति बकट में  मात्र  2 कुंजियों का उपयोग करने से 80% से अधिक लोड फैक्टर की अनुमति मिलती है।<ref>{{cite journal
+कुक्कू हैशिंग के सामान्यीकरण जो दो से अधिक वैकल्पिक हैश फलनो का उपयोग करते हैं, उनसे कुछ लुकअप और प्रविष्टि गति का त्याग करते हुए हैश तालिका की क्षमता के बड़े भाग का कुशलतापूर्वक उपयोग करने की उम्मीद की जा सकती है। मात्र तीन हैश फलनो का उपयोग करने से लोड 91% तक बढ़ जाता है।<ref name="mitzenmacher2009survey">{{cite journal | last=Mitzenmacher | first=Michael | author-link=Michael Mitzenmacher |title=कुक्कू हैशिंग से संबंधित कुछ खुले प्रश्न|journal=Proceedings of ESA 2009 | date=2009-09-09 |url=http://www.eecs.harvard.edu/~michaelm/postscripts/esa2009.pdf | access-date=2010-11-10 }}</ref>कुक्कू हैशिंग का अन्य सामान्यीकरण, जिसे ब्लॉक्ड कुक्कू हैशिंग कहा जाता है, में प्रति बकट से अधिक कुंजी का उपयोग करना सम्मिलित होता है। प्रति बकट मात्र 2 कुंजियों का उपयोग करने से 80% से अधिक लोड फैक्टर की अनुमति मिलती है।<ref>{{cite journal
   | last1 = Dietzfelbinger | first1 = Martin
   | last2 = Weidling | first2 = Christoph
@@ Line 214: / Line 214: @@
   }}</ref>
-कुक्कू   हैशिंग की  और विविधता जिसका अध्ययन किया गया है, वह है स्टैश के साथ कुक्कू   हैशिंग। इस डेटा संरचना में स्टैश, कुंजियों की निरंतर संख्या की  सरणी होती है, जिसका उपयोग उन कुंजियों को संग्रहीत करने के लिए किया जाता है जिन्हें संरचना की मुख्य हैश तालिका में सफलतापूर्वक सम्मिलित नहीं किया जा सकता है। यह संशोधन  प्रतिपादक के साथ व्युत्क्रम-बहुपद फलन में कुक्कू  हैशिंग की विफलता दर को कम कर देता है जिसे स्टैश आकार को बढ़ाकर अनैतिक  विधि  से बड़ा किया जा सकता है। यघपि, बड़े मेमोरी का अर्थ उन कुंजियों की धीमा अन्वेषण भी होता है जो उपस्थित नहीं होता हैं या मेमोरी में उपस्थित होता हैं। उच्च लोड कारकों और छोटी विफलता दर दोनों को प्राप्त करने के लिए दो से अधिक हैश फलनो  के संयोजन में या अवरुद्ध कुक्कू   हैशिंग के साथ  स्टैश का उपयोग किया जा सकता है।<ref>{{cite journal
+कुक्कू हैशिंग की और विविधता जिसका अध्ययन किया गया है, वह है स्टैश के साथ कुक्कू हैशिंग। इस डेटा संरचना में स्टैश, कुंजियों की निरंतर संख्या की सरणी होती है, जिसका उपयोग उन कुंजियों को संग्रहीत करने के लिए किया जाता है जिन्हें संरचना की मुख्य हैश तालिका में सफलतापूर्वक सम्मिलित नहीं किया जा सकता है। यह संशोधन प्रतिपादक के साथ व्युत्क्रम-बहुपद फलन में कुक्कू हैशिंग की विफलता दर को कम कर देता है जिसे स्टैश आकृति को बढ़ाकर अनैतिक विधि से बड़ा किया जा सकता है। यघपि, बड़े मेमोरी का अर्थ उन कुंजियों की धीमा अन्वेषण भी है जो उपस्थित नहीं होता हैं या मेमोरी में उपस्थिति होता हैं। उच्च लोड कारकों और छोटी विफलता दर दोनों को प्राप्त करने के लिए दो से अधिक हैश फलनो के संयोजन में या अवरुद्ध कुक्कू हैशिंग के साथ स्टैश का उपयोग किया जा सकता है।<ref>{{cite journal
   | last1 = Kirsch | first1 = Adam
   | last2 = Mitzenmacher | first2 = Michael D.
@@ Line 225: / Line 225: @@
   | title = More robust hashing: cuckoo hashing with a stash
   | volume = 39
-  | year = 2010}}</ref> स्टैश के साथ कुक्कू   हैशिंग का विश्लेषण व्यावहारिक हैश फलनो  तक फैला हुआ है, न कि मात्र  हैशिंग के सैद्धांतिक विश्लेषण में आमतौर पर उपयोग किए जाने वाले यादृच्छिक हैश फलन मॉडल तक।<ref>{{cite journal
+  | year = 2010}}</ref> स्टैश के साथ कुक्कू हैशिंग का विश्लेषण व्यावहारिक हैश फलनो तक प्रसारित होता है, न कि मात्र हैशिंग के सैद्धांतिक विश्लेषण में सामान्यतः उपयोग किए जाने वाले यादृच्छिक हैश फलन मॉडल तक होता होता।<ref>{{cite journal
   | last1 = Aumüller | first1 = Martin
   | last2 = Dietzfelbinger | first2 = Martin
@@ Line 238: / Line 238: @@
   | year = 2014| arxiv = 1204.4431| s2cid = 1888828
   }}</ref>
-कुछ लोग कुक्कू हैशिंग के सरलीकृत सामान्यीकरण की अनुशंसा करते हैं जिसे कुछ [[सीपीयू कैश]] में सीपीयू कैश#टू-वे स्क्यूड एसोसिएटिव कैश|स्कूड-एसोसिएटिव कैश कहा जाता है।<ref>
+कुछ लोग कुक्कू हैशिंग के सरलीकृत सामान्यीकरण की अनुशंसा करते हैं जिसे कुछ [[सीपीयू कैश]] में स्कूड-एसोसिएटिव कैश कहा जाता है।<ref>
 [http://www.irisa.fr/caps/PROJECTS/Architecture/ "Micro-Architecture"].
 </ref>
-कुक्कू हैश तालिका का  और रूपांतर, जिसे [[कोयल फिल्टर|कुक्कू   फिल्टर]] कहा जाता है, कुक्कू हैश तालिका की संग्रहीत कुंजियों को बहुत छोटे उंगलियों के निशान से बदल देता है, जिसकी गणना कुंजियों पर  और हैश फलन लागू करके की जाती है। इन उंगलियों के निशानों को कुक्कू फिल्टर के भीतर चारों ओर ले जाने की अनुमति देने के लिए, बिना यह जाने कि वे किस कुंजी से आए हैं, प्रत्येक फिंगरप्रिंट के दो स्थानों की गणना  दूसरे से बिटवाइज़ [[एकमात्र]] फिंगरप्रिंट के साथ संचालन या हैश के साथ की जा सकती है। फिंगरप्रिंट का. यह डेटा संरचना ब्लूम फ़िल्टर के समान गुणों के साथ  अनुमानित समुच्चय सदस्यता डेटा संरचना बनाती है: यह कुंजी के समुच्चय के सदस्यों को संग्रहीत कर सकती है, और परीक्षण कर सकती है कि क्वेरी कुंजी सदस्य है या नहीं, झूठी सकारात्मकता की कुछ संभावना के साथ (प्रश्न जो समुच्चय का हिस्सा होने के रूप में गलत तरीके से रिपोर्ट किया गया है) लेकिन कोई गलत नकारात्मक जानकारी नहीं है। यघपि , यह कई मायनों में [[ब्लूम फिल्टर]] में सुधार करता है: इसकी मेमोरी का उपयोग  स्थिर कारक से छोटा होता है, इसमें संदर्भ का बेहतर स्थान होता है, और (ब्लूम फिल्टर के विपरीत) यह बिना किसी अतिरिक्त भंडारण दंड के समुच्चय तत्वों को तेजी से हटाने की अनुमति देता है।<ref>{{citation
+कुक्कू हैश तालिका का और रूपांतर, जिसे [[कोयल फिल्टर|कुक्कू निस्पंदन]] कहा जाता है, कुक्कू हैश तालिका की संग्रहीत कुंजियों को बहुत छोटे उंगलियों के निशान से बदल देता है, जिसकी गणना कुंजियों पर और हैश फलन प्रयुक्त करके की जाती है। इन उंगलियों के चन्हो को कुक्कू फिल्टर के अंदर चारों ओर ले जाने की अनुमति देने के लिए, बिना यह जाने कि वे किस कुंजी से आए हैं, प्रत्येक फिंगरप्रिंट के दो स्थानों की गणना दूसरे से बिटवाइज़ [[एकमात्र]] फिंगरप्रिंट के साथ संचालन या हैश के साथ की जा सकती है। फिंगरप्रिंट का यह डेटा संरचना ब्लूम निस्पंदन के समान गुणों के साथ अनुमानित समुच्चय सदस्यता डेटा संरचना बनाती है: यह कुंजी के समुच्चय के सदस्यों को संग्रहीत कर सकती है, और परीक्षण कर सकती है कि क्वेरी कुंजी सदस्य है या नहीं, असत्य धनात्मक की कुछ संभावना के साथ (प्रश्न जो समुच्चय का भाग होने के रूप में अनैतिक विधि से रिपोर्ट किया गया है) यघपि कोई गलत ऋणात्मक सूचना नहीं होती है। यघपि, यह कई विधियों में [[ब्लूम फिल्टर|ब्लूम निस्पंदन]] में सुधार करता है: इसकी मेमोरी का उपयोग स्थिर कारक से छोटा होता है, इसमें संदर्भ का उच्चतर स्थान होता है, और (ब्लूम निस्पंदन के विपरीत) यह बिना किसी अतिरिक्त मेमोरी दंड के समुच्चय तत्वों को शीघ्रता से हटाने की अनुमति देता है।<ref>{{citation
   | last1 = Fan | first1 = Bin
   | last2 = Andersen | first2 = Dave G.
@@ Line 253: / Line 255: @@
   }}</ref>
+== संबंधित संरचनाओं के साथ तुलना ==
+ज़ुकोव्स्की एट अल द्वारा एक अध्ययन में<ref>{{cite journal |last=Zukowski |first=Marcin |author2=Heman, Sandor |author3=Boncz, Peter |title=वास्तुकला-जागरूक हैशिंग|journal=Proceedings of the International Workshop on Data Management on New Hardware (DaMoN) |date=June 2006 |url=https://www.cs.cmu.edu/~damon2006/pdf/zukowski06archconscioushashing.pdf |access-date=2008-10-16}}</ref> दिखाया गया है कि आधुनिक प्रोसेसर पर छोटे, सीपीयू कैश-रेजिडेंट हैश टेबल के लिए कुक्कू हैशिंग चेन्ड हैशिंग की तुलना में बहुत श्रेष्ट होते है। केनेथ रॉस<ref>{{cite report |last=Ross |first=Kenneth |title=आधुनिक प्रोसेसर पर कुशल हैश जांच|publisher=IBM |type=Research Report |id=RC24100 |date=2006-11-08 |url=http://domino.research.ibm.com/library/cyberdig.nsf/papers/DF54E3545C82E8A585257222006FD9A2/$File/rc24100.pdf |access-date=2008-10-16}}</ref> कुक्कू हैशिंग के बकेटाइज्ड संस्करणों को (वैरिएंट जो से अधिक कुंजी वाली बकट का उपयोग करते हैं) बड़े हैश तालिकाओं के लिए पारंपरिक तरीकों की तुलना में श्रेष्ट दिखाया गया है, जब स्थान उपयोग अधिक होता है। बकेटाइज्ड कुक्कू हैश टेबल के प्रदर्शन की जांच एस्किटिस द्वारा की गई थी,<ref>{{Cite book |chapter=Fast and Compact Hash Tables for Integer Keys |first1=Nikolas |last1=Askitis |year=2009 |isbn=978-1-920682-72-9 |pages=113–122 |title=Proceedings of the 32nd Australasian Computer Science Conference (ACSC 2009) |url=http://crpit.com/confpapers/CRPITV91Askitis.pdf |volume=91 |access-date=2010-06-13 |archive-url=https://web.archive.org/web/20110216180225/http://crpit.com/confpapers/CRPITV91Askitis.pdf |archive-date=2011-02-16 |url-status=dead}}</ref> इसके प्रदर्शन की तुलना वैकल्पिक हैशिंग योजनाओं से की गई थी।
+[[माइकल मिटज़ेनमाचर]] का एक सर्वेक्षण<ref name="mitzenmacher2009survey" />2009 तक कुक्कू हैशिंग से संबंधित विवृत समस्याएं प्रस्तुत करता है।
-==संबंधित संरचनाओं के साथ तुलना==
-ज़ुकोव्स्की एट अल द्वारा  अध्ययन।<ref>{{cite journal |last=Zukowski |first=Marcin |author2=Heman, Sandor |author3=Boncz, Peter |title=वास्तुकला-जागरूक हैशिंग|journal=Proceedings of the International Workshop on Data Management on New Hardware (DaMoN) |date=June 2006 |url=https://www.cs.cmu.edu/~damon2006/pdf/zukowski06archconscioushashing.pdf |access-date=2008-10-16}}</ref> दिखाया गया है कि आधुनिक प्रोसेसर पर छोटे, सीपीयू कैश-रेजिडेंट हैश टेबल के लिए अलग चेनिंग की तुलना में कुक्कू   हैशिंग बहुत तेज है। केनेथ रॉस<ref>{{cite report |last=Ross |first=Kenneth |title=आधुनिक प्रोसेसर पर कुशल हैश जांच|publisher=IBM |type=Research Report |id=RC24100 |date=2006-11-08 |url=http://domino.research.ibm.com/library/cyberdig.nsf/papers/DF54E3545C82E8A585257222006FD9A2/$File/rc24100.pdf |access-date=2008-10-16}}</ref> कुक्कू हैशिंग के बकेटाइज्ड संस्करणों को दिखाया गया है (वैरिएंट जो  से अधिक कुंजी वाली बाल्टी का उपयोग करते हैं) बड़े हैश तालिकाओं के लिए पारंपरिक तरीकों की तुलना में तेज़ होते हैं, जब अंतरिक्ष उपयोग अधिक होता है। बकेटाइज्ड कुक्कू   हैश टेबल के प्रदर्शन की जांच एस्किटिस द्वारा की गई,<ref>{{Cite book |chapter=Fast and Compact Hash Tables for Integer Keys |first1=Nikolas |last1=Askitis |year=2009 |isbn=978-1-920682-72-9 |pages=113–122 |title=Proceedings of the 32nd Australasian Computer Science Conference (ACSC 2009) |url=http://crpit.com/confpapers/CRPITV91Askitis.pdf |volume=91 |access-date=2010-06-13 |archive-url=https://web.archive.org/web/20110216180225/http://crpit.com/confpapers/CRPITV91Askitis.pdf |archive-date=2011-02-16 |url-status=dead}}</ref>
-वैकल्पिक हैशिंग योजनाओं की तुलना में इसके प्रदर्शन के साथ।
-[[माइकल मिटज़ेनमाचर]] द्वारा  सर्वेक्षण<ref name="mitzenmacher2009survey" />2009 तक कुक्कू   हैशिंग से संबंधित खुली समस्याएं प्रस्तुत करता है।
 ==अनुप्रयोग==
-एम्बेडिंग टेबल टकराव की समस्या को हल करने के लिए [[ टिकटोक |टिकटोक]] की अनुशंसा प्रणाली में कूक्कू हैशिंग का उपयोग किया जाता है, जिसके परिणामस्वरूप मॉडल की गुणवत्ता कम हो सकती है।
+एम्बेडिंग टेबल टकराव (कोलिजन) की समस्या को हल करने के लिए [[ टिकटोक |टिकटोक]] की अनुशंसा प्रणाली में कूक्कू हैशिंग का उपयोग किया जाता है, जिसके परिणामस्वरूप मॉडल की गुणवत्ता कम हो सकती है।टिकटॉक अनुशंसा प्रणाली मोनोलिथ विभिन्न अवधारणाओं को एक ही सदिश में मानचित्र होने से रोकने के लिए कुक्कू हैशिंग के टकराव स्थिरता का लाभ उठाती है।<ref>{{Cite web |title=Monolith: The Recommendation System Behind TikTok |url=https://gantry.io/blog/papers-to-know-20230110/ |access-date=2023-05-30 |website=gantry.io |language=en}}</ref>
-टिकटॉक सिफ़ारिश प्रणाली मोनोलिथ विभिन्न अवधारणाओं को  ही वैक्टर में मैप होने से रोकने के लिए कुक्कू हैशिंग के टकराव रिज़ॉल्यूशन का लाभ उठाती है।<ref>{{Cite web |title=Monolith: The Recommendation System Behind TikTok |url=https://gantry.io/blog/papers-to-know-20230110/ |access-date=2023-05-30 |website=gantry.io |language=en}}</ref>
-==यह भी देखें==
+== यह भी देखें ==
 * उत्तम हैशिंग
 * [[डबल हैशिंग]]
@@ Line 289: / Line 286: @@
 *[https://github.com/efficient/libcuckoo समवर्ती उच्च-प्रदर्शन Cuckoo हैशटेबल C++ में लिखा गया है]
 * [http://sourceforge.net/projects/cuckoo-cpp/ कुक्कू हैश मैप C++ में लिखा गया है]
-* [http://www.theiling.de/projects/lookuptable.html C/C++ के लिए स्टेटिक कुक्कू   हैशटेबल जेनरेटर]
+* [http://www.theiling.de/projects/lookuptable.html C/C++ के लिए स्टेटिक कुक्कू  हैशटेबल जेनरेटर]
-* [http://hackage.haskell.org/packages/archive/hashtables/latest/doc/html/Data-HashTable-ST-Cuckoo.html कुक्कू   हैश तालिका हास्केल में लिखी गई है]
+* [http://hackage.haskell.org/packages/archive/hashtables/latest/doc/html/Data-HashTable-ST-Cuckoo.html कुक्कू  हैश तालिका हास्केल में लिखी गई है]
 * [https://github.com/salviati/cuckoo गो के लिए कुक्कू हैशिंग]

Anonymous

Search

कुक्कू हैशिंग: Difference between revisions

Namespaces

More

Page actions

Revision as of 11:43, 19 July 2023

Contents

इतिहास

संचालन

अन्वेषण

विलोपन

प्रविष्टि

सिद्धांत

अभ्यास

उदाहरण

चक्र

भिन्नताएँ

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

अनुप्रयोग

यह भी देखें

संदर्भ

बाहरी संबंध

उदाहरण

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

कुक्कू हैशिंग: Difference between revisions

Revision as of 11:43, 19 July 2023

इतिहास

संचालन

अन्वेषण

विलोपन

प्रविष्टि

सिद्धांत

अभ्यास

उदाहरण

चक्र

भिन्नताएँ

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

अनुप्रयोग

यह भी देखें

संदर्भ

बाहरी संबंध

उदाहरण

Navigation

Wiki tools

Page tools

Other projects

Hidden categories