यह एक साक्षात्कार प्रश्न है।एक हैशटेबल के प्रदर्शन को 1 मिलियन तत्वों और 997 बाल्टी के साथ कैसे सुधारें?
मान लीजिए कि तालिका में 1 मिलियन तत्व हैं और 997 बाल्टी अनियंत्रित सूचियां हैं। आगे मान लीजिए कि हैश फ़ंक्शन समान संभावना वाले कुंजियों को वितरित करता है (यानी, प्रत्येक बाल्टी में 1000 तत्व होते हैं)।
तालिका में मौजूद तत्व को खोजने का सबसे बुरा समय क्या है? तालिका में मौजूद एक को खोजने के लिए? आप इसे कैसे सुधार सकते हैं?
मेरा समाधान: तालिका में और तालिका में नहीं तत्व को खोजने का सबसे बुरा मामला सभी ओ (1000) है। 1000 अनुरक्षित सूची की लंबाई है।
इसे सुधारें: (0) सीधा, बाल्टी संख्या> 1 मिलियन बढ़ाएं। (1) प्रत्येक बाल्टी में दूसरा हैशटेबल होता है, जो दूसरी तालिका के लिए हैश मान की गणना करने के लिए एक अलग हैश फ़ंक्शन का उपयोग करता है। यह ओ (1) (2) प्रत्येक बाल्टी में एक बाइनरी खोज पेड़ होगा। यह ओ (एलजी एन) होगा।
अंतरिक्ष और समय के बीच व्यापार-बंद करना संभव है। दोनों को उचित सीमा में रखें।
कोई बेहतर विचार? धन्यवाद !
ओ (1000) ओ (1) है। –
मुझे पता है लेकिन मैं सबसे खराब केस समय दिखाना चाहता हूं। धन्यवाद – user1002288
@ आर। मार्टिनिन्हो फर्नांडीस: यह रैली ओ (1000) नहीं है हालांकि यह है। (प्रत्येक बाल्टी मानना एक सूची है) यह ओ (एन/1000) => ओ (एन) की तरह है। जब आप हैश इतनी उत्तेजित रूप से ओवरलोड हो जाते हैं तो यह वास्तव में एक हैश नहीं है, यह अब लिंक्ड सूचियों का एक सेट है (या जो कुछ भी संरचना है वह बाल्टी लागू करता है)। –