हैश टेबल

Not to be confused with हैश सूची or हैश ट्री.

"रीहैश" redirects here. For साउथ पार्क प्रकरण, see रीहैश (साउथ पार्क).

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

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

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

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

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

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

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

इतिहास

हैशिंग का विचार अलग-अलग स्थानों पर स्वतंत्र रूप से उत्पन्न हुआ। जनवरी 1953 में, हंस पीटर लुहान ने एक आंतरिक आईबीएम ज्ञापन लिखा जिसमें चेनिंग के साथ हैशिंग का उपयोग किया गया था। ओपन एड्रेसिंग को बाद में लुहान के लेख पर ए.डी. लिन्ह रचना द्वारा प्रस्तावित किया गया था। लगभग उसी समय, जीन अमडाहल, ऐलेन एम. मैकग्रा, नथानिएल रोचेस्टर आईबीएम सर्च के आर्थर सैमुअल ने आईबीएम 701 असेंबलर के लिए हैशिंग अनुप्रयुक्त किया। लीनियर प्रोबिंग के साथ ओपन एड्रेसिंग का श्रेय अमदहल को दिया जाता है, हालांकि एंड्री एर्शोव का स्वतंत्र रूप से एक ही विचार था। "ओपन एड्रेसिंग" शब्द डब्ल्यू वेस्ले पीटरसन द्वारा अपने लेख पर सृष्ट किया गया था जो बड़ी फाइलों में सर्च की समस्या पर चर्चा करता है।

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

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

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

हैश टेबल का उपयोग सामान्यतः सेट को अनुप्रयुक्त करने के लिए किया जाता है, प्रत्येक कुंजी के लिए संग्रहीत मान को छोड़कर और केवल यह ट्रैक करके कि कुंजी उपस्थित है या नहीं।

लोड फैक्टर

एक लोड फैक्टर $\alpha$ हैश टेबल का एक क्रिटिकल स्टेटिस्टिक है और इसे निम्नानुसार परिभाषित किया गया है:

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

जहाँ

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

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

हैश फ़ंक्शन

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

एक आदर्श हैश फ़ंक्शन $h$ एक इंजेक्टिव फंक्शन के रूप में परिभाषित किया गया है जैसे कि प्रत्येक तत्व $x$ में $S$ एक अद्वितीय मान ${0,...,m-1}$ पर मैप करता है। यदि सभी कुंजियाँ समय से पहले ज्ञात हों तो एक आदर्श हैश फ़ंक्शन बनाया जा सकता है।

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

पूर्णांक ब्रह्मांड धारणा में उपयोग की जाने वाली हैशिंग की योजनाओं में विभाजन द्वारा हैशिंग, गुणन द्वारा हैशिंग, यूनिवर्सल हैशिंग, डायनामिक परफेक्ट हैशिंग और स्टैटिक परफेक्ट हैशिंग सम्मिलित हैं। हालाँकि, विभाजन द्वारा हैशिंग सामान्यतः उपयोग की जाने वाली योजना है।

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

विभाजन द्वारा हैशिंग की योजना इस प्रकार है:

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

जहाँ $M$ का हैश संकलन $x\in S$ और $n$ टेबल का आकार है।

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

गुणन द्वारा हैशिंग की योजना इस प्रकार है:

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

जहाँ $A$ एक वास्तविक-मूल्यवान स्थिरांक है। गुणन द्वारा हैशिंग का एक लाभ यह है कि $m$ आलोचनात्मक नहीं है। हालांकि कोई भी मान $A$ एक हैश फ़ंक्शन उत्पन्न करता है, डोनाल्ड नुथ बहुमुल्य अनुपात का उपयोग करने का सुझाव देते हैं।

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

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

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

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

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

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

See also: 2-चॉइस हैशिंग

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

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

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

बकेट सरणी में प्रमुख रिकॉर्ड के साथ विलग चेनिंग द्वारा हैश कलिश़न।

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

यदि तत्व संख्यात्मक या शाब्दिक रूप से तुलनीय है और कुल क्रम को बनाए रखते हुए सूची में डाला गया है, तो इसके परिणामस्वरूप असफल सर्चों का तीव्रता से समापन होता है।

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

यदि कुंजियाँ क्रमबद्ध हैं, तो "सेल्फ-ओर्गनइजिंग" अवधारणाओं का उपयोग करना कुशल हो सकता है जैसे कि सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री का उपयोग करना, जिसके माध्यम से सैद्धांतिक सबसे खराब स्थिति $O(\log {n})$ को नीचे लाया जा सकता है, हालाँकि यह अतिरिक्त जटिलताएँ प्रस्तुत करता है।

डायनामिक परफेक्ट हैशिंग में, गारंटीयुक्त लुकअप $O(1)$ को सबसे खराब स्थिति में जटिलता को कम करने के लिए दो-स्तरीय टेबलों का उपयोग किया जाता है। इस तकनीक में, $k$ प्रविष्टियों को पूर्ण टेबलों के रूप में व्यवस्थित किया गया है, $k^{2}$ स्लॉट लगातार सबसे खराब स्थिति वाले लुकअप समय और प्रविष्टि समय और प्रविष्टि के लिए कम परिशोधन समय प्रदान करते हैं। एक अध्ययन से पता चलता है कि हैवी लोड के अंतर्गत मानक लिंक्ड सूची विधि की तुलना में सरणी-आधारित सेपरेट चेनिंग 97% अधिक प्रदर्शन करने वाली होती है।

