एक ऐसे मान के लिए हैशटेबल खोज रहा है जो ओ (एन) नहीं है? (रैखिक जांच)

Question

बस रैखिक जांच तर्क को समझने की कोशिश कर रहा है।

खुले पते का उपयोग करके हैशटेबल के साथ, आप कभी भी पुष्टि कैसे कर सकते हैं कि कोई तत्व तालिका में नहीं है।

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

अब, सिर्फ इसलिए कि एक बाल्टी खाली है, ऐसा लगता है कि मानचित्र में कोई तत्व मौजूद नहीं है। जैसे तत्व ए को पहले हटा दिए जाने के बाद आप तत्व बी की खोज करते हैं। सबसे पहले आपको एक खाली बाल्टी मिलती है जहां आप बी की अपेक्षा करते हैं, लेकिन आपको एक और जांच करने की आवश्यकता है और आपको बी मिल जाएगा। यह वास्तव में है। यदि वह तर्क सही है तो क्या आपको यह पुष्टि करने के लिए पूरी तालिका खोजनी पड़ेगी कि कोई कुंजी नहीं है? यानी ओ (एन) प्रदर्शन हर बार।

मैं जो कह रहा हूं वह है, क्या आपको पूरे मानचित्र के माध्यम से वास्तव में पुष्टि करने की आवश्यकता नहीं है कि यह वहां नहीं है?

हैशप के लिए एक अलग श्रृंखला दृष्टिकोण के साथ यह समस्या मौजूद नहीं है।

संपादित करें: मैं क्या मतलब इस तस्वीर http://upload.wikimedia.org/wikipedia/commons/b/bf/Hash_table_5_0_1_1_1_1_0_SP.svg

तो जॉन स्मिथ हटा दी जाती है, को देख रहा है और हम सैंड्रा डी का पता लगाने का प्रयास करें।

या रैखिक पते के साथ आप तत्वों को चारों ओर स्थानांतरित करने के लिए हैं ताकि इस तरह के कोई छेद न हो। यानी यदि जॉन स्मिथ हटा दिया गया है तो 152 से 154 के तत्वों को एक स्थान पर वापस ले जाना चाहिए? यह वास्तव में वर्णन में नहीं देखता है लेकिन इससे कुछ समझ हो सकती है। सिवाय इसके कि टेड बेकर 154 तक और 153 के अनुसार वर्णित नहीं है। मैंने सोचा की तुलना में थोड़ा और काम की आवश्यकता है।

बस प्रत्येक बाल्टी पर एक साधारण लिंक्ड सूची के साथ जा सकते हैं।

Answer 1

पूर्ण बुरे मामले में, हाँ यह निर्धारित करने के लिए एल्गोरिदम है कि तालिका में कुछ आइटम है या नहीं (ओ) है। हालांकि, यह ठीक से प्रबंधित हैश तालिका में कभी नहीं होगा।

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

जांच अनुक्रम में प्रत्येक स्लॉट के माध्यम से आपको खोजना होगा एकमात्र तरीका यह है कि जांच अनुक्रम में कोई खाली स्लॉट नहीं है। चूंकि आपको हमेशा हैश टेबल का आधा खाली होना चाहिए, ऐसा नहीं होना चाहिए।

Answer 2

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

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

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

Answer 3

मुझे लगता है कि यह देर हो चुकी है, लेकिन जांच अनुक्रम और हैश तालिका के लिए अधिकतम जांच अनुक्रम का उल्लेख है।

प्रत्येक बार जब आप कोई तत्व डालते हैं, तो आप वास्तव में एक ट्रैक रखते हैं कि आपके द्वारा पहले से किए गए प्रोब की अधिकतम संख्या क्या है, और यह है कि मौजूदा तत्व डालने के लिए आपके द्वारा किए गए प्रोबों की संख्या से 'maxProb' छोटा है ।

आखिरकार जब आप हैशटेबल में कोई तत्व खोज रहे हैं, तो आप केवल अधिकतम मैक्सप्रोब खोज करेंगे।

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

मान लें कि आपकी हैश कुंजी पीढ़ी एल्गोरिदम ऐसा है कि यह आपको कई बार जांचने के लिए मजबूर कर रहा है, तो आप डेटा संरचना को इस तरह से कार्यान्वित कर सकते हैं, कि यदि कोई प्रविष्टि एक्स जांच लेता है, तो उसे खुद को फिर से खोलना चाहिए ।