हैश टेबल

Hash table
Hash table
Type	Unordered associative array
Invented	1953
Time complexity in big O notation
Algorithm
Algorithm	Average
Space	Θ(n)
Search	Θ(1)
Insert	Θ(1)
Delete	Θ(1)

हैश तालिका के रूप में एक छोटी फोन बुक

कम्प्यूटिंग में, एक हैश तालिका, जिसे हैश मानचित्र के रूप में भी जाना जाता है, एक डेटा संरचना है जो एक साहचर्य सरणी या शब्दकोश को अनुप्रयुक्त करती है। यह एक सार डेटा प्रकार है जो अद्वितीय कुंजी टू मान (कंप्यूटर साइंस) को मानचित्र करता है।^[2] एक हैश तालिका एक इंडेक्स की गणना करने के लिए एक हैश फंकशन का उपयोग करता है, जिसे हैश कोड भी कहा जाता है, बकेट या खाँच की एक सरणी में, जिससे वांछित मान पाया जा सकता है। लुकअप के पर्यंत, कुंजी को हैश किया जाता है और परिणामी हैश इंगित करता है कि संबंधित मान कहाँ संग्रहीत है।

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

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

इतिहास

द्रुतान्वेषण का विचार अलग-अलग जगहों पर स्वतंत्र रूप से उभरा। जनवरी 1953 में, उनका पीटर लुहान ने एक आंतरिक आईबीएम मेमोरेंडम लिखा, जिसमें द्रुतान्वेषण के साथ चेनिंग का उपयोग किया गया था। लुहान के पेपर पर बाद में ए डी लिन्ह बिल्डिंग द्वारा विवृत पताभिगमन प्रस्तावित किया गया था।^[7]^: 15 लगभग उसी समय, आईबीएम रिसर्च के जीन अमदहल, ऐलेन एम. मैकग्रा, नथानिएल रोचेस्टर (कंप्यूटर वैज्ञानिक), और आर्थर सैमुअल (कंप्यूटर वैज्ञानिक) ने आईबीएम 701 असेंबली_लैंग्वेज#असेंबलर के लिए द्रुतान्वेषण अनुप्रयुक्त किया।^[8]^: 124 रैखिक जांच के साथ खुले संबोधन का श्रेय अमदहल को दिया जाता है, हालांकि एंड्री एर्शोव का स्वतंत्र रूप से एक ही विचार था।^[8]^{: 124–125} विवृत पताभिगमन शब्द डब्ल्यू वेस्ले पीटरसन द्वारा अपने लेख पर गढ़ा गया था जो बड़ी फाइलों में खोज की समस्या पर चर्चा करता है।^[7]^: 15 चेनिंग के साथ द्रुतान्वेषण पर पहला अकादमिक_प्रकाशन कार्य का श्रेय अर्नोल्ड डूमी को दिया जाता है, जिन्होंने शेष मॉड्यूल को हैश फ़ंक्शन के रूप में उपयोग करने के विचार पर चर्चा की।^[7]^: 15 द्रुतान्वेषण शब्द सबसे पहले रॉबर्ट मॉरिस के एक लेख द्वारा प्रकाशित किया गया था।^[8]^: 126 रैखिक जांच का एक विश्लेषण_ऑफ_कलन विधि मूल रूप से कोनहेम और वीस द्वारा प्रस्तुत किया गया था।^[7]^: 15

सिंहावलोकन

एक साहचर्य सरणी (कुंजी, मान) जोड़े के एक सेट_ (सार_डेटा_टाइप) को संग्रहीत करता है और अद्वितीय कुंजियों की बाधा के साथ सम्मिलन, विलोपन और लुकअप (खोज) की अनुमति देता है। साहचर्य सरणियों के हैश तालिका कार्यान्वयन में, एक सरणी $A$ लंबाई का $m$ आंशिक रूप से भरा हुआ है $n$ तत्व, जहां $m\geq n$ . एक कीमत $x$ एक अनुक्रमणिका स्थान पर संग्रहीत हो जाता है $A[h(x)]$ , कहाँ $h$ एक हैश फ़ंक्शन है, और $h(x)<m$ .^[7]^: 2 उचित धारणाओं के तहत, हैश तालिका में स्व-संतुलन बाइनरी सर्च ट्री की तुलना में खोज, डिलीट और इंसर्ट संचालन पर बेहतर समय जटिलता होती है।^[7]^: 1 प्रत्येक कुंजी के लिए संग्रहीत मान को छोड़कर और कुंजी मौजूद है या नहीं, यह ट्रैक करके सामान्यतः हैश तालिका का उपयोग सेट को अनुप्रयुक्त करने के लिए किया जाता है।^[7]^: 1

लोड फैक्टर

एक भार कारक $\alpha$ हैश तालिका का एक महत्वपूर्ण आंकड़ा है, और इसे निम्नानुसार परिभाषित किया गया है:^[1]

{\text{load factor}}\ (\alpha )={\frac {n}{k}},

कहाँ

$n$ हैश तालिका में दर्ज प्रविष्टियों की संख्या है।
$k$ बकेटो की संख्या है।

लोड फैक्टर के संबंध में हैश तालिका का प्रदर्शन बिगड़ जाता है $\alpha$ .^[7]^: 2 इसलिए लोड कारक होने पर हैश तालिका का आकार बदल दिया जाता है या फिर से किया जाता है $\alpha$ दृष्टिकोण 1.^[9]यदि लोड कारक नीचे चला जाता है तो तालिका का आकार भी बदल दिया जाता है $\alpha _{\max }/4$ .^[9] लोड फैक्टर के स्वीकार्य आंकड़े $\alpha$ लगभग 0.6 से 0.75 के बीच होना चाहिए।^[10]^[11]^: 110

हैश फ़ंक्शन

एक हैश समारोह $h$ ब्रह्मांड को मानचित्र करता है $U$ चाबियों का $h:U\rightarrow \{0,...,m-1\}$ प्रत्येक के लिए तालिका के भीतर अनुक्रमणिका या खाँच को व्यवस्थित करने के लिए $h(x)\in {0,...,m-1}$ कहाँ $x\in S$ और $m<n$ . हैश फ़ंक्शंस के पारंपरिक कार्यान्वयन पूर्णांक ब्रह्मांड धारणा पर आधारित हैं कि तालिका के सभी तत्व ब्रह्मांड से उत्पन्न होते हैं $U=\{0,...,u-1\}$ , जहां की बिट लंबाई $u$ कंप्यूटर आर्किटेक्चर के वर्ड (कंप्यूटर आर्किटेक्चर) के भीतर ही सीमित है।^[7]^: 2 एक आदर्श हैश फ़ंक्शन $h$ एक इंजेक्शन समारोह के रूप में परिभाषित किया गया है जैसे कि प्रत्येक तत्व $x$ में $S$ में एक अद्वितीय मूल्य के लिए मानचित्र ${0,...,m-1}$ .^[12]^[13] यदि सभी कुंजियों को समय से पहले जाना जाता है तो एक संपूर्ण हैश फ़ंक्शन बनाया जा सकता है।^[12]

पूर्णांक ब्रह्मांड धारणा

पूर्णांक ब्रह्मांड धारणा में उपयोग की जाने वाली द्रुतान्वेषण की योजनाओं में विभाजन द्वारा द्रुतान्वेषण, गुणन द्वारा द्रुतान्वेषण, सार्वभौमिक द्रुतान्वेषण, गतिशील सही द्रुतान्वेषण और स्टेटिक द्रुतान्वेषण सम्मिलित हैं।^[7]^: 2 हालाँकि, विभाजन द्वारा द्रुतान्वेषण सामान्यतः उपयोग की जाने वाली योजना है।^[14]^: 264^[11]^: 110

विभाजन द्वारा द्रुतान्वेषण

विभाजन द्वारा द्रुतान्वेषण में योजना इस प्रकार है:^[7]^: 2

h(x)\ =\ M\,{\bmod {\,}}n

कहाँ

M

का हैश डाइजेस्ट है

x\in S

और

n

तालिका का आकार है।

गुणन द्वारा द्रुतान्वेषण

गुणन द्वारा द्रुतान्वेषण में योजना इस प्रकार है:^[7]^: 2–3

h(k)=\lfloor n{\bigl (}(MA){\bmod {1}}{\bigr )}\rfloor

कहाँ

A

एक Real_number|वास्तविक-मूल्यवान स्थिरांक है। गुणन द्वारा द्रुतान्वेषण का एक फायदा यह है कि

