एक TrieMap क्या है और हैश मैप की तुलना में इसके फायदे/नुकसान क्या हैं?

Question

स्कैला में एक TrieMap संग्रह है।

ट्रीमैप क्या है और हैश मैप की तुलना में इसके फायदे/नुकसान क्या हैं?

Answer 1

एक स्कैला TrieMap एक त्रि-आधारित समवर्ती स्केलेबल मानचित्र कार्यान्वयन है। सामान्य ट्राई मानचित्रों के विपरीत, एक स्कैला TrieMap में एक कुशल, गैर-अवरुद्ध, ओ (1) समय snapshot ऑपरेशन (और थोड़ा अनुकूलित readOnlySnapshot) ऑपरेशन है।

एक TrieMap के निरपेक्ष प्रदर्शन थोड़ा JDK8 ConcurrentHashMap नीचे है, लेकिन लाभ यह है कि संगत iterators, कुछ समवर्ती डेटा संरचनाओं आम तौर पर नहीं है कि प्रदान करता है। इसका मतलब यह है कि आप ट्राई में सभी तत्वों को एक बिंदु पर कैप्चर कर सकते हैं (प्रदर्शन संख्या और विश्लेषण here)। आपको TrieMap का उपयोग करना चाहिए यदि आपको एक ही समय में सभी तत्वों को कैप्चर करने की आवश्यकता है (उदा। यूआई में अपने सभी तत्वों को सूचीबद्ध करने के लिए, या लगातार उनका विश्लेषण करने के लिए)।

Answer 2

ट्रीमैप्स त्रि-डेटा संरचना का उपयोग कर मानचित्र हैं जो अनिवार्य रूप से उथले पेड़ हैं। उदाहरण के लिए, यदि आपके पास 32 बिट हैश है तो आप इसे 4 बार 8 के लिए खंडों में विभाजित करते हैं और पेड़ के प्रत्येक स्तर पर आप 256 उप पेड़ तक शाखा बनाते हैं। जाहिर है यह हैश के फिक्स आकार (कुछ टकराव मानते हुए) के कारण ओ (1) प्रदर्शन देता है।

एक त्रिभुज संरचना को एक अतिरिक्त या हटाए गए तत्व के साथ एक नया ट्राई बनाने के लिए एक त्रिभुज की संरचना का पुन: उपयोग करने के लिए अपरिवर्तनीय रूप से अपरिवर्तनीय बनाया जा सकता है। जीसी पर प्रभावित समय/स्मृति में सापेक्ष प्रदर्शन कार्यान्वयन और लोड पर निर्भर करता है, इसलिए एक सामान्य जवाब का प्रयास करें, मैं कहूंगा कि एक बेंचमार्क चलाएगा। हालांकि एक अपरिवर्तनीय आवश्यकता वाले एक धागे के लिए क्लासिक हैशप आमतौर पर बेहतर औसत प्रदर्शन और निम्नतम खराब प्रदर्शन प्रदर्शन का उत्पादन करेगा।

एक साइड नोट के रूप में मैं उल्लेख करूँगा क्योंकि trieMap भी हैश का उपयोग करता है, यह एक हैशैप भी है, इसलिए मैं इसे एक तिहाई समर्थित हैशप बनाम सरणी समर्थित हैशप को कॉल करने की अनुशंसा करता हूं।