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

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

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

इतिहास

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

संचालन

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

लुकअप

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

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

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

विलोपन

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

सम्मिलन

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

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

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

सिद्धांत

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

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

अभ्यास

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

उदाहरण

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

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

1. table for h(k)

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

2. table for h′(k)

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

साइकिल

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

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

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

भिन्नताएँ

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

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

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

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

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

अनुप्रयोग

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

यह भी देखें

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

बाहरी संबंध

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

उदाहरण

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

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

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