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

Revision as of 14:42, 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 के साथ), नई वास्तु पुनः बाहर हो हो जाती है।]]'''कुक्कू हैशिंग''' [[कंप्यूटर प्रोग्रामिंग]] में एक [[हैश तालिका|हैश टेबल]] में [[हैश फंकशन|हैश फंक्शन]] के मूल्यों के हैश कलिसिओं (कोलिजन ) को हल करने के लिए योजना होती है, जिसमें सबसे व्यर्थ स्थिति में [[निरंतर समय]] लुकअप समय होता है। यह नाम [[कोयल|कुक्कू]] की कुछ प्रजातियों के व्यवहार से लिया जाता है, जहां कुक्कू का चूजा (बच्चा) अंडे सेते समय अन्य अंडों या बच्चों को घोंसले से बाहर प्रेरित कर देता है, इस व्यवहार में भिन्नता होती है जिसे ब्रूड परजीवीवाद कहा जाता है; समान रूप से, कुक्कू हैशिंग टेबल में नई कुंजी प्रयुक्त करने से पुरानी कुंजी को टेबल में किसी भिन्न स्थान पर प्रेरित किया जा सकता है।
 ==इतिहास==
@@ Line 6: / Line 6: @@
 ==संचालन==
-कुक्कू हैशिंग [[ खुला संबोधन |विवृत संबोधन]] का एक रूप होता है जिसमें हैश तालिका के प्रत्येक गैर-विवृत सेल में [[अद्वितीय कुंजी]] या कुंजी-मूल्य जोड़ी होती है। प्रत्येक कुंजी के लिए स्थान निर्धारित करने के लिए हैश फलन का उपयोग किया जाता है, और तालिका में इसकी उपस्थिति (या इसके साथ जुड़े मूल्य) को तालिका के उस सेल की जांच करके पाया जा सकता है। यघपि, ओपन एड्रेसिंग हैश टकराव से संबद्ध होते है, जो तब सेल में से अधिक कुंजी मानचित्र की जाती हैं। कुक्कू हैशिंग का मूल विचार मात्र के अतिरिक्त दो हैश फलन का उपयोग करके टकराव को हल करता है। यह प्रत्येक कुंजी के लिए हैश तालिका में दो संभावित स्थान प्रदान करता है। कलन विधि को सामान्यतः उपयोग किए जाने वाले वेरिएंट में से एक में, हैश तालिका को समान आकृति की दो छोटी तालिकाओं में विभाजित किया जाता है, और प्रत्येक हैश फलन इन दो तालिकाओं में से एक में अनुक्रमणिका प्रदान करता है। दोनों हैश फलनो के लिए ही तालिका में अनुक्रमणिका प्रदान करना भी संभव होता है।{{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"
@@ Line 20: / Line 20: @@
 ===विलोपन===
-विलोपन <math>O(1)</math> में किया जाता है चूंकि इसमें जांच में कोई सहकारिता नहीं होती है - यदि तालिका बहुत कम है तो दबाव संचाल के मूल्य पर विचार नहीं किया जाता है।{{r|Cuckoo|p=124-125}}
+विलोपन <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}} प्रक्रिया लूप में संभावित [[अनंत पुनरावृत्ति]] से बचने के लिए, a <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"
@@ Line 47: / Line 47: @@
 '''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> की इसमें कुक्कू हैशिंग के लिए पर्याप्त अन्य गुण उपस्थित होते है । 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-स्वतंत्र हैश फलनो से अधिक कुछ भी उपयोग करना संभव नहीं बनाता है।
+चूँकि सैद्धांतिक यादृच्छिक हैश फंक्शन को व्यावहारिक उपयोग के लिए बहुत अधिक स्थान की आवश्यकता होती है, महत्वपूर्ण सैद्धांतिक प्रश्न यह है कि कुक्कू हैशिंग के लिए कौन सा व्यावहारिक हैश फंक्शन पर्याप्त होता है। दृष्टिकोण 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-स्वतंत्र हैश फंक्शनो से अधिक कुछ भी उपयोग करना संभव नहीं बनाता है।
 ==अभ्यास==
@@ Line 60: / Line 60: @@
 ==उदाहरण==
-निम्नलिखित हैश फलन दिए गए हैं:
+निम्नलिखित हैश फंक्शन दिए गए हैं:
 <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 165: / Line 165: @@
 </div>
 ===चक्र ===
-यदि आप अब तत्व 6 सम्मिलित करने का प्रयास करते हैं, तो आप एक चक्र में पहुँच जाते हैं, और असफल हो जाते हैं। तालिका की अंतिम पंक्ति में हमें फिर से वही आरंभिक स्थिति मिलती है जो आरंभ में थी।
+यदि आप अब तत्व 6 सम्मिलित करने का प्रयास करते हैं, तो आप एक चक्र में पहुँच जाते हैं, और असफल हो जाते हैं। टेबल की अंतिम पंक्ति में हमें फिर से वही आरंभिक स्थिति मिलती है जो आरंभ में थी।
 <math>h\left(6\right)=6\bmod 11=6</math><br/>
@@ Line 201: / Line 201: @@
 कुक्कू हैशिंग के कई रूपों का अध्ययन किया गया है, मुख्य रूप से लोड फैक्टर को बढ़ाकर इसके स्थानीय उपयोग में सुधार लाने के उद्देश्य से, जिसे यह मूल एल्गोरिदम की 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 243: / Line 243: @@
 </ref>
-कुक्कू हैश तालिका का और रूपांतर, जिसे [[कोयल फिल्टर|कुक्कू निस्पंदन]] कहा जाता है, कुक्कू हैश तालिका की संग्रहीत कुंजियों को बहुत छोटे उंगलियों के निशान से बदल देता है, जिसकी गणना कुंजियों पर और हैश फलन प्रयुक्त करके की जाती है। इन उंगलियों के चन्हो को कुक्कू फिल्टर के अंदर चारों ओर ले जाने की अनुमति देने के लिए, बिना यह जाने कि वे किस कुंजी से आए हैं, प्रत्येक फिंगरप्रिंट के दो स्थानों की गणना दूसरे से बिटवाइज़ [[एकमात्र]] फिंगरप्रिंट के साथ संचालन या हैश के साथ की जा सकती है। फिंगरप्रिंट का यह डेटा संरचना ब्लूम निस्पंदन के समान गुणों के साथ अनुमानित समुच्चय सदस्यता डेटा संरचना बनाती है: यह कुंजी के समुच्चय के सदस्यों को संग्रहीत कर सकती है, और परीक्षण कर सकती है कि क्वेरी कुंजी सदस्य है या नहीं, असत्य धनात्मक की कुछ संभावना के साथ (प्रश्न जो समुच्चय का भाग होने के रूप में अनैतिक विधि से रिपोर्ट किया गया है) यघपि कोई गलत ऋणात्मक सूचना नहीं होती है। यघपि, यह कई विधियों में [[ब्लूम फिल्टर|ब्लूम निस्पंदन]] में सुधार करता है: इसकी मेमोरी का उपयोग स्थिर कारक से छोटा होता है, इसमें संदर्भ का उच्चतर स्थान होता है, और (ब्लूम निस्पंदन के विपरीत) यह बिना किसी अतिरिक्त मेमोरी दंड के समुच्चय तत्वों को शीघ्रता से हटाने की अनुमति देता है।<ref>{{citation
+कुक्कू हैश टेबल का और रूपांतर, जिसे [[कोयल फिल्टर|कुक्कू निस्पंदन]] कहा जाता है, कुक्कू हैश टेबल की संग्रहीत कुंजियों को बहुत छोटे उंगलियों के निशान से बदल देता है, जिसकी गणना कुंजियों पर और हैश फंक्शन प्रयुक्त करके की जाती है। इन उंगलियों के चन्हो को कुक्कू फिल्टर के अंदर चारों ओर ले जाने की अनुमति देने के लिए, बिना यह जाने कि वे किस कुंजी से आए हैं, प्रत्येक फिंगरप्रिंट के दो स्थानों की गणना दूसरे से बिटवाइज़ [[एकमात्र]] फिंगरप्रिंट के साथ संचालन या हैश के साथ की जा सकती है। फिंगरप्रिंट का यह डेटा संरचना ब्लूम निस्पंदन के समान गुणों के साथ अनुमानित समुच्चय सदस्यता डेटा संरचना बनाती है: यह कुंजी के समुच्चय के सदस्यों को संग्रहीत कर सकती है, और परीक्षण कर सकती है कि क्वेरी कुंजी सदस्य है या नहीं, असत्य धनात्मक की कुछ संभावना के साथ (प्रश्न जो समुच्चय का भाग होने के रूप में अनैतिक विधि से रिपोर्ट किया गया है) यघपि कोई गलत ऋणात्मक सूचना नहीं होती है। यघपि, यह कई विधियों में [[ब्लूम फिल्टर|ब्लूम निस्पंदन]] में सुधार करता है: इसकी मेमोरी का उपयोग स्थिर कारक से छोटा होता है, इसमें संदर्भ का उच्चतर स्थान होता है, और (ब्लूम निस्पंदन के विपरीत) यह बिना किसी अतिरिक्त मेमोरी दंड के समुच्चय तत्वों को शीघ्रता से हटाने की अनुमति देता है।<ref>{{citation
   | last1 = Fan | first1 = Bin
   | last2 = Andersen | first2 = Dave G.
@@ Line 256: / Line 256: @@
 == संबंधित संरचनाओं के साथ तुलना ==
-ज़ुकोव्स्की एट अल द्वारा एक अध्ययन में<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>{{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 287: / Line 287: @@
 * [http://sourceforge.net/projects/cuckoo-cpp/ कुक्कू हैश मैप 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 14:42, 19 July 2023

Contents

इतिहास

संचालन

अन्वेषण

विलोपन

प्रविष्टि

सिद्धांत

अभ्यास

उदाहरण

चक्र

भिन्नताएँ

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

अनुप्रयोग

यह भी देखें

संदर्भ

बाहरी संबंध

उदाहरण

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 14:42, 19 July 2023

इतिहास

संचालन

अन्वेषण

विलोपन

प्रविष्टि

सिद्धांत

अभ्यास

उदाहरण

चक्र

भिन्नताएँ

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

अनुप्रयोग

यह भी देखें

संदर्भ

बाहरी संबंध

उदाहरण

Navigation

Wiki tools

Page tools

Other projects

Hidden categories