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

Revision as of 22:11, 18 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'''
 |}
@@ Line 24: / Line 24: @@
 ===सम्मिलन===
-एक नए नाम-मूल्य जोड़े को सम्मिलित करने के पहले चरण में यह जांचना शामिल है कि क्या स्लॉट है <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"
 |
-   '''function''' insert(x) '''is'''
+'''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'''
+'''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% से नीचे है।
-इसे साबित करने का एक तरीका [[यादृच्छिक ग्राफ]]़ के सिद्धांत का उपयोग करता है: कोई एक [[अप्रत्यक्ष ग्राफ]]़ बना सकता है जिसे कोयल ग्राफ़ कहा जाता है जिसमें प्रत्येक हैश तालिका स्थान के लिए एक शीर्ष होता है, और प्रत्येक हैशेड मान के लिए एक किनारा होता है, किनारे के अंतिम बिंदु दो संभावित होते हैं मूल्य के स्थान. फिर, कोयल हैश तालिका में मानों का एक सेट जोड़ने के लिए लालची सम्मिलन एल्गोरिथ्म सफल होता है यदि और केवल यदि मूल्यों के इस सेट के लिए कोयल ग्राफ एक [[छद्मवन]] है, तो इसके प्रत्येक जुड़े घटक में अधिकतम एक चक्र वाला एक ग्राफ (ग्राफ सिद्धांत) )एस। शीर्षों से अधिक किनारों वाला कोई भी शीर्ष-प्रेरित सबग्राफ कुंजियों के एक सेट से मेल खाता है जिसके लिए हैश तालिका में अपर्याप्त संख्या में स्लॉट हैं। जब हैश फ़ंक्शन को यादृच्छिक रूप से चुना जाता है, तो कोयल ग्राफ एर्दो-रेनी मॉडल में एक यादृच्छिक ग्राफ होता है। उच्च संभावना के साथ, 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> कोयल हैशिंग के लिए पर्याप्त अन्य गुण होना।
+चूँकि  सैद्धांतिक यादृच्छिक हैश फलन को व्यावहारिक उपयोग के लिए बहुत अधिक स्थान की आवश्यकता होती है,  महत्वपूर्ण सैद्धांतिक प्रश्न यह है कि कोयल हैशिंग के लिए कौन सा व्यावहारिक हैश फलन पर्याप्त है।  दृष्टिकोण 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-स्वतंत्र हैश फ़ंक्शंस से अधिक कुछ भी उपयोग करना संभव नहीं बनाता है।
 ==अभ्यास==
-व्यवहार में, कोयल हैशिंग [[रैखिक जांच]] की तुलना में लगभग 20-30% धीमी है, जो सामान्य तरीकों में सबसे तेज़ है।<ref name="Cuckoo"/>इसका कारण यह है कि कुक्कू हैशिंग अक्सर प्रति खोज दो कैश मिस का कारण बनती है, उन दो स्थानों की जांच करने के लिए जहां एक कुंजी संग्रहीत की जा सकती है, जबकि रैखिक जांच के कारण आमतौर पर प्रति खोज केवल एक कैश मिस होता है।
+व्यवहार में, कोयल हैशिंग [[रैखिक जांच]] की तुलना में लगभग 20-30% धीमी है, जो सामान्य तरीकों में सबसे तेज़ है।<ref name="Cuckoo"/>इसका कारण यह है कि कुक्कू हैशिंग अक्सर प्रति खोज दो कैश मिस का कारण बनती है, उन दो स्थानों की जांच करने के लिए जहां  कुंजी संग्रहीत की जा सकती है, जबकि रैखिक जांच के कारण आमतौर पर प्रति खोज केवल  कैश मिस होता है।
-हालाँकि, खोज समय पर इसकी सबसे खराब स्थिति की गारंटी के कारण, [[वास्तविक समय कंप्यूटिंग]] | वास्तविक समय प्रतिक्रिया दरों की आवश्यकता होने पर कोयल हैशिंग अभी भी मूल्यवान हो सकती है। कुक्कू हैशिंग का एक फायदा इसकी लिंक-लिस्ट मुक्त संपत्ति है, जो जीपीयू प्रोसेसिंग के लिए अच्छी तरह से फिट बैठती है।
+हालाँकि, खोज समय पर इसकी सबसे खराब स्थिति की गारंटी के कारण, [[वास्तविक समय कंप्यूटिंग]] | वास्तविक समय प्रतिक्रिया दरों की आवश्यकता होने पर कोयल हैशिंग अभी भी मूल्यवान हो सकती है। कुक्कू हैशिंग का  फायदा इसकी लिंक-लिस्ट मुक्त संपत्ति है, जो जीपीयू प्रोसेसिंग के लिए अच्छी तरह से फिट बैठती है।
 ==उदाहरण==
-निम्नलिखित हैश फ़ंक्शन दिए गए हैं:
+निम्नलिखित हैश फलन दिए गए हैं:
 <math>h\left(k\right)=k\bmod 11</math><br/>
