हैश टेबल रनटाइम जटिलता (सम्मिलित करें, खोजें और हटाएं)

Question

मैं हैश तालिका पर इन कार्यों के लिए अलग-अलग रनटाइम जटिलताओं को क्यों देख रहा हूं?

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

कुछ समय पहले कुछ पाठ्यक्रमों में नोट्स, मैं कुछ विवरणों के आधार पर जटिलताओं की एक विस्तृत श्रृंखला देखता हूं जिनमें सभी ओ (1) के साथ एक शामिल है। यदि मैं सभी ओ (1) प्राप्त कर सकता हूं तो कोई अन्य कार्यान्वयन क्यों उपयोग किया जाएगा?

यदि मैं सी ++ या जावा जैसी भाषा में मानक हैश टेबल का उपयोग कर रहा हूं, तो मैं समय की जटिलता की अपेक्षा कैसे कर सकता हूं?

Answer 1

Hash tablesO(1)औसत और amortized मामले जटिलता हैं, लेकिन यह O(n)सबसे खराब स्थिति समय जटिलता से ग्रस्त है।[और मुझे लगता है यह वह जगह है जहाँ अपने भ्रम की स्थिति है]

हैश तालिकाओं O(n) सबसे बुरा समय जटिलता से दो कारणों से ग्रस्त:

1. तो भी कई तत्व एक ही कुंजी में टुकड़ों में बांटा गया: इस कुंजी के अंदर देख सकते हैं O(n) समय ले लो।
2. एक बार हैश तालिका ने load balance पारित कर दिया है - इसे फिर से शुरू करना है [एक नई बड़ी तालिका बनाएं, और तालिका में प्रत्येक तत्व को दोबारा डालें]।

हालांकि, यह क्योंकि O(1) औसत और परिशोधित मामले होना कहा जाता है:

1. यह बहुत दुर्लभ है कि कई आइटम एक ही कुंजी को टुकड़ों में बांटा जाएगा [अगर आप एक अच्छा हैश समारोह चुना है और है आप बहुत बड़ा भार संतुलन नहीं है।
2. मिलावत ऑपरेशन है, जो O(n) है, अधिक से अधिक, n/2 ऑप्स के बाद भी हो सकता है जो सभी ग्रहण कर रहे हैं O(1): इस प्रकार आप सेशन प्रति औसत समय योग जब, आपको मिलता है: (n*O(1) + O(n))/n) = O(1)

नोट rehashing की वजह से मुद्दा - एक रीयलटाइम एप्लिकेशन और एप्लिकेशन जिन्हें कम latency की आवश्यकता है - को हैश तालिका का उपयोग उनकी डेटा संरचना के रूप में नहीं करना चाहिए।

संपादित करें: हैश तालिकाओं के साथ Annother मुद्दा: cache
एक और मुद्दा यह है जहाँ आप बड़े हैश तालिकाओं में एक प्रदर्शन नुकसान देख सकते हैं कैश प्रदर्शन के कारण है। हैश टेबल्स खराब कैश प्रदर्शन से पीड़ित हैं, और इस प्रकार बड़े संग्रह के लिए - एक्सेस समय में अधिक समय लग सकता है, क्योंकि आपको मेमोरी से वापस कैश में तालिका के प्रासंगिक हिस्से को पुनः लोड करने की आवश्यकता है।

Answer 2

इस बात पर निर्भर करता है कि आप हैशिंग को कैसे कार्यान्वित करते हैं, सबसे खराब स्थिति में यह ओ (एन) पर जा सकता है, सबसे अच्छा मामले में यह 0 (1) (आमतौर पर आप प्राप्त कर सकते हैं यदि आपका डीएस इतना बड़ा नहीं है)

Answer 3

शायद आप अंतरिक्ष जटिलता को देख रहे थे? वह ओ (एन) है। अन्य जटिलताओं की अपेक्षा hash table प्रविष्टि पर अपेक्षित है। खोज जटिलता ओ (1) तक पहुंचती है क्योंकि बाल्टी की संख्या बढ़ जाती है। यदि सबसे खराब स्थिति में हैश टेबल में केवल एक बाल्टी है, तो खोज जटिलता ओ (एन) है।

टिप्पणी के जवाब में संपादित करें मुझे नहीं लगता कि यह कहना सही है कि ओ (1) औसत मामला है। यह वास्तव में है (जैसा कि विकिपीडिया पेज कहता है) ओ (1 + एन/के) जहां के हैश टेबल आकार है। यदि के काफी बड़ा है, तो परिणाम प्रभावी ढंग से ओ (1) है। लेकिन मान लीजिए कि के 10 है और एन 100 है। उस मामले में प्रत्येक बाल्टी में औसत 10 प्रविष्टियां होंगी, इसलिए खोज समय निश्चित रूप से ओ (1) नहीं है; यह 10 प्रविष्टियों के माध्यम से एक रैखिक खोज है।

Answer 4

आदर्श रूप से, हैशटेबल O(1) है। समस्या यह है कि यदि दो कुंजियां बराबर नहीं हैं, तो वे एक ही हैश में परिणाम देते हैं।

उदाहरण के लिए, तार कल्पना "यह समय सबसे अच्छा था यह समय की सबसे खराब था" और "ग्रीन अंडे और हाम" दोनों 123 की एक हैश मान में हुई।

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

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

समझ में आओ?

Answer 5

कुछ हैश तालिकाओं (कोयल हैशिंग) की गारंटी है हे (1) देखने