m

आलोचनात्मक नहीं है।^[7]^: 2–3 हालांकि कोई मूल्य

A

एक हैश फ़ंक्शन उत्पन्न करता है, डोनाल्ड नुथ सुनहरे अनुपात का उपयोग करने का सुझाव देता है।^[7]^: 3

हैश फ़ंक्शन चुनना

हैश मानों का समान वितरण (असतत) हैश फ़ंक्शन की मूलभूत आवश्यकता है। एक असमान वितरण से टक्करों की संख्या और उन्हें हल करने की लागत बढ़ जाती है। डिजाइन द्वारा एकरूपता सुनिश्चित करना कभी-कभी मुश्किल होता है, लेकिन सांख्यिकीय परीक्षणों का उपयोग करके अनुभवजन्य रूप से मूल्यांकन किया जा सकता है, उदाहरण के लिए, पियर्सन का ची-स्क्वेर्ड परीक्षण # असतत वर्दी वितरण | पियर्सन का ची-स्क्वायर असतत समान वितरण के लिए परीक्षण।^[15]^[16] वितरण केवल अनुप्रयोग में होने वाले तालिका आकारों के लिए समान होना चाहिए। विशेष रूप से, यदि कोई डायनेमिक रीसाइज़िंग का उपयोग तालिका आकार के सटीक दोहरीकरण और आधा करने के साथ करता है, तो हैश फ़ंक्शन को केवल तभी एकसमान होना चाहिए जब आकार दो की शक्ति हो। यहां इंडेक्स की गणना हैश फ़ंक्शन के कुछ बिट्स के रूप में की जा सकती है। दूसरी ओर, कुछ द्रुतान्वेषण कलन विधि पसंद करते हैं कि आकार एक अभाज्य संख्या हो।^[17] विवृत पताभिगमन योजनाओं के लिए, हैश फ़ंक्शन को क्लस्टरिंग से भी बचना चाहिए, लगातार खाँच्स के लिए दो या दो से अधिक कुंजियों की मानचित्रिंग। इस तरह के क्लस्टरिंग से लुकअप की लागत आसमान छू सकती है, भले ही लोड फैक्टर कम हो और टक्कर कम हो। लोकप्रिय गुणात्मक हैश का विशेष रूप से खराब क्लस्टरिंग व्यवहार होने का दावा किया जाता है।^[17]^[4] के-स्वतंत्र द्रुतान्वेषण एक निश्चित हैश फ़ंक्शन को साबित करने का एक तरीका प्रदान करता है जिसमें किसी दिए गए प्रकार के हैशतालिका के लिए खराब कीसेट नहीं हैं। कई के-स्वतंत्रता परिणाम टकराव समाधान योजनाओं जैसे रैखिक जांच और कोयल द्रुतान्वेषण के लिए जाने जाते हैं। चूंकि के-स्वतंत्रता एक हैश फ़ंक्शन काम करता है, यह साबित कर सकता है कि कोई भी इस तरह के सबसे तेज़ संभव हैश फ़ंक्शन को खोजने पर ध्यान केंद्रित कर सकता है।^[18]

टक्कर संकल्प

द्रुतान्वेषण का उपयोग करने वाले खोज कलन विधि में दो भाग होते हैं। पहला भाग एक हैश फ़ंक्शन की गणना कर रहा है जो खोज कुंजी को सरणी अनुक्रमणिका में बदल देता है। आदर्श मामला ऐसा है कि कोई भी दो खोज कुंजी एक ही सरणी अनुक्रमणिका में नहीं है। हालांकि, यह हमेशा मामला नहीं होता है और अनदेखी दिए गए डेटा के लिए गारंटी देना असंभव है।^[19]^: 515 इसलिए एल्गोरिथम का दूसरा भाग टक्कर समाधान है। टक्कर समाधान के दो सामान्य तरीके अलग-अलग चेनिंग और विवृत पताभिगमन हैं।^[6]^: 458

अलग श्रृंखलन

हैश टक्कर अलग चेनिंग द्वारा हल की गई

बकेट ऐरे में हेड रिकॉर्ड के साथ अलग चेनिंग द्वारा हैश टक्कर।

अलग-अलग श्रृंखलन में, प्रक्रिया में प्रत्येक खोज सरणी अनुक्रमणिका के लिए की-मान जोड़ी के साथ एक लिंक की गई सूची बनाना सम्मिलित है। टकराई हुई वस्तुओं को एक ही लिंक की गई सूची के माध्यम से एक साथ जंजीर में बांधा जाता है, जिसे एक अद्वितीय खोज कुंजी के साथ आइटम तक पहुंचने के लिए ट्रेस किया जा सकता है।^[6]^: 464 लिंक की गई सूची के साथ चेनिंग के माध्यम से टकराव का समाधान हैश तालिका के कार्यान्वयन का एक सामान्य तरीका है। होने देना $T$ और $x$ हैश तालिका और नोड क्रमशः हो, संचालन में निम्नानुसार सम्मिलित है:^[14]^: 258

जंजीर-हैश-डालें (टी, के)

यदि तत्व तुलनीय है या तो अनुक्रम # विश्लेषण या लेक्सिकोग्राफिक अनुक्रम, और कुल अनुक्रम बनाए रखने के द्वारा सूची में डाला गया है, तो इसका परिणाम असफल खोजों की तेजी से समाप्ति में होता है।^[19]^{: 520–521}

अलग श्रंखला के लिए अन्य डेटा संरचनाएं

यदि कुंजियाँ कुल क्रम में हैं, तो यह इष्टतम बाइनरी सर्च ट्री का उपयोग करने के लिए कुशल हो सकता है | स्व-संगठित अवधारणाएँ जैसे कि स्व-संतुलन बाइनरी सर्च ट्री का उपयोग करना, जिसके माध्यम से वर्स्ट-केस जटिलता को नीचे लाया जा सकता है $O(\log {n})$ , हालांकि यह अतिरिक्त जटिलताओं का परिचय देता है।^[19]^: 521 डायनेमिक परफेक्ट द्रुतान्वेषण में, गारंटीकृत होने के लिए लुक-अप जटिलता को कम करने के लिए दो-स्तरीय हैश तालिका का उपयोग किया जाता है $O(1)$ सबसे खराब स्थिति में। इस तकनीक में, की बाल्टियाँ $k$ प्रविष्टियों को परफेक्ट हैश फंक्शन के साथ व्यवस्थित किया जाता है $k^{2}$ लगातार सबसे खराब स्थिति वाले लुकअप समय और प्रविष्टि के लिए कम परिशोधित समय प्रदान करने वाले खाँच।^[20] एक अध्ययन भारी भार के तहत मानक लिंक्ड सूची पद्धति की तुलना में सरणी आधारित अलग-अलग श्रंखला को 97% अधिक प्रदर्शन करने वाला दिखाता है।^[21]^: 99 प्रत्येक बकेटो के लिए फ्यूजन ट्री का उपयोग करने जैसी तकनीकों के परिणामस्वरूप उच्च संभावना वाले सभी कार्यों के लिए निरंतर समय मिलता है।^[22]

कैशिंग और संदर्भ का इलाका

अलग-अलग चेनिंग कार्यान्वयन की लिंक्ड सूची कैश-बेखबर कलन विधि नहीं हो सकती है। स्थानिक इलाके के कारण कैश-सचेत - संदर्भ की स्थानीयता - जब लिंक की गई सूची के नोड्स स्मृति में बिखरे हुए हैं, इस प्रकार डालने और खोज के पर्यंत सूची ट्रैवर्सल में सीपीयू सम्मिलित हो सकता है कैश अक्षमताओं।^[21]^: 91 कैश-बेपरवाह कलन विधि|कैश-सचेत वेरिएंट में, एक गतिशील सरणी जो अधिक सीपीयू कैश पाई जाती है|कैश-फ्रेंडली का उपयोग उस स्थान पर किया जाता है जहां एक लिंक्ड लिस्ट या सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री को सामान्यतः अलग-अलग चेनिंग के माध्यम से टक्कर समाधान के लिए तैनात किया जाता है, मेमोरी प्रबंधन (ऑपरेटिंग सिस्टम) के बाद से # सरणी के एकल सन्निहित आवंटन पैटर्न का उपयोग कैश प्रीफेचिंग | हार्डवेयर-कैश प्रीफ़ेचर्स द्वारा किया जा सकता है - जैसे अनुवाद लुकसाइड बफर - जिसके परिणामस्वरूप एक्सेस समय और मेमोरी की खपत कम हो जाती है।^[23]^[24]^[25]

