रैखिक हैशिंग: 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: @@
-लीनियर हैशिंग (एलएच) एक गतिशील डेटा संरचना है जो एक [[हैश तालिका]] लागू करती है और एक समय में एक बाल्टी को बढ़ाती या सिकोड़ती है। इसका आविष्कार विटोल्ड लिट्विन ने 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>
+'''लीनियर हैशिंग (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>
-<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> इसका विश्लेषण बाएज़ा-येट्स और सोज़ा-पोलमैन द्वारा किया गया है।<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">
-<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>
 {{Citation | first1 = Willard | last1 = Ruchte | first2 = Alan | last2 = Tharp |
 title = Linear hashing with Priority Splitting: A method for improving the retrieval performance of linear hashing |
 journal = IEEE Third International Conference on Data Engineering |
 date = Feb 1987 | pages=2–9}}
-</ref>
+</ref> आंशिक विस्तार और प्राथमिकता विभाजन के साथ लीनियर हैशिंग,<ref>
-आंशिक विस्तार और प्राथमिकता विभाजन के साथ रैखिक हैशिंग,
-<ref>
 {{Citation | first1 = Yannis | last1 = Manolopoulos | first2 = N. | last2 = Lorentzos |
 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> या रिकर्सिव लीनियर हैशिंग आदि।<ref name="RS">
-या पुनरावर्ती रैखिक हैशिंग।
-<ref name=RS>
 {{Citation | first1 = K. |last1 = Ramamohanarao | first2 = R. | last2 = Sacks-Davis |
 title = Recursive linear hashing |
@@ Line 26: / Line 16: @@
 volume=9 | number=3 |date=Sep 1984 | pages=369–391|doi = 10.1145/1270.1285 |s2cid = 18577730 }}
 </ref>
-डायनामिक हैशिंग डेटा संरचना की फ़ाइल संरचना फ़ाइल के आकार में परिवर्तन के अनुसार स्वयं को अनुकूलित करती है, इसलिए महंगी आवधिक फ़ाइल पुनर्गठन से बचा जाता है।<ref name=RD/>एक लीनियर हैशिंग फ़ाइल विभाजन द्वारा विस्तारित होती है
-एक पूर्व-निर्धारित बाल्टी को दो भागों में बाँटना और दो पूर्व-निर्धारित बाल्टियों को एक में मिला कर सिकुड़ना। पुनर्निर्माण के लिए ट्रिगर योजना के स्वाद पर निर्भर करता है; यह एक बाल्टी या [[लोड फैक्टर (कंप्यूटर विज्ञान)]] (बाल्टी की संख्या से विभाजित रिकॉर्ड की संख्या) पर एक पूर्व निर्धारित सीमा के बाहर अतिप्रवाह हो सकता है।<ref name=WL80 />लीनियर हैशिंग में दो प्रकार की बकेट होती हैं, एक वे जिन्हें विभाजित किया जाना है और एक वे जिन्हें विभाजित किया जाना है
-पहले से ही विभाजित. जबकि विस्तार योग्य हैशिंग केवल अतिप्रवाहित बाल्टियों को विभाजित करता है,
-[[ सर्पिल हैशिंग ]] (a.k.a. स्पाइरल स्टोरेज) बकेट पर रिकॉर्ड को असमान रूप से वितरित करता है
-सम्मिलन, विलोपन, या पुनर्प्राप्ति की उच्च लागत वाली बाल्टियाँ कतार में सबसे पहले हैं
-विभाजन के लिए.<ref name=AL/>
-लीनियर हैशिंग को एक स्केलेबल वितरित डेटा संरचना, एलएच* में भी बनाया गया है। एलएच* में, प्रत्येक बकेट एक अलग सर्वर पर रहता है।
+डायनामिक हैशिंग डेटा संरचना की फ़ाइल संरचना स्वयं को फ़ाइल के आकार में परिवर्तन के अनुसार अनुकूलित करती है, इसलिए महंगे आवधिक फ़ाइल पुनर्गठन से बचा जाता है।<ref name=RD/> लीनियर हैशिंग फ़ाइल एक पूर्व-निर्धारित बकेट को दो भागों में विभाजित करके विस्तारित होती है और दो पूर्व-निर्धारित बकेट को एक में विलय करके अनुबंधित करती है। पुनर्निर्माण की प्रेरणा योजना के स्वाद पर निर्भर करती है; यह एक बकेट या [[लोड फैक्टर (कंप्यूटर विज्ञान)|लोड फैक्टर]] (रिकॉर्ड की संख्या को बकेट की संख्या से विभाजित करने पर) पर एक पूर्व निर्धारित सीमा से बाहर जाने पर अतिप्रवाह हो सकता है।<ref name=WL80 /> लीनियर हैशिंग में दो प्रकार की बकेट होती हैं, एक वे जिन्हें विभाजित किया जाना है और वे जो पहले ही विभाजित हो चुकी हैं। जबकि विस्तार योग्य हैशिंग केवल अतिप्रवाहित बकेट्स को विभाजित करती है, [[ सर्पिल हैशिंग |सर्पिल हैशिंग]] (सर्पिल स्टोरेज) बकेट्स पर रिकॉर्ड को असमान रूप से वितरित करती है, जैसे कि प्रविष्टि, विलोपन या पुनर्प्राप्ति की उच्च लागत वाली बकेट्स विभाजन के लिए सबसे पहले होती हैं।<ref name=AL/>
-<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 |
 journal = Proceedings SIGMOD 93 International Conference on Management of Data |
 pages = 327–336 | date = 1993| doi=10.1145/170036.170084 }}
-</ref> की उपस्थिति में डेटा उपलब्धता प्रदान करने के लिए एलएच* का ही विस्तार किया गया है
+</ref> असफल बकेट की उपस्थिति में डेटा उपलब्धता प्रदान करने के लिए LH* का विस्तार किया गया है।<ref name=LMS>
-विफल बाल्टियाँ.
-<ref name=LMS>
 {{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> एलएच में कुंजी आधारित संचालन (सम्मिलित करना, हटाना, अद्यतन करना, पढ़ना)।
+</ref> LH और LH* में कुंजी (की) आधारित संचालन (सम्मिलित करना, हटाना, अपडेट करना, पढ़ना) बकेट की संख्या और इसलिए रिकॉर्ड से स्वतंत्र अधिकतम निरंतर समय लेते हैं।<ref name = WL80/><ref name=LMS/>
-एलएच* बकेट की संख्या और इसलिए रिकॉर्ड से स्वतंत्र अधिकतम स्थिर समय लेता है।
-<ref name = WL80/><ref name=LMS/>
 ==एल्गोरिदम विवरण==
-एलएच या एलएच* में रिकॉर्ड में एक कुंजी और एक सामग्री होती है, बाद में मूल रूप से रिकॉर्ड की अन्य सभी विशेषताएं होती हैं।<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>c</math> पर प्रयुक्त किया जाता है। किसी भी समय, अधिकतम दो हैश फ़ंक्शन <math>h_i</math>और <math>h_{i+1}</math> का उपयोग किया जाता है। एक विशिष्ट उदाहरण डिवीजन मॉड्यूलो x ऑपरेशन का उपयोग करता है। यदि बकेट्स की मूल संख्या <math>N</math> है, तो हैश फ़ंक्शन का वर्ग है।<ref name=LMS/>
-कुंजी पर सामूहिक रूप से एक गतिशील हैश फ़ंक्शन लागू किया जाता है <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 75: / 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>
+</ref> दो नई बकेट्स के लिए, हैश फ़ंक्शन <math>h_i</math> को <math>h_{i+1}</math> से बदल दिया गया है। विभाजित की जाने वाली बकेट की संख्या फ़ाइल स्थिति का हिस्सा है और इसे स्प्लिट पॉइंटर <math>s</math> कहा जाता है।<ref name="LMS" />
-दो नई बाल्टियों के लिए, हैश फ़ंक्शन <math>h_i</math> से प्रतिस्थापित कर दिया गया है
+===स्प्लिट नियंत्रण===
- <math>h_{i+1}</math>. विभाजित की जाने वाली बाल्टी की संख्या का हिस्सा है
+जब भी कोई बकेट ओवरफ्लो हो जाती है तो विभाजन किया जा सकता है। यह अनियंत्रित कॉन्ट्रेक्शन है। वैकल्पिक रूप से, फ़ाइल लोड फ़ैक्टर की निगरानी कर सकती है और जब भी लोड फ़ैक्टर एक सीमा से अधिक हो जाता है तो एक स्प्लिट करता है। यह नियंत्रित बंटवारा था।<ref name=LMS/>
-फ़ाइल स्थिति और स्प्लिट पॉइंटर कहा जाता है <math>s</math>.<ref name=LMS/>
+===एड्रेसिंग===
+एड्रेसिंग फ़ाइल स्थिति पर आधारित है, जिसमें विभाजित सूचक <math>s</math> और स्तर <math>l</math> सम्मिलित है। यदि स्तर <math>l</math> है, तो प्रयुक्त हैश फ़ंक्शन <math>h_l</math> और <math>h_{l+1}</math>हैं।
-===विभाजित नियंत्रण===
-जब भी बाल्टी ओवरफ्लो हो जाती है तो स्प्लिट किया जा सकता है। यह एक अनियंत्रित विभाजन है.
-वैकल्पिक रूप से, फ़ाइल लोड फ़ैक्टर की निगरानी कर सकती है और जब भी विभाजित होती है
-लोड फैक्टर एक सीमा से अधिक है। यह नियंत्रित बंटवारा था.<ref name=LMS/>
-===संबोधन===
-एड्रेसिंग फ़ाइल स्थिति पर आधारित है, जिसमें स्प्लिट पॉइंटर शामिल है <math>s</math>
-और स्तर <math>l</math>. यदि स्तर है <math>l</math>, फिर हैश कार्य करता है
-उपयोग किये जाते हैं <math>h_l</math> और <math>h_{l+1}</math>.
-हैशिंग कुंजी के लिए एलएच एल्गोरिदम <math>c</math> है<ref name=LMS/>
+हैशिंग कुंजी <math>c</math> के लिए LH एल्गोरिथ्म है <ref name=LMS/>
-<math>a := h_l(c)</math>
+<math>a := h_l(c)</math> यदि <math> a<s:  a := h_{l+1}(c) </math>
-अगर <math> a<s:  a := h_{l+1}(c) </math>
+===स्प्लिटिंग===
+जब बकेट को स्प्लिटिंग किया जाता है, तो स्प्लिट पॉइंटर और संभवतः स्तर को <ref name=LMS/> के अनुसार अपडेट किया जाता है।
-===विभाजन===
-जब एक बाल्टी को विभाजित किया जाता है, तो विभाजित सूचक और संभवतः स्तर के अनुसार अद्यतन किया जाता है<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 123: / Line 67: @@
 <math>n = 2^l+s </math>
+===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 152: / 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