मैंने एसओ री जावा हैशैप्स और उनके O(1) लुकअप समय पर कुछ दिलचस्प दावों को देखा है। क्या कोई समझा सकता है कि ऐसा क्यों है? जब तक कि इन हैशैप्स किसी भी हैशिंग एल्गोरिदम से बहुत अलग नहीं होते हैं, तब तक मुझे हमेशा एक डेटासेट मौजूद होना चाहिए जिसमें टकराव होता है।क्या जावा हैशप वास्तव में ओ (1) है?
जो मामले में, देखने O(n) बजाय O(1) होगा।
क्या कोई यह बता सकता है कि ओ (1) हैं और यदि ऐसा है, तो वे इसे कैसे प्राप्त करते हैं?
हैश मैप की एक विशेष विशेषता यह है कि संतुलित पेड़ के विपरीत, इसका व्यवहार संभाव्य है। इन मामलों में आमतौर पर सबसे बुरी स्थिति घटना होने की संभावना के संदर्भ में जटिलता के बारे में बात करने में मददगार होता है। एक हैश मानचित्र के लिए, निश्चित रूप से मानचित्र के पूर्ण होने के संबंध में टकराव का मामला है। अनुमान लगाने के लिए टक्कर बहुत आसान है।
पी टक्कर = n/क्षमता
तो भी तत्वों की एक मामूली संख्या के साथ एक हैश नक्शा बहुत कम से कम एक टक्कर अनुभव होने की संभावना है। बिग ओ नोटेशन हमें कुछ और आकर्षक बनाने की अनुमति देता है। निरीक्षण करें कि किसी भी मनमाने ढंग से, स्थिर निरंतर के लिए।
हे (एन) = हे (k * n)
हम हैश नक्शा के प्रदर्शन में सुधार करने के लिए इस सुविधा का उपयोग कर सकते हैं। हम इसके बजाय अधिकतर 2 टकरावों की संभावना के बारे में सोच सकते हैं।
पी टक्कर एक्स 2 = (एन/क्षमता)
यह बहुत कम है। चूंकि एक अतिरिक्त टकराव को संभालने की लागत बिग ओ प्रदर्शन के लिए अप्रासंगिक है, इसलिए हमें वास्तव में एल्गोरिदम को बदलने के बिना प्रदर्शन में सुधार करने का एक तरीका मिला है! हम करने के लिए
पी टक्कर xk = (एन/क्षमता) कश्मीर
इस generalzie कर सकते हैं और अब हम टकराव के कुछ मनमाना संख्या उपेक्षा और अधिक के गायब छोटे संभावना के साथ समाप्त कर सकते हैं टकराव के लिए हम लेखांकन कर रहे हैं। आप एल्गोरिदम के वास्तविक कार्यान्वयन को बदलने के बिना सही के चुनकर, मनमाने ढंग से छोटे स्तर की संभावना प्राप्त कर सकते हैं।
हम कह हैश नक्शा हे (1) का उपयोग कर सकते उच्च संभावना के साथ
एचटीएमएल के साथ भी, मैं अभी भी अंशों से वास्तव में खुश नहीं हूं। अगर आप इसे करने का एक अच्छा तरीका सोच सकते हैं तो उन्हें साफ करें। – SingleNegationElimination
असल में, उपर्युक्त कहता है कि ओ (लॉग एन) प्रभाव को निश्चित ओवरहेड द्वारा एन के चरम मूल्यों के लिए दफनाया जाता है। –
तकनीकी रूप से, आपके द्वारा दिया गया नंबर टकराव की संख्या का अनुमानित मूल्य है, जो एक टकराव की संभावना के बराबर हो सकता है। –
जावा में, हैश मैप एक बाल्टी का पता लगाने के लिए हैशकोड का उपयोग करके काम करता है। प्रत्येक बाल्टी उस बाल्टी में रहने वाली वस्तुओं की एक सूची है। तुलना के बराबर उपयोग करके आइटम स्कैन किए जाते हैं। आइटम जोड़ते समय, एक निश्चित भार प्रतिशत पहुंचने के बाद हैश मैप का आकार बदल जाता है।
तो, कभी कभी यह कुछ आइटम के खिलाफ तुलना करने के लिए होगा, लेकिन आम तौर पर यह बहुत हे (एन) की तुलना में हे (1) के करीब है। व्यावहारिक उद्देश्यों के लिए, आपको यह जानने की ज़रूरत है।
ठीक है, के बाद से बड़े-ओ सीमा का उल्लेख करना माना जाता है, इससे कोई अंतर नहीं है कि क्या यह हे के करीब है बनाता है (1) या नहीं। यहां तक कि ओ (एन/10^100) अभी भी ओ (एन) है। मुझे दक्षता के बारे में आपका बिंदु मिल जाता है जिससे अनुपात नीचे आ जाता है लेकिन यह अभी भी ओ (एन) पर एल्गोरिदम डालता है। – paxdiablo
हैश-नक्शे विश्लेषण, आप हे (एन) हो सकता है औसत मामला है, जो हे (1) (collusions के साथ) सबसे खराब स्थिति पर है पर आम तौर पर है, लेकिन है कि आमतौर पर ऐसा नहीं है। अंतर के बारे में - हे (1) का अर्थ है कि आप एक ही उपयोग समय चार्ट पर मदों की राशि की परवाह किए बिना मिलता है, और कि आम तौर पर मामला है (जब तक के रूप में वहाँ तालिका का आकार और 'के बीच एक अच्छा अनुपात है n ') –
यह ध्यान देने योग्य भी है कि यह अभी भी ठीक है (1), भले ही बाल्टी की स्कैनिंग थोड़ी देर लेती है क्योंकि इसमें कुछ तत्व पहले से ही हैं। जब तक बाल्टी का एक निश्चित अधिकतम आकार होता है, यह ओ() वर्गीकरण के लिए अप्रासंगिक एक निरंतर कारक है। लेकिन निश्चित रूप से "समान" कुंजी के साथ और भी तत्व हो सकते हैं, ताकि ये बाल्टी बहती रहें और आप अब स्थिरता की गारंटी नहीं दे सकते। – sth
बेशक hashmap के प्रदर्शन को देखते हुए ऑब्जेक्ट के लिए hashCode() फ़ंक्शन की गुणवत्ता के आधार निर्भर करेगा। हालांकि, अगर समारोह लागू किया जाता है तो टकराव की संभावना बहुत कम होती है, यह बहुत अच्छा प्रदर्शन होगा (यह में संभावित मामले में सख्ती से ओ (1) नहीं है लेकिन यह में मामलों में है)।
उदाहरण के लिए ओरेकल जेआरई में डिफ़ॉल्ट कार्यान्वयन एक यादृच्छिक संख्या का उपयोग करना है (जो वस्तु उदाहरण में संग्रहीत है ताकि यह परिवर्तित न हो - लेकिन यह पक्षपातपूर्ण लॉकिंग को भी अक्षम करता है, लेकिन यह एक और चर्चा है) इसलिए टक्कर का मौका बहुत कम है।
"यह ज्यादातर मामलों में है"। अधिक विशेष रूप से, कुल समय के के समय एन (जहां के स्थिर है) की ओर रुख होगा क्योंकि एन अनंतता की ओर जाता है। – ChrisW
यह गलत है। हैश टेबल में इंडेक्स को 'हैशकोड% टेबल साइज' के माध्यम से निर्धारित किया जा रहा है जिसका अर्थ है कि निश्चित रूप से टक्कर हो सकती है। आपको 32-बिट्स का पूर्ण उपयोग नहीं मिल रहा है। यह हैश टेबल की तरह है ... आप एक बड़ी इंडेक्सिंग स्पेस को एक छोटे से कम करते हैं। – FogleBird
"आप की गारंटी है कि वहाँ कोई टकराव हो जाएगा" नहीं, तुम नहीं कर रहे हैं क्योंकि नक्शे के आकार हैश के आकार से छोटी है: नहीं उदाहरण के लिए यदि नक्शे के आकार, दो है तो एक टक्कर की गारंटी है (इससे कोई फर्क नहीं पड़ता कि हैश) अगर/जब मैं तीन तत्व डालने का प्रयास करता हूं। – ChrisW
यह मूल रूप से अधिकांश प्रोग्रामिंग भाषाओं में अधिकांश हैश तालिका कार्यान्वयन के लिए जाता है, क्योंकि एल्गोरिदम स्वयं वास्तव में नहीं बदलता है।
कोई तालिका में मौजूद टकराव देखते हैं, तो आप केवल एक ही लुक-अप करने के लिए है, इसलिए चल रहा है समय हे है (1)। यदि टकराव मौजूद हैं, तो आपको एक से अधिक लुक-अप करना होगा, जो ओ (एन) की ओर प्रदर्शन को कम करता है।
यह मानता है कि चलने का समय लुकअप समय से घिरा हुआ है। अभ्यास में आपको कई स्थितियां मिलेंगी जहां हैश फ़ंक्शन सीमा प्रदान करता है (स्ट्रिंग) –
याद रखें कि ओ (1) मतलब यह नहीं है प्रत्येक देखने केवल एक आइटम की जांच करता है कि - इसका मतलब है कि आइटम की औसत संख्या की जाँच की निरंतर बनी हुई है w.r.t. कंटेनर में वस्तुओं की संख्या। इसलिए अगर 100 आइटम वाले कंटेनर में किसी आइटम को ढूंढने के लिए औसतन 4 तुलनाएं होती हैं, तो इसमें 10000 आइटम वाले कंटेनर में किसी आइटम को खोजने के लिए औसत 4 तुलनाएं भी लेनी चाहिए, और किसी भी अन्य आइटम के लिए (हमेशा एक भिन्नता का थोड़ा सा, विशेष रूप से उन बिंदुओं के आस-पास जहां हैश तालिका रीहैश होती है, और जब बहुत कम संख्या में आइटम होते हैं)।
तो टकराव के रूप में लंबे बाल्टी प्रति कुंजी की औसत संख्या के भीतर एक निश्चित बाध्य बना हुआ है क्योंकि ओ (1) के संचालन होने से कंटेनर को रोकने नहीं है।
आप औसत-मामले (अपेक्षित) रनटाइम के साथ सबसे खराब केस व्यवहार को मिश्रित करते हैं। पूर्व वास्तव में हैश टेबल के लिए ओ (एन) है (यानी एक परिपूर्ण हैशिंग का उपयोग नहीं कर रहा है) लेकिन यह अभ्यास में शायद ही कभी प्रासंगिक है।
कोई भी भरोसेमंद हैश तालिका कार्यान्वयन, जिसमें आधे सभ्य हैश के साथ, ओ (1) का एक पुनर्प्राप्ति प्रदर्शन होता है, जिसमें अपेक्षित मामले में एक बहुत ही कम कारक (वास्तव में) होता है, भिन्नता के बहुत संकीर्ण मार्जिन के भीतर।
मैंने हमेशा सोचा है कि ऊपरी बाउंड सबसे खराब मामला था, लेकिन ऐसा प्रतीत होता है कि मुझे गलत था - आप औसत मामले के लिए ऊपरी बाउंड कर सकते हैं। तो ऐसा प्रतीत होता है कि ओ (1) का दावा करने वाले लोगों ने यह स्पष्ट कर दिया होगा कि औसत मामले के लिए था। सबसे खराब मामला एक डेटा सेट है जहां कई टकराव इसे ओ (एन) बनाते हैं। यह अब समझ में आता है। – paxdiablo
आपको शायद यह स्पष्ट करना चाहिए कि जब आप औसत मामले के लिए बड़े ओ नोटेशन का उपयोग करते हैं तो आप अनुमानित रनटाइम फ़ंक्शन पर ऊपरी बाउंड के बारे में बात कर रहे हैं जो स्पष्ट रूप से परिभाषित गणितीय फ़ंक्शन है। अन्यथा आपका जवाब ज्यादा समझ में नहीं आता है। – ldog
gmatt: मुझे यकीन नहीं है कि मैं आपकी आपत्ति को समझता हूं: बड़े-ओ नोटेशन फ़ंक्शन पर ऊपरी बाउंड है * परिभाषा *। इसलिए मैं और क्या मतलब कर सकता था? –
यह टकराव से बचने के लिए आपके द्वारा चुने गए एल्गोरिदम पर निर्भर करता है।यदि आपका कार्यान्वयन अलग श्रृंखला का उपयोग करता है तो सबसे खराब स्थिति परिदृश्य होता है जहां प्रत्येक डेटा तत्व एक ही मूल्य (उदाहरण के लिए हैश फ़ंक्शन की खराब पसंद) पर पड़ता है। उस स्थिति में, डेटा लुकअप एक लिंक्ड सूची यानी ओ (एन) पर रैखिक खोज से अलग नहीं है। हालांकि, उस घटना की संभावना नगण्य है और लुकअप सर्वोत्तम और औसत मामले स्थिर रहते हैं यानी ओ (1)।
हम स्थापित कर लिया है हैश तालिका लुकअप के मानक वर्णन किया जा रहा है कि हे (1) के लिए संदर्भित करता है के द्वारा इस बारे में बात औसत मामले के अनुमानित समय तक, सख्त सबसे खराब केस प्रदर्शन नहीं। चेनिंग (जैसे जावा के हैशपैप) के साथ टकराव को हल करने वाली हैश तालिका के लिए यह तकनीकी रूप से ओ (1 + α) a good hash function है, जहां α तालिका का लोड कारक है। तब तक स्थिर रहें जब तक आप जो ऑब्जेक्ट्स संग्रहीत कर रहे हैं, वह टेबल आकार से अधिक स्थिर कारक से अधिक नहीं है।
यह भी समझाया गया है कि इनपुट बनाने के लिए सख्ती से बोलना संभव है जिसके लिए O (n) किसी भी निर्धारक हैश फ़ंक्शन के लिए लुकअप की आवश्यकता होती है।लेकिन सबसे बुरी स्थिति अपेक्षित समय पर विचार करना भी दिलचस्प है, जो औसत खोज समय से अलग है। चेनिंग का उपयोग करना ओ (1 + सबसे लंबी श्रृंखला की लंबाई) है, उदाहरण के लिए Θ (लॉग एन/लॉग लॉग एन) जब α = 1।
आप सैद्धांतिक तरीके लगातार समय की उम्मीद बुरी से बुरी हालत लुकअप को प्राप्त करने में रुचि रखते हैं, तो आप पढ़ सकते हैं के बारे में dynamic perfect hashing जो टकराव एक और हैश तालिका के साथ रिकर्सिवली निराकरण!
यदि बाल्टी की संख्या (इसे कॉल करें) स्थिर (सामान्य मामला) आयोजित की जाती है, तो लुकअप वास्तव में ओ (एन) है।
चूंकि एन बड़ा हो जाता है, प्रत्येक बाल्टी औसत में तत्वों की संख्या एन/बी। यदि टकराव समाधान सामान्य तरीकों में से एक में किया जाता है (उदाहरण के लिए लिंक की गई सूची), तो लुकअप ओ (एन/बी) = ओ (एन) है।
ओ नोटेशन तब होता है जब एन बड़ा और बड़ा हो जाता है। कुछ एल्गोरिदम पर लागू होने पर यह भ्रामक हो सकता है, और हैश टेबल बिंदु में एक मामला है। हम कितने तत्वों से निपटने की उम्मीद कर रहे हैं, इस आधार पर हम बाल्टी की संख्या चुनते हैं। जब n बी के समान आकार के बारे में होता है, तो लुकअप लगभग स्थिर समय होता है, लेकिन हम इसे ओ (1) नहीं कह सकते हैं क्योंकि ओ को एन → ∞ के रूप में सीमा के संदर्भ में परिभाषित किया गया है।
यह ओ (1) केवल तभी है जब आपका हैशिंग फ़ंक्शन बहुत अच्छा हो। जावा हैश तालिका कार्यान्वयन खराब हैश कार्यों के खिलाफ सुरक्षा नहीं करता है।
चाहे आप आइटम जोड़ते समय टेबल को बढ़ाना चाहते हैं या नहीं, प्रश्न के लिए प्रासंगिक नहीं है क्योंकि यह लुकअप समय के बारे में है।
शिक्षाविदों एक तरफ, एक व्यावहारिक दृष्टिकोण से, HashMaps एक अप्रासंगिक प्रदर्शन प्रभाव होने के रूप में स्वीकार किया जाना चाहिए (जब तक अपने प्रोफाइलर आप अन्यथा बताता है।)
व्यावहारिक अनुप्रयोगों में नहीं। जैसे ही आप एक कुंजी के रूप में एक स्ट्रिंग का उपयोग करते हैं, आप देखेंगे कि सभी हैश फ़ंक्शन आदर्श नहीं हैं, और कुछ वास्तव में धीमे हैं। –
O(1+n/k) जहां k बकेट की संख्या है।
कार्यान्वयन सेट करता है k = n/alpha तो यह O(1+alpha) = O(1) है के बाद से alpha एक निरंतर है।
निरंतर ** अल्फा ** क्या इंगित करता है? –
मुझे पता है कि यह एक पुराना सवाल है, लेकिन वास्तव में इसका एक नया जवाब है।
आप सही हैं कि हैश नक्शा वास्तव में O(1) नहीं है, सख्ती से बोल रहा है, क्योंकि तत्वों की संख्या मनमाने ढंग से बड़ी हो जाती है, अंततः आप निरंतर समय में खोज नहीं पाएंगे (और ओ-नोटेशन में परिभाषित किया गया है संख्याओं की शर्तें जो मनमाने ढंग से बड़ी हो सकती हैं)।
लेकिन यह नहीं है कि वास्तविक समय जटिलता O(n) है - क्योंकि ऐसा कोई नियम नहीं है जो कहता है कि बाल्टी को रैखिक सूची के रूप में कार्यान्वित किया जाना है।
वास्तव में, जावा 8 बार्स को TreeMaps के रूप में लागू करता है जब वे थ्रेसहोल्ड से अधिक हो जाते हैं, जो वास्तविक समय O(log n) बनाता है।
केवल सैद्धांतिक मामले में, जब हैशकोड हमेशा अलग होते हैं और प्रत्येक हैश कोड के लिए बाल्टी भी अलग होती है, तो ओ (1) मौजूद होगा। अन्यथा, यह निरंतर क्रम है यानी हैशपैप की वृद्धि पर, खोज का उसका क्रम निरंतर बना रहता है।
हैश मैप के अंदर तत्वों को लिंक की गई सूची (नोड) की सरणी के रूप में संग्रहीत किया जाता है, सरणी में प्रत्येक लिंक की गई सूची एक या अधिक कुंजी के अद्वितीय हैश मान के लिए बाल्टी का प्रतिनिधित्व करती है।
location = (arraylength - 1) & keyhashcode
यहाँ & बिटवाइज़ AND ऑपरेटर का प्रतिनिधित्व करता है:
HashMap में एक प्रविष्टि जोड़ते समय कुंजी hashCode सरणी में, जैसे कुछ बाल्टी के स्थान का निर्धारण किया जाता है।
उदाहरण के लिए: 100 & "ABC".hashCode() = 64 (location of the bucket for the key "ABC")
प्राप्त ऑपरेशन के दौरान यह कुंजी के लिए बाल्टी का स्थान निर्धारित करने में उसी तरह का उपयोग करता है। सबसे अच्छे मामले में प्रत्येक हैशकोड अद्वितीय है और प्रत्येक कुंजी के लिए एक अनूठी बाल्टी में परिणाम मिलता है, इस मामले में प्राप्त विधि केवल बाल्टी स्थान निर्धारित करने और स्थिर ओ (1) के मान को पुनर्प्राप्त करने के लिए समय बिताती है।
सबसे खराब स्थिति के तहत, सभी चाबियाँ एक ही hashCode है और एक ही बाल्टी में जमा हो जाती है, इस पूरी सूची जो हे (एन) की ओर जाता है के माध्यम से traversing का परिणाम है।
जावा 8 के मामले में, यदि आकार 8 से अधिक हो जाता है तो लिंक्ड लिस्ट बाल्टी को ट्रीमैप के साथ प्रतिस्थापित किया जाता है, इससे ओ (लॉग एन) में सबसे खराब केस सर्च दक्षता कम हो जाती है।
बिग ओ अंकन एक ऊपरी आप कर रहे हैं विश्लेषण के विशेष प्रकार के लिए बाध्य कर देता है। आपको अभी भी निर्दिष्ट करना चाहिए कि क्या आपको सबसे बुरी स्थिति, औसत मामले इत्यादि में रुचि है या नहीं। –
मुझे पता है कि यह कोई जवाब नहीं हो सकता है लेकिन मुझे याद है कि विकिपीडिया में [बहुत अच्छा लेख] है (http://en.wikipedia.org/wiki/हैश_टेबल) इसके बारे में। [प्रदर्शन विश्लेषण] न चूकें (http://en.wikipedia.org/wiki/Hash_table#Performance_analysis) अनुभाग –