सी ++ एसटीएल में एसटीएल

Question

में मानचित्र और हैशपैप के बीच क्या अंतर है, दो मानचित्र, मानचित्र और हैशपैप हैं। किसी को भी उनके मुख्य अंतर पता है?

Answer 1

नक्शा डेटा संरचना के रूप में एक लाल-काले पेड़ का उपयोग करता है, तो तत्व आप में हल कर रहे हैं रखा, और सम्मिलित करें/हटाएं हे (लॉग (एन)) है। तत्वों को कम से कम operator< लागू करने की आवश्यकता है।

हैशपैप हैश का उपयोग करता है, इसलिए तत्वों को बिना छेड़छाड़ की जाती है, डालें/हटाएं ओ (1) है। तत्वों को कम से कम operator== लागू करने की आवश्यकता है और आपको हैश फ़ंक्शन की आवश्यकता है।

Answer 2

map एक लाल-काला पेड़ है, O(log(n)) एक्सेस समय। hash_map (जो मानक नहीं है, हालांकि unordered_map मानक बन जाएगा) लिंक की सूचियों की एक सरणी में एक इंडेक्स के रूप में कुंजी का एक हैश (अवधारणात्मक रूप से) का उपयोग करता है, और इसलिए O(1) का सबसे अच्छा केस एक्सेस समय और O(n) का सबसे खराब मामला है।

http://en.wikipedia.org/wiki/Red-black_tree

Answer 3

मुख्य अंतर खोज समय है।

कुछ डेटा के लिए बेहतर नक्शा

डेटा के बहुत सारे के लिए बेहतर hashmap

वैसे भी पहले से दिए गए tecnical उत्तर सही हैं है।

Answer 4

हैश_मैप एक हैश तालिका का उपयोग करता है। यह सिद्धांत में "स्थिर" समय है। अधिकांश कार्यान्वयन "टक्कर" हैश तालिका का उपयोग करते हैं। क्या वास्तव में होता है:

• यह एक बड़ी मेज
• आपको लगता है कि आप (तालिका में एक यादृच्छिक जगह उत्पन्न करता है अपने वस्तु के लिए एक "हैश" समारोह है बनाता है यादृच्छिक दिखने, लेकिन हैश फंक्शन हमेशा होगा अपनी ऑब्जेक्ट के लिए एक ही मान वापस करें) और आमतौर पर यह तालिका के आकार के साथ वास्तविक 32-बिट (या 64-बिट) हैश मान का मोड है।
• तालिका यह देखने के लिए लगती है कि स्थान उपलब्ध है या नहीं। यदि ऐसा है तो यह आइटम को तालिका में रखता है। यदि नहीं, तो यह जांचता है कि तत्व उस तत्व को है जिसे आप सम्मिलित करने का प्रयास कर रहे हैं। यदि ऐसा है तो यह एक डुप्लिकेट है इसलिए कोई सम्मिलित नहीं है। यदि नहीं, तो इसे "टकराव" कहा जाता है और यह किसी अन्य सेल को खोजने के लिए कुछ सूत्र का उपयोग करता है और यह तब तक जारी रहता है जब तक कि इसे डुप्लिकेट या खाली सेल न मिल जाए।
• जब तालिका बहुत अधिक भर जाती है तो यह आकार बदलती है। एक कुशल (समय में) कार्यान्वयन सभी मूल हैश मानों को तत्वों के साथ एक साथ संग्रहीत करेगा, इसलिए इसे होने पर हैश को फिर से समझने की आवश्यकता नहीं होगी। इसके अलावा, हैश की तुलना करना आमतौर पर तत्वों की तुलना करने से तेज़ होता है, इसलिए यह अधिकांश चरणों को पूर्व-चरण के रूप में खत्म करने के लिए खोज कर ऐसा कर सकता है।
• यदि आप कभी भी कुछ भी नहीं हटाते हैं तो यह आसान है। हालांकि तत्वों को हटाने से अतिरिक्त जटिलता बढ़ जाती है। एक सेल जिसमें उसमें एक तत्व था जिसे हटा दिया गया है, एक अलग राज्य में है जो कि बस खाली था, क्योंकि आप टकराव कर सकते थे और यदि आप इसे खाली करते हैं, तो वे तत्व नहीं पाए जाएंगे। तो आमतौर पर कुछ "निशान" होता है। बेशक अब जब हम सेल का पुन: उपयोग करना चाहते हैं, तो हमें अभी भी एक डुप्लिकेट निचला डाउन होने पर भी रिकर्स करना होगा (इस मामले में हम इस सेल में सम्मिलित नहीं कर सकते हैं), फिर हटाए गए सेल का पुन: उपयोग करना याद रखें।
• सामान्य बाधा यह है कि आपकी वस्तुओं को समानता की जांच के लिए लागू किया जाना चाहिए, लेकिन डंकमवेयर (या यह एसजीआई) ऑपरेटर < के साथ अपना कार्यान्वित किया गया जो धीमा हो सकता है लेकिन आपके तत्वों और संबंधित कंटेनर के प्रकार को अपनाने का लाभ है इसमें संग्रहीत किया जा सकता है, हालांकि आपको अभी भी हैश में स्टोर करने के लिए हैश फ़ंक्शन की आवश्यकता है।

