हैश टेबल: Difference between revisions

हैश टेबल
हैश टेबल
Type	अव्यवस्थित सहयोगी सरणी
Invented	1953
Time complexity in big O notation
Algorithm
Algorithm	Average
Space	Θ(n)
Search	Θ(1)
Insert	Θ(1)
Delete	Θ(1)

Latest revision as of 14:13, 3 August 2023

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

कंप्यूटिंग में, एक हैश टेबल, जिसे हैश मैप के रूप में भी जाना जाता है, एक डेटा स्ट्रक्चर है जो एक साहचर्य सरणी या शब्दकोश को अनुप्रयुक्त करती है। यह एक अमूर्त डेटा प्रकार है जो कीस को मानों से मैप करता है।^[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$ के संबंध में हैश टेबल का प्रदर्शन बिगड़ जाता है। इसलिए लोड फैक्टर $\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

एक वास्तविक-मूल्यवान स्थिरांक है। गुणन द्वारा हैशिंग का एक लाभ यह है कि

m

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

A

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

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

हैश मानों का समान वितरण (असतत) हैश फ़ंक्शन की मूलभूत आवश्यकता है। एक असमान वितरण से कलिश़नों की संख्या और उन्हें हल करने की लागत बढ़ जाती है। डिज़ाइन द्वारा एकरूपता सुनिश्चित करना कभी-कभी कठिन होता है, परन्तु सांख्यिकीय परीक्षणों का उपयोग करके अनुभवजन्य रूप से इसका मूल्यांकन किया जा सकता है, उदाहरण के लिए, सतत समान वितरण के लिए पियर्सन का ची-स्क्वायर परीक्षण है।^[15]^[16]

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

ओपन एड्रेसिंग योजनाओं के लिए, हैश फ़ंक्शनों को क्लस्टरिंग, क्रमागत स्लॉट में दो या दो से अधिक कीस की मैप से भी बचना चाहिए। इस तरह के क्लस्टरिंग से लुकअप की लागत बढ़ सकती है, भले ही लोड फैक्टर और कलिश़न कम हो। लोकप्रिय गुणात्मक हैश का विशेष रूप से खराब क्लस्टरिंग व्यवहार होने का अनुरोध किया जाता है।^[17]^[4]

K-इंडिपेंडेंट हैशिंग यह सिद्ध करने का एक तरीका प्रदान करता है कि एक निश्चित हैश फ़ंक्शन में किसी दिए गए प्रकार के हैशटेबल के लिए खराब कीसेट नहीं हैं। कई K-इंडिपेंडेंस परिणाम कलिश़न समाधान योजनाओं जैसे लीनियर प्रोबिंग और कुक्कू हैशिंग के लिए जाने जाते हैं। चूंकि K-इंडिपेंडेंस एक हैश फ़ंक्शन कार्य करता है, यह सिद्ध कर सकता है कि कोई भी इस तरह के सबसे तीव्र संभव हैश फ़ंक्शन को खोजने पर ध्यान केंद्रित कर सकता है।^[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

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

रॉबिन हुड हैशिंग

रॉबिन हुड हैशिंग एक ओपन एड्रेसिंग आधारित कलिश़न समाधान कलन विधि है; कलिश़नों को उस तत्व के विस्थापन को अनुकूल बनाकर हल किया जाता है, जो अपने "होम स्थान" से सबसे दूर - या सबसे लंबी प्रोबिंग अनुक्रम लंबाई (PSL) है, अर्थात, वह बकेट जिसमें पद को हैश किया गया था।^[32]^: 12 हालांकि रॉबिन हुड हैशिंग सैद्धांतिक सर्च लागत में परिवर्तन नहीं होता है, परन्तु यह बकेट पर पदों के संभाव्यता वितरण के विचरण को महत्वपूर्ण रूप से प्रभावित करता है,^[33]^: 2 अर्थात हैश टेबल में क्लस्टर गठन से व्यवहार करना है।^[34] रॉबिन हुड हैशिंग का उपयोग करने वाली हैश टेबल के भीतर प्रत्येक नोड को एक अतिरिक्त पीएसएल मान संग्रहीत करने के लिए संवर्धित किया जाना चाहिए।^[35] मान लीजिए कि $x$ सम्मिलित करने के लिए की है, $x.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 हालांकि, ऐसे हैश फ़ंक्शन का निर्माण व्यावहारिक रूप से असंभव है, ऐसा होने पर, उच्च प्रदर्शन प्राप्त करने के लिए कार्यान्वयन स्थिति-विशिष्ट कलिश़न समाधान तकनीकों पर निर्भर करता है।^[42]^: 2

एप्लिकेशन

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

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

डाटाबेस अनुक्रमण

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

कैश

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

सेट

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

ट्रांसपोजीशन टेबल

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

कार्यान्वयन

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

जावास्क्रिप्ट में, एक "ऑब्जेक्ट" की-मान युग्म (जिन्हें "गुण" कहा जाता है) का एक परिवर्तनशील संग्रह है, जहां प्रत्येक की या तो एक श्रृंखला या एक गारंटीकृत-अद्वितीय "प्रतीक" है; किसी अन्य मान को, जब की के रूप में उपयोग किया जाता है, तो पहले उसे एक श्रृंखला से जोड़ा जाता है। सात "आदिम" डेटा प्रकारों के अतिरिक्त, जावास्क्रिप्ट में प्रत्येक मान एक ऑब्जेक्ट है।^[48]ईसीएमएस्क्रिप्ट 2015 ने Map डेटा स्ट्रक्चर भी जोड़ी, जो यादृच्छिक मानों को की के रूप में स्वीकार करती है।

सी ++ 11 में यादृच्छिक प्रकार की कीस और मानों को संग्रहीत करने के लिए अपनी मानक लाइब्रेरी में unordered_map सम्मिलित हैं।^[49]

गो का अंतर्निर्मित 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 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 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

@@ Line 1: / Line 1: @@
 {{Short description|Associative array for storing key-value pairs}}
 {{Distinguish|हैश सूची|Hash tree (disambiguation){{!}}हैश ट्री}}
-{{Redirect|रीहैश|''दक्षिण पार्क'' प्रकरण|रीहैश (दक्षिण पार्क)}}
+{{Redirect|रीहैश|''साउथ पार्क'' प्रकरण|रीहैश (साउथ पार्क)}}
 {{Use mdy dates|date=January 2013}}
 <!--THE UNDERSCORE "_" IS SIGNIFICANT, DO NOT CHANGE IT TO SPACE-->
 {{Infobox data structure
-|name=Hash table
+|name=हैश टेबल
-|type=Unordered [[associative array]]
+|type=अव्यवस्थित [[सहयोगी सरणी]]
 |invented_by=
 |invented_year=1953
@@ Line 32: / Line 32: @@
 |delete_worst=O(''n'')
 }}
-[[File:Hash table 3 1 1 0 1 0 0 SP.svg|thumb|315px|right|हैश तालिका के रूप में एक छोटी फोन बुक]][[कम्प्यूटिंग]] में, एक हैश तालिका, जिसे हैश मानचित्र के रूप में भी जाना जाता है, एक [[डेटा संरचना]] है जो एक [[साहचर्य सरणी]] या शब्दकोश को अनुप्रयुक्त करती है। यह एक [[सार डेटा प्रकार]] है जो अद्वितीय कुंजी टू मान (कंप्यूटर साइंस) को मानचित्र करता है।<ref name="ms">{{citation|contribution=4 Hash Tables and Associative Arrays|title=Algorithms and Data Structures: The Basic Toolbox|first1=Kurt|last1=Mehlhorn|author1-link=Kurt Mehlhorn|first2=Peter|last2=Sanders|author2-link=Peter Sanders (computer scientist)|publisher=Springer|year=2008|pages=81–98 |url=http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/HashTables.pdf}}</ref> एक हैश तालिका एक इंडेक्स की गणना करने के लिए एक [[हैश फंकशन]] का उपयोग करता है, जिसे हैश कोड भी कहा जाता है, बकेट या खाँच की एक सरणी में, जिससे वांछित मान पाया जा सकता है। लुकअप के पर्यंत, कुंजी को हैश किया जाता है और परिणामी हैश इंगित करता है कि संबंधित मान कहाँ संग्रहीत है।
+[[File:Hash table 3 1 1 0 1 0 0 SP.svg|thumb|315px|right|हैश टेबल के रूप में एक छोटी छोटी फ़ोन बुक।]][[कम्प्यूटिंग|कंप्यूटिंग]] में, एक '''हैश टेबल''', जिसे हैश मैप के रूप में भी जाना जाता है, एक [[डेटा संरचना|डेटा स्ट्रक्चर]] है जो एक [[साहचर्य सरणी]] या शब्दकोश को अनुप्रयुक्त करती है। यह एक [[सार डेटा प्रकार|अमूर्त डेटा प्रकार]] है जो कीस को मानों से मैप करता है।<ref name="ms">{{citation|contribution=4 Hash Tables and Associative Arrays|title=Algorithms and Data Structures: The Basic Toolbox|first1=Kurt|last1=Mehlhorn|author1-link=Kurt Mehlhorn|first2=Peter|last2=Sanders|author2-link=Peter Sanders (computer scientist)|publisher=Springer|year=2008|pages=81–98 |url=http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/HashTables.pdf}}</ref> एक हैश टेबल एक इंडेक्स की गणना करने के लिए [[हैश फंकशन|हैश फ़ंक्शन]] का उपयोग करती है, जिसे हैश कोड भी कहा जाता है, बकेट या स्लॉट की एक सरणी में, जिससे वांछित मान पाया जा सकता है। लुकअप के पर्यंत, की को हैश किया जाता है और परिणामी हैश इंगित करता है कि संबंधित मान कहाँ संग्रहीत है।
-आदर्श रूप से, हैश फ़ंक्शन प्रत्येक कुंजी को एक अद्वितीय बकेट के लिए असाइन करेगा, लेकिन अधिकांश हैश तालिका डिज़ाइन एक अपूर्ण हैश फ़ंक्शन को नियोजित करते हैं, जो हैश हैश टकराव का कारण बन सकता है जहां हैश फ़ंक्शन एक से अधिक कुंजी के लिए समान अनुक्रमणिका उत्पन्न करता है। इस तरह की टक्करों को सामान्यतः किसी तरह से समायोजित किया जाता है।
+आदर्श रूप से, हैश फ़ंक्शन प्रत्येक की के एक अद्वितीय बकेट को निर्दिष्ट करेगा, परन्तु अधिकांश हैश टेबल डिज़ाइन एक अपूर्ण हैश फ़ंक्शन को नियोजित करते हैं, जो हैश कलिश़न का कारण बन सकता है जहां हैश फ़ंक्शन एक से अधिक की के लिए समान इंडेक्स उत्पन्न करता है। इस तरह की कलिश़नों को सामान्यतः किसी न किसी तरह से समायोजित किया जाता है।
-एक अच्छी तरह से आयामी हैश तालिका में, प्रत्येक लुकअप के लिए औसत समय जटिलता तालिका में संग्रहीत तत्वों की संख्या से स्वतंत्र होती है। कई हैश तालिका डिज़ाइन नाम-मूल्य जोड़ी के मनमाना सम्मिलन और विलोपन की अनुमति भी देते हैं। कुंजी-मूल्य जोड़े, [[परिशोधित विश्लेषण]] पर प्रति संचालन निरंतर औसत लागत।<ref name="leiser">[[Charles E. Leiserson]], [http://videolectures.net/mit6046jf05_leiserson_lec13/ ''Amortized Algorithms, Table Doubling, Potential Method''] {{webarchive|url=https://web.archive.org/web/20090807022046/http://videolectures.net/mit6046jf05_leiserson_lec13/ |date=August 7, 2009 }} Lecture 13, course MIT 6.046J/18.410J Introduction to Algorithms—Fall 2005 </ref><ref name="knuth">{{cite book | first=Donald |last=Knuth |author1-link=Donald Knuth | title = The Art of Computer Programming | volume = 3: ''Sorting and Searching'' | edition = 2nd | publisher = Addison-Wesley | year = 1998 | isbn = 978-0-201-89685-5 | pages = 513–558 }}</ref><ref name="cormen">{{cite book |last1=Cormen |first1=Thomas H. |author1-link=Thomas H. Cormen |last2=Leiserson |first2=Charles E. |author2-link=Charles E. Leiserson |last3=Rivest |first3=Ronald L. |author3-link=Ronald L. Rivest |last4=Stein |first4=Clifford |author4-link=Clifford Stein | title = Introduction to Algorithms | publisher = MIT Press and McGraw-Hill | year= 2001 | isbn = 978-0-262-53196-2 | edition = 2nd | pages=[https://archive.org/details/introductiontoal00corm_691/page/n243 221]–252 | chapter = Chapter 11: Hash Tables |title-link=Introduction to Algorithms }}</ref>
+एक अच्छी तरह से आकार वाले हैश टेबल में, प्रत्येक लुकअप के लिए औसत समय जटिलता टेबल में संग्रहीत तत्वों की संख्या से स्वतंत्र होती है। कई हैश टेबल डिज़ाइन प्रति ऑपरेशन परिशोधित स्थिर औसत लागत पर, की-मान युग्म के यादृच्छिक इन्सर्शन और डिलीशन की भी अनुमति देते हैं।<ref name="leiser">[[Charles E. Leiserson]], [http://videolectures.net/mit6046jf05_leiserson_lec13/ ''Amortized Algorithms, Table Doubling, Potential Method''] {{webarchive|url=https://web.archive.org/web/20090807022046/http://videolectures.net/mit6046jf05_leiserson_lec13/ |date=August 7, 2009 }} Lecture 13, course MIT 6.046J/18.410J Introduction to Algorithms—Fall 2005 </ref><ref name="knuth">{{cite book | first=Donald |last=Knuth |author1-link=Donald Knuth | title = The Art of Computer Programming | volume = 3: ''Sorting and Searching'' | edition = 2nd | publisher = Addison-Wesley | year = 1998 | isbn = 978-0-201-89685-5 | pages = 513–558 }}</ref><ref name="cormen">{{cite book |last1=Cormen |first1=Thomas H. |author1-link=Thomas H. Cormen |last2=Leiserson |first2=Charles E. |author2-link=Charles E. Leiserson |last3=Rivest |first3=Ronald L. |author3-link=Ronald L. Rivest |last4=Stein |first4=Clifford |author4-link=Clifford Stein | title = Introduction to Algorithms | publisher = MIT Press and McGraw-Hill | year= 2001 | isbn = 978-0-262-53196-2 | edition = 2nd | pages=[https://archive.org/details/introductiontoal00corm_691/page/n243 221]–252 | chapter = Chapter 11: Hash Tables |title-link=Introduction to Algorithms }}</ref>
-द्रुतान्वेषण [[स्पेस-टाइम ट्रेडऑफ़]] का एक उदाहरण है। यदि [[स्मृति]] अनंत है, तो पूरी कुंजी को एक मेमोरी एक्सेस के साथ इसके मान का पता लगाने के लिए सीधे एक इंडेक्स के रूप में उपयोग किया जा सकता है। दूसरी ओर, यदि अनंत समय उपलब्ध है, तो मानों को उनकी कुंजियों की परवाह किए बिना संग्रहीत किया जा सकता है, और तत्व को पुनः प्राप्त करने के लिए एक [[द्विआधारी खोज]] या [[रैखिक खोज]] का उपयोग किया जा सकता है।{{r|algo1rob|p=458}}
-कई स्थितियों में, हैश तालिकाएँ खोज ट्री या किसी अन्य तालिका (अभिकलन) लुकअप संरचना की तुलना में औसतन अधिक कुशल होती हैं। इस कारण से, वे व्यापक रूप से कई प्रकार के कंप्यूटर [[सॉफ़्टवेयर]] में उपयोग किए जाते हैं, विशेष रूप से साहचर्य सरणियों, डेटाबेस अनुक्रमण, [[कैश (कंप्यूटिंग)|कैश (अभिकलन)]] और [[सेट (सार डेटा प्रकार)]] के लिए।
+हैशिंग स्पेस टाइम [[स्पेस-टाइम ट्रेडऑफ़|ट्रेडऑफ़]] का एक उदाहरण है। यदि [[स्मृति|मेमोरी]] अनंत है, तो एकल मेमोरी एक्सेस के साथ इसके मान का पता लगाने के लिए संपूर्ण की को सीधे एक इंडेक्स के रूप में उपयोग किया जा सकता है। दूसरी ओर, यदि अनंत समय उपलब्ध है, तो मानों को उनकी कीस की परवाह किए बिना संग्रहीत किया जा सकता है और तत्व को पुनः प्राप्त करने के लिए एक [[द्विआधारी खोज|बाइनरी सर्च]] या [[रैखिक खोज|लीनियर सर्च]] का उपयोग किया जा सकता है।{{r|algo1rob|p=458}}
+कई स्थितियों में, हैश टेबल सर्च ट्रीज या किसी अन्य टेबल लुकअप स्ट्रक्चर की तुलना में औसतन अधिक कुशल होती हैं। इस कारण से, वे व्यापक रूप से कई प्रकार के कंप्यूटर [[सॉफ़्टवेयर]] में, विशेष रूप से साहचर्य सरणियों, डेटाबेस इंडेक्सिंग, [[कैश (कंप्यूटिंग)|कैश]] और [[सेट (सार डेटा प्रकार)|सेट]] के लिए उपयोग किए जाते हैं।
 == इतिहास ==
-द्रुतान्वेषण का विचार अलग-अलग जगहों पर स्वतंत्र रूप से उभरा। जनवरी 1953 में, [[उनका पीटर लुहान]] ने एक आंतरिक [[आईबीएम]] मेमोरेंडम लिखा, जिसमें द्रुतान्वेषण के साथ चेनिंग का उपयोग किया गया था। लुहान के पेपर पर बाद में ए डी लिन्ह बिल्डिंग द्वारा [[ओपन एड्रेसिंग|विवृत पताभिगमन]] प्रस्तावित किया गया था।<ref name="hashhist">{{cite book|title=Handbook of Datastructures and Applications|url=https://www.taylorfrancis.com/books/mono/10.1201/9781420035179/handbook-data-structures-applications-dinesh-mehta-dinesh-mehta-sartaj-sahni|publisher=[[Taylor & Francis]]|isbn=978-1-58488-435-4|first1=Dinesh P. |chapter=9: Hash Tables|last1=Mehta |first2=Sartaj |last2=Sahni | author2-link = Sartaj Sahni|date=28 October 2004|edition=1|doi=10.1201/9781420035179}}</ref>{{rp|p=15}} लगभग उसी समय, [[आईबीएम रिसर्च]] के [[जीन अमदहल]], ऐलेन एम. मैकग्रा, [[नथानिएल रोचेस्टर (कंप्यूटर वैज्ञानिक)]], और [[आर्थर सैमुअल (कंप्यूटर वैज्ञानिक)]] ने [[आईबीएम 701]] असेंबली_लैंग्वेज#असेंबलर के लिए द्रुतान्वेषण अनुप्रयुक्त किया।{{r|Konheim|p=124}} रैखिक जांच के साथ खुले संबोधन का श्रेय अमदहल को दिया जाता है, हालांकि [[एंड्री एर्शोव]] का स्वतंत्र रूप से एक ही विचार था।<ref name="Konheim">{{cite book|title=Hashing in Computer Science: Fifty Years of Slicing and Dicing|publisher=[[John Wiley & Sons, Inc.]]|first=Alan G.|last=Konheim|date=21 June 2010|isbn=9780470630617|doi=10.1002/9780470630617|url=https://onlinelibrary.wiley.com/doi/book/10.1002/9780470630617}}</ref>{{rp|pp=124-125}} विवृत पताभिगमन शब्द डब्ल्यू वेस्ले पीटरसन द्वारा अपने लेख पर गढ़ा गया था जो बड़ी फाइलों में खोज की समस्या पर चर्चा करता है।{{r|hashhist|p=15}}
+हैशिंग का विचार अलग-अलग स्थानों पर स्वतंत्र रूप से उत्पन्न हुआ। जनवरी 1953 में, [[उनका पीटर लुहान|हंस पीटर लुहान]] ने एक आंतरिक [[आईबीएम]] ज्ञापन लिखा जिसमें चेनिंग के साथ हैशिंग का उपयोग किया गया था। [[ओपन एड्रेसिंग]] को बाद में लुहान के लेख पर ए.डी. लिन्ह रचना द्वारा प्रस्तावित किया गया था।<ref name="hashhist">{{cite book|title=Handbook of Datastructures and Applications|url=https://www.taylorfrancis.com/books/mono/10.1201/9781420035179/handbook-data-structures-applications-dinesh-mehta-dinesh-mehta-sartaj-sahni|publisher=[[Taylor & Francis]]|isbn=978-1-58488-435-4|first1=Dinesh P. |chapter=9: Hash Tables|last1=Mehta |first2=Sartaj |last2=Sahni | author2-link = Sartaj Sahni|date=28 October 2004|edition=1|doi=10.1201/9781420035179}}</ref>{{rp|p=15}} लगभग उसी समय, [[जीन अमदहल|जीन अमडाहल]], ऐलेन एम. मैकग्रा, [[नथानिएल रोचेस्टर (कंप्यूटर वैज्ञानिक)|नथानिएल रोचेस्टर]] आईबीएम सर्च के [[आर्थर सैमुअल (कंप्यूटर वैज्ञानिक)|आर्थर सैमुअल]] ने [[आईबीएम 701]] असेंबलर के लिए हैशिंग अनुप्रयुक्त किया।{{r|Konheim|p=124}} लीनियर प्रोबिंग के साथ ओपन एड्रेसिंग का श्रेय अमदहल को दिया जाता है, हालांकि [[एंड्री एर्शोव]] का स्वतंत्र रूप से एक ही विचार था।<ref name="Konheim">{{cite book|title=Hashing in Computer Science: Fifty Years of Slicing and Dicing|publisher=[[John Wiley & Sons, Inc.]]|first=Alan G.|last=Konheim|date=21 June 2010|isbn=9780470630617|doi=10.1002/9780470630617|url=https://onlinelibrary.wiley.com/doi/book/10.1002/9780470630617}}</ref>{{rp|pp=124-125}} "ओपन एड्रेसिंग" शब्द डब्ल्यू वेस्ले पीटरसन द्वारा अपने लेख पर सृष्ट किया गया था जो बड़ी फाइलों में सर्च की समस्या पर चर्चा करता है।{{r|hashhist|p=15}}
-चेनिंग के साथ द्रुतान्वेषण पर पहला अकादमिक_प्रकाशन कार्य का श्रेय [[अर्नोल्ड डूमी]] को दिया जाता है, जिन्होंने शेष मॉड्यूल को हैश फ़ंक्शन के रूप में उपयोग करने के विचार पर चर्चा की।{{r|hashhist|p=15}} द्रुतान्वेषण शब्द सबसे पहले रॉबर्ट मॉरिस के एक लेख द्वारा प्रकाशित किया गया था।{{r|Konheim|p=126}} रैखिक जांच का एक विश्लेषण_ऑफ_कलन विधि मूल रूप से कोनहेम और वीस द्वारा प्रस्तुत किया गया था।{{r|hashhist|p=15}}
+चेनिंग के साथ हैशिंग पर पहले प्रकाशित कार्य का श्रेय [[अर्नोल्ड डूमी]] को दिया जाता है, जिन्होंने हैश फ़ंक्शन के रूप में शेष मॉड्यूल अभाज्य का उपयोग करने के विचार पर चर्चा की।{{r|hashhist|p=15}} शब्द "हैशिंग" पहली बार रॉबर्ट मॉरिस के एक लेख में प्रकाशित हुआ था।{{r|Konheim|p=126}} लीनियर प्रोबिंग का एक सैद्धांतिक विश्लेषण मूल रूप से कोनहेम और वीस द्वारा प्रस्तुत किया गया था।{{r|hashhist|p=15}}
+== संक्षिप्त विवरण ==
+एक साहचर्य सरणी (की, मान) युग्म का एक [[सेट (सार डेटा प्रकार)|समुच्चय]] संग्रहीत करती है और अद्वितीय की की बाधा के साथ  इन्सर्शन, डिलीशन और लुकअप (सर्च) की अनुमति देती है। साहचर्य सरणियों के हैश टेबल कार्यान्वयन में, एक सरणी <math>A</math> लंबाई <math>m</math> का आंशिक रूप से भरा हुआ तत्व <math>n</math> है, जहां <math>m \ge n</math> है। एक मान <math>x</math> इंडेक्स स्थान <math>A[h(x)]</math> पर संग्रहीत हो जाता है, जहाँ <math>h</math> एक हैश फ़ंक्शन और <math>h(x) < m</math> है।{{r|hashhist|p=2}} उचित मान्यताओं के अंतर्गत, हैश टेबलों में [[स्व-संतुलन बाइनरी सर्च ट्री|सेल्फ बैलेंसिंग बाइनरी सर्च ट्रीज]] की तुलना में सर्च, डिलीट और इंसर्ट आपरेशन पर अपेक्षाकृत अधिक [[समय जटिलता]] सीमाएं होती है।{{r|hashhist|p=1}}
+हैश टेबल का उपयोग सामान्यतः सेट को अनुप्रयुक्त करने के लिए किया जाता है, प्रत्येक की के लिए संग्रहीत मान को छोड़कर और केवल यह ट्रैक करके कि की उपस्थित है या नहीं।{{r|hashhist|p=1}}
-== सिंहावलोकन ==
-एक साहचर्य सरणी (कुंजी, मान) जोड़े के एक सेट_ (सार_डेटा_टाइप) को संग्रहीत करता है और अद्वितीय कुंजियों की बाधा के साथ सम्मिलन, विलोपन और लुकअप (खोज) की अनुमति देता है। साहचर्य सरणियों के हैश तालिका कार्यान्वयन में, एक सरणी <math>A</math> लंबाई का <math>m</math> आंशिक रूप से भरा हुआ है <math>n</math> तत्व, जहां <math>m \ge n</math>. एक कीमत <math>x</math> एक अनुक्रमणिका स्थान पर संग्रहीत हो जाता है <math>A[h(x)]</math>, कहाँ <math>h</math> एक हैश फ़ंक्शन है, और <math>h(x) < m</math>.{{r|hashhist|p=2}} उचित धारणाओं के तहत, हैश तालिका में [[स्व-संतुलन बाइनरी सर्च ट्री]] की तुलना में खोज, डिलीट और इंसर्ट संचालन पर बेहतर [[समय जटिलता]] होती है।{{r|hashhist|p=1}}
-प्रत्येक कुंजी के लिए संग्रहीत मान को छोड़कर और कुंजी मौजूद है या नहीं, यह ट्रैक करके सामान्यतः हैश तालिका का उपयोग सेट को अनुप्रयुक्त करने के लिए किया जाता है।{{r|hashhist|p=1}}
 === लोड फैक्टर ===
-एक भार कारक <math>\alpha</math> हैश तालिका का एक महत्वपूर्ण आंकड़ा है, और इसे निम्नानुसार परिभाषित किया गया है:<ref name="Cormen et al" />
+एक लोड फैक्टर <math>\alpha</math> हैश टेबल का एक क्रिटिकल स्टेटिस्टिक है और इसे निम्नानुसार परिभाषित किया गया है:<ref name="Cormen et al" />
 <math display="block">\text{load factor}\ (\alpha) = \frac{n}{k},</math>
-कहाँ
+जहाँ
-* <math>n</math> हैश तालिका में दर्ज प्रविष्टियों की संख्या है।
+* <math>n</math> हैश टेबल में व्याप्त प्रविष्टियों की संख्या है।
-* <math>k</math> बकेटो की संख्या है।
+* <math>k</math> बकेटोंं की संख्या है।
-लोड फैक्टर के संबंध में हैश तालिका का प्रदर्शन बिगड़ जाता है <math>\alpha</math>.{{r|hashhist|p=2}} इसलिए लोड कारक होने पर हैश तालिका का आकार बदल दिया जाता है या फिर से किया जाता है <math>\alpha</math> दृष्टिकोण 1.<ref name="cornell08" />यदि लोड कारक नीचे चला जाता है तो तालिका का आकार भी बदल दिया जाता है <math>\alpha_{\max}/4</math>.<ref name="cornell08">{{cite web|url=https://www.cs.cornell.edu/courses/cs312/2008sp/lectures/lec20.html|title=CS 312: Hash tables and amortized analysis|publisher=[[Cornell University]], Department of Computer Science|first=Andrew|last=Mayers|access-date=26 October 2021|year=2008|archive-url=https://web.archive.org/web/20210426052033/http://www.cs.cornell.edu/courses/cs312/2008sp/lectures/lec20.html|archive-date=26 April 2021|url-status=live|via=cs.cornell.edu}}</ref> लोड फैक्टर के स्वीकार्य आंकड़े <math>\alpha</math> लगभग 0.6 से 0.75 के बीच होना चाहिए।<ref>{{cite journal|journal=ACM Computing Surveys|issue=1|volume=1|first1=W.D.|last1=Maurer|first2=T.G.|last2=Lewis|date=1 March 1975|doi=10.1145/356643.356645|url=https://dl.acm.org/doi/10.1145/356643.356645|publisher=[[Journal of the ACM]]|page=14|title=Hash Table Methods|s2cid=17874775}}</ref>{{r|owo03|p=110}}
+लोड फैक्टर <math>\alpha</math> के संबंध में हैश टेबल का प्रदर्शन बिगड़ जाता है। इसलिए लोड फैक्टर <math>\alpha</math> दृष्टिकोण 1 होने पर हैश टेबल का आकार बदल दिया जाता है या फिर से किया जाता है।<ref name="cornell08" />यदि लोड फैक्टर <math>\alpha_{\max}/4</math> नीचे चला जाता है तो टेबल का आकार भी बदल दिया जाता है।<ref name="cornell08">{{cite web|url=https://www.cs.cornell.edu/courses/cs312/2008sp/lectures/lec20.html|title=CS 312: Hash tables and amortized analysis|publisher=[[Cornell University]], Department of Computer Science|first=Andrew|last=Mayers|access-date=26 October 2021|year=2008|archive-url=https://web.archive.org/web/20210426052033/http://www.cs.cornell.edu/courses/cs312/2008sp/lectures/lec20.html|archive-date=26 April 2021|url-status=live|via=cs.cornell.edu}}</ref> लोड फैक्टर के स्वीकार्य डेटा <math>\alpha</math> लगभग 0.6 से 0.75 के मध्य होने चाहिए।<ref>{{cite journal|journal=ACM Computing Surveys|issue=1|volume=1|first1=W.D.|last1=Maurer|first2=T.G.|last2=Lewis|date=1 March 1975|doi=10.1145/356643.356645|url=https://dl.acm.org/doi/10.1145/356643.356645|publisher=[[Journal of the ACM]]|page=14|title=Hash Table Methods|s2cid=17874775}}</ref>{{r|owo03|p=110}}
 == हैश फ़ंक्शन ==
-एक हैश समारोह <math>h</math> ब्रह्मांड को मानचित्र करता है <math>U</math> चाबियों का <math>h : U \rightarrow \{0, ..., m-1\}</math> प्रत्येक के लिए तालिका के भीतर अनुक्रमणिका या खाँच को व्यवस्थित करने के लिए <math>h(x) \in {0, ..., m-1}</math> कहाँ <math>x \in S</math> और <math>m < n</math>. हैश फ़ंक्शंस के पारंपरिक कार्यान्वयन पूर्णांक ब्रह्मांड धारणा पर आधारित हैं कि तालिका के सभी तत्व ब्रह्मांड से उत्पन्न होते हैं <math>U = \{0, ..., u - 1\}</math>, जहां की [[बिट लंबाई]] <math>u</math> [[कंप्यूटर आर्किटेक्चर]] के वर्ड (कंप्यूटर आर्किटेक्चर) के भीतर ही सीमित है।{{r|hashhist|p=2}}
+एक हैश फ़ंक्शन <math>h</math> ब्रह्मांड <math>U</math> कीस का <math>h : U \rightarrow \{0, ..., m-1\}</math> प्रत्येक के लिए टेबल के भीतर इंडेक्सों या स्लॉटों को व्यवस्थित करने के लिए, <math>h(x) \in {0, ..., m-1}</math> को मैप करता है जहाँ <math>x \in S</math> और <math>m < n</math> है। हैश फ़ंक्शन के पारंपरिक कार्यान्वयन पूर्णांक ब्रह्मांड धारणा पर आधारित हैं कि टेबल के सभी तत्व ब्रह्मांड <math>U = \{0, ..., u - 1\}</math> से उत्पन्न होते हैं, जहां <math>u</math> की [[बिट लंबाई]] [[कंप्यूटर आर्किटेक्चर]] के शब्द आकार के भीतर ही सीमित है।{{r|hashhist|p=2}}
-एक आदर्श हैश फ़ंक्शन <math>h</math> एक [[इंजेक्शन समारोह]] के रूप में परिभाषित किया गया है जैसे कि प्रत्येक तत्व <math>x</math> में <math>S</math> में एक अद्वितीय मूल्य के लिए मानचित्र <math>{0, ..., m-1}</math>.<ref name="Yi06">{{citation | last1 = Lu | first1 = Yi | last2 = Prabhakar | first2 = Balaji | last3 = Bonomi | first3 = Flavio | doi = 10.1109/ISIT.2006.261567 | journal = 2006 IEEE International Symposium on Information Theory | pages = 2774–2778 | title = Perfect Hashing for Network Applications | year = 2006| isbn = 1-4244-0505-X | s2cid = 1494710 }}</ref><ref name="CHD">{{citation | last1 = Belazzougui | first1 = Djamal | last2 = Botelho | first2 = Fabiano C. | last3 = Dietzfelbinger | first3 = Martin | contribution = Hash, displace, and compress | contribution-url = http://cmph.sourceforge.net/papers/esa09.pdf | doi = 10.1007/978-3-642-04128-0_61 | location = Berlin | mr = 2557794 | pages = 682–693 | publisher = Springer | series = [[Lecture Notes in Computer Science]] | title = Algorithms—ESA 2009: 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009, Proceedings | volume = 5757 | year = 2009| citeseerx = 10.1.1.568.130 | url = http://cmph.sourceforge.net/papers/esa09.pdf }}</ref> यदि सभी कुंजियों को समय से पहले जाना जाता है तो एक संपूर्ण हैश फ़ंक्शन बनाया जा सकता है।<ref name="Yi06" />
+एक आदर्श हैश फ़ंक्शन <math>h</math> एक [[इंजेक्शन समारोह|इंजेक्टिव फंक्शन]] के रूप में परिभाषित किया गया है जैसे कि प्रत्येक तत्व <math>x</math> में <math>S</math> एक अद्वितीय मान <math>{0, ..., m-1}</math> पर मैप करता है।<ref name="Yi06">{{citation | last1 = Lu | first1 = Yi | last2 = Prabhakar | first2 = Balaji | last3 = Bonomi | first3 = Flavio | doi = 10.1109/ISIT.2006.261567 | journal = 2006 IEEE International Symposium on Information Theory | pages = 2774–2778 | title = Perfect Hashing for Network Applications | year = 2006| isbn = 1-4244-0505-X | s2cid = 1494710 }}</ref><ref name="CHD">{{citation | last1 = Belazzougui | first1 = Djamal | last2 = Botelho | first2 = Fabiano C. | last3 = Dietzfelbinger | first3 = Martin | contribution = Hash, displace, and compress | contribution-url = http://cmph.sourceforge.net/papers/esa09.pdf | doi = 10.1007/978-3-642-04128-0_61 | location = Berlin | mr = 2557794 | pages = 682–693 | publisher = Springer | series = [[Lecture Notes in Computer Science]] | title = Algorithms—ESA 2009: 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009, Proceedings | volume = 5757 | year = 2009| citeseerx = 10.1.1.568.130 | url = http://cmph.sourceforge.net/papers/esa09.pdf }}</ref> यदि सभी कुंजियाँ समय से पहले ज्ञात हों तो एक आदर्श हैश फ़ंक्शन बनाया जा सकता है।<ref name="Yi06" />
 === पूर्णांक ब्रह्मांड धारणा ===
-पूर्णांक ब्रह्मांड धारणा में उपयोग की जाने वाली द्रुतान्वेषण की योजनाओं में विभाजन द्वारा द्रुतान्वेषण, गुणन द्वारा द्रुतान्वेषण, सार्वभौमिक द्रुतान्वेषण, [[गतिशील सही हैशिंग|गतिशील सही द्रुतान्वेषण]] और [[स्टेटिक हैशिंग|स्टेटिक द्रुतान्वेषण]] सम्मिलित हैं।{{r|hashhist|p=2}} हालाँकि, विभाजन द्वारा द्रुतान्वेषण सामान्यतः उपयोग की जाने वाली योजना है।{{r|cormenalgo01|p=264}}<ref name="owo03">{{cite journal|journal= Information and Software Technology |volume=45|issue=2|date=1 February 2003|doi=10.1016/S0950-5849(02)00174-X|url=https://www.sciencedirect.com/science/article/abs/pii/S095058490200174X|title= Empirical studies of some hashing functions |via=[[ScienceDirect]]|first=Olumide|last=Owolabi|pages=109–112 |publisher= Department of Mathematics and Computer Science, University of Port Harcourt}}</ref>{{rp|p=110}}
+पूर्णांक ब्रह्मांड धारणा में उपयोग की जाने वाली हैशिंग की योजनाओं में विभाजन द्वारा हैशिंग, गुणन द्वारा हैशिंग, यूनिवर्सल हैशिंग, [[गतिशील सही हैशिंग|डायनामिक परफेक्ट हैशिंग]] और [[स्टेटिक हैशिंग|स्टैटिक]] [[गतिशील सही हैशिंग|परफेक्ट]] हैशिंग सम्मिलित हैं।{{r|hashhist|p=2}} हालाँकि, विभाजन द्वारा हैशिंग सामान्यतः उपयोग की जाने वाली योजना है।{{r|cormenalgo01|p=264}}<ref name="owo03">{{cite journal|journal= Information and Software Technology |volume=45|issue=2|date=1 February 2003|doi=10.1016/S0950-5849(02)00174-X|url=https://www.sciencedirect.com/science/article/abs/pii/S095058490200174X|title= Empirical studies of some hashing functions |via=[[ScienceDirect]]|first=Olumide|last=Owolabi|pages=109–112 |publisher= Department of Mathematics and Computer Science, University of Port Harcourt}}</ref>{{rp|p=110}}
-==== विभाजन द्वारा द्रुतान्वेषण ====
+==== विभाजन द्वारा हैशिंग ====
-विभाजन द्वारा द्रुतान्वेषण में योजना इस प्रकार है:{{r|hashhist|p=2}}
+विभाजन द्वारा हैशिंग की योजना इस प्रकार है:{{r|hashhist|p=2}}
 <math display="block">h(x)\ =\ M\, \bmod\, n</math>
-कहाँ <math>M</math> का हैश डाइजेस्ट है <math>x \in S</math> और <math>n</math> तालिका का आकार है।
+जहाँ <math>M</math> का हैश संकलन <math>x \in S</math> और <math>n</math> टेबल का आकार है।
-==== गुणन द्वारा द्रुतान्वेषण ====
+==== गुणन द्वारा हैशिंग ====
-गुणन द्वारा द्रुतान्वेषण में योजना इस प्रकार है:{{r|hashhist|pp=2-3}}
+गुणन द्वारा हैशिंग की योजना इस प्रकार है:{{r|hashhist|pp=2-3}}
 <math display="block">h(k) = \lfloor n \bigl((M A) \bmod 1\bigr) \rfloor</math>
-कहाँ <math>A</math> एक Real_number|वास्तविक-मूल्यवान स्थिरांक है। गुणन द्वारा द्रुतान्वेषण का एक फायदा यह है कि <math>m</math> आलोचनात्मक नहीं है।{{r|hashhist|pp=2-3}} हालांकि कोई मूल्य <math>A</math> एक हैश फ़ंक्शन उत्पन्न करता है, [[डोनाल्ड नुथ]] सुनहरे अनुपात का उपयोग करने का सुझाव देता है।{{r|hashhist|p=3}}
+जहाँ <math>A</math> एक वास्तविक-मूल्यवान स्थिरांक है। गुणन द्वारा हैशिंग का एक लाभ यह है कि <math>m</math> आलोचनात्मक नहीं है।{{r|hashhist|pp=2-3}} हालांकि कोई भी मान <math>A</math> एक हैश फ़ंक्शन उत्पन्न करता है, [[डोनाल्ड नुथ]] बहुमुल्य अनुपात का उपयोग करने का सुझाव देते हैं।{{r|hashhist|p=3}}
-=== हैश फ़ंक्शन चुनना ===
+=== हैश फ़ंक्शन का चयन ===
-हैश मानों का [[समान वितरण (असतत)]] हैश फ़ंक्शन की मूलभूत आवश्यकता है। एक असमान वितरण से टक्करों की संख्या और उन्हें हल करने की लागत बढ़ जाती है। डिजाइन द्वारा एकरूपता सुनिश्चित करना कभी-कभी मुश्किल होता है, लेकिन सांख्यिकीय परीक्षणों का उपयोग करके अनुभवजन्य रूप से मूल्यांकन किया जा सकता है, उदाहरण के लिए, पियर्सन का ची-स्क्वेर्ड परीक्षण # असतत वर्दी वितरण | पियर्सन का ची-स्क्वायर असतत समान वितरण के लिए परीक्षण।<ref name="chernoff">{{Cite journal | first=Karl |last=Pearson |author1-link=Karl Pearson | year = 1900 | title = 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 | journal = Philosophical Magazine |series=Series 5 | volume = 50 | number = 302 | pages = 157–175 | doi=10.1080/14786440009463897 |url=https://zenodo.org/record/1430618 }}</ref><ref name="plackett">{{Cite journal |first=Robin |last=Plackett |author1-link=Robin Plackett | year = 1983 | title =  Karl Pearson and the Chi-Squared Test | journal = International Statistical Review | volume = 51 | number = 1 | pages = 59–72 | doi=10.2307/1402731 |jstor=1402731 }}</ref>
+हैश मानों का [[समान वितरण (असतत)]] हैश फ़ंक्शन की मूलभूत आवश्यकता है। एक असमान वितरण से कलिश़नों की संख्या और उन्हें हल करने की लागत बढ़ जाती है। डिज़ाइन द्वारा एकरूपता सुनिश्चित करना कभी-कभी कठिन होता है, परन्तु सांख्यिकीय परीक्षणों का उपयोग करके अनुभवजन्य रूप से इसका मूल्यांकन किया जा सकता है, उदाहरण के लिए, सतत समान वितरण के लिए पियर्सन का ची-स्क्वायर परीक्षण है।<ref name="chernoff">{{Cite journal | first=Karl |last=Pearson |author1-link=Karl Pearson | year = 1900 | title = 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 | journal = Philosophical Magazine |series=Series 5 | volume = 50 | number = 302 | pages = 157–175 | doi=10.1080/14786440009463897 |url=https://zenodo.org/record/1430618 }}</ref><ref name="plackett">{{Cite journal |first=Robin |last=Plackett |author1-link=Robin Plackett | year = 1983 | title =  Karl Pearson and the Chi-Squared Test | journal = International Statistical Review | volume = 51 | number = 1 | pages = 59–72 | doi=10.2307/1402731 |jstor=1402731 }}</ref>
-वितरण केवल अनुप्रयोग में होने वाले तालिका आकारों के लिए समान होना चाहिए। विशेष रूप से, यदि कोई डायनेमिक रीसाइज़िंग का उपयोग तालिका आकार के सटीक दोहरीकरण और आधा करने के साथ करता है, तो हैश फ़ंक्शन को केवल तभी एकसमान होना चाहिए जब आकार [[दो की शक्ति]] हो। यहां इंडेक्स की गणना हैश फ़ंक्शन के कुछ बिट्स के रूप में की जा सकती है। दूसरी ओर, कुछ द्रुतान्वेषण कलन विधि पसंद करते हैं कि आकार एक [[अभाज्य संख्या]] हो।<ref name=":0">{{Cite web|title = Prime Double Hash Table|url = https://www.concentric.net/~Ttwang/tech/primehash.htm|date = March 1997|access-date = 2015-05-10|last = Wang|first = Thomas|archive-url = https://web.archive.org/web/19990903133921/http://www.concentric.net/~Ttwang/tech/primehash.htm|archive-date = 1999-09-03}}</ref>
-विवृत पताभिगमन योजनाओं के लिए, हैश फ़ंक्शन को क्लस्टरिंग से भी बचना चाहिए, लगातार खाँच्स के लिए दो या दो से अधिक कुंजियों की मानचित्रिंग। इस तरह के क्लस्टरिंग से लुकअप की लागत आसमान छू सकती है, भले ही लोड फैक्टर कम हो और टक्कर कम हो। लोकप्रिय गुणात्मक हैश का विशेष रूप से खराब क्लस्टरिंग व्यवहार होने का दावा किया जाता है।<ref name=":0" /><ref name="knuth"/>
-	[[के-स्वतंत्र हैशिंग|के-स्वतंत्र द्रुतान्वेषण]] एक निश्चित हैश फ़ंक्शन को साबित करने का एक तरीका प्रदान करता है जिसमें किसी दिए गए प्रकार के हैशतालिका के लिए खराब कीसेट नहीं हैं। कई के-स्वतंत्रता परिणाम टकराव समाधान योजनाओं जैसे रैखिक जांच और कोयल द्रुतान्वेषण के लिए जाने जाते हैं। चूंकि के-स्वतंत्रता एक हैश फ़ंक्शन काम करता है, यह साबित कर सकता है कि कोई भी इस तरह के सबसे तेज़ संभव हैश फ़ंक्शन को खोजने पर ध्यान केंद्रित कर सकता है।<ref>{{cite journal | last1 = Wegman | first1 = Mark N. | author1-link = Mark N. Wegman | last2 = Carter | first2 = J. Lawrence | title = New hash functions and their use in authentication and set equality | journal = Journal of Computer and System Sciences | volume = 22 | issue = 3 | pages = 265–279 | year = 1981 | doi = 10.1016/0022-0000(81)90033-7 | id = Conference version in FOCS'79 | url = http://www.fi.muni.cz/~xbouda1/teaching/2009/IV111/Wegman_Carter_1981_New_hash_functions.pdf | accessdate = 9 February 2011 | doi-access = free }}</ref>
+वितरण केवल अनुप्रयोग में आने वाले टेबल आकारों के लिए एक समान होना चाहिए। विशेष रूप से, यदि कोई टेबल आकार को सटीक रूप से दोगुना और आधा करने के साथ गतिशील आकार बदलने का उपयोग करता है, तो हैश फ़ंक्शन को केवल तभी एकसमान होना चाहिए जब आकार [[दो की शक्ति|दो की घात]] हो। यहां इंडेक्स की गणना हैश फ़ंक्शन के कुछ बिट्स की कुछ श्रृंखला के रूप में की जा सकती है। दूसरी ओर, कुछ हैशिंग कलन विधि का चयन करते हैं कि आकार एक [[अभाज्य संख्या]] हो।<ref name=":0">{{Cite web|title = Prime Double Hash Table|url = https://www.concentric.net/~Ttwang/tech/primehash.htm|date = March 1997|access-date = 2015-05-10|last = Wang|first = Thomas|archive-url = https://web.archive.org/web/19990903133921/http://www.concentric.net/~Ttwang/tech/primehash.htm|archive-date = 1999-09-03}}</ref>
-== टक्कर संकल्प ==
+ओपन एड्रेसिंग योजनाओं के लिए, हैश फ़ंक्शनों को क्लस्टरिंग, क्रमागत स्लॉट में दो या दो से अधिक कीस की मैप से भी बचना चाहिए। इस तरह के क्लस्टरिंग से लुकअप की लागत बढ़ सकती है, भले ही लोड फैक्टर और कलिश़न कम हो। लोकप्रिय गुणात्मक हैश का विशेष रूप से खराब क्लस्टरिंग व्यवहार होने का अनुरोध किया जाता है।<ref name=":0" /><ref name="knuth" />
-{{see also| 2-choice hashing}}
-द्रुतान्वेषण का उपयोग करने वाले खोज कलन विधि में दो भाग होते हैं। पहला भाग एक हैश फ़ंक्शन की गणना कर रहा है जो खोज कुंजी को सरणी अनुक्रमणिका में बदल देता है। आदर्श मामला ऐसा है कि कोई भी दो खोज कुंजी एक ही सरणी अनुक्रमणिका में नहीं है। हालांकि, यह हमेशा मामला नहीं होता है और अनदेखी दिए गए डेटा के लिए गारंटी देना असंभव है।<ref name="donald3">{{cite book|title=The Art of Computer Programming: Volume 3: Sorting and Searching|publisher= Addison-Wesley Professional |author=[[Donald E. Knuth]]|date=24 April 1998|url=https://dl.acm.org/doi/10.5555/280635|isbn=978-0-201-89685-5}}</ref>{{rp|p=515}} इसलिए एल्गोरिथम का दूसरा भाग टक्कर समाधान है। टक्कर समाधान के दो सामान्य तरीके अलग-अलग चेनिंग और विवृत पताभिगमन हैं।<ref name="algo1rob">{{cite book|first1=Robert|last1=Sedgewick|first2=Kevin|last2=Wayne|url=https://algs4.cs.princeton.edu/|via=[[Princeton University]], Department of Computer Science|title=एल्गोरिदम|edition=4|volume=1|publisher= Addison-Wesley Professional |year=2011|author-link1=Robert_Sedgewick_(computer_scientist)}}</ref>{{rp|p=458}}
+[[के-स्वतंत्र हैशिंग|K-इंडिपेंडेंट हैशिंग]] यह सिद्ध करने का एक तरीका प्रदान करता है कि एक निश्चित हैश फ़ंक्शन में किसी दिए गए प्रकार के हैशटेबल के लिए खराब कीसेट नहीं हैं। कई K-इंडिपेंडेंस परिणाम कलिश़न समाधान योजनाओं जैसे लीनियर प्रोबिंग और कुक्कू हैशिंग के लिए जाने जाते हैं। चूंकि K-इंडिपेंडेंस एक हैश फ़ंक्शन कार्य करता है, यह सिद्ध कर सकता है कि कोई भी इस तरह के सबसे तीव्र संभव हैश फ़ंक्शन को खोजने पर ध्यान केंद्रित कर सकता है।<ref>{{cite journal | last1 = Wegman | first1 = Mark N. | author1-link = Mark N. Wegman | last2 = Carter | first2 = J. Lawrence | title = New hash functions and their use in authentication and set equality | journal = Journal of Computer and System Sciences | volume = 22 | issue = 3 | pages = 265–279 | year = 1981 | doi = 10.1016/0022-0000(81)90033-7 | id = Conference version in FOCS'79 | url = http://www.fi.muni.cz/~xbouda1/teaching/2009/IV111/Wegman_Carter_1981_New_hash_functions.pdf | accessdate = 9 February 2011 | doi-access = free }}</ref>
-=== अलग श्रृंखलन ===
-[[File:Hash table 5 0 1 1 1 1 1 LL.svg|thumb|450px|right|हैश टक्कर अलग चेनिंग द्वारा हल की गई]]
-[[File:Hash table 5 0 1 1 1 1 0 LL.svg|thumb|right|500px|बकेट ऐरे में हेड रिकॉर्ड के साथ अलग चेनिंग द्वारा हैश टक्कर।]]अलग-अलग श्रृंखलन में, प्रक्रिया में प्रत्येक खोज सरणी अनुक्रमणिका के लिए की-मान जोड़ी के साथ एक लिंक की गई सूची बनाना सम्मिलित है। टकराई हुई वस्तुओं को एक ही लिंक की गई सूची के माध्यम से एक साथ जंजीर में बांधा जाता है, जिसे एक अद्वितीय खोज कुंजी के साथ आइटम तक पहुंचने के लिए ट्रेस किया जा सकता है।{{r|algo1rob|p=464}} लिंक की गई सूची के साथ चेनिंग के माध्यम से टकराव का समाधान हैश तालिका के कार्यान्वयन का एक सामान्य तरीका है। होने देना <math>T</math> और <math>x</math> हैश तालिका और नोड क्रमशः हो, संचालन में निम्नानुसार सम्मिलित है:<ref name="cormenalgo01">{{cite book|last1=Cormen |first1=Thomas H. |author1-link=Thomas H. Cormen|last2=Leiserson |first2=Charles E. |author2-link=Charles E. Leiserson|last3=Rivest |first3=Ronald L. |author3-link=Ronald L. Rivest|last4=Stein |first4=Clifford |author4-link=Clifford Stein| title = Introduction to Algorithms| publisher = [[Massachusetts Institute of Technology]]| year= 2001| isbn = 978-0-262-53196-2| edition = 2nd|chapter = Chapter 11: Hash Tables|title-link=Introduction to Algorithms }}</ref>{{rp|p=258}}
+== कलिश़न संकल्प ==
+{{see also|2-चॉइस हैशिंग}}
+हैशिंग का उपयोग करने वाले सर्च एल्गोरिथ्म में दो भाग होते हैं। पहला भाग एक हैश फ़ंक्शन की गणना कर रहा है जो सर्च की को सरणी इंडेक्स में परिवर्तित कर देता है। आदर्श स्थिति ऐसी है कि कोई भी दो सर्च की एक ही सरणी इंडेक्स में नहीं है। हालांकि, यह सदैव स्थिति नहीं होती है और अपठित डेटा के लिए गारंटी देना असंभव है।<ref name="donald3">{{cite book|title=The Art of Computer Programming: Volume 3: Sorting and Searching|publisher= Addison-Wesley Professional |author=[[Donald E. Knuth]]|date=24 April 1998|url=https://dl.acm.org/doi/10.5555/280635|isbn=978-0-201-89685-5}}</ref>{{rp|p=515}} इसलिए कलन विधि का दूसरा भाग कलिश़न समाधान है। कलिश़न समाधान के दो सामान्य तरीके सेपरेट चेनिंग और ओपन एड्रेसिंग हैं।<ref name="algo1rob">{{cite book|first1=Robert|last1=Sedgewick|first2=Kevin|last2=Wayne|url=https://algs4.cs.princeton.edu/|via=[[Princeton University]], Department of Computer Science|title=एल्गोरिदम|edition=4|volume=1|publisher= Addison-Wesley Professional |year=2011|author-link1=Robert_Sedgewick_(computer_scientist)}}</ref>{{rp|p=458}}
+=== सेपरेट चेनिंग ===
+[[File:Hash table 5 0 1 1 1 1 1 LL.svg|thumb|450px|right|हैश कलिश़न विलग चेनिंग द्वारा हल की गई।]]
+[[File:Hash table 5 0 1 1 1 1 0 LL.svg|thumb|right|500px|बकेट सरणी में प्रमुख रिकॉर्ड के साथ विलग चेनिंग द्वारा हैश कलिश़न।]]सेपरेट चेनिंग में, प्रक्रिया में प्रत्येक सर्च सरणी इंडेक्स के लिए की-मान युग्म के साथ एक लिंक की गई सूची बनाना सम्मिलित है। कॉलिडेड आइटमों को एक ही लिंक की गई सूची के माध्यम से एक साथ श्रृंखलाबद्ध किया जाता है, जिसे एक अद्वितीय सर्च की के साथ आइटम तक पहुंचने के लिए पार किया जा सकता है।{{r|algo1rob|p=464}} लिंक की गई सूची के साथ चेनिंग के माध्यम से कलिश़न का समाधान हैश टेबल के कार्यान्वयन का एक सामान्य तरीका है। मान लीजिए कि <math>T</math> और <math>x</math> क्रमशः हैश टेबल और नोड है, आपरेशन में निम्नानुसार सम्मिलित है:<ref name="cormenalgo01">{{cite book|last1=Cormen |first1=Thomas H. |author1-link=Thomas H. Cormen|last2=Leiserson |first2=Charles E. |author2-link=Charles E. Leiserson|last3=Rivest |first3=Ronald L. |author3-link=Ronald L. Rivest|last4=Stein |first4=Clifford |author4-link=Clifford Stein| title = Introduction to Algorithms| publisher = [[Massachusetts Institute of Technology]]| year= 2001| isbn = 978-0-262-53196-2| edition = 2nd|chapter = Chapter 11: Hash Tables|title-link=Introduction to Algorithms }}</ref>{{rp|p=258}}
 <!-- the lines with only a space are significant. don't remove the lines or the spaces -->
-जंजीर-हैश-डालें (टी, के)
+यदि तत्व संख्यात्मक या शाब्दिक रूप से तुलनीय है और कुल क्रम को बनाए रखते हुए सूची में डाला गया है, तो इसके परिणामस्वरूप असफल सर्चों का तीव्रता से समापन होता है।{{r|donald3|pp=520-521}}
+==== विलग श्रंखला के लिए अन्य डेटा स्ट्रक्चरएं ====
+यदि कुंजियाँ क्रमबद्ध हैं, तो "सेल्फ-ओर्गनइजिंग" अवधारणाओं का उपयोग करना कुशल हो सकता है जैसे कि सेल्फ-बैलेंसिंग [[इष्टतम बाइनरी सर्च ट्री|बाइनरी सर्च ट्री]] का उपयोग करना, जिसके माध्यम से सैद्धांतिक सबसे खराब स्थिति <math>O(\log{n})</math> को नीचे लाया जा सकता है, हालाँकि यह अतिरिक्त जटिलताएँ प्रस्तुत करता है।{{r|donald3|p=521}}
+डायनामिक परफेक्ट हैशिंग में, गारंटीयुक्त लुकअप <math>O(1)</math> को सबसे खराब स्थिति में जटिलता को कम करने के लिए दो-स्तरीय टेबलों का उपयोग किया जाता है। इस तकनीक में, <math>k</math> प्रविष्टियों को पूर्ण टेबलों के रूप में व्यवस्थित किया गया है, <math>k^2</math> स्लॉट लगातार सबसे खराब स्थिति वाले लुकअप समय और प्रविष्टि समय और प्रविष्टि के लिए कम परिशोधन समय प्रदान करते हैं।<ref>Erik Demaine, Jeff Lind. 6.897: Advanced Data Structures. MIT Computer Science and Artificial Intelligence Laboratory. Spring 2003. {{cite web |url=http://courses.csail.mit.edu/6.897/spring03/scribe_notes/L2/lecture2.pdf |title=Archived copy |access-date=2008-06-30 |url-status=live |archive-url=https://web.archive.org/web/20100615203901/http://courses.csail.mit.edu/6.897/spring03/scribe_notes/L2/lecture2.pdf |archive-date=June 15, 2010 |df=mdy-all }}</ref> एक अध्ययन से पता चलता है कि हैवी लोड के अंतर्गत मानक लिंक्ड सूची विधि की तुलना में सरणी-आधारित सेपरेट चेनिंग 97% अधिक प्रदर्शन करने वाली होती है।{{r|nick05|p=99}}
+प्रत्येक बकेट के लिए [[फ्यूजन ट्री|फ्यूज़न ट्री]] का उपयोग करने जैसी तकनीकों के परिणामस्वरूप उच्च संभावना वाले सभी कार्यों के लिए सतत समय मिलता है।<ref>{{cite journal | last = Willard | first = Dan E. | author-link = Dan Willard | doi = 10.1137/S0097539797322425 | issue = 3 | journal = [[SIAM Journal on Computing]] | mr = 1740562 | pages = 1030–1049 | title = Examining computational geometry, van Emde Boas trees, and hashing from the perspective of the fusion tree | volume = 29 | year = 2000}}.</ref>
-यदि तत्व तुलनीय है या तो अनुक्रम # विश्लेषण या [[लेक्सिकोग्राफिक ऑर्डर|लेक्सिकोग्राफिक अनुक्रम]], और कुल अनुक्रम बनाए रखने के द्वारा सूची में डाला गया है, तो इसका परिणाम असफल खोजों की तेजी से समाप्ति में होता है।{{r|donald3|pp=520-521}}
+==== कैशिंग और संदर्भ का स्थान ====
+सेपरेट चेनिंग कार्यान्वयन की लिंक की गई सूची स्थानिक स्थान - संदर्भ की स्थानीयता - के कारण कैश-सचेत नहीं हो सकती है - जब लिंक की गई सूची के नोड्स मेमोरी में बिखरे हुए होते हैं, इस प्रकार इन्सर्ट और सर्च के पर्यंत सूची पथक्रमण सीपीयू कैश अक्षमताओं की उत्पत्ति कर सकता है।<ref name="nick05">{{cite journal|journal= International Symposium on String Processing and Information Retrieval|title=Cache-Conscious Collision Resolution in String Hash Tables| first1=Nikolas|last1=Askitis|first2=Justin|last2=Zobel|url=https://link.springer.com/chapter/10.1007/11575832_11| doi=10.1007/11575832_1|publisher=[[Springer Science+Business Media]]|isbn= 978-3-540-29740-6|year=2005|pages=91–102 }}</ref>{{rp|p=91}}
-==== अलग श्रंखला के लिए अन्य डेटा संरचनाएं ====
+कैश-सचेत भिन्नरूप में, अधिक कैश-अनुकूल पाए जाने वाले गतिशील सरणी का उपयोग उस स्थान पर किया जाता है जहां एक लिंक्ड सूची या स्व-संतुलन बाइनरी सर्च ट्री को सामान्यतः सेपरेट चेनिंग के माध्यम से कलिश़न समाधान के लिए परिनियोजित किया जाता है, क्योंकि सरणी के एकल सन्निहित आवंटन पैटर्न हार्डवेयर-कैश प्रीफेचर्स द्वारा शोषण किया जा सकता है - जैसे [[अनुवाद लुकसाइड बफर|ट्रान्सलेशन लुकसाइड बफर]] - जिसके परिणामस्वरूप एक्सेस टाइम और मेमोरी खपत कम हो जाती है।<ref>{{Cite journal| title=Engineering scalable, cache and space efficient tries for strings| first1=Nikolas| last1=Askitis| first2=Ranjan| last2=Sinha| year=2010| issn=1066-8888| doi=10.1007/s00778-010-0183-9| journal=The VLDB Journal| volume=17| issue=5| s2cid=432572|page=634}}</ref><ref>{{Cite book | title=Cache-conscious Collision Resolution in String Hash Tables | first1=Nikolas | last1=Askitis | first2=Justin | last2=Zobel |date=October 2005 | isbn=978-3-540-29740-6 | pages=91–102 | journal=Proceedings of the 12th International Conference, String Processing and Information Retrieval (SPIRE 2005) | doi=10.1007/11575832_11 | volume=3772/2005}}</ref><ref>{{Cite book |title       = Fast and Compact Hash Tables for Integer Keys |first1      = Nikolas |last1       = Askitis |year        = 2009 |isbn        = 978-1-920682-72-9 |url         = http://crpit.com/confpapers/CRPITV91Askitis.pdf |pages       = 113–122 |journal     = Proceedings of the 32nd Australasian Computer Science Conference (ACSC 2009) |volume      = 91 |url-status  = dead |archive-url  = https://web.archive.org/web/20110216180225/http://crpit.com/confpapers/CRPITV91Askitis.pdf |archive-date = February 16, 2011 |df          = mdy-all |access-date = June 13, 2010 }}</ref>
-यदि कुंजियाँ कुल क्रम में हैं, तो यह [[इष्टतम बाइनरी सर्च ट्री]] का उपयोग करने के लिए कुशल हो सकता है | स्व-संगठित अवधारणाएँ जैसे कि स्व-संतुलन बाइनरी सर्च ट्री का उपयोग करना, जिसके माध्यम से वर्स्ट-केस जटिलता को नीचे लाया जा सकता है <math>O(\log{n})</math>, हालांकि यह अतिरिक्त जटिलताओं का परिचय देता है।{{r|donald3|p=521}}
-डायनेमिक परफेक्ट द्रुतान्वेषण में, गारंटीकृत होने के लिए लुक-अप जटिलता को कम करने के लिए दो-स्तरीय हैश तालिका का उपयोग किया जाता है <math>O(1)</math> सबसे खराब स्थिति में। इस तकनीक में, की बाल्टियाँ <math>k</math> प्रविष्टियों को परफेक्ट हैश फंक्शन के साथ व्यवस्थित किया जाता है <math>k^2</math> लगातार सबसे खराब स्थिति वाले लुकअप समय और प्रविष्टि के लिए कम परिशोधित समय प्रदान करने वाले खाँच।<ref>Erik Demaine, Jeff Lind. 6.897: Advanced Data Structures. MIT Computer Science and Artificial Intelligence Laboratory. Spring 2003. {{cite web |url=http://courses.csail.mit.edu/6.897/spring03/scribe_notes/L2/lecture2.pdf |title=Archived copy |access-date=2008-06-30 |url-status=live |archive-url=https://web.archive.org/web/20100615203901/http://courses.csail.mit.edu/6.897/spring03/scribe_notes/L2/lecture2.pdf |archive-date=June 15, 2010 |df=mdy-all }}</ref> एक अध्ययन भारी भार के तहत मानक लिंक्ड सूची पद्धति की तुलना में सरणी आधारित अलग-अलग श्रंखला को 97% अधिक प्रदर्शन करने वाला दिखाता है।{{r|nick05|p=99}}
-प्रत्येक बकेटो के लिए [[फ्यूजन ट्री]] का उपयोग करने जैसी तकनीकों के परिणामस्वरूप उच्च संभावना वाले सभी कार्यों के लिए निरंतर समय मिलता है।<ref>{{cite journal | last = Willard | first = Dan E. | author-link = Dan Willard | doi = 10.1137/S0097539797322425 | issue = 3 | journal = [[SIAM Journal on Computing]] | mr = 1740562 | pages = 1030–1049 | title = Examining computational geometry, van Emde Boas trees, and hashing from the perspective of the fusion tree | volume = 29 | year = 2000}}.</ref>
-==== कैशिंग और [[संदर्भ का इलाका]] ====
+=== ओपन एड्रेसिंग ===
-अलग-अलग चेनिंग कार्यान्वयन की लिंक्ड सूची कैश-बेखबर कलन विधि नहीं हो सकती है। स्थानिक इलाके के कारण कैश-सचेत - संदर्भ की स्थानीयता - जब लिंक की गई सूची के नोड्स स्मृति में बिखरे हुए हैं, इस प्रकार डालने और खोज के पर्यंत सूची ट्रैवर्सल में सीपीयू सम्मिलित हो सकता है कैश अक्षमताओं।<ref name="nick05">{{cite journal|journal= International Symposium on String Processing and Information Retrieval|title=Cache-Conscious Collision Resolution in String Hash Tables| first1=Nikolas|last1=Askitis|first2=Justin|last2=Zobel|url=https://link.springer.com/chapter/10.1007/11575832_11| doi=10.1007/11575832_1|publisher=[[Springer Science+Business Media]]|isbn= 978-3-540-29740-6|year=2005|pages=91–102 }}</ref>{{rp|p=91}}
+{{Main|ओपन एड्रेसिंग}}
-कैश-बेपरवाह  कलन विधि|कैश-सचेत वेरिएंट में, एक [[गतिशील सरणी]] जो अधिक सीपीयू कैश पाई जाती है|कैश-फ्रेंडली का उपयोग उस स्थान पर किया जाता है जहां एक लिंक्ड लिस्ट या सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री को सामान्यतः अलग-अलग चेनिंग के माध्यम से टक्कर समाधान के लिए तैनात किया जाता है, मेमोरी प्रबंधन (ऑपरेटिंग सिस्टम) के बाद से # सरणी के एकल सन्निहित आवंटन पैटर्न का उपयोग [[कैश प्रीफेचिंग]] | हार्डवेयर-कैश प्रीफ़ेचर्स द्वारा किया जा सकता है - जैसे [[अनुवाद लुकसाइड बफर]] - जिसके परिणामस्वरूप एक्सेस समय और मेमोरी की खपत कम हो जाती है।<ref>{{Cite journal| title=Engineering scalable, cache and space efficient tries for strings| first1=Nikolas| last1=Askitis| first2=Ranjan| last2=Sinha| year=2010| issn=1066-8888| doi=10.1007/s00778-010-0183-9| journal=The VLDB Journal| volume=17| issue=5| s2cid=432572|page=634}}</ref><ref>{{Cite book | title=Cache-conscious Collision Resolution in String Hash Tables | first1=Nikolas | last1=Askitis | first2=Justin | last2=Zobel |date=October 2005 | isbn=978-3-540-29740-6 | pages=91–102 | journal=Proceedings of the 12th International Conference, String Processing and Information Retrieval (SPIRE 2005) | doi=10.1007/11575832_11 | volume=3772/2005}}</ref><ref>{{Cite book |title       = Fast and Compact Hash Tables for Integer Keys |first1      = Nikolas |last1       = Askitis |year        = 2009 |isbn        = 978-1-920682-72-9 |url         = http://crpit.com/confpapers/CRPITV91Askitis.pdf |pages       = 113–122 |journal     = Proceedings of the 32nd Australasian Computer Science Conference (ACSC 2009) |volume      = 91 |url-status  = dead |archive-url  = https://web.archive.org/web/20110216180225/http://crpit.com/confpapers/CRPITV91Askitis.pdf |archive-date = February 16, 2011 |df          = mdy-all |access-date = June 13, 2010 }}</ref>
+[[File:Hash table 5 0 1 1 1 1 0 SP.svg|thumb|380px|right|हैश कॉलिडेड लीनियर प्रोबिंग (अंतराल = 1) ओपन एड्रेसिंग द्वारा हल किया गया। ध्यान दें कि "टेड बेकर" के पास एक अद्वितीय हैश है, परन्तु फिर भी वह "सैंड्रा डी" से टकराया, जो पहले "जॉन स्मिथ" से टकराया था।]]
+[[File:Hash table average insertion time.png|thumb|right|362px|यह आलेख चेनिंग और लीनियर प्रोबिंग के साथ बड़े हैश टेबल (कैश के आकार से कहीं अधिक) में तत्वों को देखने के लिए आवश्यक सीपीयू कैश मिस की औसत संख्या की तुलना करता है। संदर्भ की उन्नत स्थानीयता के कारण रेखीय प्रोबिंग उन्नत प्रदर्शन करती है, हालाँकि जैसे-जैसे टेबल भर जाती है, इसका प्रदर्शन बहुत कम हो जाता है।]]ओपन एड्रेसिंग एक अन्य कलिश़न समाधान तकनीक है जिसमें प्रत्येक प्रविष्टि रिकॉर्ड को बकेट सरणी में ही संग्रहीत किया जाता है और हैश समाधान प्रोबिंग के माध्यम से किया जाता है। जब एक नई प्रविष्टि सम्मिलित करनी होती है, तो बकेट की प्रोबिंग की जाती है, हैशेड-से स्लॉट से प्रारंभ करके और कुछ प्रोबिंग अनुक्रम में आगे बढ़ते हुए, जब तक कि रिक्त स्लॉट नहीं मिल जाता है। किसी प्रविष्टि की सर्च करते समय, बकेट को उसी क्रम में क्रमवीक्षित किया जाता है, जब तक या तो लक्ष्य रिकॉर्ड नहीं मिल जाता है, या एक अप्रयुक्त सरणी स्लॉट नहीं मिल जाता है, जो एक असफल सर्च को इंगित करता है।<ref name="tenenbaum90">{{Cite book | title=Data Structures Using C | first1=Aaron M. | last1=Tenenbaum | first2=Yedidyah | last2=Langsam | first3=Moshe J. | last3=Augenstein | publisher=Prentice Hall | year=1990 | isbn=978-0-13-199746-2 | pages=456–461, p. 472 }}</ref>
+प्रसिद्ध प्रोबिंग अनुक्रमों में सम्मिलित हैं:
+* लीनियर प्रोबिंग, जिसमें प्रोबिंग के मध्य का अंतराल निश्चित होता है (सामान्यतः 1)।<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 | pages = 121–133| year = 2001 | isbn = 978-3-540-42493-2 | citeseerx = 10.1.1.25.4189}}</ref>
+* [[द्विघात जांच|क्वॉड्रिक प्रोबिंग]], जिसमें मूल हैश संगणना द्वारा दिए गए मान में द्विघात बहुपद के क्रमिक आउटपुट को जोड़कर प्रोबिंग के मध्य के अंतराल को बढ़ाया जाता है।{{r|clrs|p=272}}
+* [[डबल हैशिंग]], जिसमें प्रोबिंग के मध्य अंतराल की गणना द्वितीयक हैश फ़ंक्शन द्वारा की जाती है।{{r|clrs|pp=272-273}}
+ओपन एड्रेसिंग का प्रदर्शन सेपरेट चेनिंग की तुलना में धीमा हो सकता है क्योंकि लोड फैक्टर <math>\alpha</math> दृष्टिकोण 1, होने पर प्रोबिंग अनुक्रम बढ़ जाता है।<ref name="cornell08" />{{r|nick05|p=93}} पूर्णतया भरित टेबल की स्थिति में, यदि लोड फैक्टर 1 तक पहुंच जाता है, तो प्रोबिंग का परिणाम [[अनंत लूप]] में होता है।{{r|algo1rob|p=471}}क्लस्टरिंग से बचने के लिए हैश फ़ंक्शन की पूर्ण टेबल में तत्वों को समान रूप से वितरित करने की क्षमता है, क्योंकि क्लस्टर के गठन के परिणामस्वरूप सर्च समय में वृद्धि होगी।{{r|algo1rob|p=472}}
-=== विवृत पताभिगमन ===
+==== कैशिंग और संदर्भ का स्थान ====
-{{Main|विवृत पताभिगमन}}
+चूंकि स्लॉट सतत स्थानों में स्थित हैं, लीनियर प्रोबिंग से सीपीयू कैश का अपेक्षाकृत अधिक उपयोग हो सकता है क्योंकि संदर्भों की स्थानीयता कम [[स्मृति विलंबता|मेमोरी विलंबता]] के कारण होती है।<ref name="Cuckoo" />
-[[File:Hash table 5 0 1 1 1 1 0 SP.svg|thumb|380px|right|हैश टक्कर रैखिक जांच (अंतराल = 1) के साथ खुले पते से हल हो गई। ध्यान दें कि टेड बेकर के पास एक अद्वितीय हैश है, लेकिन फिर भी सैंड्रा डी से टकराया, जो पहले जॉन स्मिथ से टकराया था।]]
-[[File:Hash table average insertion time.png|thumb|right|362px|यह ग्राफ चेनिंग और रैखिक जांच के साथ बड़े हैश तालिका (कैश के आकार से कहीं अधिक) में तत्वों को देखने के लिए आवश्यक सीपीयू कैश मिस की औसत संख्या की तुलना करता है। संदर्भ की बेहतर स्थानीयता के कारण रेखीय जांच बेहतर प्रदर्शन करती है, हालाँकि जैसे-जैसे तालिका भर जाती है, इसका प्रदर्शन बहुत कम हो जाता है।]]विवृत पताभिगमन एक अन्य टक्कर रिज़ॉल्यूशन तकनीक है जिसमें प्रत्येक प्रविष्टि रिकॉर्ड को बकेट ऐरे में ही संग्रहीत किया जाता है, और हैश रिज़ॉल्यूशन जांच के माध्यम से किया जाता है। जब एक नई प्रविष्टि सम्मिलित करनी होती है, तो बकेट की जांच की जाती है, हैशेड-टू खाँच से शुरू होकर कुछ ''जांच क्रम'' में आगे बढ़ते हुए, जब तक कि एक खाली खाँच नहीं मिल जाता। किसी प्रविष्टि की खोज करते समय, बकेट को उसी क्रम में स्कैन किया जाता है, जब तक या तो लक्ष्य रिकॉर्ड नहीं मिल जाता है, या एक अप्रयुक्त सरणी खाँच नहीं मिल जाता है, जो एक असफल खोज का संकेत देता है।<ref name="tenenbaum90">{{Cite book | title=Data Structures Using C | first1=Aaron M. | last1=Tenenbaum | first2=Yedidyah | last2=Langsam | first3=Moshe J. | last3=Augenstein | publisher=Prentice Hall | year=1990 | isbn=978-0-13-199746-2 | pages=456–461, p. 472 }}</ref>
-प्रसिद्ध जांच अनुक्रमों में सम्मिलित हैं:
-* रेखीय जांच, जिसमें जांच के बीच का अंतराल निश्चित होता है (सामान्यतः 1)।<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 | pages = 121–133| year = 2001 | isbn = 978-3-540-42493-2 | citeseerx = 10.1.1.25.4189}}</ref>
-* [[द्विघात जांच]], जिसमें मूल हैश संगणना द्वारा दिए गए मान में द्विघात बहुपद के क्रमिक आउटपुट को जोड़कर जांच के बीच के अंतराल को बढ़ाया जाता है।{{r|clrs|p=272}}
-* [[डबल हैशिंग|डबल द्रुतान्वेषण]], जिसमें जांच के बीच अंतराल की गणना द्वितीयक हैश फ़ंक्शन द्वारा की जाती है।{{r|clrs|pp=272-273}}
-अलग-अलग चेनिंग की तुलना में विवृत पताभिगमन का प्रदर्शन धीमा हो सकता है क्योंकि लोड फैक्टर होने पर जांच अनुक्रम बढ़ जाता है <math>\alpha</math> दृष्टिकोण 1.<ref name="cornell08" />{{r|nick05|p=93}} पूरी तरह से भरी हुई तालिका के स्थिति में, यदि लोड कारक 1 तक पहुंच जाता है, तो जांच का परिणाम [[अनंत लूप]] में होता है।{{r|algo1rob|p=471}} रैखिक जांच की [[औसत-मामले की जटिलता|औसत-स्थिति की जटिलता]] [[क्लस्टर विश्लेषण]] से बचने के लिए तत्वों के संभाव्यता वितरण के लिए हैश फ़ंक्शन की क्षमता पर [[निरंतर समान वितरण]] पर निर्भर करती है, क्योंकि क्लस्टर के गठन से खोज समय में वृद्धि होगी।{{r|algo1rob|p=472}}
-==== कैशिंग और संदर्भ का इलाका ====
+==== ओपन एड्रेसिंग पर आधारित अन्य कलिश़न समाधान तकनीक ====
-चूंकि खाँच लगातार स्थानों में स्थित हैं, रैखिक जांच से सीपीयू कैश का बेहतर उपयोग हो सकता है क्योंकि संदर्भों की स्थानीयता कम [[स्मृति विलंबता]] के कारण होती है।<ref name="Cuckoo" />
+=== कलेसेड हैशिंग ===
+{{main|कलेसेड हैशिंग}}
+[[कोलेस्ड हैशिंग|संलयित हैशिंग]] सेपरेट चेनिंग और ओपन एड्रेसिंग दोनों का एक मिश्रण है जिसमें बकेट या नोड्स टेबल के भीतर लिंक होते हैं।<ref name="chen87">{{cite book|publisher=[[Oxford University Press]]|year=1987|first1=Jeffery S.|last1=Vitter|first2=Wen-Chin|last2=Chen|isbn= 978-0-19-504182-8 |location=New York, United States|url=https://archive.org/details/designanalysisof0000vitt/ |url-access= registration|via=[[Archive.org]]|title= The design and analysis of coalesced hashing}}</ref>{{rp|pp=6–8}} कलन विधि आदर्श रूप से [[मेमोरी पूल]] के लिए उपयुक्त है।{{r|chen87|p=4}} संलयित हैशिंग में कलिश़न को हैश टेबल पर सबसे बड़े अनुक्रमित रिक्त स्लॉट की पहचान करके हल किया जाता है, फिर उस स्लॉट में कॉलिडिंग का मान डाला जाता है। बकेट सम्मिलित किए गए नोड के स्लॉट से भी जुड़ा हुआ है जिसमें इसका कॉलिडिंग हैश पता होता है।{{r|chen87|p=8}}
-==== विवृत पताभिगमन पर आधारित अन्य टक्कर समाधान तकनीक ====
-=== एकत्रित द्रुतान्वेषण ===
+=== कुक्कू हैशिंग ===
-{{main|एकत्रित हैशिंग}}
+{{main|कुक्कू हैशिंग}}
-[[कोलेस्ड हैशिंग|कोलेस्ड द्रुतान्वेषण]] अलग-अलग चेनिंग और विवृत पताभिगमन दोनों का एक हाइब्रिड है जिसमें बकेट या नोड्स तालिका के भीतर लिंक होते हैं।<ref name="chen87">{{cite book|publisher=[[Oxford University Press]]|year=1987|first1=Jeffery S.|last1=Vitter|first2=Wen-Chin|last2=Chen|isbn= 978-0-19-504182-8 |location=New York, United States|url=https://archive.org/details/designanalysisof0000vitt/ |url-access= registration|via=[[Archive.org]]|title= The design and analysis of coalesced hashing}}</ref>{{rp|pp=6–8}} कलन विधि आदर्श रूप से [[मेमोरी पूल]] के लिए उपयुक्त है।{{r|chen87|p=4}} कोलेस्ड द्रुतान्वेषण में टकराव को हैश तालिका पर सबसे बड़े अनुक्रमित खाली खाँच की पहचान करके हल किया जाता है, फिर उस खाँच में टकराने का मान डाला जाता है। बकेट सम्मिलित किए गए नोड के खाँच से भी जुड़ा हुआ है जिसमें इसका टकराने वाला हैश पता होता है।{{r|chen87|p=8}}
+[[कोयल हैशिंग|कुक्कू हैशिंग]] ओपन एड्रेसिंग कलिश़न समाधान तकनीक का एक रूप है जो गारंटी <math>O(1)</math>, सबसे खराब स्थिति लुकअप जटिलता और सम्मिलन के लिए निरंतर परिशोधित समय देता है। कलिश़न को दो हैश टेबल बनाए रखने के माध्यम से हल किया जाता है, प्रत्येक का अपना हैशिंग फ़ंक्शन होता है और कॉलिडेड स्लॉट को दिए गए पद के साथ बदल दिया जाता है और स्लॉट का व्यस्त तत्व अन्य हैश टेबल में विस्थापित हो जाता है। यह प्रक्रिया तब तक जारी रहती है जब तक कि टेबलों की रिक्त बकेटों में प्रत्येक की का अपना स्थान न हो जाए; यदि प्रक्रिया अनंत लूप में प्रवेश करती है - जिसे प्रभावसीमा लूप गणक को बनाए रखने के माध्यम से पहचाना जाता है - दोनों हैश टेबल नए हैश फ़ंक्शनों के साथ दोबारा जुड़ जाते हैं और प्रक्रिया जारी रहती है।<ref>{{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>{{rp|pp=124–125}}
-=== कोयल द्रुतान्वेषण ===
+===हॉपस्कॉच हैशिंग ===
-{{main|कोयल हैशिंग}}
+{{main|हॉप्सकॉच हैशिंग}}
-[[कोयल हैशिंग|कोयल द्रुतान्वेषण]] विवृत पताभिगमन कोलिशन रेजोल्यूशन तकनीक का एक रूप है जो गारंटी देता है <math>O(1)</math> सबसे खराब स्थिति लुकअप जटिलता और सम्मिलन के लिए निरंतर परिशोधित समय। टकराव को दो हैश तालिका बनाए रखने के माध्यम से हल किया जाता है, प्रत्येक का अपना द्रुतान्वेषण फ़ंक्शन होता है, और टकराए गए खाँच को दिए गए आइटम के साथ बदल दिया जाता है, और खाँच का व्यस्त तत्व अन्य हैश तालिका में विस्थापित हो जाता है। यह प्रक्रिया तब तक जारी रहती है जब तक कि तालिकाओं की खाली बकेटो में प्रत्येक कुंजी का अपना स्थान नहीं हो जाता; यदि प्रक्रिया अनंत लूप में प्रवेश करती है - जिसे थ्रेशोल्ड लूप काउंटर को बनाए रखने के माध्यम से पहचाना जाता है - दोनों हैश तालिकाएँ नए हैश फ़ंक्शंस के साथ फिर से मिलती हैं और प्रक्रिया जारी रहती है।<ref>{{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>{{rp|pp=124–125}}
+[[हॉपस्कॉच हैशिंग]] एक ओपन एड्रेसिंग आधारित कलन विधि है जो कुक्कू हैशिंग, लीनियर प्रोबिंग और चेनिंग के तत्वों को बकेटों के एक प्रतिवेश की धारणा के माध्यम से जोड़ती है - किसी भी अधिकृत बकेटोंं  के आसपास के बकेटोंं, जिसे एक वर्चुअल बकेट भी कहा जाता है।<ref name="nir08">{{cite journal|doi=10.1007/978-3-540-87779-0_24|isbn= 978-3-540-87778-3 |publisher=[[Springer Publishing]]|journal= International Symposium on Distributed Computing |year=2008|last1=Herlihy |first1=Maurice |last2=Shavit |first2=Nir |last3=Tzafrir |first3=Moran|title=Hopscotch Hashing|volume=5218|via=Springer Link|series= Distributed Computing|pages= 350–364 |url=https://link.springer.com/chapter/10.1007/978-3-540-87779-0_24|location=Berlin, Heidelberg}}</ref>{{rp|pp=351–352}}  कलन विधि को श्रेष्ठतर प्रदर्शन देने के लिए रूपांकित किया गया है जब हैश टेबल का लोड फैक्टर 90% से अधिक बढ़ जाता है; यह [[समवर्ती कंप्यूटिंग|कन्करन्ट सेटिंग]] में उच्च साद्यांत भी प्रदान करता है, इस प्रकार आकार बदलने योग्य [[समवर्ती हैश तालिका|कन्करन्ट हैश टेबल]] को अनुप्रयुक्त करने के लिए उपयुक्त है।{{r|nir08|p=350}} हॉप्सकॉच हैशिंग की प्रतिवेश विशेषता एक गुणधर्म की गारंटी देती है कि प्रतिवेश के भीतर किसी भी बकेट से वांछित पद को खोजने की लागत बकेट में ही इसे खोजने की लागत के बहुत समीप है; अन्य पदों को विस्थापित करने में सम्मिलित संभावित लागत के साथ, कलन विधि अपने प्रतिवेश में एक पद बनने का प्रयास करती है।{{r|nir08|p=352}}
+हैश टेबल के भीतर प्रत्येक बकेट में एक अतिरिक्त हॉप-सूचना सम्मिलित है - यूक्लिडियन दूरी को इंगित करने के लिए [[बिट सरणी]] जो मूल रूप से H -1 प्रविष्टियों के भीतर वर्तमान आभासी बकेटों में हैश की गई थी।{{r|nir08|p=352}} मान लीजिए कि <math>k</math> और <math>Bk</math> सम्मिलित की जाने वाली की और बकेट जिसमें की को क्रमशः हैश किया जाता है; सम्मिलन प्रक्रिया में कई स्थिति सम्मिलित हैं जैसे कि कलन विधि के प्रतिवेश गुणधर्म की प्रतिज्ञा की जाती है:{{r|nir08|pp=352-353}} यदि <math>Bk</math> रिक्त है, तत्व डाला गया है और बिट-मैप का सबसे बायां बिट 1 पर नियत है; यदि रिक्त नहीं है, तो टेबल में एक रिक्त स्लॉट खोजने के लिए लीनियर प्रोबिंग का उपयोग किया जाता है, बकेट का बिट-मैप सम्मिलन के बाद अद्यतन हो जाता है; यदि रिक्त स्लॉट प्रतिवेश की सीमा के भीतर नहीं है, अर्थात H-1, बाद में प्रत्येक बकेट की स्वैप और हॉप-इन्फो बिट सरणी में प्रकलन उसके प्रतिवेश के के अपरिवर्तनीय गुणों के अनुसार किया जाता है।{{r|nir08|p=353}}
-===हॉपस्कॉच द्रुतान्वेषण ===
-{{main|
-हॉप्सकॉच हैशिंग}}
-[[हॉपस्कॉच हैशिंग|हॉपस्कॉच द्रुतान्वेषण]] एक विवृत पताभिगमन आधारित कलन विधि है जो कोयल द्रुतान्वेषण, रैखिक जांच और चेनिंग के तत्वों को बकेटो के एक पड़ोस की धारणा के माध्यम से जोड़ती है - किसी भी कब्जे वाली बकेट के आसपास की बाल्टियाँ, जिसे एक आभासी बकेट भी कहा जाता है।<ref name="nir08">{{cite journal|doi=10.1007/978-3-540-87779-0_24|isbn= 978-3-540-87778-3 |publisher=[[Springer Publishing]]|journal= International Symposium on Distributed Computing |year=2008|last1=Herlihy |first1=Maurice |last2=Shavit |first2=Nir |last3=Tzafrir |first3=Moran|title=Hopscotch Hashing|volume=5218|via=Springer Link|series= Distributed Computing|pages= 350–364 |url=https://link.springer.com/chapter/10.1007/978-3-540-87779-0_24|location=Berlin, Heidelberg}}</ref>{{rp|pp=351–352}}  कलन विधि को बेहतर प्रदर्शन देने के लिए डिज़ाइन किया गया है जब हैश तालिका का लोड फैक्टर 90% से अधिक हो जाता है; यह [[समवर्ती कंप्यूटिंग|समवर्ती अभिकलन]] में उच्च थ्रूपुट भी प्रदान करता है, इस प्रकार आकार बदलने योग्य [[समवर्ती हैश तालिका]] को अनुप्रयुक्त करने के लिए उपयुक्त है।{{r|nir08|p=350}} हॉप्सकॉच द्रुतान्वेषण की पड़ोस विशेषता एक संपत्ति की गारंटी देती है कि, पड़ोस के भीतर किसी भी बकेट से वांछित वस्तु को खोजने की लागत बकेट में ही इसे खोजने की लागत के बहुत करीब है; एल्गोरिथम अपने पड़ोस में एक वस्तु बनने का प्रयास करता है - अन्य वस्तुओं को विस्थापित करने में सम्मिलित संभावित लागत के साथ।{{r|nir08|p=352}}
-हैश तालिका के भीतर प्रत्येक बकेट में एक अतिरिक्त हॉप-सूचना सम्मिलित है - यूक्लिडियन दूरी को इंगित करने के लिए एच-बिट [[बिट सरणी]] # आइटम का एक आयाम जो मूल रूप से एच -1 प्रविष्टियों के भीतर वर्तमान वर्चुअल बकेट में हैश किया गया था।{{r|nir08|p=352}} होने देना <math>k</math> और <math>Bk</math> सम्मिलित की जाने वाली कुंजी और बकेट जिसमें कुंजी को क्रमशः हैश किया जाता है; सम्मिलन प्रक्रिया में कई स्थिति सम्मिलित हैं जैसे कि  कलन विधि की पड़ोस संपत्ति की प्रतिज्ञा की जाती है:{{r|nir08|pp=352-353}} यदि <math>Bk</math> खाली है, तत्व डाला गया है, और बिटमानचित्र का सबसे बाईं ओर [[बिटवाइज़ ऑपरेशन|बिटवाइज़ संचालन]] 1 है; यदि खाली नहीं है, तो तालिका में एक खाली खाँच खोजने के लिए रैखिक जांच का उपयोग किया जाता है, बकेट का बिटमानचित्र सम्मिलन के बाद अद्यतन हो जाता है; यदि खाली खाँच पड़ोस की सीमा के भीतर नहीं है, अर्थात H-1, बाद में प्रत्येक बकेट की स्वैप और हॉप-इन्फो बिट सरणी में हेरफेर उसके पड़ोस के इनवेरिएंट (गणित) के अनुसार किया जाता है।{{r|nir08|p=353}}
-=== रॉबिन हुड द्रुतान्वेषण ===
+=== रॉबिन हुड हैशिंग ===
-रॉबिन हुड द्रुतान्वेषण एक विवृत पताभिगमन आधारित कोलिज़न रेज़ोल्यूशन एल्गोरिथम है; टक्करों को उस तत्व के विस्थापन के पक्ष में करके हल किया जाता है जो सबसे दूर है—या सबसे लंबी जांच अनुक्रम लंबाई (PSL)—उसके गृह स्थान से अर्थात वह बकेट जिसमें आइटम को हैश किया गया था।<ref name="waterloo86">{{cite book|title=Robin Hood Hashing|first=Pedro|last=Celis|publisher=[[University of Waterloo]], Dept. of Computer Science|year=1986|url=https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf |location=Ontario, Canada|isbn= 031529700X|oclc= 14083698|archive-url=https://web.archive.org/web/20211101071032/https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf|archive-date=1 November 2021|access-date=2 November 2021|url-status=live}}</ref>{{rp|p=12}} हालांकि रॉबिन हुड द्रुतान्वेषण [[कम्प्यूटेशनल जटिलता सिद्धांत]] को नहीं बदलता है, लेकिन यह बकेटो पर वस्तुओं के संभाव्यता वितरण के विचरण को महत्वपूर्ण रूप से प्रभावित करता है,<ref>{{cite journal|publisher=[[Cambridge University Press]]|date=14 August 2018|first1=P.V.|last1=Poblete|first2=A.|last2=Viola|journal=[[Combinatorics, Probability and Computing]]|volume=28|issue=4|title=Analysis of Robin Hood and Other Hashing Algorithms Under the Random Probing Model, With and Without Deletions|pages=600–617 |doi=10.1017/S0963548318000408|s2cid=125374363 |url=https://www.cambridge.org/core/journals/combinatorics-probability-and-computing/article/abs/analysis-of-robin-hood-and-other-hashing-algorithms-under-the-random-probing-model-with-and-without-deletions/933D4F203E3C70EF15053287412242E0|via=Cambridge Core|access-date=1 November 2021|issn= 1469-2163}}</ref>{{rp|p=2}} अर्थात हैश तालिका में क्लस्टर एनालिसिस फॉर्मेशन से निपटना।<ref name="cornell14">{{cite web|url=https://www.cs.cornell.edu/courses/cs3110/2014fa/lectures/13/lec13.html|title= Lecture 13: Hash tables|publisher=[[Cornell University]], Department of Computer Science|first=Michael|last=Clarkson|access-date=1 November 2021|year=2014|archive-url=https://web.archive.org/web/20211007011300/https://www.cs.cornell.edu/courses/cs3110/2014fa/lectures/13/lec13.html|archive-date=7 October 2021|url-status=live|via=cs.cornell.edu}}</ref> रॉबिन हुड द्रुतान्वेषण का उपयोग करने वाली हैश तालिका के भीतर प्रत्येक नोड को एक अतिरिक्त पीएसएल मान संग्रहीत करने के लिए संवर्धित किया जाना चाहिए।<ref>{{cite web|publisher=[[Cornell University]], Department of Computer Science|url=https://www.cs.cornell.edu/courses/JavaAndDS/files/hashing_RobinHood.pdf|title=JavaHyperText and Data Structure: Robin Hood Hashing|access-date=2 November 2021|first=David|last=Gries|year=2017|archive-url=https://web.archive.org/web/20210426051503/http://www.cs.cornell.edu/courses/JavaAndDS/files/hashing_RobinHood.pdf|archive-date=26 April 2021|url-status=live|via=cs.cornell.edu}}</ref> होने देना <math>x</math> डालने की कुंजी हो, <math>x.psl</math> की (वृद्धिशील) PSL लंबाई हो <math>x</math>, <math>T</math> हैश तालिका हो और <math>j</math> सूचकांक हो, सम्मिलन प्रक्रिया इस प्रकार है:{{r|waterloo86|pp=12-13}}<ref name="indiana88">{{cite techreport|first=Pedro|last=Celis|date=28 March 1988| number=246|institution=[[Indiana University]], Department of Computer Science|location=Bloomington, Indiana| url=https://legacy.cs.indiana.edu/ftp/techreports/TR246.pdf|archive-url=https://web.archive.org/web/20211103013505/https://legacy.cs.indiana.edu/ftp/techreports/TR246.pdf|archive-date=2 November 2021|access-date=2 November 2021|url-status=live| title=External Robin Hood Hashing}}</ref>{{rp|p=5}}
+रॉबिन हुड हैशिंग एक ओपन एड्रेसिंग आधारित कलिश़न समाधान कलन विधि है; कलिश़नों को उस तत्व के विस्थापन को अनुकूल बनाकर हल किया जाता है, जो अपने "होम स्थान" से सबसे दूर - या सबसे लंबी प्रोबिंग अनुक्रम लंबाई (PSL) है, अर्थात, वह बकेट जिसमें पद को हैश किया गया था।<ref name="waterloo86">{{cite book|title=Robin Hood Hashing|first=Pedro|last=Celis|publisher=[[University of Waterloo]], Dept. of Computer Science|year=1986|url=https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf |location=Ontario, Canada|isbn= 031529700X|oclc= 14083698|archive-url=https://web.archive.org/web/20211101071032/https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf|archive-date=1 November 2021|access-date=2 November 2021|url-status=live}}</ref>{{rp|p=12}} हालांकि रॉबिन हुड हैशिंग सैद्धांतिक सर्च लागत में परिवर्तन नहीं होता है, परन्तु यह बकेट पर पदों के संभाव्यता वितरण के विचरण को महत्वपूर्ण रूप से प्रभावित करता है,<ref>{{cite journal|publisher=[[Cambridge University Press]]|date=14 August 2018|first1=P.V.|last1=Poblete|first2=A.|last2=Viola|journal=[[Combinatorics, Probability and Computing]]|volume=28|issue=4|title=Analysis of Robin Hood and Other Hashing Algorithms Under the Random Probing Model, With and Without Deletions|pages=600–617 |doi=10.1017/S0963548318000408|s2cid=125374363 |url=https://www.cambridge.org/core/journals/combinatorics-probability-and-computing/article/abs/analysis-of-robin-hood-and-other-hashing-algorithms-under-the-random-probing-model-with-and-without-deletions/933D4F203E3C70EF15053287412242E0|via=Cambridge Core|access-date=1 November 2021|issn= 1469-2163}}</ref>{{rp|p=2}} अर्थात हैश टेबल में क्लस्टर गठन से व्यवहार करना है।<ref name="cornell14">{{cite web|url=https://www.cs.cornell.edu/courses/cs3110/2014fa/lectures/13/lec13.html|title= Lecture 13: Hash tables|publisher=[[Cornell University]], Department of Computer Science|first=Michael|last=Clarkson|access-date=1 November 2021|year=2014|archive-url=https://web.archive.org/web/20211007011300/https://www.cs.cornell.edu/courses/cs3110/2014fa/lectures/13/lec13.html|archive-date=7 October 2021|url-status=live|via=cs.cornell.edu}}</ref> रॉबिन हुड हैशिंग का उपयोग करने वाली हैश टेबल के भीतर प्रत्येक नोड को एक अतिरिक्त पीएसएल मान संग्रहीत करने के लिए संवर्धित किया जाना चाहिए।<ref>{{cite web|publisher=[[Cornell University]], Department of Computer Science|url=https://www.cs.cornell.edu/courses/JavaAndDS/files/hashing_RobinHood.pdf|title=JavaHyperText and Data Structure: Robin Hood Hashing|access-date=2 November 2021|first=David|last=Gries|year=2017|archive-url=https://web.archive.org/web/20210426051503/http://www.cs.cornell.edu/courses/JavaAndDS/files/hashing_RobinHood.pdf|archive-date=26 April 2021|url-status=live|via=cs.cornell.edu}}</ref> मान लीजिए कि <math>x</math> सम्मिलित करने के लिए की है, <math>x.psl</math> की (वृद्धिशील) पीएसएल लंबाई <math>x</math>, <math>T</math> हैश टेबल और <math>j</math> इंडेक्स है, सम्मिलन प्रक्रिया इस प्रकार है:{{r|waterloo86|pp=12-13}}<ref name="indiana88">{{cite techreport|first=Pedro|last=Celis|date=28 March 1988| number=246|institution=[[Indiana University]], Department of Computer Science|location=Bloomington, Indiana| url=https://legacy.cs.indiana.edu/ftp/techreports/TR246.pdf|archive-url=https://web.archive.org/web/20211103013505/https://legacy.cs.indiana.edu/ftp/techreports/TR246.pdf|archive-date=2 November 2021|access-date=2 November 2021|url-status=live| title=External Robin Hood Hashing}}</ref>{{rp|p=5}}
-* यदि <math>x.psl\ \le\ T[j].psl</math>: बाहरी जांच का प्रयास किए बिना पुनरावृति अगली बकेट में चली जाती है।
+* यदि <math>x.psl\ \le\ T[j].psl</math>: बाहरी प्रोबिंग का प्रयास किए बिना पुनरावृति अगले बकेट में चली जाती है।
-* यदि <math>x.psl\ >\ T[j].psl</math>: आइटम डालें <math>x</math> बकेट में <math>j</math>; बदलना <math>x</math> साथ <math>T[j]</math>-जाने भी दो <math>x'</math>; से जांच जारी रखें <math>j+1</math>सेंट बकेट डालने के लिए <math>x'</math>; प्रक्रिया को तब तक दोहराएं जब तक कि प्रत्येक तत्व सम्मिलित न हो जाए।
+* यदि <math>x.psl\ >\ T[j].psl</math>: पद <math>x</math> बकेट <math>j</math> में; स्वैप <math>x</math> के साथ <math>T[j]</math> सम्मलित करें-मान लीजिए कि <math>x'</math>; <math>j+1</math> सम्मिलित करने के लिए <math>x'</math> से प्रोबिंग जारी रखें ; प्रक्रिया को तब तक दोहराएं जब तक कि प्रत्येक तत्व सम्मिलित न हो जाए।
-== गतिशील आकार बदलना ==
+== गतिशील आकार परिवर्तन ==
-बार-बार सम्मिलन के कारण हैश तालिका में प्रविष्टियों की संख्या बढ़ जाती है, जिसके परिणामस्वरूप लोड कारक बढ़ जाता है; परिशोधित बनाए रखने के लिए <math>O(1)</math> लुकअप और सम्मिलन संचालन का प्रदर्शन, एक हैश तालिका को गतिशील रूप से आकार दिया जाता है और तालिकाओं की वस्तुओं को नई हैश तालिका की बकेटो में फिर से डाला जाता है,<ref name="cornell08" />चूंकि [[मॉड्यूल ऑपरेशन|मॉड्यूल संचालन]] के कारण अलग-अलग हैश मान में अलग-अलग तालिका आकार के परिणामस्वरूप आइटम कॉपी नहीं किए जा सकते हैं।<ref>{{cite web|url=https://people.cs.clemson.edu/~goddard/texts/algor/C5.pdf|first=Wayne|last=Goddard|year=2021|access-date=9 November 2021|title=Chater C5: Hash Tables|archive-url=https://web.archive.org/web/20211109025300/https://people.cs.clemson.edu/~goddard/texts/algor/C5.pdf|archive-date=9 November 2021|url-status=live|publisher=[[Clemson University]]|via=people.cs.clemson.edu|pages=15–16}}</ref> यदि कुछ तत्वों को हटाने के बाद हैश तालिका बहुत खाली हो जाती है, तो अत्यधिक [[स्मृति पदचिह्न]] से बचने के लिए आकार बदला जा सकता है।<ref>{{cite web|url=https://courses.csail.mit.edu/6.006/spring11/rec/rec07.pdf|title=Intro to Algorithms: Resizing Hash Tables|date=25 February 2011|first1=Srini|last1=Devadas|first2=Erik|last2=Demaine|publisher=[[Massachusetts Institute of Technology]], Department of Computer Science|via=[[MIT OpenCourseWare]]|archive-url=https://web.archive.org/web/20210507102944/https://courses.csail.mit.edu/6.006/spring11/rec/rec07.pdf|archive-date=7 May 2021|url-status=live|access-date=9 November 2021}}</ref>
+बार-बार सम्मिलन के कारण हैश टेबल में प्रविष्टियों की संख्या बढ़ जाती है, जिसके परिणामस्वरूप लोड फैक्टर बढ़ जाता है; परिशोधित बनाए रखने के लिए <math>O(1)</math> लुकअप और सम्मिलन आपरेशन का प्रदर्शन, एक हैश टेबल को गतिशील रूप से आकार दिया जाता है और टेबलों के पदों को नई हैश टेबल की बकेटों में फिर से डाला जाता है,<ref name="cornell08" />चूंकि [[मॉड्यूल ऑपरेशन|मॉड्यूल आपरेशन]] के कारण सेपरेट हैश मान में सेपरेट टेबल आकार के परिणामस्वरूप पदों के अनुकरण नहीं किए जा सकते हैं।<ref>{{cite web|url=https://people.cs.clemson.edu/~goddard/texts/algor/C5.pdf|first=Wayne|last=Goddard|year=2021|access-date=9 November 2021|title=Chater C5: Hash Tables|archive-url=https://web.archive.org/web/20211109025300/https://people.cs.clemson.edu/~goddard/texts/algor/C5.pdf|archive-date=9 November 2021|url-status=live|publisher=[[Clemson University]]|via=people.cs.clemson.edu|pages=15–16}}</ref> यदि कुछ तत्वों को हटाने के बाद हैश टेबल बहुत रिक्त हो जाती है, तो अत्यधिक [[स्मृति पदचिह्न|मेमोरी पदचिह्न]] से बचने के लिए आकार बदला जा सकता है।<ref>{{cite web|url=https://courses.csail.mit.edu/6.006/spring11/rec/rec07.pdf|title=Intro to Algorithms: Resizing Hash Tables|date=25 February 2011|first1=Srini|last1=Devadas|first2=Erik|last2=Demaine|publisher=[[Massachusetts Institute of Technology]], Department of Computer Science|via=[[MIT OpenCourseWare]]|archive-url=https://web.archive.org/web/20210507102944/https://courses.csail.mit.edu/6.006/spring11/rec/rec07.pdf|archive-date=7 May 2021|url-status=live|access-date=9 November 2021}}</ref>
 === सभी प्रविष्टियों को स्थानांतरित करके आकार बदलना ===
-सामान्यतः, मूल हैश तालिका के आकार के दोगुने आकार वाली एक नई हैश तालिका को गतिशील मेमोरी आवंटन निजी रूप से प्राप्त होता है और मूल हैश तालिका में प्रत्येक आइटम सम्मिलन संचालन के बाद आइटमों के हैश मानों की गणना करके नए आवंटित में ले जाया जाता है। इसकी सरलता के बावजूद रीद्रुतान्वेषण कम्प्यूटेशनल रूप से महंगा है।<ref>{{cite book|title= Data Structures Using C|date=13 October 2018|edition=2|first=Reema|last=Thareja|publisher=[[Oxford University Press]]| url=https://global.oup.com/academic/product/data-structures-using-c-9780198099307|isbn= 9780198099307|url-access=subscription| chapter=Hashing and Collision}}</ref>{{rp|pp=478–479}}
+सामान्यतः, मूल हैश टेबल के आकार के दोगुने आकार वाली एक नई हैश टेबल को गतिशील मेमोरी आवंटन निजी रूप से प्राप्त होता है और मूल हैश टेबल में प्रत्येक पद सम्मिलन आपरेशन के बाद पदों के हैश मानों की गणना करके नए आवंटित में ले जाया जाता है। इसकी सरलता के बावजूद रीहैशिंग अभिकलनीयतः बहुमूल्य है।<ref>{{cite book|title= Data Structures Using C|date=13 October 2018|edition=2|first=Reema|last=Thareja|publisher=[[Oxford University Press]]| url=https://global.oup.com/academic/product/data-structures-using-c-9780198099307|isbn= 9780198099307|url-access=subscription| chapter=Hashing and Collision}}</ref>{{rp|pp=478–479}}
-=== ऑल-एट-वन्स रीद्रुतान्वेषण === के विकल्प
+=== सभी को एक साथ पुनः दोहराने के विकल्प ===
+कुछ हैश टेबल कार्यान्वयन, विशेष रूप से [[वास्तविक समय प्रणाली|वास्तविक समय प्रणालियों]] में, हैश टेबल को एक साथ बड़ा करने के मूल्य का भुगतान नहीं कर सकते हैं, क्योंकि यह समय-महत्वपूर्ण आपरेशन को बाधित कर सकता है। यदि कोई गतिशील आकार बदलने से बच नहीं सकता है, तो एक समाधान यह है कि रीहैशिंग के भंडारण ब्लिप से बचने के लिए धीरे-धीरे आकार बदलें - नई टेबल के आकार का 50% पर - और मेमोरी विखंडन से बचने के लिए जो पुराने हैश टेबल के कारण बड़े मेमोरी खंडों के आवंटन रद्द के कारण पुंज संघनन को सक्रियकृत करता है।<ref name="scott03">{{cite journal|journal=All Computer Science and Engineering Research|url=https://users.cs.northwestern.edu/~sef318/docs/hashtables.pdf|doi= 10.7936/K7WD3XXV |date=18 March 2003|first1=Scott|last1=Friedman|first2=Anand|last2=Krishnan|first3=Nicholas|last3=Leidefrost|title=Hash Tables for Embedded and Real-time systems|publisher=[[Washington University in St. Louis]]|via=[[Northwestern University]], Department of Computer Science|archive-url=https://web.archive.org/web/20210609163643/https://users.cs.northwestern.edu/~sef318/docs/hashtables.pdf|archive-date=9 June 2021|access-date=9 November 2021|url-status=live}}</ref>{{rp|pp=2–3}} ऐसी स्थिति में, पुराने हैश टेबल के लिए आवंटित पूर्व मेमोरी खंड को विस्तारित करके रीहैशिंग आपरेशन को क्रमिक रूप से किया जाता है ताकि हैश टेबल के बकेट अपरिवर्तित रहें। परिशोधन पुनर्मूल्यांकन के लिए एक सामान्य दृष्टिकोण में दो हैश फ़ंक्शनों <math>h_\text{old}</math> और <math>h_\text{new}</math> को बनाए रखना सम्मिलित है। नए हैश फ़ंक्शनों के अनुसार बकेट के पदों को दोबारा बदलने की प्रक्रिया को विरलन कहा जाता है, जिसे [[कमांड पैटर्न]] के माध्यम से क्रियान्वित किया जाता है जैसे कि आपरेशनों, <math>\mathrm{Add}(\mathrm{key})</math>, <math>\mathrm{Get}(\mathrm{key})</math> और <math>\mathrm{Delete}(\mathrm{key})</math> को प्रावरण करके कार्यान्वित किया जाता है, <math>\mathrm{Lookup}(\mathrm{key}, \text{command})</math> के जरिए परिवेष्टक इस प्रकार है कि बकेट में प्रत्येक तत्व दोबारा हो जाता है और इसकी प्रक्रिया इस प्रकार होती है:{{r|scott03|p=3}}
+* <math>\mathrm{Table}[h_\text{old}(\mathrm{key})]</math> बकेट को क्लीन करें।
+* <math>\mathrm{Table}[h_\text{new}(\mathrm{key})]</math> बकेट को क्लीन करें।
+* समादेश निष्पादित हो जाता है।
-कुछ हैश तालिका कार्यान्वयन, विशेष रूप से [[वास्तविक समय प्रणाली]] में, हैश तालिका को एक साथ बड़ा करने की कीमत का भुगतान नहीं कर सकते हैं, क्योंकि यह समय-महत्वपूर्ण संचालन को बाधित कर सकता है। यदि कोई डायनेमिक रीसाइज़िंग से बच नहीं सकता है, तो स्टोरेज ब्लिप से बचने के लिए धीरे-धीरे रीसाइज़िंग करना एक समाधान है - सामान्यतः नए तालिका के आकार के 50% पर - रीद्रुतान्वेषण के पर्यंत और फ्रैग्मेंटेशन (अभिकलन) से बचने के लिए जो बड़े पेज के डीलोकेशन के कारण [[मार्क-कॉम्पैक्ट एल्गोरिदम|मार्क-कॉम्पैक्ट कलन विधि]] को ट्रिगर करता है। (कंप्यूटर मेमोरी) पुराने हैश तालिका के कारण होता है।<ref name="scott03">{{cite journal|journal=All Computer Science and Engineering Research|url=https://users.cs.northwestern.edu/~sef318/docs/hashtables.pdf|doi= 10.7936/K7WD3XXV |date=18 March 2003|first1=Scott|last1=Friedman|first2=Anand|last2=Krishnan|first3=Nicholas|last3=Leidefrost|title=Hash Tables for Embedded and Real-time systems|publisher=[[Washington University in St. Louis]]|via=[[Northwestern University]], Department of Computer Science|archive-url=https://web.archive.org/web/20210609163643/https://users.cs.northwestern.edu/~sef318/docs/hashtables.pdf|archive-date=9 June 2021|access-date=9 November 2021|url-status=live}}</ref>{{rp|pp=2–3}} ऐसे स्थिति में, पुराने हैश तालिका के लिए आवंटित पूर्व मेमोरी खंड को विस्तारित करके रीद्रुतान्वेषण संचालन वृद्धिशील रूप से किया जाता है, जैसे कि हैश तालिका की बकेट अपरिवर्तित रहती है। परिशोधित पुनर्वसन के लिए एक सामान्य दृष्टिकोण में दो हैश कार्यों को बनाए रखना सम्मिलित है <math>h_\text{old}</math> और <math>h_\text{new}</math>. नए हैश फंक्शन के अनुसार बकेट के आइटम्स को फिर से हैश करने की प्रक्रिया को क्लीनिंग कहा जाता है, जिसे [[कमांड पैटर्न]] के माध्यम से क्रियान्वित किया जाता है जैसे कि संचालन को एनकैप्सुलेट करके <math>\mathrm{Add}(\mathrm{key})</math>, <math>\mathrm{Get}(\mathrm{key})</math> और <math>\mathrm{Delete}(\mathrm{key})</math> किसी के जरिए <math>\mathrm{Lookup}(\mathrm{key}, \text{command})</math> [[आवरण समारोह]] जैसे कि बकेट में प्रत्येक तत्व को फिर से मिलाया जाता है और इसकी प्रक्रिया में निम्नानुसार सम्मिलित होता है:{{r|scott03|p=3}}
+==== लीनियर हैशिंग ====
-* साफ़ <math>\mathrm{Table}[h_\text{old}(\mathrm{key})]</math> बकेट।
+{{main|लीनियर हैशिंग}}
-* साफ़ <math>\mathrm{Table}[h_\text{new}(\mathrm{key})]</math> बकेट।
-* कमांड निष्पादित हो जाती है।
+[[रैखिक हैशिंग|लीनियर हैशिंग]] हैश टेबल का एक कार्यान्वयन है जो एक समय में एक बकेट टेबल के गतिशील विकास या श्रिंक को सक्षम करता है।<ref>{{cite conference | first=Witold | last=Litwin | title=Linear hashing: A new tool for file and table addressing | year=1980 | pages=212–223 | book-title=Proc. 6th Conference on Very Large Databases|publisher=[[Carnegie Mellon University]] | url=https://www.cs.cmu.edu/afs/cs.cmu.edu/user/christos/www/courses/826-resources/PAPERS+BOOK/linear-hashing.PDF | via=cs.cmu.edu|archive-url=https://web.archive.org/web/20210506233325/http://www.cs.cmu.edu/afs/cs.cmu.edu/user/christos/www/courses/826-resources/PAPERS+BOOK/linear-hashing.PDF|archive-date=6 May 2021|url-status=live|access-date=10 November 2021}}</ref>
-==== रेखीय द्रुतान्वेषण ====
-{{main|Linear hashing}}
-[[रैखिक हैशिंग|रैखिक द्रुतान्वेषण]] हैश तालिका का एक कार्यान्वयन है जो एक समय में एक बकेट तालिका के गतिशील विकास या सिकुड़न को सक्षम करता है।<ref>{{cite conference | first=Witold | last=Litwin | title=Linear hashing: A new tool for file and table addressing | year=1980 | pages=212–223 | book-title=Proc. 6th Conference on Very Large Databases|publisher=[[Carnegie Mellon University]] | url=https://www.cs.cmu.edu/afs/cs.cmu.edu/user/christos/www/courses/826-resources/PAPERS+BOOK/linear-hashing.PDF | via=cs.cmu.edu|archive-url=https://web.archive.org/web/20210506233325/http://www.cs.cmu.edu/afs/cs.cmu.edu/user/christos/www/courses/826-resources/PAPERS+BOOK/linear-hashing.PDF|archive-date=6 May 2021|url-status=live|access-date=10 November 2021}}</ref>
 == प्रदर्शन ==
-एक हैश तालिका का प्रदर्शन कम-विसंगति अनुक्रम उत्पन्न करने में हैश फ़ंक्शन की क्षमता पर निर्भर है। अर्ध-यादृच्छिक संख्या (<math>\sigma</math>) हैश तालिका में प्रविष्टियों के लिए जहां <math>K</math>, <math>n</math> और <math>h(x)</math> कुंजी, बकेटो की संख्या और हैश फ़ंक्शन को इस तरह दर्शाता है <math>\sigma\ =\ h(K)\ \%\ n</math>. यदि हैश फ़ंक्शन समान उत्पन्न करता है <math>\sigma</math> विशिष्ट कुंजियों के लिए (<math>K_1 \ne K_2,\ h(K_1)\ =\ h(K_2)</math>), इसके परिणामस्वरूप टकराव होता है, जिसे विभिन्न तरीकों से निपटाया जाता है। निरंतर समय जटिलता (<math>O(1)</math>) हैश तालिका में संचालन का अनुमान इस शर्त पर लगाया जाता है कि हैश फ़ंक्शन टकराने वाले सूचकांक उत्पन्न नहीं करता है; इस प्रकार, हैश तालिका का प्रदर्शन आनुपातिकता (गणित) है#चुने गए हैश फ़ंक्शन की सूचकांकों को [[सांख्यिकीय फैलाव]] की क्षमता के लिए प्रत्यक्ष आनुपातिकता।<ref name="dijk10">{{cite web|title=Analysing and Improving Hash Table Performance|first=Tom Van|last=Dijk|publisher=[[University of Twente]]|location=[[Netherlands]]|url=https://www.tvandijk.nl/pdf/bscthesis.pdf|access-date=31 December 2021|archive-url=https://web.archive.org/web/20211106094558/http://www.tvandijk.nl/pdf/bscthesis.pdf|archive-date=6 November 2021|url-status=live|year=2010}}</ref>{{rp|1}} हालांकि, ऐसे हैश फ़ंक्शन का निर्माण [[एनपी-कठोरता]] है, ऐसा होने पर, कार्यान्वयन उच्च प्रदर्शन प्राप्त करने में केस-विशिष्ट #Collision रिज़ॉल्यूशन के उपयोग पर निर्भर करता है।{{r|dijk10|p=2}}
+एक हैश टेबल का प्रदर्शन कम-विसंगति अनुक्रम उत्पन्न करने में हैश फ़ंक्शन की क्षमता पर निर्भर है। अर्ध-यादृच्छिक संख्या (<math>\sigma</math>) हैश टेबल में प्रविष्टियों के लिए, जहां <math>K</math>, <math>n</math> और <math>h(x)</math> की, बकेटों की संख्या और हैश फ़ंक्शनों, <math>\sigma\ =\ h(K)\ \%\ n</math> को इस तरह दर्शाता है। यदि हैश फ़ंक्शन समान <math>\sigma</math>, विशिष्ट कीस (<math>K_1 \ne K_2,\ h(K_1)\ =\ h(K_2)</math> के लिए उत्पन्न करता है। इसके परिणामस्वरूप कॉलिडिंग होता है, जिससे विभिन्न तरीकों से निपटा जाता है। सतत समय जटिलता (<math>O(1)</math>) हैश टेबल में आपरेशन का अनुमान इस स्थिति पर माना जाता है कि हैश फ़ंक्शन कलिश़न इंडेक्स उत्पन्न नहीं करता है; इस प्रकार, हैश टेबल का प्रदर्शन इंडेक्सों को फैलाने के लिए चुने गए हैश फ़ंक्शनों की क्षमता के सीधे आनुपातिक है।<ref name="dijk10">{{cite web|title=Analysing and Improving Hash Table Performance|first=Tom Van|last=Dijk|publisher=[[University of Twente]]|location=[[Netherlands]]|url=https://www.tvandijk.nl/pdf/bscthesis.pdf|access-date=31 December 2021|archive-url=https://web.archive.org/web/20211106094558/http://www.tvandijk.nl/pdf/bscthesis.pdf|archive-date=6 November 2021|url-status=live|year=2010}}</ref>{{rp|1}} हालांकि, ऐसे हैश फ़ंक्शन का निर्माण व्यावहारिक रूप से असंभव है, ऐसा होने पर, उच्च प्रदर्शन प्राप्त करने के लिए कार्यान्वयन स्थिति-विशिष्ट कलिश़न समाधान तकनीकों पर निर्भर करता है।{{r|dijk10|p=2}}
-== अनुप्रयोग ==
+== एप्लिकेशन ==
 === साहचर्य सरणियाँ ===
-{{Main|सहयोगी सरणी}}
+{{Main|साहचर्य सरणि}}
-हैश तालिका का उपयोग सामान्यतः कई प्रकार की इन-मेमोरी तालिका को अनुप्रयुक्त करने के लिए किया जाता है। उनका उपयोग साहचर्य सरणियों को अनुप्रयुक्त करने के लिए किया जाता है।<ref name="clrs">{{citation | last1 = Cormen | first1 = Thomas H. | author1-link=Thomas H. Cormen | author2-link = Charles E. Leiserson|last2=Leiserson|first2=Charles E.|author3-link=Ron Rivest|last3=Rivest|first3=Ronald L.|author4-link=Clifford Stein|last4=Stein|first4=Clifford | title = [[Introduction to Algorithms]] | edition = 2nd | year = 2001 | publisher = [[MIT Press]] and [[McGraw-Hill]] | isbn=0-262-03293-7 | chapter = 11 Hash Tables | pages = 221–252}}.</ref>
+हैश टेबल का उपयोग सामान्यतः कई प्रकार की मेमोरी में टेबल को अनुप्रयुक्त करने के लिए किया जाता है। उनका उपयोग साहचर्य सरणियों को अनुप्रयुक्त करने के लिए किया जाता है।<ref name="clrs">{{citation | last1 = Cormen | first1 = Thomas H. | author1-link=Thomas H. Cormen | author2-link = Charles E. Leiserson|last2=Leiserson|first2=Charles E.|author3-link=Ron Rivest|last3=Rivest|first3=Ronald L.|author4-link=Clifford Stein|last4=Stein|first4=Clifford | title = [[Introduction to Algorithms]] | edition = 2nd | year = 2001 | publisher = [[MIT Press]] and [[McGraw-Hill]] | isbn=0-262-03293-7 | chapter = 11 Hash Tables | pages = 221–252}}.</ref>
-=== डाटाबेस इंडेक्सिंग ===
+=== डाटाबेस अनुक्रमण ===
-हैश तालिका का उपयोग [[डिस्क ड्राइव]]-आधारित डेटा संरचनाओं और [[सूचकांक (डेटाबेस)]] (जैसे [[डीबीएम (कंप्यूटिंग)|डीबीएम (अभिकलन)]] में) के रूप में भी किया जा सकता है, हालांकि इन अनुप्रयोगों में [[बी-वृक्ष|बी-ट्री]] अधिक लोकप्रिय हैं।<ref>{{cite web|url=https://edux.pjwstk.edu.pl/mat/262/lec/rW9.htm|title=Indexes and external sorting|archive-url=https://ghostarchive.org/archive/HW0hp|archive-date=26 March 2022|access-date=26 March 2022|publisher=[[:pl:Polsko-Japońska Akademia Technik Komputerowych]]|author= Lech Banachowski}}</ref>
+हैश टेबल का उपयोग [[डिस्क ड्राइव]]-आधारित डेटा स्ट्रक्चरों और [[सूचकांक (डेटाबेस)|इंडेक्स (डेटाबेस)]] (जैसे [[डीबीएम (कंप्यूटिंग)|डीबीएम]] में) के रूप में भी किया जा सकता है, हालांकि इन एप्लिकेशनों में [[बी-वृक्ष|बी-ट्री]] अधिक लोकप्रिय हैं।<ref>{{cite web|url=https://edux.pjwstk.edu.pl/mat/262/lec/rW9.htm|title=Indexes and external sorting|archive-url=https://ghostarchive.org/archive/HW0hp|archive-date=26 March 2022|access-date=26 March 2022|publisher=[[:pl:Polsko-Japońska Akademia Technik Komputerowych]]|author= Lech Banachowski}}</ref>
 === कैश ===
-{{Main|कैश (अभिकलन)}}
+{{Main|कैश}}
+हैश टेबल का उपयोग कैश को अनुप्रयुक्त करने के लिए किया जा सकता है, सहायक डेटा टेबल जिनका उपयोग मुख्य रूप से धीमे मीडिया में संग्रहीत डेटा तक अभिगम को गति देने के लिए किया जाता है। इस एप्लिकेशन में, हैश कलिश़न को दो कलिश़न प्रविष्टियों में से एक को हटाकर नियंत्रित किया जा सकता है - सामान्यतः पुराने पदों को मिटाना जो वर्तमान में टेबल में संग्रहीत है और इसे नए पद के साथ अधिलेखित करना है, इसलिए टेबल में प्रत्येक पद का एक अद्वितीय हैश मान होता है।<ref>{{Cite journal|last1=Zhong|first1=Liang|last2=Zheng|first2=Xueqian|last3=Liu|first3=Yong|last4=Wang|first4=Mengting|last5=Cao|first5=Yang|date=February 2020|title=Cache hit ratio maximization in device-to-device communications overlaying cellular networks|url=http://dx.doi.org/10.23919/jcc.2020.02.018|journal=China Communications|volume=17|issue=2|pages=232–238|doi=10.23919/jcc.2020.02.018|s2cid=212649328|issn=1673-5447}}</ref><ref>{{cite web|url=https://www.linuxjournal.com/article/7105|publisher=[[Linux Journal]]|access-date=16 April 2022|date=1 January 2004|title=Understanding Caching|first=James|last=Bottommley|url-status=live|archive-url=https://web.archive.org/web/20201204195114/https://www.linuxjournal.com/article/7105|archive-date=4 December 2020}}</ref>
-हैश तालिका का उपयोग कैश (अभिकलन) को अनुप्रयुक्त करने के लिए किया जा सकता है, सहायक डेटा तालिका जिनका उपयोग मुख्य रूप से धीमे मीडिया में संग्रहीत डेटा तक पहुंच को गति देने के लिए किया जाता है। इस एप्लिकेशन में, दो टकराने वाली प्रविष्टियों में से एक को हटाकर हैश टकराव को नियंत्रित किया जा सकता है - सामान्यतः पुराने आइटम को मिटा दिया जाता है जो वर्तमान में तालिका में संग्रहीत होता है और इसे नए आइटम के साथ अधिलेखित कर देता है, इसलिए तालिका में प्रत्येक आइटम का एक अद्वितीय हैश मान होता है।<ref>{{Cite journal|last1=Zhong|first1=Liang|last2=Zheng|first2=Xueqian|last3=Liu|first3=Yong|last4=Wang|first4=Mengting|last5=Cao|first5=Yang|date=February 2020|title=Cache hit ratio maximization in device-to-device communications overlaying cellular networks|url=http://dx.doi.org/10.23919/jcc.2020.02.018|journal=China Communications|volume=17|issue=2|pages=232–238|doi=10.23919/jcc.2020.02.018|s2cid=212649328|issn=1673-5447}}</ref><ref>{{cite web|url=https://www.linuxjournal.com/article/7105|publisher=[[Linux Journal]]|access-date=16 April 2022|date=1 January 2004|title=Understanding Caching|first=James|last=Bottommley|url-status=live|archive-url=https://web.archive.org/web/20201204195114/https://www.linuxjournal.com/article/7105|archive-date=4 December 2020}}</ref>
+=== सेट ===
+{{main|सेट डेटा संरचना }}
-=== समूह ===
+सेट डेटा स्ट्रक्चर के कार्यान्वयन में हैश टेबल का उपयोग किया जा सकता है, जो बिना किसी विशेष क्रम के अद्वितीय मानों को संग्रहीत कर सकता है; बकेट का उपयोग सामान्यतः तत्व पुनर्प्राप्ति के बजाय संग्रह में मानों की सदस्यता का परीक्षण करने के लिए किया जाता है।<ref>{{cite web|url=https://userweb.cs.txstate.edu/~js236/201412/cs5301/week13.pdf|title=Set & Hash Tables|author=Jill Seaman|archive-url=https://web.archive.org/web/20220401134706/https://userweb.cs.txstate.edu/~js236/201412/cs5301/week13.pdf|archive-date=April 1, 2022|access-date=26 March 2022|publisher=[[Texas State University]]|date=2014|url-status=bot: unknown}}</ref>
-{{main|समूह डेटा संरचना }}
-सेट डेटा संरचना के कार्यान्वयन में हैश तालिका का उपयोग किया जा सकता है, जो बिना किसी विशेष क्रम के अद्वितीय मानों को संग्रहीत कर सकता है; सेट का उपयोग सामान्यतः तत्व पुनर्प्राप्ति के बजाय संग्रह में मूल्य की सदस्यता का परीक्षण करने के लिए किया जाता है।<ref>{{cite web|url=https://userweb.cs.txstate.edu/~js236/201412/cs5301/week13.pdf|title=Set & Hash Tables|author=Jill Seaman|archive-url=https://web.archive.org/web/20220401134706/https://userweb.cs.txstate.edu/~js236/201412/cs5301/week13.pdf|archive-date=April 1, 2022|access-date=26 March 2022|publisher=[[Texas State University]]|date=2014|url-status=bot: unknown}}</ref>
+=== ट्रांसपोजीशन टेबल ===
+{{Main|ट्रांसपोजीशन टेबल
+}}
-=== ट्रांसपोजिशन तालिका ===
+एक जटिल हैश टेबल के लिए एक ट्रांसपोजीशन टेबल-1 जो किये गए प्रत्येक अनुभाग के विषय में जानकारी संग्रहीत करती है।<ref>{{Cite web|title=Transposition Table - Chessprogramming wiki|url=https://www.chessprogramming.org/Transposition_Table|website=chessprogramming.org|access-date=2020-05-01|archive-date=February 14, 2021|archive-url=https://web.archive.org/web/20210214110941/https://www.chessprogramming.org/Transposition_Table|url-status=live}}</ref>
-{{Main|Transposition table}}
-एक जटिल हैश तालिका के लिए एक स्थानान्तरण तालिका जो खोजे गए प्रत्येक अनुभाग के बारे में जानकारी संग्रहीत करती है।<ref>{{Cite web|title=Transposition Table - Chessprogramming wiki|url=https://www.chessprogramming.org/Transposition_Table|website=chessprogramming.org|access-date=2020-05-01|archive-date=February 14, 2021|archive-url=https://web.archive.org/web/20210214110941/https://www.chessprogramming.org/Transposition_Table|url-status=live}}</ref>
 == कार्यान्वयन ==
-कई प्रोग्रामिंग लैंग्वेज हैश तालिका की कार्यक्षमता प्रदान करती हैं, या तो अंतर्निहित साहचर्य सरणियों के रूप में या मानक लाइब्रेरी मॉड्यूल के रूप में।
+कई प्रोग्रामिंग भाषाएं हैश टेबल की कार्यक्षमता प्रदान करती हैं, या तो अंतर्निहित सहयोगी सरणी के रूप में या मानक लाइब्रेरी मॉड्यूल के रूप में प्रदान करती हैं।
-[[जावास्क्रिप्ट]] में, 7 आदिम डेटा प्रकारों को छोड़कर प्रत्येक मान को एक ऑब्जेक्ट कहा जाता है, जो हैश मानचित्र के लिए कुंजी के रूप में पूर्णांक, स्ट्रिंग्स, या गारंटीकृत-अद्वितीय प्रतीक आदिम मानों का उपयोग करता है। ईसीएमएस्क्रिप्ट 6 भी जोड़ा गया <code>Map</code> और <code>Set</code> डेटा संरचनाएं।<ref>{{cite web |title=JavaScript data types and data structures - JavaScript {{!}} MDN |url=https://developer.mozilla.org/en-US/docs/Web/JavaScript/Data_structures#objects |website=developer.mozilla.org |access-date=24 July 2022}}</ref>
+[[जावास्क्रिप्ट]] में, एक "ऑब्जेक्ट" की-मान युग्म (जिन्हें "गुण" कहा जाता है) का एक परिवर्तनशील संग्रह है, जहां प्रत्येक की या तो एक श्रृंखला या एक गारंटीकृत-अद्वितीय "प्रतीक" है; किसी अन्य मान को, जब की के रूप में उपयोग किया जाता है, तो पहले उसे एक श्रृंखला से जोड़ा जाता है। सात "आदिम" डेटा प्रकारों के अतिरिक्त, जावास्क्रिप्ट में प्रत्येक मान एक ऑब्जेक्ट है।<ref>{{cite web |title=JavaScript data types and data structures - JavaScript {{!}} MDN |url=https://developer.mozilla.org/en-US/docs/Web/JavaScript/Data_structures#objects |website=developer.mozilla.org |access-date=24 July 2022}}</ref>ईसीएमएस्क्रिप्ट 2015 ने <code>Map</code> डेटा स्ट्रक्चर भी जोड़ी, जो यादृच्छिक मानों को की के रूप में स्वीकार करती है।
-[[सी ++ 11]] सम्मिलित हैं <code>[[unordered map (C++)|unordered_map]]</code> Template_(C%2B%2B).<ref>{{cite web|url=http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3690.pdf|title=Programming language C++ - Technical Specification|access-date=8 February 2022|publisher=[[International Organization for Standardization]]|archive-url=https://web.archive.org/web/20220121061142/http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2013/n3690.pdf|archive-date=21 January 2022|pages=812–813}}</ref>
-Go_(programming_language) का बिल्ट-इन <code>map</code> एक हैश तालिका को प्रिमिटिव_डेटा_टाइप के रूप में अनुप्रयुक्त करता है।<ref>{{cite web|url=https://go.dev/ref/spec#Map_types|title=The Go Programming Language Specification|website=go.dev|access-date=January 1, 2023|url-status=live}}</ref>
+[[सी ++ 11]] में यादृच्छिक प्रकार की कीस और मानों को संग्रहीत करने के लिए अपनी मानक लाइब्रेरी में <code>[[unordered map (C++)|unordered_map]]</code> सम्मिलित हैं।<ref>{{cite web|url=http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3690.pdf|title=Programming language C++ - Technical Specification|access-date=8 February 2022|publisher=[[International Organization for Standardization]]|archive-url=https://web.archive.org/web/20220121061142/http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2013/n3690.pdf|archive-date=21 January 2022|pages=812–813}}</ref>
-[[जावा (प्रोग्रामिंग भाषा)]] प्रोग्रामिंग लैंग्वेज में सम्मिलित है <code>HashSet</code>, <code>HashMap</code>, <code>LinkedHashSet</code>, और <code>LinkedHashMap</code> जावा संग्रह में जेनरिक।<ref>{{cite web|url=https://docs.oracle.com/javase/tutorial/collections/implementations/index.html|title=Lesson: Implementations (The Java™ Tutorials > Collections)|website=docs.oracle.com|access-date=April 27, 2018|url-status=live|archive-url=https://web.archive.org/web/20170118041252/https://docs.oracle.com/javase/tutorial/collections/implementations/index.html|archive-date=January 18, 2017|df=mdy-all}}</ref>
-पायथन (प्रोग्रामिंग लैंग्वेज) का बिल्ट-इन <code>dict</code> एक हैश तालिका को प्रिमिटिव_डेटा_टाइप के रूप में अनुप्रयुक्त करता है।<ref>{{cite journal|journal=[[Journal of Physics: Conference Series]]|first1=Juan|last1=Zhang|first2=Yunwei|last2=Jia|title=Redis rehash optimization based on machine learning|volume=1453|year=2020|issue=1 |page=3|doi=10.1088/1742-6596/1453/1/012048 |bibcode=2020JPhCS1453a2048Z |s2cid=215943738 |doi-access=free}}</ref>
+गो का अंतर्निर्मित <code>map</code> एक प्रकार के रूप में हैश टेबल अनुप्रयुक्त करता है।<ref>{{cite web|url=https://go.dev/ref/spec#Map_types|title=The Go Programming Language Specification|website=go.dev|access-date=January 1, 2023|url-status=live}}</ref>
-[[रूबी (प्रोग्रामिंग भाषा)]] की बिल्ट-इन <code>Hash</code> रूबी 2.4 के बाद से विवृत पताभिगमन मॉडल का उपयोग करता है।<ref>{{cite web|url=https://blog.heroku.com/ruby-2-4-features-hashes-integers-rounding#hash-changes|title=Ruby 2.4 Released: Faster Hashes, Unified Integers and Better Rounding|author=Jonan Scheffler|date=December 25, 2016|website=heroku.com|access-date=July 3, 2019|df=mdy-all|archive-date=July 3, 2019|archive-url=https://web.archive.org/web/20190703145530/https://blog.heroku.com/ruby-2-4-features-hashes-integers-rounding#hash-changes|url-status=live}}</ref>
-[[जंग (प्रोग्रामिंग भाषा)]] प्रोग्रामिंग लैंग्वेज में सम्मिलित है <code>HashMap</code>, <code>HashSet</code> रस्ट स्टैंडर्ड लाइब्रेरी के हिस्से के रूप में। <ref>{{cite web|url=https://doc.rust-lang.org/std/index.html|title=doc.rust-lang.org|access-date=December 14, 2022|url-status=live|archive-url=https://web.archive.org/web/20221208155205/https://doc.rust-lang.org/std/index.html|archive-date=December 8, 2022|df=mdy-all}}
+[[जावा (प्रोग्रामिंग भाषा)|जावा प्रोग्रामिंग भाषा]] में <code>HashSet</code>, <code>HashMap</code>, <code>LinkedHashSet</code> और <code>LinkedHashMap</code> वर्गीय संग्रह सम्मिलित है।<ref>{{cite web|url=https://docs.oracle.com/javase/tutorial/collections/implementations/index.html|title=Lesson: Implementations (The Java™ Tutorials > Collections)|website=docs.oracle.com|access-date=April 27, 2018|url-status=live|archive-url=https://web.archive.org/web/20170118041252/https://docs.oracle.com/javase/tutorial/collections/implementations/index.html|archive-date=January 18, 2017|df=mdy-all}}</ref>
+पायथन का अंतर्निर्मित <code>dict</code> एक हैश टेबल को एक प्रकार के रूप में अनुप्रयुक्त करता है।<ref>{{cite journal|journal=[[Journal of Physics: Conference Series]]|first1=Juan|last1=Zhang|first2=Yunwei|last2=Jia|title=Redis rehash optimization based on machine learning|volume=1453|year=2020|issue=1 |page=3|doi=10.1088/1742-6596/1453/1/012048 |bibcode=2020JPhCS1453a2048Z |s2cid=215943738 |doi-access=free}}</ref>
+[[रूबी (प्रोग्रामिंग भाषा)|रूबी]] का अंतर्निर्मित <code>Hash</code> रूबी 2.4 के बाद से ओपन एड्रेसिंग पैटर्न का उपयोग करता है।<ref>{{cite web|url=https://blog.heroku.com/ruby-2-4-features-hashes-integers-rounding#hash-changes|title=Ruby 2.4 Released: Faster Hashes, Unified Integers and Better Rounding|author=Jonan Scheffler|date=December 25, 2016|website=heroku.com|access-date=July 3, 2019|df=mdy-all|archive-date=July 3, 2019|archive-url=https://web.archive.org/web/20190703145530/https://blog.heroku.com/ruby-2-4-features-hashes-integers-rounding#hash-changes|url-status=live}}</ref>
+रस्ट प्रोग्रामिंग भाषा में रस्ट मानक लाइब्रेरी के भाग के रूप में <code>HashMap</code>, <code>HashSet</code> सम्मिलित हैं।<ref>{{cite web|url=https://doc.rust-lang.org/std/index.html|title=doc.rust-lang.org|access-date=December 14, 2022|url-status=live|archive-url=https://web.archive.org/web/20221208155205/https://doc.rust-lang.org/std/index.html|archive-date=December 8, 2022|df=mdy-all}}
 test</ref>
@@ Line 231: / Line 257: @@
 {{div col}}
 * राबिन-कार्प स्ट्रिंग सर्च एल्गोरिदम
-* [[स्थिर हैशिंग]]
+* [[कंसिस्टेंट हैशिंग]]
-* [[लगातार हैशिंग]]
+* [[स्टेबल हैशिंग]]
-* [[विस्तार योग्य हैशिंग]]
+* [[एक्सटेन्डिब्ले हैशिंग]]
-* [[आलसी विलोपन]]
+* [[लेज़ी विलोपन]]
 * [[पियर्सन हैशिंग]]
 * फोटो डीएनए
-* [[डेटा संरचना खोजें]]
+* [[डेटा स्ट्रक्चर अन्वेषण]]
-* समवर्ती हैश तालिका
+* समवर्ती हैश टेबल
-* [[ब्लूम फिल्टर]]
+* [[प्रफुल्लन फ़िल्टर]]
-* [[हैश ऐरे मैप्ड ट्राई]]
+* [[हैश सरणी मैप ट्राई]]
-* [[वितरित हैश तालिका]]
+* [[डिस्ट्रिब्यूटेड हैश टेबल]]
 {{div col end}}
@@ Line 264: / Line 290: @@
 {{Data structures}}
 {{Authority control}}
-[[Category: उदाहरण सी कोड वाले लेख]] [[Category: हैशिंग|*]] [[Category: हैश आधारित डेटा संरचनाएं]]
-[[Category: Machine Translated Page]]
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
+[[Category:Articles with invalid date parameter in template]]
+[[Category:CS1]]
+[[Category:CS1 maint]]
+[[Category:Collapse templates]]
+[[Category:Commons category link is locally defined]]
 [[Category:Created On 14/02/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Missing redirects]]
+[[Category:Multi-column templates]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists]]
+[[Category:Pages using div col with small parameter]]
+[[Category:Pages with script errors]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Sidebars with styles needing conversion]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates generating microformats]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that are not mobile friendly]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:Templates using under-protected Lua modules]]
+[[Category:Use mdy dates from January 2013]]
+[[Category:Webarchive template wayback links]]
+[[Category:Wikipedia fully protected templates|Div col]]
+[[Category:Wikipedia metatemplates]]
+[[Category:उदाहरण सी कोड वाले लेख]]
+[[Category:हैश आधारित डेटा संरचनाएं]]
+[[Category:हैशिंग|*]]

Anonymous

Search

हैश टेबल: Difference between revisions

Latest revision as of 14:13, 3 August 2023

इतिहास

संक्षिप्त विवरण

लोड फैक्टर

हैश फ़ंक्शन

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

विभाजन द्वारा हैशिंग

गुणन द्वारा हैशिंग

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

कलिश़न संकल्प

सेपरेट चेनिंग

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

कैशिंग और संदर्भ का स्थान

ओपन एड्रेसिंग

कैशिंग और संदर्भ का स्थान

ओपन एड्रेसिंग पर आधारित अन्य कलिश़न समाधान तकनीक

कलेसेड हैशिंग

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

हॉपस्कॉच हैशिंग

रॉबिन हुड हैशिंग

गतिशील आकार परिवर्तन

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

सभी को एक साथ पुनः दोहराने के विकल्प

लीनियर हैशिंग

प्रदर्शन

एप्लिकेशन

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

डाटाबेस अनुक्रमण

कैश

सेट

ट्रांसपोजीशन टेबल

कार्यान्वयन

यह भी देखें

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories