हैश टेबल

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)

File:Hash table 3 1 1 0 1 0 0 SP.svg

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

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

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

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

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

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

इतिहास

हैशिंग का विचार अलग-अलग स्थानों पर स्वतंत्र रूप से उत्पन्न हुआ। जनवरी 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$ एक वास्तविक-मूल्यवान स्थिरांक है। गुणन द्वारा हैशिंग का एक लाभ यह है कि