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

Revision as of 07:39, 19 July 2023

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

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

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

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

एलएच या एलएच* में रिकॉर्ड में एक कुंजी और एक सामग्री होती है, बाद में मूल रूप से रिकॉर्ड की अन्य सभी विशेषताएं होती हैं।^[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$ है^[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$

एलएच*

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

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

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

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

लीनियर हैशिंग का उपयोग बर्कले डीबी | बर्कले डेटाबेस सिस्टम (बीडीबी) में किया जाता है, जो बदले में एसीएम लेख के संचार से प्राप्त सी कार्यान्वयन का उपयोग करके कई सॉफ्टवेयर सिस्टम द्वारा उपयोग किया जाता है और पहली बार 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>
+'''लीनियर हैशिंग (एलएच)''' एक गतिशील डेटा संरचना है जो हैश तालिका को लागू करती है और एक समय में एक बाल्टी को बढ़ाती या सिकोड़ती है। इसका आविष्कार 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> एलएच और एलएच* में कुंजी आधारित संचालन (सम्मिलित करना, हटाना, अपडेट करना, पढ़ना) बकेट की संख्या और इसलिए रिकॉर्ड से स्वतंत्र अधिकतम निरंतर समय लेते हैं।<ref name = WL80/><ref name=LMS/>
-एलएच* बकेट की संख्या और इसलिए रिकॉर्ड से स्वतंत्र अधिकतम स्थिर समय लेता है।
-<ref name = WL80/><ref name=LMS/>
 ==एल्गोरिदम विवरण==
@@ Line 139: / Line 118: @@
 ==भाषा प्रणालियों में अपनाना==
-ग्रिसवॉल्ड और टाउनसेंड <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 में एस्मंड पिट द्वारा यूज़नेट पर प्रकाशित किया गया था।
+लीनियर हैशिंग का उपयोग [[बर्कले डीबी]] | बर्कले डेटाबेस सिस्टम (बीडीबी) में किया जाता है, जो बदले में एसीएम लेख के संचार से प्राप्त सी कार्यान्वयन का उपयोग करके कई सॉफ्टवेयर सिस्टम द्वारा उपयोग किया जाता है और पहली बार 1988 में एस्मंड पिट द्वारा यूज़नेट पर प्रकाशित किया गया था।
 ==संदर्भ==

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 07:39, 19 July 2023

Contents

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

हैश फ़ंक्शन

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

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

संबोधन

विभाजन

फ़ाइल संकुचन

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

एलएच*

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

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

संदर्भ

बाहरी संबंध

यह भी देखें

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 07:39, 19 July 2023

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

हैश फ़ंक्शन

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

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

संबोधन

विभाजन

फ़ाइल संकुचन

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

एलएच*

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

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

संदर्भ

बाहरी संबंध

यह भी देखें

Navigation

Wiki tools

Page tools

Other projects

Hidden categories