रैखिक हैशिंग

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

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

लीनियर हैशिंग को एक स्केलेबल वितरित डेटा संरचना, LH* में भी बनाया गया है। LH* में, प्रत्येक बकेट अलग सर्वर पर रहता है। असफल बकेट की उपस्थिति में डेटा उपलब्धता प्रदान करने के लिए LH* का विस्तार किया गया है। LH और 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$ के लिए LH एल्गोरिथ्म है

$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$

LH*

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

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

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

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

रैखिक हैशिंग का उपयोग बर्कले डेटाबेस सिस्टम (बीडीबी) में किया जाता है, जो बदले में कई सॉफ्टवेयर सिस्टम द्वारा उपयोग किया जाता है, सीएसीएम लेख से प्राप्त C कार्यान्वयन का उपयोग करके और पहली बार 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

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