बाइनरी खोज पेड़ के साथ हैश की तुलना करें

Question

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

यहां मैं इस प्रश्न के साथ कैसे आया? मुझे लगता है कि स्टैंडर्ड सी ++ एसटीएल set और map जो बाइनरी खोज पेड़ के साथ लागू किया जाता है है, लेकिन कोई हैश (के बारे में गैर stardard hash_set, hash_map में बात नहीं है) पर ध्यान दें। जबकि, रूबी में केवल Hash है। मैं इस अंतर के पीछे तर्कसंगत समझना चाहता हूं।

Answer 1

पेड़ इन-ऑर्डर ट्रैवर्सन की अनुमति देते हैं।

हैश तालिका के लिए सबसे खराब केस प्रदर्शन ओ (एन) (एक बाल्टी के माध्यम से रैखिक खोज) है, एक बाइनरी खोज ओ (लॉग एन) से बंधी है।

एनबी: इसके लिए पेड़ को संतुलित करने की आवश्यकता होती है - यही कारण है कि सामान्य कार्यान्वयन एक स्व-संतुलन वृक्ष, एसएचएचसी को लाल-काले पेड़ के रूप में उपयोग करता है।

जबकि इस तरह के एक गिरावट की संभावना नहीं है, यह असंभव नहीं है और क्षमता एक उपयुक्त हैश फंक्शन और वास्तविक डेटा के वितरण के लिए चुना है पर दृढ़ता से निर्भर करता है।

एक पेड़ कार्यान्वयन भी आवश्यक आकार के लिए छोटे से बढ़ता है, जबकि एक हैशपैप पूर्ण हो जाने पर गिरावट शुरू होता है (अधिकांश कार्यान्वयन के लिए, यह लगभग 70% बाल्टी भर जाती है)। आपको या तो पूरी तालिका (फिर से, वास्तविक समय के लिए खराब समय) को फिर से चालू करने की आवश्यकता है, या वृद्धिशील रूप से एक नई तालिका में स्थानांतरित करने की आवश्यकता है, जो एक सरल कार्यान्वयन नहीं है।

अंत में, अतिरिक्त कार्यान्वयन जटिलता से बचने के लिए एसटीएल शायद एक "बेस" कंटेनर टेम्पलेट, पेड़ के साथ चला गया।

Answer 2

अच्छी तरह से खोज पेड़ का आदेश दिया गया है, हैश नहीं हैं।

Answer 3

आप क्रम में एक बाइनरी खोज पेड़ में डेटा तक पहुंच सकते हैं।

Answer 4

पीटरचेन उत्तर, हैश संरचनाओं को जोड़ने के लिए हालांकि सम्मिलन और हटाने पर सैद्धांतिक रूप से तेज़ी से वास्तविक डेटा, चयनित हैश फ़ंक्शन और डेटा की मात्रा पर निर्भर करता है।

• एक सही हैश फ़ंक्शन डेटा की मात्रा और वितरण पर निर्भर करता है।

सबसे अच्छे और बुरे मामलों के बीच बड़े प्रदर्शन विविधताओं के बाद उन्हें सामान्य प्रयोजन संरचनाओं के लिए अयोग्य बना देता है। दूसरी तरफ बाइनरी पेड़ स्वतंत्र रूप से उपयोग की जाने वाली डेटा/मात्रा के स्वतंत्र रूप से अधिक अनुमानित हैं, भले ही सर्वश्रेष्ठ केस परिदृश्य पर कम कुशल हो।

Answer 5

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

दूसरी तरफ पेड़ अपेक्षाकृत सरल हैं। यह पहले से ही ज्ञात था कि चूंकि ये इन-मेमोरी डेटा संरचनाएं हैं, इसलिए हम केवल बी-पेड़ के बजाय बाइनरी पेड़ का उपयोग कर सकते हैं।फिर यह एवीएल और आरबी पेड़ों के बीच एक विकल्प था। बेहतर प्रदर्शन विशेषताओं के कारण आरबी पेड़ों का चयन किया जाता है, जिन पर मैं टिप्पणी करने की स्थिति में नहीं हूं, लेकिन दोनों संरचनाओं पर विकिपीडिया लेख (AVL और RB) आपको अपेक्षाकृत अच्छी जानकारी में और बताएंगे।

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

Answer 6

पेड़ का उपयोग करने के लिए आपको पेड़ में वस्तुओं को ऑर्डर करने का एक तरीका चाहिए। हैश तालिका का उपयोग करने के लिए आपको हैश तालिका में किसी आइटम के हैश मान की गणना करने के लिए फ़ंक्शन की आवश्यकता है।

दिलचस्प बात यह है कि .NET ढांचे के लिए प्रत्येक वर्ग को GetHashCode फ़ंक्शन को लागू करने (या उत्तराधिकारी) की आवश्यकता होती है ताकि प्रत्येक ऑब्जेक्ट को हैश तालिका में संग्रहीत किया जा सके। हालांकि, यह उन डेवलपर्स पर एक अतिरिक्त बोझ भी जोड़ता है जो कि अर्थात् सही हैश कार्यों को लागू करने के लिए आवश्यक हैं, भले ही वे वर्ग को ढकने का इरादा न करें। एक समाधान GetHashCode से निरंतर मान वापस करना है जो कि अर्थात् सही है, लेकिन हैशिंग के लिए फ़ंक्शन का कभी भी उपयोग नहीं किया जाना चाहिए।

Answer 7

सी ++ लोगों के समय डेटा संरचनाओं और एल्गोरिदम के लिए हार्ड-कोर अकादमिक दृष्टिकोण के प्रशंसकों थे, इसलिए वे छोटी स्मृति पदचिह्न के साथ संरचनाओं को पसंद करते थे और सबसे अच्छी तरह से समझते थे- और सबसे खराब मामले व्यवहार।

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

Answer 8

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

मामले को ऑर्डर करते समय हैशिस काम नहीं करता है। उदाहरण के लिए, मान लें कि आप एक मेमोरी आवंटक लिख रहे हैं और आप डेटा संरचना में स्मृति के मुक्त ब्लॉक स्टोर करते हैं। कुंजी ब्लॉक के आकार हैं और मान उनके लिए पॉइंटर्स हैं।

मेमोरी के लिए अनुरोध इस डेटा संरचना को देखकर और छोटे (ऑर्डर करने का तात्पर्य है!) ब्लॉक को अनुरोध को संतुष्ट करने में शामिल है। उदाहरण के लिए यदि आपके पास कुंजी 10, 20, 30 के साथ ब्लॉक हैं और 20 बाइट्स मेमोरी के लिए अनुरोध आता है, तो आप दूसरा ब्लॉक चुनते हैं। एक हैशप आसानी से ऐसा कर सकता है।

लेकिन अगर अनुरोध 22 बाइट्स के लिए है तो क्या होगा? चूंकि मूल्य 20 के साथ कोई कुंजी नहीं है, इसलिए आपको संपूर्ण हैमपैप को सही कुंजी (30) ढूंढने के लिए फिर से करना है जो ओ (एन) ऑपरेशन है। लेकिन अगर आपने एक पेड़ का इस्तेमाल किया था, तो "किसी दिए गए कुंजी से छोटी छोटी कुंजी ढूंढें" एक ओ (लॉग एन) ऑपरेशन है।