रैखिक हैशिंग: Difference between revisions

From Vigyanwiki
Line 44: Line 44:
</ref> दो नई बाल्टियों के लिए, हैश फ़ंक्शन <math>h_i</math> को <math>h_{i+1}</math> से बदल दिया गया है। विभाजित की जाने वाली बकेट की संख्या फ़ाइल स्थिति का हिस्सा है और इसे स्प्लिट पॉइंटर <math>s</math> कहा जाता है।<ref name="LMS" />
</ref> दो नई बाल्टियों के लिए, हैश फ़ंक्शन <math>h_i</math> को <math>h_{i+1}</math> से बदल दिया गया है। विभाजित की जाने वाली बकेट की संख्या फ़ाइल स्थिति का हिस्सा है और इसे स्प्लिट पॉइंटर <math>s</math> कहा जाता है।<ref name="LMS" />
===विभाजित नियंत्रण===
===विभाजित नियंत्रण===
जब भी बाल्टी ओवरफ्लो हो जाती है तो स्प्लिट किया जा सकता है। यह एक अनियंत्रित विभाजन है.
जब भी कोई बाल्टी ओवरफ्लो हो जाती है तो विभाजन किया जा सकता है। यह एक अनियंत्रित बंटवारा है. वैकल्पिक रूप से, फ़ाइल लोड फ़ैक्टर की निगरानी कर सकती है और जब भी लोड फ़ैक्टर एक सीमा से अधिक हो जाता है तो एक विभाजन करता है। यह नियंत्रित बंटवारा था।<ref name=LMS/>
वैकल्पिक रूप से, फ़ाइल लोड फ़ैक्टर की निगरानी कर सकती है और जब भी विभाजित होती है
===एड्रेसिंग===
लोड फैक्टर एक सीमा से अधिक है। यह नियंत्रित बंटवारा था.<ref name=LMS/>
एड्रेसिंग फ़ाइल स्थिति पर आधारित है, जिसमें विभाजित सूचक <math>s</math> और स्तर <math>l</math> शामिल है। यदि स्तर <math>l</math> है, तो प्रयुक्त हैश फ़ंक्शन <math>h_l</math> और <math>h_{l+1}</math>हैं।
 
 
===संबोधन===
एड्रेसिंग फ़ाइल स्थिति पर आधारित है, जिसमें स्प्लिट पॉइंटर शामिल है <math>s</math>
और स्तर <math>l</math>. यदि स्तर है <math>l</math>, फिर हैश कार्य करता है
उपयोग किये जाते हैं <math>h_l</math> और <math>h_{l+1}</math>.
 
हैशिंग कुंजी के लिए LH एल्गोरिदम <math>c</math> है<ref name=LMS/>
 
<math>a := h_l(c)</math>
अगर <math> a<s:  a := h_{l+1}(c) </math>


हैशिंग कुंजी <math>c</math> के लिए LH एल्गोरिथ्म है <ref name=LMS/>


<math>a := h_l(c)</math> यदि <math> a<s:  a := h_{l+1}(c) </math>
===विभाजन===
===विभाजन===
जब एक बाल्टी को विभाजित किया जाता है, तो विभाजित सूचक और संभवतः स्तर के अनुसार अद्यतन किया जाता है<ref name=LMS/>
जब एक बाल्टी को विभाजित किया जाता है, तो स्प्लिट पॉइंटर और संभवतः स्तर को <ref name=LMS/> के अनुसार अपडेट किया जाता है।


<math>s := s+1</math>
<math>s := s+1</math>
अगर <math>s \ge N\times 2^l</math>: <math>l+=1, s=0</math>
यदि <math>s \ge N\times 2^l</math>: <math>l+=1, s=0</math>
 
===फाइल कॉन्ट्रेक्शन ===
 