विवृत पताभिगमन

हैश टक्कर रैखिक जांच (अंतराल = 1) के साथ खुले पते से हल हो गई। ध्यान दें कि टेड बेकर के पास एक अद्वितीय हैश है, लेकिन फिर भी सैंड्रा डी से टकराया, जो पहले जॉन स्मिथ से टकराया था।

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

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

प्रसिद्ध जांच अनुक्रमों में सम्मिलित हैं:

रेखीय जांच, जिसमें जांच के बीच का अंतराल निश्चित होता है (सामान्यतः 1)।^[27]
द्विघात जांच, जिसमें मूल हैश संगणना द्वारा दिए गए मान में द्विघात बहुपद के क्रमिक आउटपुट को जोड़कर जांच के बीच के अंतराल को बढ़ाया जाता है।^[28]^: 272
डबल द्रुतान्वेषण, जिसमें जांच के बीच अंतराल की गणना द्वितीयक हैश फ़ंक्शन द्वारा की जाती है।^[28]^{: 272–273}

अलग-अलग चेनिंग की तुलना में विवृत पताभिगमन का प्रदर्शन धीमा हो सकता है क्योंकि लोड फैक्टर होने पर जांच अनुक्रम बढ़ जाता है $\alpha$ दृष्टिकोण 1.^[9]^[21]^: 93 पूरी तरह से भरी हुई तालिका के स्थिति में, यदि लोड कारक 1 तक पहुंच जाता है, तो जांच का परिणाम अनंत लूप में होता है।^[6]^: 471 रैखिक जांच की औसत-स्थिति की जटिलता क्लस्टर विश्लेषण से बचने के लिए तत्वों के संभाव्यता वितरण के लिए हैश फ़ंक्शन की क्षमता पर निरंतर समान वितरण पर निर्भर करती है, क्योंकि क्लस्टर के गठन से खोज समय में वृद्धि होगी।^[6]^: 472

कैशिंग और संदर्भ का इलाका

चूंकि खाँच लगातार स्थानों में स्थित हैं, रैखिक जांच से सीपीयू कैश का बेहतर उपयोग हो सकता है क्योंकि संदर्भों की स्थानीयता कम स्मृति विलंबता के कारण होती है।^[27]

विवृत पताभिगमन पर आधारित अन्य टक्कर समाधान तकनीक

एकत्रित द्रुतान्वेषण

कोलेस्ड द्रुतान्वेषण अलग-अलग चेनिंग और विवृत पताभिगमन दोनों का एक हाइब्रिड है जिसमें बकेट या नोड्स तालिका के भीतर लिंक होते हैं।^[29]^: 6–8 कलन विधि आदर्श रूप से मेमोरी पूल के लिए उपयुक्त है।^[29]^: 4 कोलेस्ड द्रुतान्वेषण में टकराव को हैश तालिका पर सबसे बड़े अनुक्रमित खाली खाँच की पहचान करके हल किया जाता है, फिर उस खाँच में टकराने का मान डाला जाता है। बकेट सम्मिलित किए गए नोड के खाँच से भी जुड़ा हुआ है जिसमें इसका टकराने वाला हैश पता होता है।^[29]^: 8

कोयल द्रुतान्वेषण

कोयल द्रुतान्वेषण विवृत पताभिगमन कोलिशन रेजोल्यूशन तकनीक का एक रूप है जो गारंटी देता है $O(1)$ सबसे खराब स्थिति लुकअप जटिलता और सम्मिलन के लिए निरंतर परिशोधित समय। टकराव को दो हैश तालिका बनाए रखने के माध्यम से हल किया जाता है, प्रत्येक का अपना द्रुतान्वेषण फ़ंक्शन होता है, और टकराए गए खाँच को दिए गए आइटम के साथ बदल दिया जाता है, और खाँच का व्यस्त तत्व अन्य हैश तालिका में विस्थापित हो जाता है। यह प्रक्रिया तब तक जारी रहती है जब तक कि तालिकाओं की खाली बकेटो में प्रत्येक कुंजी का अपना स्थान नहीं हो जाता; यदि प्रक्रिया अनंत लूप में प्रवेश करती है - जिसे थ्रेशोल्ड लूप काउंटर को बनाए रखने के माध्यम से पहचाना जाता है - दोनों हैश तालिकाएँ नए हैश फ़ंक्शंस के साथ फिर से मिलती हैं और प्रक्रिया जारी रहती है।^[30]^{: 124–125}

हॉपस्कॉच द्रुतान्वेषण

हॉपस्कॉच द्रुतान्वेषण एक विवृत पताभिगमन आधारित कलन विधि है जो कोयल द्रुतान्वेषण, रैखिक जांच और चेनिंग के तत्वों को बकेटो के एक पड़ोस की धारणा के माध्यम से जोड़ती है - किसी भी कब्जे वाली बकेट के आसपास की बाल्टियाँ, जिसे एक आभासी बकेट भी कहा जाता है।^[31]^{: 351–352} कलन विधि को बेहतर प्रदर्शन देने के लिए डिज़ाइन किया गया है जब हैश तालिका का लोड फैक्टर 90% से अधिक हो जाता है; यह समवर्ती अभिकलन में उच्च थ्रूपुट भी प्रदान करता है, इस प्रकार आकार बदलने योग्य समवर्ती हैश तालिका को अनुप्रयुक्त करने के लिए उपयुक्त है।^[31]^: 350 हॉप्सकॉच द्रुतान्वेषण की पड़ोस विशेषता एक संपत्ति की गारंटी देती है कि, पड़ोस के भीतर किसी भी बकेट से वांछित वस्तु को खोजने की लागत बकेट में ही इसे खोजने की लागत के बहुत करीब है; एल्गोरिथम अपने पड़ोस में एक वस्तु बनने का प्रयास करता है - अन्य वस्तुओं को विस्थापित करने में सम्मिलित संभावित लागत के साथ।^[31]^: 352 हैश तालिका के भीतर प्रत्येक बकेट में एक अतिरिक्त हॉप-सूचना सम्मिलित है - यूक्लिडियन दूरी को इंगित करने के लिए एच-बिट बिट सरणी # आइटम का एक आयाम जो मूल रूप से एच -1 प्रविष्टियों के भीतर वर्तमान वर्चुअल बकेट में हैश किया गया था।^[31]^: 352 होने देना $k$ और $Bk$ सम्मिलित की जाने वाली कुंजी और बकेट जिसमें कुंजी को क्रमशः हैश किया जाता है; सम्मिलन प्रक्रिया में कई स्थिति सम्मिलित हैं जैसे कि कलन विधि की पड़ोस संपत्ति की प्रतिज्ञा की जाती है:^[31]^{: 352–353} यदि $Bk$ खाली है, तत्व डाला गया है, और बिटमानचित्र का सबसे बाईं ओर बिटवाइज़ संचालन 1 है; यदि खाली नहीं है, तो तालिका में एक खाली खाँच खोजने के लिए रैखिक जांच का उपयोग किया जाता है, बकेट का बिटमानचित्र सम्मिलन के बाद अद्यतन हो जाता है; यदि खाली खाँच पड़ोस की सीमा के भीतर नहीं है, अर्थात H-1, बाद में प्रत्येक बकेट की स्वैप और हॉप-इन्फो बिट सरणी में हेरफेर उसके पड़ोस के इनवेरिएंट (गणित) के अनुसार किया जाता है।^[31]^: 353

रॉबिन हुड द्रुतान्वेषण

रॉबिन हुड द्रुतान्वेषण एक विवृत पताभिगमन आधारित कोलिज़न रेज़ोल्यूशन एल्गोरिथम है; टक्करों को उस तत्व के विस्थापन के पक्ष में करके हल किया जाता है जो सबसे दूर है—या सबसे लंबी जांच अनुक्रम लंबाई (PSL)—उसके गृह स्थान से अर्थात वह बकेट जिसमें आइटम को हैश किया गया था।^[32]^: 12 हालांकि रॉबिन हुड द्रुतान्वेषण कम्प्यूटेशनल जटिलता सिद्धांत को नहीं बदलता है, लेकिन यह बकेटो पर वस्तुओं के संभाव्यता वितरण के विचरण को महत्वपूर्ण रूप से प्रभावित करता है,^[33]^: 2 अर्थात हैश तालिका में क्लस्टर एनालिसिस फॉर्मेशन से निपटना।^[34] रॉबिन हुड द्रुतान्वेषण का उपयोग करने वाली हैश तालिका के भीतर प्रत्येक नोड को एक अतिरिक्त पीएसएल मान संग्रहीत करने के लिए संवर्धित किया जाना चाहिए।^[35] होने देना $x$ डालने की कुंजी हो, $x.psl$ की (वृद्धिशील) PSL लंबाई हो $x$ , $T$ हैश तालिका हो और $j$ सूचकांक हो, सम्मिलन प्रक्रिया इस प्रकार है:^[32]^: 12–13^[36]^: 5