सिद्धांत यह है कि यदि आपके पास पर्याप्त बड़ी तालिका है, तो संचालन निरंतर समय है, यानी यह आपके वास्तविक तत्वों की संख्या पर निर्भर नहीं है। अभ्यास में, ज़ाहिर है, जितना अधिक तत्व आपके पास अधिक टकराव होते हैं।

std :: नक्शा एक बाइनरी पेड़ का उपयोग करता है। ऑब्जेक्ट के लिए हैश फ़ंक्शन को परिभाषित करने की कोई आवश्यकता नहीं है, केवल कड़ाई से आदेश दिया गया है। सम्मिलन पर यह सम्मिलन बिंदु (और क्या कोई डुप्लिकेट है) खोजने के लिए पेड़ को दोहराता है और नोड जोड़ता है, और पेड़ को पुनर्व्यवस्थित करने की आवश्यकता हो सकती है ताकि पत्तियों की गहराई 1 से अधिक न हो। समय को पुनर्व्यवस्थित करना पेड़ की गहराई के सापेक्ष है, इसलिए ये सभी ऑपरेशन ओ (लॉग एन) हैं जहां एन तत्वों की संख्या है।

• पूरी तरह से स्केलेबल:

  हैश के फायदे जटिलता पेड़ के फायदे है। यह केवल उस चीज का उपयोग करता है जो इसकी आवश्यकता है, एक बड़ी मेज की आवश्यकता नहीं है या तालिका के आकार को पूर्व-खाली करने के लिए, हालांकि हैश को पेड़ की तुलना में प्रति तत्व कम "सामान" की आवश्यकता हो सकती है।

• पहले हैश की आवश्यकता नहीं है, जो एक अच्छा फ़ंक्शन के लिए तुलना से अधिक समय ले सकता है यदि डेटा सेट बड़ा नहीं है।

std::map के साथ एक अन्य मुद्दा यह है कि यह जबकि एक "की तुलना" समारोह है कि -1, 0 या 1 लौटे विशेष रूप से सबसे अधिक इस्तेमाल किया कुंजी के साथ, एक बहुत अधिक कुशल हो जाएगा एक भी सख्ती से आदेश दिया तुलना फ़ंक्शन का उपयोग करता है टाइप, std :: स्ट्रिंग, जो पहले से ही इस फ़ंक्शन को लागू किया गया है (यह char_traits::compare है)। (यह अक्षमता इस आधार पर आधारित है कि x==y को जांचने के लिए, आप x<y और y<x देखें ताकि आप दो तुलना कर सकें। आप इसे प्रति बार एक बार ऐसा करेंगे)।