हैश टेबल

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: सहयोगी सरणी

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

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

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

कैश

Main article: कैश (अभिकलन)

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

समूह

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

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

स्थानान्तरण तालिका

Main article: स्थानान्तरण तालिका

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

कार्यान्वयन

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

जावास्क्रिप्ट में, एक "विषय" कुंजी-मान युग्म (जिन्हें "गुण" कहा जाता है) का एक परिवर्तनशील संग्रह है, जहां प्रत्येक कुंजी या तो एक श्रृंखला या एक गारंटीकृत-अद्वितीय "प्रतीक" है; किसी अन्य मान को, जब कुंजी के रूप में उपयोग किया जाता है, तो पहले उसे एक श्रृंखला से जोड़ा जाता है। सात "आदिम" डेटा प्रकारों के अतिरिक्त, जावास्क्रिप्ट में प्रत्येक मान एक उद्देश्य है।ईसीएमएस्क्रिप्ट 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