यदि $x.psl\ \leq \ T[j].psl$ : बाहरी जांच का प्रयास किए बिना पुनरावृति अगली बकेट में चली जाती है।
यदि $x.psl\ >\ T[j].psl$ : आइटम डालें $x$ बकेट में $j$ ; बदलना $x$ साथ $T[j]$ -जाने भी दो $x'$ ; से जांच जारी रखें $j+1$ सेंट बकेट डालने के लिए $x'$ ; प्रक्रिया को तब तक दोहराएं जब तक कि प्रत्येक तत्व सम्मिलित न हो जाए।

गतिशील आकार बदलना

बार-बार सम्मिलन के कारण हैश तालिका में प्रविष्टियों की संख्या बढ़ जाती है, जिसके परिणामस्वरूप लोड कारक बढ़ जाता है; परिशोधित बनाए रखने के लिए $O(1)$ लुकअप और सम्मिलन संचालन का प्रदर्शन, एक हैश तालिका को गतिशील रूप से आकार दिया जाता है और तालिकाओं की वस्तुओं को नई हैश तालिका की बकेटो में फिर से डाला जाता है,^[9]चूंकि मॉड्यूल संचालन के कारण अलग-अलग हैश मान में अलग-अलग तालिका आकार के परिणामस्वरूप आइटम कॉपी नहीं किए जा सकते हैं।^[37] यदि कुछ तत्वों को हटाने के बाद हैश तालिका बहुत खाली हो जाती है, तो अत्यधिक स्मृति पदचिह्न से बचने के लिए आकार बदला जा सकता है।^[38]

सभी प्रविष्टियों को स्थानांतरित करके आकार बदलना

सामान्यतः, मूल हैश तालिका के आकार के दोगुने आकार वाली एक नई हैश तालिका को गतिशील मेमोरी आवंटन निजी रूप से प्राप्त होता है और मूल हैश तालिका में प्रत्येक आइटम सम्मिलन संचालन के बाद आइटमों के हैश मानों की गणना करके नए आवंटित में ले जाया जाता है। इसकी सरलता के बावजूद रीद्रुतान्वेषण कम्प्यूटेशनल रूप से महंगा है।^[39]^{: 478–479}

=== ऑल-एट-वन्स रीद्रुतान्वेषण === के विकल्प

कुछ हैश तालिका कार्यान्वयन, विशेष रूप से वास्तविक समय प्रणाली में, हैश तालिका को एक साथ बड़ा करने की कीमत का भुगतान नहीं कर सकते हैं, क्योंकि यह समय-महत्वपूर्ण संचालन को बाधित कर सकता है। यदि कोई डायनेमिक रीसाइज़िंग से बच नहीं सकता है, तो स्टोरेज ब्लिप से बचने के लिए धीरे-धीरे रीसाइज़िंग करना एक समाधान है - सामान्यतः नए तालिका के आकार के 50% पर - रीद्रुतान्वेषण के पर्यंत और फ्रैग्मेंटेशन (अभिकलन) से बचने के लिए जो बड़े पेज के डीलोकेशन के कारण मार्क-कॉम्पैक्ट कलन विधि को ट्रिगर करता है। (कंप्यूटर मेमोरी) पुराने हैश तालिका के कारण होता है।^[40]^: 2–3 ऐसे स्थिति में, पुराने हैश तालिका के लिए आवंटित पूर्व मेमोरी खंड को विस्तारित करके रीद्रुतान्वेषण संचालन वृद्धिशील रूप से किया जाता है, जैसे कि हैश तालिका की बकेट अपरिवर्तित रहती है। परिशोधित पुनर्वसन के लिए एक सामान्य दृष्टिकोण में दो हैश कार्यों को बनाए रखना सम्मिलित है $h_{\text{old}}$ और $h_{\text{new}}$ . नए हैश फंक्शन के अनुसार बकेट के आइटम्स को फिर से हैश करने की प्रक्रिया को क्लीनिंग कहा जाता है, जिसे कमांड पैटर्न के माध्यम से क्रियान्वित किया जाता है जैसे कि संचालन को एनकैप्सुलेट करके $\mathrm {Add} (\mathrm {key} )$ , $\mathrm {Get} (\mathrm {key} )$ और $\mathrm {Delete} (\mathrm {key} )$ किसी के जरिए $\mathrm {Lookup} (\mathrm {key} ,{\text{command}})$ आवरण समारोह जैसे कि बकेट में प्रत्येक तत्व को फिर से मिलाया जाता है और इसकी प्रक्रिया में निम्नानुसार सम्मिलित होता है:^[40]^: 3

साफ़ $\mathrm {Table} [h_{\text{old}}(\mathrm {key} )]$ बकेट।
साफ़ $\mathrm {Table} [h_{\text{new}}(\mathrm {key} )]$ बकेट।
कमांड निष्पादित हो जाती है।

रेखीय द्रुतान्वेषण

रैखिक द्रुतान्वेषण हैश तालिका का एक कार्यान्वयन है जो एक समय में एक बकेट तालिका के गतिशील विकास या सिकुड़न को सक्षम करता है।^[41]

प्रदर्शन

एक हैश तालिका का प्रदर्शन कम-विसंगति अनुक्रम उत्पन्न करने में हैश फ़ंक्शन की क्षमता पर निर्भर है। अर्ध-यादृच्छिक संख्या ( $\sigma$ ) हैश तालिका में प्रविष्टियों के लिए जहां $K$ , $n$ और $h(x)$ कुंजी, बकेटो की संख्या और हैश फ़ंक्शन को इस तरह दर्शाता है $\sigma \ =\ h(K)\ \%\ n$ . यदि हैश फ़ंक्शन समान उत्पन्न करता है $\sigma$ विशिष्ट कुंजियों के लिए ( $K_{1}\neq K_{2},\ h(K_{1})\ =\ h(K_{2})$ ), इसके परिणामस्वरूप टकराव होता है, जिसे विभिन्न तरीकों से निपटाया जाता है। निरंतर समय जटिलता ( $O(1)$ ) हैश तालिका में संचालन का अनुमान इस शर्त पर लगाया जाता है कि हैश फ़ंक्शन टकराने वाले सूचकांक उत्पन्न नहीं करता है; इस प्रकार, हैश तालिका का प्रदर्शन आनुपातिकता (गणित) है#चुने गए हैश फ़ंक्शन की सूचकांकों को सांख्यिकीय फैलाव की क्षमता के लिए प्रत्यक्ष आनुपातिकता।^[42]^: 1 हालांकि, ऐसे हैश फ़ंक्शन का निर्माण एनपी-कठोरता है, ऐसा होने पर, कार्यान्वयन उच्च प्रदर्शन प्राप्त करने में केस-विशिष्ट #Collision रिज़ॉल्यूशन के उपयोग पर निर्भर करता है।^[42]^: 2

अनुप्रयोग

साहचर्य सरणियाँ

हैश तालिका का उपयोग सामान्यतः कई प्रकार की इन-मेमोरी तालिका को अनुप्रयुक्त करने के लिए किया जाता है। उनका उपयोग साहचर्य सरणियों को अनुप्रयुक्त करने के लिए किया जाता है।^[28]

डाटाबेस इंडेक्सिंग

हैश तालिका का उपयोग डिस्क ड्राइव-आधारित डेटा संरचनाओं और सूचकांक (डेटाबेस) (जैसे डीबीएम (अभिकलन) में) के रूप में भी किया जा सकता है, हालांकि इन अनुप्रयोगों में बी-ट्री अधिक लोकप्रिय हैं।^[43]

कैश

