हैशसेट <T> (IEqualityComparer <T>) की लुकअप टाइम जटिलता क्या है?

Question

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

क्या मुझे confuses HashSet, जो एक तर्क के रूप IEqualityComparer लेता है के लिए निर्माता है:

http://msdn.microsoft.com/en-us/library/bb359100.aspx

ऊपर के लिंक में, टिप्पणी, ध्यान दें कि "निर्माता एक हे (1) ऑपरेशन है "लेकिन अगर ऐसा है, तो मैं उत्सुक हूं यदि लुकअप अभी भी ओ (1) है।

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

कार्यान्वयन आंतरिक रूप से एक लुकअप टेबल बनाते हैं क्योंकि तत्व संग्रह में जोड़े जाते हैं?

सामान्य रूप से, मैं .NET डेटा संरचनाओं की जटिलता के बारे में जानकारी कैसे प्राप्त कर सकता हूं?

Answer 1

ए HashSet हैशिंग के माध्यम से काम करता है (IEqualityComparer.GetHashCode के माध्यम से) आपके द्वारा डाली गई वस्तुओं और हैश के अनुसार बाल्टी में वस्तुओं को फेंक देता है। बाल्टी खुद को एक सरणी में संग्रहीत किया जाता है, इसलिए ओ (1) भाग।

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

अब, जब आप कुछ देखते हैं, तो यह इसे धो देता है, और उपयुक्त बाल्टी के माध्यम से कूदता है। इसे कई सर लुकअप (हैश में प्रत्येक चरित्र के लिए एक) करना है, लेकिन एन के एक समारोह के रूप में नहीं बढ़ता है, आपके द्वारा जोड़े गए ऑब्जेक्ट्स की संख्या, इसलिए ओ (1) रेटिंग। (GetHashCode()) अपने IEqualityComparer कार्यान्वयन प्रदान करता है http://c-sharp-snippets.blogspot.com/2010/03/runtime-complexity-of-net-generic.html

Answer 2

यह हैश समारोह की गुणवत्ता पर निर्भर होगा:

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

तुलनात्मक कोड को पर जांचने के लिए प्रत्येक कुंजी पर निष्पादित किया जाना होगा कि कोई मैच था या नहीं। यह ओ (1) नहीं होगा, लेकिन ओ (एन)।

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

Answer 3

लुकअप अभी भी ओ (1) है यदि आप IEqualityComparer पास करते हैं।हैश सेट अभी भी उसी तर्क का उपयोग करता है जैसे कि आप एक IEqualityComparer पास नहीं करते हैं; यह System.Object (या वस्तु में प्रश्न द्वारा प्रदान किए गए ओवरराइड) के उदाहरण विधियों के बजाय GetHashCode और Equals के IEqualityComparer के कार्यान्वयन का उपयोग करता है।

Answer 4

अगर मैं एक हैशसेट के निर्माता को पास करने के लिए एक तुलनाकर्ता लिखना चाहता था, जब भी मैं एक लुकअप करता हूं, तो तुलना करने के लिए प्रत्येक कुंजी पर तुलनाकर्ता कोड को निष्पादित करना होगा ताकि यह देखने के लिए कि कोई मैच था या नहीं। यह ओ (1) नहीं होगा, लेकिन ओ (एन)।

चलिए उस मान को कॉल करें जिसे आप "क्वेरी" मान के लिए खोज रहे हैं।

क्या आप समझा सकते हैं कि क्यों आप मानते हैं कि तुलनाकर्ता को प्रत्येक कुंजी पर निष्पादित किया जाना चाहिए ताकि यह देखने के लिए कि यह क्वेरी से मेल खाता है या नहीं?

यह विश्वास गलत है। (बेशक तुलनात्मक द्वारा आपूर्ति किए गए हैश कोड प्रत्येक कुंजी के लिए समान नहीं है!) खोज एल्गोरिदम प्रत्येक कुंजी पर समानता तुलनाकर्ता निष्पादित करता है जिसका हैश कोड क्वेरी के हैश कोड से मेल खाता है, हैश तालिका में बाल्टी की संख्या मॉड्यूल करें। इस तरह हैश टेबल को ओ (1) लुकअप टाइम मिलता है।

कार्यान्वयन आंतरिक रूप से एक लुकअप टेबल बनाते हैं क्योंकि तत्व संग्रह में जोड़े जाते हैं?

हां।

सामान्य रूप से, मैं .NET डेटा संरचनाओं की जटिलता के बारे में जानकारी कैसे प्राप्त कर सकता हूं?

दस्तावेज़ीकरण पढ़ें।