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

Latest revision as of 15:25, 31 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]

हैश फ़ंक्शन

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

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

फ़ाइल एक्सपेंशन

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

स्प्लिट नियंत्रण

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

एड्रेसिंग

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

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

$a:=h_{l}(c)$ यदि $a<s:a:=h_{l+1}(c)$

स्प्लिटिंग

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

$s:=s+1$ यदि $s\geq N\times 2^{l}$ : $l+=1,s=0$

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

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

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

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

$n=2^{l}+s$

LH*

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

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

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

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

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

यह भी देखें

संदर्भ

↑ ^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.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.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.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.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
↑ 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
↑ 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
↑ 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
↑ 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.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
↑ 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.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
↑ 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

बाहरी संबंध

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

[WL80-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

[Ellis-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

[BS-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

[RD-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

[AL-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

[ruchte-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

[RS-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

[WL93-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

[LMS-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

[Fagin-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

[CS-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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

@@ Line 1: / Line 1: @@
-'''लीनियर हैशिंग (LH)''' एक गतिशील डेटा संरचना है जो हैश तालिका को लागू करती है और एक समय में एक बाल्टी को बढ़ाती या सिकोड़ती है। इसका आविष्कार 1980 में विटोल्ड लिटविन ने किया था।<ref name=WL80>{{Citation | first1=Witold | last1=Litwin | title=Linear hashing: A new tool for file and table addressing | journal=Proc. 6th Conference on Very Large Databases | pages=212–223 | year=1980 | url=https://www.cs.cmu.edu/afs/cs.cmu.edu/user/christos/www/courses/826-resources/PAPERS+BOOK/linear-hashing.PDF}}</ref><ref name=Ellis>
+'''लीनियर हैशिंग (LH)''' एक गतिशील डेटा संरचना है जो हैश तालिका को प्रयुक्त करती है और एक समय में बकेट को बढ़ाती या संकुचित करती है। इसका आविष्कार 1980 में विटोल्ड लिटविन ने किया था।<ref name=WL80>{{Citation | first1=Witold | last1=Litwin | title=Linear hashing: A new tool for file and table addressing | journal=Proc. 6th Conference on Very Large Databases | pages=212–223 | year=1980 | url=https://www.cs.cmu.edu/afs/cs.cmu.edu/user/christos/www/courses/826-resources/PAPERS+BOOK/linear-hashing.PDF}}</ref><ref name=Ellis>
 {{Citation | first1 = Carla Schlatter | last1=Ellis | title=Concurrency in Linear Hashing | journal=ACM Transactions on Database Systems  | volume=12 | number=2 | pages=195–217 | date=June 1987| doi=10.1145/22952.22954 | s2cid=14260177 | doi-access=free }}
 </ref> इसका विश्लेषण बाएज़ा-येट्स और सोज़ा-पोलमैन द्वारा किया गया है।<ref name=BS>{{Citation | first1=Ricardo | last1=Baeza-Yates | first2=Hector | last2=Soza-Pollman | title=Analysis of Linear Hashing Revised | journal=Nordic Journal of Computing | pages=70–85 | year=1998 | s2cid=7497598 | url=http://pdfs.semanticscholar.org/e6cd/667fef7cd377ed8d417cc648d3d578675ad5.pdf | archive-url=https://web.archive.org/web/20190307204217/http://pdfs.semanticscholar.org/e6cd/667fef7cd377ed8d417cc648d3d578675ad5.pdf | url-status=dead | archive-date=2019-03-07 }}</ref> यह डायनेमिक हैशिंग के नाम से जानी जाने वाली कई योजनाओं में पहला है <ref name=BS/><ref name=RD>{{Citation | first1=Richard | last1=Enbody | first2 = HC | last2 = Du | title=Dynamic hashing schemes | journal=ACM Computing Surveys  |  pages=85–113 | date=June 1988 | volume=20 | number=2 | doi=10.1145/46157.330532 | s2cid=1437123 | doi-access=free }}</ref> जैसे कि आंशिक विस्तार के साथ लार्सन की लीनियर हैशिंग, <ref name="AL">{{Citation | first1=Per-Åke | last1=Larson | title=Dynamic Hash Tables | journal=Communications of the ACM | pages=446–457 | date=April 1988 | volume=31 | number=4 | doi=10.1145/42404.42410| s2cid=207548097 }}</ref> प्राथमिकता विभाजन के साथ लीनियर हैशिंग, <ref name="ruchte">
@@ Line 10: / Line 10: @@
 title = Performance of linear hashing schemes for primary key retrieval |
 journal = Information Systems | volume = 19 | number = 5 |date = 1994 | pages =433–446| doi = 10.1016/0306-4379(94)90005-1 }}
-</ref> या रिकर्सिव लीनियर हैशिंग।<ref name="RS">
+</ref> या रिकर्सिव लीनियर हैशिंग आदि।<ref name="RS">
 {{Citation | first1 = K. |last1 = Ramamohanarao | first2 = R. | last2 = Sacks-Davis |
 title = Recursive linear hashing |
@@ Line 17: / Line 17: @@
 </ref>
-डायनामिक हैशिंग डेटा संरचना की फ़ाइल संरचना स्वयं को फ़ाइल के आकार में परिवर्तन के अनुसार अनुकूलित करती है, इसलिए महंगे आवधिक फ़ाइल पुनर्गठन से बचा जाता है।<ref name=RD/> एक लीनियर हैशिंग फ़ाइल एक पूर्व-निर्धारित बकेट को दो भागों में विभाजित करके विस्तारित होती है और दो पूर्व-निर्धारित बकेट को एक में विलय करके अनुबंधित करती है। पुनर्निर्माण की प्रेरणा योजना के स्वाद पर निर्भर करती है; यह एक बाल्टी या [[लोड फैक्टर (कंप्यूटर विज्ञान)|लोड फैक्टर]] (रिकॉर्ड की संख्या को बकेट की संख्या से विभाजित करने पर) पर एक पूर्व निर्धारित सीमा से बाहर जाने पर अतिप्रवाह हो सकता है।<ref name=WL80 /> लीनियर हैशिंग में दो प्रकार की बकेट होती हैं, एक वे जिन्हें विभाजित किया जाना है और वे जो पहले ही विभाजित हो चुकी हैं। जबकि विस्तार योग्य हैशिंग केवल अतिप्रवाहित बकेट्स को विभाजित करती है, [[ सर्पिल हैशिंग |सर्पिल हैशिंग]] (सर्पिल स्टोरेज) बकेट्स पर रिकॉर्ड को असमान रूप से वितरित करती है, जैसे कि प्रविष्टि, विलोपन या पुनर्प्राप्ति की उच्च लागत वाली बकेट्स विभाजन के लिए सबसे पहले होती हैं।<ref name=AL/>
+डायनामिक हैशिंग डेटा संरचना की फ़ाइल संरचना स्वयं को फ़ाइल के आकार में परिवर्तन के अनुसार अनुकूलित करती है, इसलिए महंगे आवधिक फ़ाइल पुनर्गठन से बचा जाता है।<ref name=RD/> लीनियर हैशिंग फ़ाइल एक पूर्व-निर्धारित बकेट को दो भागों में विभाजित करके विस्तारित होती है और दो पूर्व-निर्धारित बकेट को एक में विलय करके अनुबंधित करती है। पुनर्निर्माण की प्रेरणा योजना के स्वाद पर निर्भर करती है; यह एक बकेट या [[लोड फैक्टर (कंप्यूटर विज्ञान)|लोड फैक्टर]] (रिकॉर्ड की संख्या को बकेट की संख्या से विभाजित करने पर) पर एक पूर्व निर्धारित सीमा से बाहर जाने पर अतिप्रवाह हो सकता है।<ref name=WL80 /> लीनियर हैशिंग में दो प्रकार की बकेट होती हैं, एक वे जिन्हें विभाजित किया जाना है और वे जो पहले ही विभाजित हो चुकी हैं। जबकि विस्तार योग्य हैशिंग केवल अतिप्रवाहित बकेट्स को विभाजित करती है, [[ सर्पिल हैशिंग |सर्पिल हैशिंग]] (सर्पिल स्टोरेज) बकेट्स पर रिकॉर्ड को असमान रूप से वितरित करती है, जैसे कि प्रविष्टि, विलोपन या पुनर्प्राप्ति की उच्च लागत वाली बकेट्स विभाजन के लिए सबसे पहले होती हैं।<ref name=AL/>
-लीनियर हैशिंग को एक स्केलेबल वितरित डेटा संरचना, '''LH*''' में भी बनाया गया है। LH* में, प्रत्येक बाल्टी एक अलग सर्वर पर रहती है।<ref name=WL93>
+लीनियर हैशिंग को एक स्केलेबल वितरित डेटा संरचना, '''LH*''' में भी बनाया गया है। LH* में, प्रत्येक बकेट अलग सर्वर पर रहता है।<ref name=WL93>
 {{Citation | first1=Witold | last1=Litwin | first2=Marie-Anne |last2 = Neimat |
 first3 = Donavan A. | last3 = Schneider | title = Linear Hashing for Distributed Files |
@@ Line 27: / Line 27: @@
 {{Citation | first1=Witold | last1=Litwin | first2 = Rim | last2 = Moussa |
 first3 = Thomas | last3 = Schwarz | title=LH*RS - a highly-available scalable distributed data structure |journal=ACM Transactions on Database Systems  | volume=30 | number=3 | pages=769–811 | date=Sep 2005| doi=10.1145/1093382.1093386 | s2cid=1802386 | url=https://basepub.dauphine.fr/handle/123456789/15124 }}
-</ref> LH और LH* में कुंजी आधारित संचालन (सम्मिलित करना, हटाना, अपडेट करना, पढ़ना) बकेट की संख्या और इसलिए रिकॉर्ड से स्वतंत्र अधिकतम निरंतर समय लेते हैं।<ref name = WL80/><ref name=LMS/>
+</ref> LH और LH* में कुंजी (की) आधारित संचालन (सम्मिलित करना, हटाना, अपडेट करना, पढ़ना) बकेट की संख्या और इसलिए रिकॉर्ड से स्वतंत्र अधिकतम निरंतर समय लेते हैं।<ref name = WL80/><ref name=LMS/>
 ==एल्गोरिदम विवरण==
-LH या LH* में रिकॉर्ड में एक कुंजी और एक सामग्री होती है, बाद में मूल रूप से रिकॉर्ड की अन्य सभी विशेषताएं होती हैं।<ref name=WL80/><ref name=LMS/> इन्हें बाल्टियों में संग्रहित किया जाता है। उदाहरण के लिए, एलिस के कार्यान्वयन में, एक बकेट रिकॉर्ड्स की एक लिंक की गई सूची है।<ref name=Ellis/> फ़ाइल कुंजी आधारित सीआरयूडी संचालन को बनाने या सम्मिलित करने, पढ़ने, अद्यतन करने और हटाने के साथ-साथ एक स्कैन संचालन की अनुमति देती है जो सभी रिकॉर्ड को स्कैन करती है, उदाहरण के लिए एक गैर-कुंजी विशेषता पर डेटाबेस चयन ऑपरेशन करना।<ref name=LMS/> रिकॉर्ड्स को बाल्टियों में संग्रहित किया जाता है जिनकी संख्या 0 से शुरू होती है।<ref name=LMS/>
+LH या LH* में रिकॉर्ड में एक कुंजी और सामग्री होती है, बाद में मूल रूप से रिकॉर्ड की अन्य सभी विशेषताएं होती हैं।<ref name=WL80/><ref name=LMS/> इन्हें बकेट्स में संग्रहित किया जाता है। उदाहरण के लिए, एलिस के कार्यान्वयन में, बकेट रिकॉर्ड्स की एक लिंक की गई सूची है।<ref name=Ellis/> फ़ाइल कुंजी आधारित सीआरयूडी संचालन को बनाने या सम्मिलित करने, पढ़ने, अद्यतन करने और हटाने के साथ-साथ स्कैन संचालन की अनुमति देती है जो सभी रिकॉर्ड को स्कैन करती है, उदाहरण के लिए गैर-कुंजी विशेषता पर डेटाबेस चयन ऑपरेशन करना।<ref name=LMS/> रिकॉर्ड्स को बकेट्स में संग्रहित किया जाता है जिनकी संख्या 0 से प्रारम्भ होती है।<ref name=LMS/>
 ===हैश फ़ंक्शन===
-कुंजी <math>c</math> के साथ रिकॉर्ड तक पहुंचने के लिए, हैश फ़ंक्शंस का एक परिवार, जिसे सामूहिक रूप से डायनेमिक हैश फ़ंक्शन कहा जाता है, कुंजी <math>c</math> पर लागू किया जाता है। किसी भी समय, अधिकतम दो हैश फ़ंक्शन <math>h_i</math>और <math>h_{i+1}</math> का उपयोग किया जाता है। एक विशिष्ट उदाहरण डिवीजन मॉड्यूलो x ऑपरेशन का उपयोग करता है। यदि बाल्टियों की मूल संख्या <math>N</math> है, तो हैश फ़ंक्शन का परिवार है।<ref name=LMS/>
+कुंजी (की) <math>c</math> के साथ रिकॉर्ड तक पहुंचने के लिए, हैश फ़ंक्शंस का एक वर्ग, जिसे सामूहिक रूप से डायनेमिक हैश फ़ंक्शन कहा जाता है, कुंजी <math>c</math> पर प्रयुक्त किया जाता है। किसी भी समय, अधिकतम दो हैश फ़ंक्शन <math>h_i</math>और <math>h_{i+1}</math> का उपयोग किया जाता है। एक विशिष्ट उदाहरण डिवीजन मॉड्यूलो x ऑपरेशन का उपयोग करता है। यदि बकेट्स की मूल संख्या <math>N</math> है, तो हैश फ़ंक्शन का वर्ग है।<ref name=LMS/>
 <math> h_i(c) \mapsto c \pmod{N \cdot 2^i}</math>
-===फ़ाइल विस्तार===
+===फ़ाइल एक्सपेंशन===
-जैसे-जैसे फ़ाइल सम्मिलन के माध्यम से बढ़ती है, यह एक बाल्टी को दो बाल्टी में विभाजित करने के माध्यम से सुन्दरता से विस्तारित होती है। बाल्टियों को विभाजित करने का क्रम पूर्व निर्धारित है। फागिन की विस्तार योग्य हैशिंग जैसी योजनाओं में यह मूलभूत अंतर है।<ref name = Fagin>
+जैसे-जैसे फ़ाइल सम्मिलन के माध्यम से बढ़ती है, यह बकेट को दो बकेट में विभाजित करने के माध्यम से सुन्दरता से विस्तारित होती है। बकेट्स को विभाजित करने का क्रम पूर्व निर्धारित है। फागिन की विस्तार योग्य हैशिंग जैसी योजनाओं में यह मूलभूत अंतर है।<ref name = Fagin>
 {{Citation | first1=Ronald | last1 = Fagin | first2= Jurg | last2 = Nievergelt
 | first3 = Nicholas | last3 = Pippenger | first4 = Raymond | last4 = Strong
@@ Line 42: / Line 42: @@
 | journal = ACM Transactions on Database Systems
 | volume = 4 | number = 2 | date = Sep 1979 | pages = 315–344| doi = 10.1145/320083.320092 | s2cid = 2723596 | url = http://dl.acm.org/citation.cfm?doid=320083.320092 }}
-</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>c</math> के लिए LH एल्गोरिथ्म है <ref name=LMS/>
-===संबोधन===
+<math>a := h_l(c)</math> यदि <math> a<s:  a := h_{l+1}(c) </math>
-एड्रेसिंग फ़ाइल स्थिति पर आधारित है, जिसमें स्प्लिट पॉइंटर शामिल है <math>s</math>
+===स्प्लिटिंग===
-और स्तर <math>l</math>. यदि स्तर है <math>l</math>, फिर हैश कार्य करता है
+जब बकेट को स्प्लिटिंग किया जाता है, तो स्प्लिट पॉइंटर और संभवतः स्तर को <ref name=LMS/> के अनुसार अपडेट किया जाता है।
-उपयोग किये जाते हैं <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>
-===विभाजन===
-जब एक बाल्टी को विभाजित किया जाता है, तो विभाजित सूचक और संभवतः स्तर के अनुसार अद्यतन किया जाता है<ref name=LMS/>
 <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
 | title=Fast LH* | journal=International Journal of Parallel Programming
@@ Line 85: / Line 67: @@
 <math>n = 2^l+s </math>
 ===LH*===
-LH* का मुख्य योगदान LH* फ़ाइल के क्लाइंट को बकेट ढूंढने की अनुमति देना है
+LH* का मुख्य योगदान LH* फ़ाइल के क्लाइंट को उस बकेट को खोजने की अनुमति देना है जहां रिकॉर्ड रहता है, भले ही क्लाइंट को फ़ाइल की स्थिति पता न हो। ग्राहक वास्तव में फ़ाइल स्थिति के अपने संस्करण को संग्रहीत करते हैं, जो प्रारंभ में केवल पहली बकेट, अर्थात् बकेट 0 का ज्ञान होता है। उनकी फ़ाइल स्थिति के आधार पर, एक क्लाइंट कुंजी के एड्रेस की गणना करता है और उस बकेट को एक अनुरोध भेजता है। बकेट पर, अनुरोध की जाँच की जाती है और यदि रिकॉर्ड बकेट में नहीं है, तो इसे अग्रेषित किया जाता है। एक यथोचित स्थिर प्रणाली में, यानी, यदि अनुरोध संसाधित होने के दौरान केवल एक विभाजन या विलय हो रहा है, तो यह दिखाया जा सकता है कि अधिकतम दो फॉरवर्ड हैं। फ़ॉरवर्ड के बाद, अंतिम बकेट उस क्लाइंट को एक इमेज समायोजन संदेश भेजता है जिसकी स्थिति अब वितरित फ़ाइल की स्थिति के समीप है।<ref name=LMS/> जबकि सक्रिय ग्राहकों के लिए फॉरवर्ड यथोचित दुर्लभ हैं, सर्वर और क्लाइंट के बीच अतिरिक्त सूचना आदान-प्रदान द्वारा उनकी संख्या को और भी कम किया जा सकता है। <ref name=CS/>
-भले ही क्लाइंट को फ़ाइल की स्थिति पता न हो, फिर भी रिकॉर्ड मौजूद रहता है। ग्राहक वास्तव में दुकान करते हैं
-फ़ाइल स्थिति का उनका संस्करण, जो शुरू में केवल पहली बकेट, अर्थात् बकेट 0 का ज्ञान है। उनकी फ़ाइल स्थिति के आधार पर, एक ग्राहक एक के पते की गणना करता है
-key और उस बकेट को एक अनुरोध भेजता है। बकेट पर, अनुरोध की जाँच की जाती है और यदि
-रिकॉर्ड बकेट में नहीं है, इसे अग्रेषित कर दिया गया है। एक यथोचित स्थिर प्रणाली में, अर्थात्,
-यदि अनुरोध संसाधित होने के दौरान केवल एक विभाजन या विलय हो रहा है, तो यह हो सकता है
-दिखाया जाए कि अधिकतम दो फॉरवर्ड हैं। फॉरवर्ड के बाद, अंतिम बकेट एक भेजता है
-उस क्लाइंट को छवि समायोजन संदेश जिसकी स्थिति अब वितरित फ़ाइल की स्थिति के करीब है।<ref name=LMS/>  जबकि सक्रिय ग्राहकों के लिए फॉरवर्ड काफी दुर्लभ हैं,
-इनके बीच अतिरिक्त सूचनाओं के आदान-प्रदान से इनकी संख्या और भी कम की जा सकती है
-सर्वर और क्लाइंट <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> ने आइकन भाषा में रैखिक हैशिंग को अपनाने पर चर्चा की। उन्होंने लीनियर हैशिंग में उपयोग किए जाने वाले डायनामिक ऐरे एल्गोरिदम के कार्यान्वयन विकल्पों पर चर्चा की और आइकन बेंचमार्क अनुप्रयोगों की एक सूची का उपयोग करके प्रदर्शन तुलना प्रस्तुत की।
 ==डेटाबेस सिस्टम में अपनाना==
-लीनियर हैशिंग का उपयोग [[बर्कले डीबी]] | बर्कले डेटाबेस सिस्टम (बीडीबी) में किया जाता है, जो बदले में एसीएम लेख के संचार से प्राप्त सी कार्यान्वयन का उपयोग करके कई सॉफ्टवेयर सिस्टम द्वारा उपयोग किया जाता है और पहली बार 1988 में एस्मंड पिट द्वारा यूज़नेट पर प्रकाशित किया गया था।
+रैखिक हैशिंग का उपयोग [[बर्कले डीबी|बर्कले]] डेटाबेस सिस्टम (बीडीबी) में किया जाता है, जो बदले में कई सॉफ्टवेयर सिस्टम द्वारा उपयोग किया जाता है, सीएसीएम लेख से प्राप्त C कार्यान्वयन का उपयोग करके और पहली बार 1988 में एसमंड पिट द्वारा यूज़नेट पर प्रकाशित किया गया था।
+== यह भी देखें ==
+* [[विस्तार योग्य हैशिंग|एक्सटेन्डिब्ले हैसिंग]]
+* [[लगातार हैशिंग|कंसिस्टेंट हैसिंग]]
+* सर्पिल हैशिंग
 ==संदर्भ==
@@ Line 114: / Line 88: @@
 * [http://hackthology.com/an-in-memory-go-implementation-of-linear-hashing.html An in Memory Go Implementation with Explanation]
 * [https://github.com/KevinStern/index-cpp/blob/master/src/linear_hashing_table.h A C++ Implementation of Linear Hashtable which Supports Both Filesystem and In-Memory storage]
-==यह भी देखें==
-* [[विस्तार योग्य हैशिंग]]
-* [[लगातार हैशिंग]]
-* सर्पिल हैशिंग
 श्रेणी:खोज एल्गोरिदम
 श्रेणी:हैशिंग
-[[Category: Machine Translated Page]]
 [[Category:Created On 11/07/2023]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 15:25, 31 July 2023

Contents

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

हैश फ़ंक्शन

फ़ाइल एक्सपेंशन

स्प्लिट नियंत्रण

एड्रेसिंग

स्प्लिटिंग

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

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

LH*

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

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

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Latest revision as of 15:25, 31 July 2023

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

हैश फ़ंक्शन

फ़ाइल एक्सपेंशन

स्प्लिट नियंत्रण

एड्रेसिंग

स्प्लिटिंग

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

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

LH*

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

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

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Hidden categories