हैश तालिका का उपयोग कैश (अभिकलन) को अनुप्रयुक्त करने के लिए किया जा सकता है, सहायक डेटा तालिका जिनका उपयोग मुख्य रूप से धीमे मीडिया में संग्रहीत डेटा तक पहुंच को गति देने के लिए किया जाता है। इस एप्लिकेशन में, दो टकराने वाली प्रविष्टियों में से एक को हटाकर हैश टकराव को नियंत्रित किया जा सकता है - सामान्यतः पुराने आइटम को मिटा दिया जाता है जो वर्तमान में तालिका में संग्रहीत होता है और इसे नए आइटम के साथ अधिलेखित कर देता है, इसलिए तालिका में प्रत्येक आइटम का एक अद्वितीय हैश मान होता है।^[44]^[45]

समूह

सेट डेटा संरचना के कार्यान्वयन में हैश तालिका का उपयोग किया जा सकता है, जो बिना किसी विशेष क्रम के अद्वितीय मानों को संग्रहीत कर सकता है; सेट का उपयोग सामान्यतः तत्व पुनर्प्राप्ति के बजाय संग्रह में मूल्य की सदस्यता का परीक्षण करने के लिए किया जाता है।^[46]

ट्रांसपोजिशन तालिका

एक जटिल हैश तालिका के लिए एक स्थानान्तरण तालिका जो खोजे गए प्रत्येक अनुभाग के बारे में जानकारी संग्रहीत करती है।^[47]

कार्यान्वयन

कई प्रोग्रामिंग लैंग्वेज हैश तालिका की कार्यक्षमता प्रदान करती हैं, या तो अंतर्निहित साहचर्य सरणियों के रूप में या मानक लाइब्रेरी मॉड्यूल के रूप में।

जावास्क्रिप्ट में, 7 आदिम डेटा प्रकारों को छोड़कर प्रत्येक मान को एक ऑब्जेक्ट कहा जाता है, जो हैश मानचित्र के लिए कुंजी के रूप में पूर्णांक, स्ट्रिंग्स, या गारंटीकृत-अद्वितीय प्रतीक आदिम मानों का उपयोग करता है। ईसीएमएस्क्रिप्ट 6 भी जोड़ा गया Map और Set डेटा संरचनाएं।^[48] सी ++ 11 सम्मिलित हैं unordered_map Template_(C%2B%2B).^[49] Go_(programming_language) का बिल्ट-इन map एक हैश तालिका को प्रिमिटिव_डेटा_टाइप के रूप में अनुप्रयुक्त करता है।^[50] जावा (प्रोग्रामिंग भाषा) प्रोग्रामिंग लैंग्वेज में सम्मिलित है HashSet, HashMap, LinkedHashSet, और LinkedHashMap जावा संग्रह में जेनरिक।^[51] पायथन (प्रोग्रामिंग लैंग्वेज) का बिल्ट-इन dict एक हैश तालिका को प्रिमिटिव_डेटा_टाइप के रूप में अनुप्रयुक्त करता है।^[52] रूबी (प्रोग्रामिंग भाषा) की बिल्ट-इन Hash रूबी 2.4 के बाद से विवृत पताभिगमन मॉडल का उपयोग करता है।^[53] जंग (प्रोग्रामिंग भाषा) प्रोग्रामिंग लैंग्वेज में सम्मिलित है HashMap, HashSet रस्ट स्टैंडर्ड लाइब्रेरी के हिस्से के रूप में। ^[54]

यह भी देखें

संदर्भ

