हैश टेबल

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

"रीहैश" redirects here. For दक्षिण पार्क प्रकरण, see रीहैश (दक्षिण पार्क).

Hash table
Type	Unordered associative array
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$