यदि नियंत्रित कॉन्ट्रेक्शन के तहत लोड फैक्टर एक सीमा से नीचे चला जाता है, तो मर्ज ऑपरेशन शुरू हो जाता है। मर्ज ऑपरेशन अंतिम विभाजन को पूर्ववत कर देता है, साथ ही फ़ाइल स्थिति को भी रीसेट कर देता है।<ref name=LMS/>
===फ़ाइल संकुचन===
यदि नियंत्रित विभाजन के तहत लोड फैक्टर एक सीमा से नीचे चला जाता है, तो मर्ज ऑपरेशन होता है
शुरू हो रहा है। मर्ज ऑपरेशन अंतिम विभाजन को पूर्ववत करता है, फ़ाइल स्थिति को भी रीसेट करता है।
<ref name=LMS/>
 
 
===फ़ाइल स्थिति गणना===
===फ़ाइल स्थिति गणना===
फ़ाइल स्थिति में स्प्लिट पॉइंटर होता है <math>s</math> और स्तर <math>l</math>. यदि
फ़ाइल स्थिति में विभाजित सूचक <math>s</math> और स्तर <math>l</math> शामिल हैं। यदि मूल फ़ाइल <math>N=1</math>बकेट से प्रारंभ हुई है, तो बकेट <math>n</math> की संख्या और फ़ाइल स्थिति संबंधित हैं।<ref name="CS">
मूल फ़ाइल से प्रारंभ हुई <math>N=1</math> बाल्टियाँ, फिर बाल्टियों की संख्या
<math>n</math> और फ़ाइल स्थिति के माध्यम से संबंधित हैं
<ref name = CS>
{{Citation | first1=Juan | last1 = Chabkinian | first2=Thomas | last2=Schwarz  
{{Citation | first1=Juan | last1 = Chabkinian | first2=Thomas | last2=Schwarz  
| title=Fast LH* | journal=International Journal of Parallel Programming
| title=Fast LH* | journal=International Journal of Parallel Programming
Line 85: Line 67:


<math>n = 2^l+s </math>
<math>n = 2^l+s </math>
===LH*===
===LH*===
LH* का मुख्य योगदान LH* फ़ाइल के क्लाइंट को बकेट ढूंढने की अनुमति देना है
LH* का मुख्य योगदान LH* फ़ाइल के क्लाइंट को बकेट ढूंढने की अनुमति देना है
Line 98: Line 78:
इनके बीच अतिरिक्त सूचनाओं के आदान-प्रदान से इनकी संख्या और भी कम की जा सकती है
इनके बीच अतिरिक्त सूचनाओं के आदान-प्रदान से इनकी संख्या और भी कम की जा सकती है
सर्वर और क्लाइंट <ref name=CS/>
सर्वर और क्लाइंट <ref name=CS/>
==भाषा प्रणालियों में अपनाना==
==भाषा प्रणालियों में अपनाना==
ग्रिसवॉल्ड और टाउनसेंड <ref>{{Citation | title=The Design and Implementation of Dynamic Hashing for Sets and Tables in Icon | first1=William G. | last1=Griswold | author1-link = Bill Griswold | first2=Gregg M. | last2=Townsend | journal=Software - Practice and Experience | volume=23 | issue=4 | date=April 1993 | pages=351–367 | doi=10.1002/spe.4380230402 | s2cid=11595927 | url=http://citeseer.ist.psu.edu/griswold93design.html}}</ref> आइकॉन भाषा में लीनियर हैशिंग को अपनाने पर चर्चा की गई। उन्होंने लीनियर हैशिंग में उपयोग किए जाने वाले [[गतिशील सरणी]] एल्गोरिदम के कार्यान्वयन विकल्पों पर चर्चा की, और आइकन बेंचमार्क अनुप्रयोगों की एक सूची का उपयोग करके प्रदर्शन तुलना प्रस्तुत की।
ग्रिसवॉल्ड और टाउनसेंड <ref>{{Citation | title=The Design and Implementation of Dynamic Hashing for Sets and Tables in Icon | first1=William G. | last1=Griswold | author1-link = Bill Griswold | first2=Gregg M. | last2=Townsend | journal=Software - Practice and Experience | volume=23 | issue=4 | date=April 1993 | pages=351–367 | doi=10.1002/spe.4380230402 | s2cid=11595927 | url=http://citeseer.ist.psu.edu/griswold93design.html}}</ref> आइकॉन भाषा में लीनियर हैशिंग को अपनाने पर चर्चा की गई। उन्होंने लीनियर हैशिंग में उपयोग किए जाने वाले [[गतिशील सरणी]] एल्गोरिदम के कार्यान्वयन विकल्पों पर चर्चा की, और आइकन बेंचमार्क अनुप्रयोगों की एक सूची का उपयोग करके प्रदर्शन तुलना प्रस्तुत की।

Revision as of 08:07, 19 July 2023

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

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

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

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

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

हैश फ़ंक्शन

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

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

जैसे-जैसे फ़ाइल सम्मिलन के माध्यम से बढ़ती है, यह एक बाल्टी को दो बाल्टी में विभाजित करने के माध्यम से सुन्दरता से विस्तारित होती है। बाल्टियों को विभाजित करने का क्रम पूर्व निर्धारित है। फागिन की विस्तार योग्य हैशिंग जैसी योजनाओं में यह मूलभूत अंतर है।[11] दो नई बाल्टियों के लिए, हैश फ़ंक्शन को से बदल दिया गया है। विभाजित की जाने वाली बकेट की संख्या फ़ाइल स्थिति का हिस्सा है और इसे स्प्लिट पॉइंटर कहा जाता है।[10]

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

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

एड्रेसिंग

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

हैशिंग कुंजी के लिए LH एल्गोरिथ्म है [10]

यदि

विभाजन

जब एक बाल्टी को विभाजित किया जाता है, तो स्प्लिट पॉइंटर और संभवतः स्तर को [10] के अनुसार अपडेट किया जाता है।

यदि :

फाइल कॉन्ट्रेक्शन

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

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

फ़ाइल स्थिति में विभाजित सूचक और स्तर शामिल हैं। यदि मूल फ़ाइल बकेट से प्रारंभ हुई है, तो बकेट की संख्या और फ़ाइल स्थिति संबंधित हैं।[12]

LH*

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

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

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

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

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

संदर्भ

  1. 1.0 1.1 1.2 1.3 Litwin, Witold (1980), "Linear hashing: A new tool for file and table addressing" (PDF), Proc. 6th Conference on Very Large Databases: 212–223
  2. 2.0 2.1 Ellis, Carla Schlatter (June 1987), "Concurrency in Linear Hashing", ACM Transactions on Database Systems, 12 (2): 195–217, doi:10.1145/22952.22954, S2CID 14260177
  3. 3.0 3.1 Baeza-Yates, Ricardo; Soza-Pollman, Hector (1998), "Analysis of Linear Hashing Revised" (PDF), Nordic Journal of Computing: 70–85, S2CID 7497598, archived from the original (PDF) on 2019-03-07
  4. 4.0 4.1 Enbody, Richard; Du, HC (June 1988), "Dynamic hashing schemes", ACM Computing Surveys, 20 (2): 85–113, doi:10.1145/46157.330532, S2CID 1437123
  5. 5.0 5.1 Larson, Per-Åke (April 1988), "Dynamic Hash Tables", Communications of the ACM, 31 (4): 446–457, doi:10.1145/42404.42410, S2CID 207548097
  6. Ruchte, Willard; Tharp, Alan (Feb 1987), "Linear hashing with Priority Splitting: A method for improving the retrieval performance of linear hashing", IEEE Third International Conference on Data Engineering: 2–9
  7. Manolopoulos, Yannis; Lorentzos, N. (1994), "Performance of linear hashing schemes for primary key retrieval", Information Systems, 19 (5): 433–446, doi:10.1016/0306-4379(94)90005-1
  8. Ramamohanarao, K.; Sacks-Davis, R. (Sep 1984), "Recursive linear hashing", ACM Transactions on Databases, 9 (3): 369–391, doi:10.1145/1270.1285, S2CID 18577730
  9. Litwin, Witold; Neimat, Marie-Anne; Schneider, Donavan A. (1993), "Linear Hashing for Distributed Files", Proceedings SIGMOD 93 International Conference on Management of Data: 327–336, doi:10.1145/170036.170084
  10. 10.00 10.01 10.02 10.03 10.04 10.05 10.06 10.07 10.08 10.09 10.10 10.11 Litwin, Witold; Moussa, Rim; Schwarz, Thomas (Sep 2005), "LH*RS - a highly-available scalable distributed data structure", ACM Transactions on Database Systems, 30 (3): 769–811, doi:10.1145/1093382.1093386, S2CID 1802386
  11. Fagin, Ronald; Nievergelt, Jurg; Pippenger, Nicholas; Strong, Raymond (Sep 1979), "Extendible Hashing - A Fast Access Method for Dynamic Files", ACM Transactions on Database Systems, 4 (2): 315–344, doi:10.1145/320083.320092, S2CID 2723596
  12. 12.0 12.1 Chabkinian, Juan; Schwarz, Thomas (2016), "Fast LH*", International Journal of Parallel Programming, 44 (4): 709–734, doi:10.1007/s10766-015-0371-8, S2CID 7448240
  13. Griswold, William G.; Townsend, Gregg M. (April 1993), "The Design and Implementation of Dynamic Hashing for Sets and Tables in Icon", Software - Practice and Experience, 23 (4): 351–367, doi:10.1002/spe.4380230402, S2CID 11595927


बाहरी संबंध


यह भी देखें

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