↑ ^1.0 ^1.1 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms (3rd ed.). Massachusetts Institute of Technology. pp. 253–280. ISBN 978-0-262-03384-8.
↑ Mehlhorn, Kurt; Sanders, Peter (2008), "4 Hash Tables and Associative Arrays", Algorithms and Data Structures: The Basic Toolbox (PDF), Springer, pp. 81–98
↑ Charles E. Leiserson, Amortized Algorithms, Table Doubling, Potential Method Archived August 7, 2009, at the Wayback Machine Lecture 13, course MIT 6.046J/18.410J Introduction to Algorithms—Fall 2005
↑ ^4.0 ^4.1 Knuth, Donald (1998). The Art of Computer Programming. Vol. 3: Sorting and Searching (2nd ed.). Addison-Wesley. pp. 513–558. ISBN 978-0-201-89685-5.
↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Chapter 11: Hash Tables". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 221–252. ISBN 978-0-262-53196-2.
↑ ^6.0 ^6.1 ^6.2 ^6.3 ^6.4 Sedgewick, Robert; Wayne, Kevin (2011). एल्गोरिदम. Vol. 1 (4 ed.). Addison-Wesley Professional – via Princeton University, Department of Computer Science.
↑ ^7.00 ^7.01 ^7.02 ^7.03 ^7.04 ^7.05 ^7.06 ^7.07 ^7.08 ^7.09 ^7.10 ^7.11 ^7.12 ^7.13 Mehta, Dinesh P.; Sahni, Sartaj (October 28, 2004). "9: Hash Tables". Handbook of Datastructures and Applications (1 ed.). Taylor & Francis. doi:10.1201/9781420035179. ISBN 978-1-58488-435-4.
↑ ^8.0 ^8.1 ^8.2 Konheim, Alan G. (June 21, 2010). Hashing in Computer Science: Fifty Years of Slicing and Dicing. John Wiley & Sons, Inc. doi:10.1002/9780470630617. ISBN 9780470630617.
↑ ^9.0 ^9.1 ^9.2 ^9.3 Mayers, Andrew (2008). "CS 312: Hash tables and amortized analysis". Cornell University, Department of Computer Science. Archived from the original on April 26, 2021. Retrieved October 26, 2021 – via cs.cornell.edu.
↑ Maurer, W.D.; Lewis, T.G. (March 1, 1975). "Hash Table Methods". ACM Computing Surveys. Journal of the ACM. 1 (1): 14. doi:10.1145/356643.356645. S2CID 17874775.
↑ ^11.0 ^11.1 Owolabi, Olumide (February 1, 2003). "Empirical studies of some hashing functions". Information and Software Technology. Department of Mathematics and Computer Science, University of Port Harcourt. 45 (2): 109–112. doi:10.1016/S0950-5849(02)00174-X – via ScienceDirect.
↑ ^12.0 ^12.1 Lu, Yi; Prabhakar, Balaji; Bonomi, Flavio (2006), "Perfect Hashing for Network Applications", 2006 IEEE International Symposium on Information Theory: 2774–2778, doi:10.1109/ISIT.2006.261567, ISBN 1-4244-0505-X, S2CID 1494710
↑ Belazzougui, Djamal; Botelho, Fabiano C.; Dietzfelbinger, Martin (2009), "Hash, displace, and compress" (PDF), Algorithms—ESA 2009: 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009, Proceedings (PDF), Lecture Notes in Computer Science, vol. 5757, Berlin: Springer, pp. 682–693, CiteSeerX 10.1.1.568.130, doi:10.1007/978-3-642-04128-0_61, MR 2557794
↑ ^14.0 ^14.1 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Chapter 11: Hash Tables". Introduction to Algorithms (2nd ed.). Massachusetts Institute of Technology. ISBN 978-0-262-53196-2.
↑ Pearson, Karl (1900). "On the criterion that a given system of deviations from the probable in the case of a correlated system of variables is such that it can be reasonably supposed to have arisen from random sampling". Philosophical Magazine. Series 5. 50 (302): 157–175. doi:10.1080/14786440009463897.
↑ Plackett, Robin (1983). "Karl Pearson and the Chi-Squared Test". International Statistical Review. 51 (1): 59–72. doi:10.2307/1402731. JSTOR 1402731.
↑ ^17.0 ^17.1 Wang, Thomas (March 1997). "Prime Double Hash Table". Archived from the original on September 3, 1999. Retrieved May 10, 2015.
↑ Wegman, Mark N.; Carter, J. Lawrence (1981). "New hash functions and their use in authentication and set equality" (PDF). Journal of Computer and System Sciences. 22 (3): 265–279. doi:10.1016/0022-0000(81)90033-7. Conference version in FOCS'79. Retrieved February 9, 2011.
↑ ^19.0 ^19.1 ^19.2 Donald E. Knuth (April 24, 1998). The Art of Computer Programming: Volume 3: Sorting and Searching. Addison-Wesley Professional. ISBN 978-0-201-89685-5.
↑ Erik Demaine, Jeff Lind. 6.897: Advanced Data Structures. MIT Computer Science and Artificial Intelligence Laboratory. Spring 2003. "Archived copy" (PDF). Archived (PDF) from the original on June 15, 2010. Retrieved June 30, 2008.{{cite web}}: CS1 maint: archived copy as title (link)
↑ ^21.0 ^21.1 ^21.2 Askitis, Nikolas; Zobel, Justin (2005). "Cache-Conscious Collision Resolution in String Hash Tables". International Symposium on String Processing and Information Retrieval. Springer Science+Business Media: 91–102. doi:10.1007/11575832_1. ISBN 978-3-540-29740-6.
↑ Willard, Dan E. (2000). "Examining computational geometry, van Emde Boas trees, and hashing from the perspective of the fusion tree". SIAM Journal on Computing. 29 (3): 1030–1049. doi:10.1137/S0097539797322425. MR 1740562..
↑ Askitis, Nikolas; Sinha, Ranjan (2010). "Engineering scalable, cache and space efficient tries for strings". The VLDB Journal. 17 (5): 634. doi:10.1007/s00778-010-0183-9. ISSN 1066-8888. S2CID 432572.
↑ Askitis, Nikolas; Zobel, Justin (October 2005). Cache-conscious Collision Resolution in String Hash Tables. pp. 91–102. doi:10.1007/11575832_11. ISBN 978-3-540-29740-6. {{cite book}}: |journal= ignored (help)
↑ Askitis, Nikolas (2009). Fast and Compact Hash Tables for Integer Keys (PDF). pp. 113–122. ISBN 978-1-920682-72-9. Archived from the original (PDF) on February 16, 2011. Retrieved June 13, 2010. {{cite book}}: |journal= ignored (help)
↑ Tenenbaum, Aaron M.; Langsam, Yedidyah; Augenstein, Moshe J. (1990). Data Structures Using C. Prentice Hall. pp. 456–461, p. 472. ISBN 978-0-13-199746-2.
↑ ^27.0 ^27.1 Pagh, Rasmus; Rodler, Flemming Friche (2001). "Cuckoo Hashing". Algorithms — ESA 2001. Lecture Notes in Computer Science. Vol. 2161. pp. 121–133. CiteSeerX 10.1.1.25.4189. doi:10.1007/3-540-44676-1_10. ISBN 978-3-540-42493-2.
↑ ^28.0 ^28.1 ^28.2 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "11 Hash Tables", Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, pp. 221–252, ISBN 0-262-03293-7.
↑ ^29.0 ^29.1 ^29.2 Vitter, Jeffery S.; Chen, Wen-Chin (1987). The design and analysis of coalesced hashing. New York, United States: Oxford University Press. ISBN 978-0-19-504182-8 – via Archive.org.
↑ 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.
↑ ^31.0 ^31.1 ^31.2 ^31.3 ^31.4 ^31.5 Herlihy, Maurice; Shavit, Nir; Tzafrir, Moran (2008). "Hopscotch Hashing". International Symposium on Distributed Computing. Distributed Computing. Berlin, Heidelberg: Springer Publishing. 5218: 350–364. doi:10.1007/978-3-540-87779-0_24. ISBN 978-3-540-87778-3 – via Springer Link.
↑ ^32.0 ^32.1 Celis, Pedro (1986). Robin Hood Hashing (PDF). Ontario, Canada: University of Waterloo, Dept. of Computer Science. ISBN 031529700X. OCLC 14083698. Archived (PDF) from the original on November 1, 2021. Retrieved November 2, 2021.
↑ Poblete, P.V.; Viola, A. (August 14, 2018). "Analysis of Robin Hood and Other Hashing Algorithms Under the Random Probing Model, With and Without Deletions". Combinatorics, Probability and Computing. Cambridge University Press. 28 (4): 600–617. doi:10.1017/S0963548318000408. ISSN 1469-2163. S2CID 125374363. Retrieved November 1, 2021 – via Cambridge Core.
↑ Clarkson, Michael (2014). "Lecture 13: Hash tables". Cornell University, Department of Computer Science. Archived from the original on October 7, 2021. Retrieved November 1, 2021 – via cs.cornell.edu.
↑ Gries, David (2017). "JavaHyperText and Data Structure: Robin Hood Hashing" (PDF). Cornell University, Department of Computer Science. Archived (PDF) from the original on April 26, 2021. Retrieved November 2, 2021 – via cs.cornell.edu.
↑ Celis, Pedro (March 28, 1988). External Robin Hood Hashing (PDF) (Technical report). Bloomington, Indiana: Indiana University, Department of Computer Science. 246. Archived (PDF) from the original on November 2, 2021. Retrieved November 2, 2021. {{cite tech report}}: |archive-date= / |archive-url= timestamp mismatch (help)
↑ Goddard, Wayne (2021). "Chater C5: Hash Tables" (PDF). Clemson University. pp. 15–16. Archived (PDF) from the original on November 9, 2021. Retrieved November 9, 2021 – via people.cs.clemson.edu.
↑ Devadas, Srini; Demaine, Erik (February 25, 2011). "Intro to Algorithms: Resizing Hash Tables" (PDF). Massachusetts Institute of Technology, Department of Computer Science. Archived (PDF) from the original on May 7, 2021. Retrieved November 9, 2021 – via MIT OpenCourseWare.
↑ Thareja, Reema (October 13, 2018). "Hashing and Collision". Data Structures Using C (2 ed.). Oxford University Press. ISBN 9780198099307.
↑ ^40.0 ^40.1 Friedman, Scott; Krishnan, Anand; Leidefrost, Nicholas (March 18, 2003). "Hash Tables for Embedded and Real-time systems" (PDF). All Computer Science and Engineering Research. Washington University in St. Louis. doi:10.7936/K7WD3XXV. Archived (PDF) from the original on June 9, 2021. Retrieved November 9, 2021 – via Northwestern University, Department of Computer Science.
↑ Litwin, Witold (1980). "Linear hashing: A new tool for file and table addressing" (PDF). Proc. 6th Conference on Very Large Databases. Carnegie Mellon University. pp. 212–223. Archived (PDF) from the original on May 6, 2021. Retrieved November 10, 2021 – via cs.cmu.edu.
↑ ^42.0 ^42.1 Dijk, Tom Van (2010). "Analysing and Improving Hash Table Performance" (PDF). Netherlands: University of Twente. Archived (PDF) from the original on November 6, 2021. Retrieved December 31, 2021.
↑ Lech Banachowski. "Indexes and external sorting". pl:Polsko-Japońska Akademia Technik Komputerowych. Archived from the original on March 26, 2022. Retrieved March 26, 2022.
↑ Zhong, Liang; Zheng, Xueqian; Liu, Yong; Wang, Mengting; Cao, Yang (February 2020). "Cache hit ratio maximization in device-to-device communications overlaying cellular networks". China Communications. 17 (2): 232–238. doi:10.23919/jcc.2020.02.018. ISSN 1673-5447. S2CID 212649328.
↑ Bottommley, James (January 1, 2004). "Understanding Caching". Linux Journal. Archived from the original on December 4, 2020. Retrieved April 16, 2022.
↑ Jill Seaman (2014). "Set & Hash Tables" (PDF). Texas State University. Archived from the original on April 1, 2022. Retrieved March 26, 2022.{{cite web}}: CS1 maint: bot: original URL status unknown (link)
↑ "Transposition Table - Chessprogramming wiki". chessprogramming.org. Archived from the original on February 14, 2021. Retrieved May 1, 2020.
↑ "JavaScript data types and data structures - JavaScript | MDN". developer.mozilla.org. Retrieved July 24, 2022.
↑ "Programming language C++ - Technical Specification" (PDF). International Organization for Standardization. pp. 812–813. Archived from the original (PDF) on January 21, 2022. Retrieved February 8, 2022.
↑ "The Go Programming Language Specification". go.dev. Retrieved January 1, 2023.{{cite web}}: CS1 maint: url-status (link)
↑ "Lesson: Implementations (The Java™ Tutorials > Collections)". docs.oracle.com. Archived from the original on January 18, 2017. Retrieved April 27, 2018.
↑ Zhang, Juan; Jia, Yunwei (2020). "Redis rehash optimization based on machine learning". Journal of Physics: Conference Series. 1453 (1): 3. Bibcode:2020JPhCS1453a2048Z. doi:10.1088/1742-6596/1453/1/012048. S2CID 215943738.
↑ Jonan Scheffler (December 25, 2016). "Ruby 2.4 Released: Faster Hashes, Unified Integers and Better Rounding". heroku.com. Archived from the original on July 3, 2019. Retrieved July 3, 2019.
↑ "doc.rust-lang.org". Archived from the original on December 8, 2022. Retrieved December 14, 2022. test

