रैखिक हैशिंग

लीनियर हैशिंग (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$बकेट से प्रारंभ हुई है, तो बकेट ${\displaystyle }$