जब हम हैश तालिका में एक कुंजी डालते हैं/लुकअप करते हैं, तो पाठ्यपुस्तक ने कहा कि यह ओ (1) समय है। फिर भी, ओ (1) लुकअप समय कैसे संभव है? यदि हैश टेबल एक वेक्टर में कुंजी स्टोर करता है, तो यह ओ (एन) खर्च करेगा, अगर बाइनरी पेड़ में, तो यह ओ (लॉगएन) होगा। मैं ओ (1) समय तक पहुंचने के साथ कुछ डेटा संरचना को चित्रित नहीं कर सकता।हैश टेबल लुकअप समय
धन्यवाद!
हैशटेबल आपकी कुंजी है और इसे सरणी में रखता है।
उदाहरण के लिए, हैश (x) = 3, जहां x आपकी कुंजी है। तब तालिका इसे सरणी में रखती है [3]। सरणी से एक्सेस ओ (1) है।
कम से कम, हैश टेबल में एक सरणी और हैश फ़ंक्शन शामिल है। जब किसी ऑब्जेक्ट को तालिका में जोड़ा जाता है, तो हैश फ़ंक्शन ऑब्जेक्ट पर गणना की जाती है और यह गणना की गई मान के सूचकांक पर सरणी में संग्रहीत होती है। उदाहरण के लिए, यदि hash(obj) = 2 तो arr[2] = obj।
हैश तालिका पर औसत डालने/लुकअप O(1) है।
हालांकि ऑब्जेक्ट्स एक ही हैश मान की गणना करते समय टक्कर लगाना संभव है।
सामान्य मामले में इन टकरावों को संभालने के लिए सरणी के प्रत्येक सूचकांक में "बाल्टी" होती है। मतलब, हैश तालिका के सूचकांक पर सभी तीन वस्तुओं को कुछ अन्य डेटा संरचना (शायद एक लिंक्ड सूची या अन्य सरणी) में संग्रहीत किया जाता है।
इसलिए, हैश तालिका पर लुकअप के लिए सबसे खराब मामला O(n) है क्योंकि यह संभव है कि हैश तालिका में संग्रहीत सभी ऑब्जेक्ट टकराए और उसी बाल्टी में संग्रहीत हो जाएं।
हैश तालिका पर लुकअप के लिए सबसे खराब मामला 'ओ (एन) 'है। विचार करें: 'हैश (एक्स) = 3',' हैश (वाई) = 3' 'हैश (जेड) = 3', इत्यादि। –