@@ Line 165: / Line 165: @@
 |}
 </div>
-{{clear}}
 ===साइकिल===
-यदि आप अब तत्व 6 सम्मिलित करने का प्रयास करते हैं, तो आप एक चक्र में पहुँच जाते हैं, और असफल हो जाते हैं। तालिका की अंतिम पंक्ति में हमें फिर से वही आरंभिक स्थिति मिलती है जो आरंभ में थी।
+यदि आप अब तत्व 6 सम्मिलित करने का प्रयास करते हैं, तो आप  चक्र में पहुँच जाते हैं, और असफल हो जाते हैं। तालिका की अंतिम पंक्ति में हमें फिर से वही आरंभिक स्थिति मिलती है जो आरंभ में थी।
 <math>h\left(6\right)=6\bmod 11=6</math><br/>
@@ Line 204: / Line 202: @@
 कोयल हैशिंग के कई रूपों का अध्ययन किया गया है, मुख्य रूप से लोड फैक्टर (कंप्यूटर विज्ञान) को बढ़ाकर इसके अंतरिक्ष उपयोग में सुधार लाने के उद्देश्य से, जिसे यह मूल एल्गोरिदम की 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>
+कोयल हैशिंग के सामान्यीकरण जो दो से अधिक वैकल्पिक हैश फ़ंक्शंस का उपयोग करते हैं, उनसे कुछ लुकअप और प्रविष्टि गति का त्याग करते हुए हैश तालिका की क्षमता के  बड़े हिस्से का कुशलतापूर्वक उपयोग करने की उम्मीद की जा सकती है। केवल तीन हैश फ़ंक्शंस का उपयोग करने से लोड 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
+कोयल हैशिंग का  अन्य सामान्यीकरण, जिसे ब्लॉक्ड कोयल हैशिंग कहा जाता है, में प्रति बाल्टी  से अधिक कुंजी का उपयोग करना शामिल है। प्रति बाल्टी केवल 2 कुंजियों का उपयोग करने से 80% से अधिक लोड फैक्टर की अनुमति मिलती है।<ref>{{cite journal
   | last1 = Dietzfelbinger | first1 = Martin
   | last2 = Weidling | first2 = Christoph
@@ Line 217: / Line 215: @@
   | year = 2007| doi-access = free
   }}</ref>
