7
मैं हैश तालिका डेटा संरचना के मूल सिद्धांत को जानता हूं। अगर मेरे पास आकार एन की हैश तालिका है, तो मुझे अपने डेटा को इन एन बाल्टी में जितना संभव हो उतना वितरित करना होगा।एक गतिशील आकार हैश तालिका को कैसे कार्यान्वित करें?
लेकिन वास्तव में, अधिकांश भाषाओं में उनके अंतर्निहित हैश तालिका प्रकार होते हैं। जब मैं उनका उपयोग करता हूं, मुझे पहले से हैश टेबल के आकार को जानने की आवश्यकता नहीं है। मैं बस कुछ भी चाहता हूं जो मैं चाहता हूं। उदाहरण के लिए, Ruby:
h = {}
10000000.times{ |i| h[i]=rand(10000) }
यह कैसे कर सकता है?
एक अच्छा रीहशिंग दृष्टिकोण तालिका के आकार को दोगुना करना है, और फिर जब आप किसी मान की खोज करते हैं, तो आप इसकी कुंजी हैश करते हैं, और 'हैश% current_size' से शुरू होने वाली अपनी हैश तालिका में एक मॉडुलू खोज करते हैं, फिर' हैश % current_size/2', आदि। जब आपको मान मिल जाए, तो आप इसे पुनः प्राप्त कर सकते हैं। इस तरह आप बहुत अधिक प्रदर्शन खोए बिना आलसी रिहाशिंग कर सकते हैं, क्योंकि आम तौर पर एक्सेस किए गए मान स्वचालित रूप से पुनः प्राप्त होते हैं। –
@DvirVolk, आलसी rehash अच्छा है। आप पहले से ही सबसे अधिक हैश तालिका में प्रवेश जानते हैं और जानते हैं कि निचले हैश टेबल से कहां से इंस्टॉलेशन करना है। लेकिन आपके पास स्थिति हो सकती है जब कुछ प्रविष्टि खाली बाल्टी की पूरी मेज रखेगी। विकी से "वृद्धिशील आकार" डेटा के आकार के लिए ट्रेडऑफ गति का समाधान है जैसा कि मैं समझता हूं (अंत में आप 2 * एन बाल्टी धारण करते हैं जहां एन शीर्षतम हैश तालिका का आकार है)। दोगुनी आकार "सभी प्रविष्टियों की प्रतिलिपि" के लिए अच्छा है, इस तथ्य से कि आपको एकल बाल्टी को दो में विभाजित करना है या पुरानी बाल्टी की लिंक्ड-सूचियों का पुन: उपयोग करने के साथ दो में एक हैश (बिना हैश पुनर्मूल्यांकन के) विलय करना है। – ony