हैशिंग के पास ओ (1) खोज समय कैसा है?

Question

जब हम डेटा संग्रहीत करने के लिए HashTable का उपयोग करते हैं, तो ऐसा कहा जाता है कि खोज ओ (1) समय लेती है। मैं उलझन में हूं, क्या कोई समझा सकता है?

Answer 1

वैसे यह थोड़ा झूठ का थोड़ा सा है - इसमें इससे अधिक समय लग सकता है, लेकिन आमतौर पर ऐसा नहीं होता है।

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

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

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

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

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

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

Answer 2

खोज में हे (1) समय लगता है यदि हैशटेबल में कोई टकराव नहीं है, तो यह है कि हैशटेबल में खोज करना सी (ओ) या निरंतर समय लेता है।

See how Hashtable works on MSDN?

संपादित

mgiuca यह खूबसूरती से बताते हैं और मैं बस एक और Collosion परिहार तकनीक है जो श्रृंखलन कहा जाता है जोड़ने कर रहा हूँ।

इस तकनीक में, हम प्रत्येक स्थान पर मूल्यों की एक लिंकलिस्ट बनाए रखते हैं, इसलिए जब आपके पास एक टक्कर हो, तो आपका मूल्य उस स्थिति में लिंकलिस्ट में जोड़ा जाएगा ताकि जब आप कोई मूल्य खोज रहे हों तो वहां परिदृश्य हो सकता है संपूर्ण लिंक सूची में मूल्य की खोज करने के लिए, इसलिए उस स्थिति में खोज ओ (1) ऑपरेशन नहीं होगी।