हैश ऐरे मैप्ड ट्रिए
 | This article may be too technical for most readers to understand. (October 2019) (Learn how and when to remove this template message) |
एक हैश सरणी मानचित्रित ट्री [1](एचएएमटी) एक साहचर्य सरणी का कार्यान्वयन है जो हैश तालिका और हैश सरणी मानचित्रित ट्री की विशेषताओं को जोड़ता है। [1] यह हैश ट्री (लगातार डेटा संरचना) की अधिक सामान्य धारणा का एक परिष्कृत संस्करण है।
संचालन
एचएएमटी एक सरणी मानचित्रित ट्री है जहां कीज़ का समान वितरण और निरंतर कुंजी लंबाई सुनिश्चित करने के लिए कीज़ को पहले हैश किया जाता है।
एचएएमटी के एरे मानचित्रित ट्री के एक विशिष्ट कार्यान्वयन में, प्रत्येक बिंदु में कुछ निश्चित संख्या N छिद्र के साथ एक तालिका होती है, जिसमें प्रत्येक छिद्र में एक शून्य सूचक या दूसरे बिंदु के लिए एक सूचक होता है। N सामान्यतः 32 है। चूंकि प्रत्येक बिंदु के लिए N सूचक के लिए स्थान आवंटित करना महंगा होगा, इसके स्थान पर प्रत्येक बिंदु में एक बिटमैप होता है जो N बिट लंबा होता है जहां प्रत्येक बिट एक गैर-शून्य सूचक की उपस्थिति को इंगित करता है। इसके बाद बिटमैप (इसका हैमिंग भार) में सूचक की संख्या के बराबर लंबाई वाले सूचक की एक सरणी होती है।
एचएएमटी के लाभ
हैश ऐरे मानचित्रित ट्राई मेमोरी का अधिक मितव्ययितापूर्वक उपयोग करते हुए लगभग हैश सारिणी जैसी गति प्राप्त करता है। साथ ही, हैश तालिका का समय-समय पर आकार बदलना पड़ सकता है, जो एक महंगा संचालन है, जबकि एचएएमटी गतिशील रूप से बढ़ते हैं। सामान्यतः, एचएएमटी प्रदर्शन में कुछ एन छिद्र के साथ एक बड़ी क्रम सारिणी द्वारा सुधार किया जाता है; कुछ एचएएमटी प्रकार जड़ को प्रदर्शन पर नगण्य प्रभाव के साथ धीरे-धीरे बढ़ने देते हैं। [1]
कार्यान्वयन विवरण
एचएएमटी के कार्यान्वयन में हैमिंग भार फलन का उपयोग सम्मिलित है, जो किसी संख्या के बाइनरी प्रतिनिधित्व में इकाइयों की संख्या की गणना करता है। यह संचालन हैमिंग भार समर्थन में उपलब्ध है, लेकिन यह हैमिंग भार केवल कुछ उच्च-स्तरीय भाषाओं में उपलब्ध है। हालाँकि जनसंख्या गणना को हैमिंग भार कार्यान्वयन का उपयोग करके O(1) समय में सॉफ़्टवेयर में लागू किया जा सकता है, ऐसा करने से संचालन परिमाण के क्रम में धीमा हो सकता है।
कार्यान्वयन
प्रोग्रामिंग भाषाएँ क्लोजर,[2] स्काला (प्रोग्रामिंग भाषा), और फ़्रीज (प्रोग्रामिंग भाषा) [3] अपने मूल हैश मानचित्र प्रकार के लिए हैश सरणी मानचित्र किए गए प्रयासों के लगातार डेटा संरचना संस्करण का उपयोग करें। हास्केल (प्रोग्रामिंग भाषा) लाइब्रेरी अव्यवस्थित-धारक लगातार मानचित्र को लागू करने और डेटा संरचनाओं को सम्मुच्चय करने के लिए इसका उपयोग करती है। [4] एक अन्य हास्केल लाइब्रेरी एसटीएम-धारक सॉफ़्टवेयर ट्रांसेक्शनल मेमोरी के संदर्भ में उपयोग के लिए कलन विधि को अनुकूलित करता है। [5] एक जावास्क्रिप्ट एचएएमटी लाइब्रेरी [6] क्लोजर कार्यान्वयन पर आधारित भी उपलब्ध है। रुबिनियस [7] रूबी (प्रोग्रामिंग भाषा) के कार्यान्वयन में एक एचएएमटी सम्मिलित है, जो अधिकतर रूबी में लिखा गया है लेकिन 3 के साथ [8] एर्लैंग (प्रोग्रामिंग भाषा) में बड़े मानचित्र विमोचन 18.0 के बाद से आंतरिक रूप से एक पर्सिस्टेंट डेटा संरचना एचएएमटी प्रतिनिधित्व का उपयोग करते हैं। [9] पोनी प्रोग्रामिंग भाषा अपने सतत संग्रह पैकेज में हैश मानचित्र के लिए एचएएमटी का उपयोग करती है। [10]
आईएम और आईएम-आरसी क्रेट्स, जो रस्ट प्रोग्रामिंग भाषा के लिए लगातार संग्रह प्रकार प्रदान करते हैं, अपने लगातार हैश सारिणी और हैश सम्मुच्चय के लिए एचएएमटी का उपयोग करते हैं।[11] समवर्ती लॉक-मुक्त संस्करण [12] सीटीआरआई नामक हैश ट्री एक परिवर्तनीय थ्रेड-सुरक्षित कार्यान्वयन है जो प्रगति सुनिश्चित करता है। डेटा-संरचना सही सिद्ध हुई है [13] - सीटीआरआई ऑपरेशंस में अटॉमिसिटी (प्रोग्रामिंग), रैखिकता और लॉक-फ्रीडम गुण दिखाए गए हैं।
यह भी देखें
संदर्भ
- ↑ 1.0 1.1 1.2 Phil Bagwell (2000). Ideal Hash Trees (PDF) (Report). Infoscience Department, École Polytechnique Fédérale de Lausanne.
- ↑ "clojure/clojure". GitHub. 8 December 2022.
- ↑ "Frege/frege". GitHub. 7 December 2022.
- ↑ Johan Tibell, A. Announcing unordered-containers 0.2
- ↑ Nikita Volkov, Announcing the "stm-containers" library, 2014
- ↑ "mattbierner/hamt". GitHub. 27 November 2022.
- ↑ "रुबिनियस के HAMT की रूबी स्रोत फ़ाइल". GitHub.
- ↑ https://github.com/rubinius/rubinius/blob/master/machine/builtin/system.cpp#L1724-L1802[dead link]
- ↑ "Erlang Programming Language".
- ↑ "horse: Pony is an open-source, actor-model, capabilities-secure, high performance programming language: Ponylang/ponyc". GitHub. 2018-11-26.
- ↑ "API docs for Rust im-rc crate".
- ↑ Prokopec, A. Implementation of Concurrent Hash Tries on GitHub
- ↑ Prokopec, A. et al. (2011) Cache-Aware Lock-Free Concurrent Hash Tries. Technical Report, 2011.