प्रत्येक बकेट के लिए फ्यूज़न ट्री का उपयोग करने जैसी तकनीकों के परिणामस्वरूप उच्च संभावना वाले सभी कार्यों के लिए सतत समय मिलता है।

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

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

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

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

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

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

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

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

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

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

ओपन एड्रेसिंग का प्रदर्शन सेपरेट चेनिंग की तुलना में धीमा हो सकता है क्योंकि लोड फैक्टर $\alpha$ दृष्टिकोण 1, होने पर प्रोबिंग अनुक्रम बढ़ जाता है। पूर्णतया भरित टेबल की स्थिति में, यदि लोड फैक्टर 1 तक पहुंच जाता है, तो प्रोबिंग का परिणाम अनंत लूप में होता है।क्लस्टरिंग से बचने के लिए हैश फ़ंक्शन की पूर्ण टेबल में तत्वों को समान रूप से वितरित करने की क्षमता है, क्योंकि क्लस्टर के गठन के परिणामस्वरूप सर्च समय में वृद्धि होगी।

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

चूंकि स्लॉट सतत स्थानों में स्थित हैं, लीनियर प्रोबिंग से सीपीयू कैश का अपेक्षाकृत अधिक उपयोग हो सकता है क्योंकि संदर्भों की स्थानीयता कम मेमोरी विलंबता के कारण होती है।

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

Main article: कलेसेड हैशिंग

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

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

Main article: कुक्कू हैशिंग

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

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

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

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

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

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

रॉबिन हुड हैशिंग एक ओपन एड्रेसिंग आधारित कलिश़न समाधान कलन विधि है; कलिश़नों को उस तत्व के विस्थापन को अनुकूल बनाकर हल किया जाता है, जो अपने "होम स्थान" से सबसे दूर - या सबसे लंबी प्रोबिंग अनुक्रम लंबाई (PSL) है, अर्थात, वह बकेट जिसमें पद को हैश किया गया था। हालांकि रॉबिन हुड हैशिंग सैद्धांतिक सर्च लागत में परिवर्तन नहीं होता है, परन्तु यह बकेट पर पदों के संभाव्यता वितरण के विचरण को महत्वपूर्ण रूप से प्रभावित करता है, अर्थात हैश टेबल में क्लस्टर गठन से व्यवहार करना है। रॉबिन हुड हैशिंग का उपयोग करने वाली हैश टेबल के भीतर प्रत्येक नोड को एक अतिरिक्त पीएसएल मान संग्रहीत करने के लिए संवर्धित किया जाना चाहिए। मान लीजिए कि $x$ सम्मिलित करने के लिए कुंजी है, $x.psl$ की (वृद्धिशील) पीएसएल लंबाई $x$, $T$ हैश टेबल और $j$ इंडेक्स है, सम्मिलन प्रक्रिया इस प्रकार है:

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

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

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

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

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

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

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

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

रेखीय हैशिंग

Main article: रैखिक हैशिंग

लीनियर हैशिंग हैश टेबल का एक कार्यान्वयन है जो एक समय में एक बकेट टेबल के गतिशील विकास या संकुचन को सक्षम करता है।

प्रदर्शन

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

एप्लिकेशन

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

Main article: साहचर्य सरणि

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

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

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

कैश

Main article: कैश

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

सेट

Main article: सेट डेटा संरचना

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

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

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

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

कार्यान्वयन

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

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

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

गो का अंतर्निर्मित map एक प्रकार के रूप में हैश टेबल अनुप्रयुक्त करता है।

जावा प्रोग्रामिंग भाषा में HashSet, HashMap, LinkedHashSet और LinkedHashMap वर्गीय संग्रह सम्मिलित है।

पायथन का अंतर्निर्मित dict एक हैश टेबल को एक प्रकार के रूप में अनुप्रयुक्त करता है।

रूबी का अंतर्निर्मित Hash रूबी 2.4 के बाद से ओपन एड्रेसिंग पैटर्न का उपयोग करता है।

रस्ट प्रोग्रामिंग भाषा में रस्ट मानक लाइब्रेरी के भाग के रूप में HashMap, HashSet सम्मिलित हैं।

यह भी देखें

• राबिन-कार्प स्ट्रिंग सर्च एल्गोरिदम
• कंसिस्टेंट हैशिंग
• स्टेबल हैशिंग
• एक्सटेन्डिब्ले हैशिंग
• लेज़ी विलोपन
• पियर्सन हैशिंग
• फोटो डीएनए
• डेटा स्ट्रक्चर अन्वेषण
• समवर्ती हैश टेबल
• प्रफुल्लन फ़िल्टर
• हैश सरणी मैप ट्राई
• डिस्ट्रिब्यूटेड हैश टेबल

अग्रिम पठन

• 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