रैखिक हैशिंग

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

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

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

एल्गोरिदम विवरण

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

हैश फ़ंक्शन

कुंजी के साथ रिकॉर्ड तक पहुंचने के लिए $c$, हैश फ़ंक्शंस का एक परिवार, जिसे कहा जाता है कुंजी पर सामूहिक रूप से एक गतिशील हैश फ़ंक्शन लागू किया जाता है $c$. किसी भी समय, अधिकतम दो हैश फ़ंक्शन $h_{i}$ और $h_{i+1}$ उपयोग किया जाता है। एक ठेठ उदाहरण डिवीजन मॉड्यूलो x ऑपरेशन का उपयोग करता है। यदि बाल्टियों की मूल संख्या है $N$, तो हैश फ़ंक्शंस का परिवार है

$h_{i}(c)\mapsto c{\pmod {N\cdot 2^{i}}}$

फ़ाइल विस्तार

जैसे-जैसे फ़ाइल सम्मिलन के माध्यम से बढ़ती है, यह विभाजन के माध्यम से शानदार ढंग से विस्तारित होती है एक बाल्टी का दो बाल्टी में। बाल्टियों के फूटने का क्रम पूर्व निर्धारित है। फागिन की एक्सटेंडिबल हैशिंग जैसी योजनाओं में यह मूलभूत अंतर है। दो नई बाल्टियों के लिए, हैश फ़ंक्शन $h_{i}$ से प्रतिस्थापित कर दिया गया है

$h_{i+1}$. विभाजित की जाने वाली बाल्टी की संख्या का हिस्सा है

फ़ाइल स्थिति और स्प्लिट पॉइंटर कहा जाता है $s$.

विभाजित नियंत्रण

जब भी बाल्टी ओवरफ्लो हो जाती है तो स्प्लिट किया जा सकता है। यह एक अनियंत्रित विभाजन है. वैकल्पिक रूप से, फ़ाइल लोड फ़ैक्टर की निगरानी कर सकती है और जब भी विभाजित होती है लोड फैक्टर एक सीमा से अधिक है। यह नियंत्रित बंटवारा था.

संबोधन

एड्रेसिंग फ़ाइल स्थिति पर आधारित है, जिसमें स्प्लिट पॉइंटर शामिल है $s$ और स्तर $l$. यदि स्तर है $l$, फिर हैश कार्य करता है उपयोग किये जाते हैं $h_{l}$ और $h_{l+1}$.

हैशिंग कुंजी के लिए एलएच एल्गोरिदम $c$ है

$a:=h_{l}(c)$ अगर $a<s:a:=h_{l+1}(c)$

विभाजन

जब एक बाल्टी को विभाजित किया जाता है, तो विभाजित सूचक और संभवतः स्तर के अनुसार अद्यतन किया जाता है

$s:=s+1$ अगर $s\geq N\times 2^{l}$: $l+=1,s=0$

फ़ाइल संकुचन

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

फ़ाइल स्थिति गणना

फ़ाइल स्थिति में स्प्लिट पॉइंटर होता है $s$ और स्तर $l$. यदि मूल फ़ाइल से प्रारंभ हुई $N=1$ बाल्टियाँ, फिर बाल्टियों की संख्या

$n$ और फ़ाइल स्थिति के माध्यम से संबंधित हैं

$n=2^{l}+s$

एलएच*

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

भाषा प्रणालियों में अपनाना

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

डेटाबेस सिस्टम में अपनाना

लीनियर हैशिंग का उपयोग बर्कले डीबी | बर्कले डेटाबेस सिस्टम (बीडीबी) में किया जाता है, जो बदले में एसीएम लेख के संचार से प्राप्त सी कार्यान्वयन का उपयोग करके कई सॉफ्टवेयर सिस्टम द्वारा उपयोग किया जाता है और पहली बार 1988 में एस्मंड पिट द्वारा यूज़नेट पर प्रकाशित किया गया था।

बाहरी संबंध

• TommyDS, C implementation of a Linear Hashtable
• An in Memory Go Implementation with Explanation
• A C++ Implementation of Linear Hashtable which Supports Both Filesystem and In-Memory storage

यह भी देखें

• विस्तार योग्य हैशिंग
• लगातार हैशिंग
• सर्पिल हैशिंग

श्रेणी:खोज एल्गोरिदम श्रेणी:हैशिंग