-कोयल हैशिंग की एक और विविधता जिसका अध्ययन किया गया है, वह है स्टैश के साथ कोयल हैशिंग। इस डेटा संरचना में स्टैश, कुंजियों की निरंतर संख्या की एक सरणी है, जिसका उपयोग उन कुंजियों को संग्रहीत करने के लिए किया जाता है जिन्हें संरचना की मुख्य हैश तालिका में सफलतापूर्वक सम्मिलित नहीं किया जा सकता है। यह संशोधन एक प्रतिपादक के साथ व्युत्क्रम-बहुपद फ़ंक्शन में कोयल हैशिंग की विफलता दर को कम कर देता है जिसे स्टैश आकार को बढ़ाकर मनमाने ढंग से बड़ा किया जा सकता है। हालाँकि, बड़े भंडार का मतलब उन चाबियों की धीमी खोज भी है जो मौजूद नहीं हैं या भंडार में हैं। उच्च लोड कारकों और छोटी विफलता दर दोनों को प्राप्त करने के लिए दो से अधिक हैश फ़ंक्शंस के संयोजन में या अवरुद्ध कोयल हैशिंग के साथ एक स्टैश का उपयोग किया जा सकता है।<ref>{{cite journal
+कोयल हैशिंग की  और विविधता जिसका अध्ययन किया गया है, वह है स्टैश के साथ कोयल हैशिंग। इस डेटा संरचना में स्टैश, कुंजियों की निरंतर संख्या की  सरणी है, जिसका उपयोग उन कुंजियों को संग्रहीत करने के लिए किया जाता है जिन्हें संरचना की मुख्य हैश तालिका में सफलतापूर्वक सम्मिलित नहीं किया जा सकता है। यह संशोधन  प्रतिपादक के साथ व्युत्क्रम-बहुपद फलन में कोयल हैशिंग की विफलता दर को कम कर देता है जिसे स्टैश आकार को बढ़ाकर मनमाने ढंग से बड़ा किया जा सकता है। हालाँकि, बड़े भंडार का मतलब उन चाबियों की धीमी खोज भी है जो मौजूद नहीं हैं या भंडार में हैं। उच्च लोड कारकों और छोटी विफलता दर दोनों को प्राप्त करने के लिए दो से अधिक हैश फ़ंक्शंस के संयोजन में या अवरुद्ध कोयल हैशिंग के साथ  स्टैश का उपयोग किया जा सकता है।<ref>{{cite journal
   | last1 = Kirsch | first1 = Adam
   | last2 = Mitzenmacher | first2 = Michael D.
@@ Line 228: / Line 226: @@
   | 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 244: / Line 242: @@
 [http://www.irisa.fr/caps/PROJECTS/Architecture/ "Micro-Architecture"].
 </ref>
-कुक्कू हैश तालिका का एक और रूपांतर, जिसे [[कोयल फिल्टर]] कहा जाता है, कुक्कू हैश तालिका की संग्रहीत कुंजियों को बहुत छोटे उंगलियों के निशान से बदल देता है, जिसकी गणना कुंजियों पर एक और हैश फ़ंक्शन लागू करके की जाती है। इन उंगलियों के निशानों को कुक्कू फिल्टर के भीतर चारों ओर ले जाने की अनुमति देने के लिए, बिना यह जाने कि वे किस कुंजी से आए हैं, प्रत्येक फिंगरप्रिंट के दो स्थानों की गणना एक दूसरे से बिटवाइज़ [[एकमात्र]] फिंगरप्रिंट के साथ ऑपरेशन या हैश के साथ की जा सकती है। फिंगरप्रिंट का. यह डेटा संरचना ब्लूम फ़िल्टर के समान गुणों के साथ एक अनुमानित सेट सदस्यता डेटा संरचना बनाती है: यह कुंजी के सेट के सदस्यों को संग्रहीत कर सकती है, और परीक्षण कर सकती है कि क्वेरी कुंजी सदस्य है या नहीं, झूठी सकारात्मकता की कुछ संभावना के साथ (प्रश्न जो सेट का हिस्सा होने के रूप में गलत तरीके से रिपोर्ट किया गया है) लेकिन कोई गलत नकारात्मक जानकारी नहीं है। हालाँकि, यह कई मायनों में [[ब्लूम फिल्टर]] में सुधार करता है: इसकी मेमोरी का उपयोग एक स्थिर कारक से छोटा होता है, इसमें संदर्भ का बेहतर स्थान होता है, और (ब्लूम फिल्टर के विपरीत) यह बिना किसी अतिरिक्त भंडारण दंड के सेट तत्वों को तेजी से हटाने की अनुमति देता है।<ref>{{citation
+कुक्कू हैश तालिका का  और रूपांतर, जिसे [[कोयल फिल्टर]] कहा जाता है, कुक्कू हैश तालिका की संग्रहीत कुंजियों को बहुत छोटे उंगलियों के निशान से बदल देता है, जिसकी गणना कुंजियों पर  और हैश फलन लागू करके की जाती है। इन उंगलियों के निशानों को कुक्कू फिल्टर के भीतर चारों ओर ले जाने की अनुमति देने के लिए, बिना यह जाने कि वे किस कुंजी से आए हैं, प्रत्येक फिंगरप्रिंट के दो स्थानों की गणना  दूसरे से बिटवाइज़ [[एकमात्र]] फिंगरप्रिंट के साथ ऑपरेशन या हैश के साथ की जा सकती है। फिंगरप्रिंट का. यह डेटा संरचना ब्लूम फ़िल्टर के समान गुणों के साथ  अनुमानित सेट सदस्यता डेटा संरचना बनाती है: यह कुंजी के सेट के सदस्यों को संग्रहीत कर सकती है, और परीक्षण कर सकती है कि क्वेरी कुंजी सदस्य है या नहीं, झूठी सकारात्मकता की कुछ संभावना के साथ (प्रश्न जो सेट का हिस्सा होने के रूप में गलत तरीके से रिपोर्ट किया गया है) लेकिन कोई गलत नकारात्मक जानकारी नहीं है। हालाँकि, यह कई मायनों में [[ब्लूम फिल्टर]] में सुधार करता है: इसकी मेमोरी का उपयोग  स्थिर कारक से छोटा होता है, इसमें संदर्भ का बेहतर स्थान होता है, और (ब्लूम फिल्टर के विपरीत) यह बिना किसी अतिरिक्त भंडारण दंड के सेट तत्वों को तेजी से हटाने की अनुमति देता है।<ref>{{citation
   | last1 = Fan | first1 = Bin
   | last2 = Andersen | first2 = Dave G.
@@ Line 258: / 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 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>

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 22:11, 18 July 2023

Contents

इतिहास

संचालन

लुकअप

विलोपन

सम्मिलन

सिद्धांत

अभ्यास

उदाहरण

साइकिल

भिन्नताएँ

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

अनुप्रयोग

यह भी देखें

संदर्भ

बाहरी संबंध

उदाहरण

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 22:11, 18 July 2023

इतिहास

संचालन

लुकअप

विलोपन

सम्मिलन

सिद्धांत

अभ्यास

उदाहरण

साइकिल

भिन्नताएँ

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

अनुप्रयोग

यह भी देखें

संदर्भ

बाहरी संबंध

उदाहरण

Navigation

Wiki tools

Page tools

Other projects

Hidden categories