अग्रिम पठन

Tamassia, Roberto; Goodrich, Michael T. (2006). "Chapter Nine: Maps and Dictionaries". Data structures and algorithms in Java : [updated for Java 5.0] (4th ed.). Hoboken, NJ: Wiley. pp. 369–418. ISBN 978-0-471-73884-8.
McKenzie, B. J.; Harries, R.; Bell, T. (February 1990). "Selecting a hashing algorithm". Software: Practice and Experience. 20 (2): 209–224. doi:10.1002/spe.4380200207. hdl:10092/9691. S2CID 12854386.

बाहरी संबंध

NIST entry on hash tables
Open Data Structures – Chapter 5 – Hash Tables, Pat Morin
MIT's Introduction to Algorithms: Hashing 1 MIT OCW lecture Video
MIT's Introduction to Algorithms: Hashing 2 MIT OCW lecture Video

[Cormen_et_al-1] 1.0 ^1.1 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms (3rd ed.). Massachusetts Institute of Technology. pp. 253–280. ISBN 978-0-262-03384-8.

[ms-2] Mehlhorn, Kurt; Sanders, Peter (2008), "4 Hash Tables and Associative Arrays", Algorithms and Data Structures: The Basic Toolbox (PDF), Springer, pp. 81–98

[leiser-3] Charles E. Leiserson, Amortized Algorithms, Table Doubling, Potential Method Archived August 7, 2009, at the Wayback Machine Lecture 13, course MIT 6.046J/18.410J Introduction to Algorithms—Fall 2005

[knuth-4] 4.0 ^4.1 Knuth, Donald (1998). The Art of Computer Programming. Vol. 3: Sorting and Searching (2nd ed.). Addison-Wesley. pp. 513–558. ISBN 978-0-201-89685-5.

[cormen-5] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Chapter 11: Hash Tables". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 221–252. ISBN 978-0-262-53196-2.

[algo1rob-6] 6.0 ^6.1 ^6.2 ^6.3 ^6.4 Sedgewick, Robert; Wayne, Kevin (2011). एल्गोरिदम. Vol. 1 (4 ed.). Addison-Wesley Professional – via Princeton University, Department of Computer Science.

[hashhist-7] 7.00 ^7.01 ^7.02 ^7.03 ^7.04 ^7.05 ^7.06 ^7.07 ^7.08 ^7.09 ^7.10 ^7.11 ^7.12 ^7.13 Mehta, Dinesh P.; Sahni, Sartaj (October 28, 2004). "9: Hash Tables". Handbook of Datastructures and Applications (1 ed.). Taylor & Francis. doi:10.1201/9781420035179. ISBN 978-1-58488-435-4.

[Konheim-8] 8.0 ^8.1 ^8.2 Konheim, Alan G. (June 21, 2010). Hashing in Computer Science: Fifty Years of Slicing and Dicing. John Wiley & Sons, Inc. doi:10.1002/9780470630617. ISBN 9780470630617.

[cornell08-9] 9.0 ^9.1 ^9.2 ^9.3 Mayers, Andrew (2008). "CS 312: Hash tables and amortized analysis". Cornell University, Department of Computer Science. Archived from the original on April 26, 2021. Retrieved October 26, 2021 – via cs.cornell.edu.

[10] Maurer, W.D.; Lewis, T.G. (March 1, 1975). "Hash Table Methods". ACM Computing Surveys. Journal of the ACM. 1 (1): 14. doi:10.1145/356643.356645. S2CID 17874775.

[owo03-11] 11.0 ^11.1 Owolabi, Olumide (February 1, 2003). "Empirical studies of some hashing functions". Information and Software Technology. Department of Mathematics and Computer Science, University of Port Harcourt. 45 (2): 109–112. doi:10.1016/S0950-5849(02)00174-X – via ScienceDirect.

[Yi06-12] 12.0 ^12.1 Lu, Yi; Prabhakar, Balaji; Bonomi, Flavio (2006), "Perfect Hashing for Network Applications", 2006 IEEE International Symposium on Information Theory: 2774–2778, doi:10.1109/ISIT.2006.261567, ISBN 1-4244-0505-X, S2CID 1494710

[CHD-13] Belazzougui, Djamal; Botelho, Fabiano C.; Dietzfelbinger, Martin (2009), "Hash, displace, and compress" (PDF), Algorithms—ESA 2009: 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009, Proceedings (PDF), Lecture Notes in Computer Science, vol. 5757, Berlin: Springer, pp. 682–693, CiteSeerX 10.1.1.568.130, doi:10.1007/978-3-642-04128-0_61, MR 2557794

[cormenalgo01-14] 14.0 ^14.1 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Chapter 11: Hash Tables". Introduction to Algorithms (2nd ed.). Massachusetts Institute of Technology. ISBN 978-0-262-53196-2.

[chernoff-15] Pearson, Karl (1900). "On the criterion that a given system of deviations from the probable in the case of a correlated system of variables is such that it can be reasonably supposed to have arisen from random sampling". Philosophical Magazine. Series 5. 50 (302): 157–175. doi:10.1080/14786440009463897.

[plackett-16] Plackett, Robin (1983). "Karl Pearson and the Chi-Squared Test". International Statistical Review. 51 (1): 59–72. doi:10.2307/1402731. JSTOR 1402731.

[:0-17] 17.0 ^17.1 Wang, Thomas (March 1997). "Prime Double Hash Table". Archived from the original on September 3, 1999. Retrieved May 10, 2015.

[18] Wegman, Mark N.; Carter, J. Lawrence (1981). "New hash functions and their use in authentication and set equality" (PDF). Journal of Computer and System Sciences. 22 (3): 265–279. doi:10.1016/0022-0000(81)90033-7. Conference version in FOCS'79. Retrieved February 9, 2011.

[donald3-19] 19.0 ^19.1 ^19.2 Donald E. Knuth (April 24, 1998). The Art of Computer Programming: Volume 3: Sorting and Searching. Addison-Wesley Professional. ISBN 978-0-201-89685-5.

[20] Erik Demaine, Jeff Lind. 6.897: Advanced Data Structures. MIT Computer Science and Artificial Intelligence Laboratory. Spring 2003. "Archived copy" (PDF). Archived (PDF) from the original on June 15, 2010. Retrieved June 30, 2008.{{cite web}}: CS1 maint: archived copy as title (link)

[nick05-21] 21.0 ^21.1 ^21.2 Askitis, Nikolas; Zobel, Justin (2005). "Cache-Conscious Collision Resolution in String Hash Tables". International Symposium on String Processing and Information Retrieval. Springer Science+Business Media: 91–102. doi:10.1007/11575832_1. ISBN 978-3-540-29740-6.

[22] Willard, Dan E. (2000). "Examining computational geometry, van Emde Boas trees, and hashing from the perspective of the fusion tree". SIAM Journal on Computing. 29 (3): 1030–1049. doi:10.1137/S0097539797322425. MR 1740562..

[23] Askitis, Nikolas; Sinha, Ranjan (2010). "Engineering scalable, cache and space efficient tries for strings". The VLDB Journal. 17 (5): 634. doi:10.1007/s00778-010-0183-9. ISSN 1066-8888. S2CID 432572.

[24] Askitis, Nikolas; Zobel, Justin (October 2005). Cache-conscious Collision Resolution in String Hash Tables. pp. 91–102. doi:10.1007/11575832_11. ISBN 978-3-540-29740-6. {{cite book}}: |journal= ignored (help)

[25] Askitis, Nikolas (2009). Fast and Compact Hash Tables for Integer Keys (PDF). pp. 113–122. ISBN 978-1-920682-72-9. Archived from the original (PDF) on February 16, 2011. Retrieved June 13, 2010. {{cite book}}: |journal= ignored (help)

[tenenbaum90-26] Tenenbaum, Aaron M.; Langsam, Yedidyah; Augenstein, Moshe J. (1990). Data Structures Using C. Prentice Hall. pp. 456–461, p. 472. ISBN 978-0-13-199746-2.

