अपरिवर्तनीय मानचित्रों के लिए किस प्रकार की डेटा संरचना का उपयोग किया जाता है?

Question

मुझे पता है कि सामान्य म्यूटेबल मानचित्र कैसे काम करते हैं (हैशटेबल्स का उपयोग करके), और मुझे पता है कि अपरिवर्तनीय सूचियां कैसे काम करती हैं (रिकर्सिव लिंक्ड सूचियां) और म्यूटेबल सूचियों पर उनके लाभ (निरंतर समय मूल को गड़बड़ किए बिना जोड़ना) लेकिन अपरिवर्तनीय मानचित्र कैसे हैं (उदाहरण के लिए स्कैला) काम?

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

Answer 1

लगातार हैश नक्शे एक संरचना का उपयोग करके लागू एक Hash trie कहा जाता है। यह originally proposed by Phil Bagwell था (जो ईपीएफएल में स्कैला समूह का सदस्य है) लेकिन वास्तव में क्लोजर द्वारा वास्तव में लागू किया गया था। यह स्केला मारा जब 2,8 2010.

में बाहर आया था वहाँ दान Spiewak द्वारा एक great talk on functional data structures जहां हैश trie के यांत्रिकी (जैसे बैंकर कतारों के रूप में अन्य बातों के साथ साथ) अत्यंत स्पष्ट रूप से समझाया गया है है! वह इस बात में एसिम्प्टोटिक बिग-ओ प्रदर्शन भी बहुत अच्छी तरह से बताते हैं।

पिछले अक्टूबर फिल London scala Lift Off में एक और बात करते हैं, समानांतर लगातार डेटा संरचनाओं पर इस समय देने को देखा।

लगातार क्रमबद्ध नक्शे एक Red-Black tree

Answer 2

यह एक पेड़ (लाल-काला) या हैश नक्शा हो सकता है। उनकी पहुंच विशेषताओं अंतर्निहित कार्यान्वयन पर निर्भर करती है। पढ़ने के लिए एक पेड़ ओ (लॉग एन) है; एक हैश नक्शा ओ (1) है।