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

कुक्कू हैशिंग उदाहरण. तीर प्रत्येक कुंजी का वैकल्पिक स्थान दिखाते हैं। A के स्थान में नया आइटम डाला जाएगा, A को उसके वैकल्पिक स्थान पर ले जाया जाएगा, जो वर्तमान में B द्वारा कब्जा कर लिया गया है, और B को उसके वैकल्पिक स्थान पर ले जाया जाएगा जो वर्तमान में खाली है। H के स्थान पर किसी नए आइटम का सम्मिलन सफल नहीं होगा: चूँकि H चक्र का हिस्सा है (W के साथ), नया आइटम फिर से बाहर हो जाएगा।

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

इतिहास

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

संचालन

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

अन्वेषण

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

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

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

विलोपन

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

सम्मिलन

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

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

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

सिद्धांत

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

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

अभ्यास

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

उदाहरण

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

$h\left(k\right)=k{\bmod {1}}1$
$h'\left(k\right)=\left\lfloor {\frac {k}{11}}\right\rfloor {\bmod {1}}1$ निम्नलिखित दो तालिकाएँ कुछ उदाहरण तत्वों का सम्मिलन दिखाती हैं। प्रत्येक कॉलम समय के साथ दो हैश तालिकाओं की स्थिति से मेल खाता है। प्रत्येक नए मान के लिए संभावित प्रविष्टि स्थानों पर प्रकाश डाला गया है।

1. table for h(k)

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

2. table for h′(k)

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

साइकिल

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

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

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

भिन्नताएँ

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

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

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

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

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

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

अनुप्रयोग

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

यह भी देखें

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

बाहरी संबंध

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

उदाहरण

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

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

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