[Cuckoo-27] 27.0 ^27.1 Pagh, Rasmus; Rodler, Flemming Friche (2001). "Cuckoo Hashing". Algorithms — ESA 2001. Lecture Notes in Computer Science. Vol. 2161. pp. 121–133. CiteSeerX 10.1.1.25.4189. doi:10.1007/3-540-44676-1_10. ISBN 978-3-540-42493-2.

[clrs-28] 28.0 ^28.1 ^28.2 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "11 Hash Tables", Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, pp. 221–252, ISBN 0-262-03293-7.

[chen87-29] 29.0 ^29.1 ^29.2 Vitter, Jeffery S.; Chen, Wen-Chin (1987). The design and analysis of coalesced hashing. New York, United States: Oxford University Press. ISBN 978-0-19-504182-8 – via Archive.org.

[30] 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.

[nir08-31] 31.0 ^31.1 ^31.2 ^31.3 ^31.4 ^31.5 Herlihy, Maurice; Shavit, Nir; Tzafrir, Moran (2008). "Hopscotch Hashing". International Symposium on Distributed Computing. Distributed Computing. Berlin, Heidelberg: Springer Publishing. 5218: 350–364. doi:10.1007/978-3-540-87779-0_24. ISBN 978-3-540-87778-3 – via Springer Link.

[waterloo86-32] 32.0 ^32.1 Celis, Pedro (1986). Robin Hood Hashing (PDF). Ontario, Canada: University of Waterloo, Dept. of Computer Science. ISBN 031529700X. OCLC 14083698. Archived (PDF) from the original on November 1, 2021. Retrieved November 2, 2021.

[33] Poblete, P.V.; Viola, A. (August 14, 2018). "Analysis of Robin Hood and Other Hashing Algorithms Under the Random Probing Model, With and Without Deletions". Combinatorics, Probability and Computing. Cambridge University Press. 28 (4): 600–617. doi:10.1017/S0963548318000408. ISSN 1469-2163. S2CID 125374363. Retrieved November 1, 2021 – via Cambridge Core.

[cornell14-34] Clarkson, Michael (2014). "Lecture 13: Hash tables". Cornell University, Department of Computer Science. Archived from the original on October 7, 2021. Retrieved November 1, 2021 – via cs.cornell.edu.

[35] Gries, David (2017). "JavaHyperText and Data Structure: Robin Hood Hashing" (PDF). Cornell University, Department of Computer Science. Archived (PDF) from the original on April 26, 2021. Retrieved November 2, 2021 – via cs.cornell.edu.

[indiana88-36] Celis, Pedro (March 28, 1988). External Robin Hood Hashing (PDF) (Technical report). Bloomington, Indiana: Indiana University, Department of Computer Science. 246. Archived (PDF) from the original on November 2, 2021. Retrieved November 2, 2021. {{cite tech report}}: |archive-date= / |archive-url= timestamp mismatch (help)

[37] Goddard, Wayne (2021). "Chater C5: Hash Tables" (PDF). Clemson University. pp. 15–16. Archived (PDF) from the original on November 9, 2021. Retrieved November 9, 2021 – via people.cs.clemson.edu.

[38] Devadas, Srini; Demaine, Erik (February 25, 2011). "Intro to Algorithms: Resizing Hash Tables" (PDF). Massachusetts Institute of Technology, Department of Computer Science. Archived (PDF) from the original on May 7, 2021. Retrieved November 9, 2021 – via MIT OpenCourseWare.

[39] Thareja, Reema (October 13, 2018). "Hashing and Collision". Data Structures Using C (2 ed.). Oxford University Press. ISBN 9780198099307.

[scott03-40] 40.0 ^40.1 Friedman, Scott; Krishnan, Anand; Leidefrost, Nicholas (March 18, 2003). "Hash Tables for Embedded and Real-time systems" (PDF). All Computer Science and Engineering Research. Washington University in St. Louis. doi:10.7936/K7WD3XXV. Archived (PDF) from the original on June 9, 2021. Retrieved November 9, 2021 – via Northwestern University, Department of Computer Science.

[41] Litwin, Witold (1980). "Linear hashing: A new tool for file and table addressing" (PDF). Proc. 6th Conference on Very Large Databases. Carnegie Mellon University. pp. 212–223. Archived (PDF) from the original on May 6, 2021. Retrieved November 10, 2021 – via cs.cmu.edu.

[dijk10-42] 42.0 ^42.1 Dijk, Tom Van (2010). "Analysing and Improving Hash Table Performance" (PDF). Netherlands: University of Twente. Archived (PDF) from the original on November 6, 2021. Retrieved December 31, 2021.

[43] Lech Banachowski. "Indexes and external sorting". pl:Polsko-Japońska Akademia Technik Komputerowych. Archived from the original on March 26, 2022. Retrieved March 26, 2022.

[44] Zhong, Liang; Zheng, Xueqian; Liu, Yong; Wang, Mengting; Cao, Yang (February 2020). "Cache hit ratio maximization in device-to-device communications overlaying cellular networks". China Communications. 17 (2): 232–238. doi:10.23919/jcc.2020.02.018. ISSN 1673-5447. S2CID 212649328.

[45] Bottommley, James (January 1, 2004). "Understanding Caching". Linux Journal. Archived from the original on December 4, 2020. Retrieved April 16, 2022.

[46] Jill Seaman (2014). "Set & Hash Tables" (PDF). Texas State University. Archived from the original on April 1, 2022. Retrieved March 26, 2022.{{cite web}}: CS1 maint: bot: original URL status unknown (link)

[47] "Transposition Table - Chessprogramming wiki". chessprogramming.org. Archived from the original on February 14, 2021. Retrieved May 1, 2020.

[48] "JavaScript data types and data structures - JavaScript | MDN". developer.mozilla.org. Retrieved July 24, 2022.

[49] "Programming language C++ - Technical Specification" (PDF). International Organization for Standardization. pp. 812–813. Archived from the original (PDF) on January 21, 2022. Retrieved February 8, 2022.

[50] "The Go Programming Language Specification". go.dev. Retrieved January 1, 2023.{{cite web}}: CS1 maint: url-status (link)

[51] "Lesson: Implementations (The Java™ Tutorials > Collections)". docs.oracle.com. Archived from the original on January 18, 2017. Retrieved April 27, 2018.

[52] Zhang, Juan; Jia, Yunwei (2020). "Redis rehash optimization based on machine learning". Journal of Physics: Conference Series. 1453 (1): 3. Bibcode:2020JPhCS1453a2048Z. doi:10.1088/1742-6596/1453/1/012048. S2CID 215943738.

[53] Jonan Scheffler (December 25, 2016). "Ruby 2.4 Released: Faster Hashes, Unified Integers and Better Rounding". heroku.com. Archived from the original on July 3, 2019. Retrieved July 3, 2019.

[54] "doc.rust-lang.org". Archived from the original on December 8, 2022. Retrieved December 14, 2022. test

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]

[48]

[49]

[50]

[51]

[52]

[53]

[54]

v t e Well-known data structures
Types	Collection Container
Abstract	Associative array Multimap Retrieval Data Structure List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set
Arrays	Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix
Linked	Association list Linked list Skip list Unrolled linked list XOR linked list
Trees	B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Trie Hash tree
Graphs	Binary decision diagram Directed acyclic graph Directed acyclic word graph
List of data structures

Anonymous

Search

हैश टेबल

इतिहास

सिंहावलोकन

लोड फैक्टर

हैश फ़ंक्शन

पूर्णांक ब्रह्मांड धारणा

विभाजन द्वारा द्रुतान्वेषण

गुणन द्वारा द्रुतान्वेषण

हैश फ़ंक्शन चुनना

टक्कर संकल्प

अलग श्रृंखलन

अलग श्रंखला के लिए अन्य डेटा संरचनाएं

कैशिंग और संदर्भ का इलाका

विवृत पताभिगमन

कैशिंग और संदर्भ का इलाका

विवृत पताभिगमन पर आधारित अन्य टक्कर समाधान तकनीक

एकत्रित द्रुतान्वेषण

कोयल द्रुतान्वेषण

हॉपस्कॉच द्रुतान्वेषण

रॉबिन हुड द्रुतान्वेषण

गतिशील आकार बदलना

सभी प्रविष्टियों को स्थानांतरित करके आकार बदलना

रेखीय द्रुतान्वेषण

प्रदर्शन

अनुप्रयोग

साहचर्य सरणियाँ

डाटाबेस इंडेक्सिंग

कैश

समूह

ट्रांसपोजिशन तालिका

कार्यान्वयन

यह भी देखें

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories