Google साक्षात्कार प्रश्न

Question

यह Google साक्षात्कार प्रश्नों में से एक था।

क्या संभावित समस्या है अगर हैश तालिका 30 GB से अधिक (बुरा हैश फंक्शन जैसी समस्याओं पर ध्यान न दें)

मैं इसे नहीं पता था कि बढ़ता है। संतोषजनक उत्तर क्या हो सकता है?

धन्यवाद

Answer 1

कुछ समस्याओं:

1. Hash Collision बड़ी समस्या संभव में से एक हो सकता है।
2. डिस्क में डेटा स्टोर हैश टेबल के रूप में अक्सर डिस्क पढ़ने के लिए अक्षम भी होगा।

Answer 2

मुझे लगता है कि साक्षात्कारकर्ता Distributed Hash table की तर्ज पर कुछ उम्मीद कर रहा था, (कम से कम वर्तमान 64-बिट दुनिया में) के बाद से एक 30GB हैश तालिका एक मशीन पर संग्रहीत नहीं किया जा सकता है; मेरे व्यक्तिगत अनुभव से, कुछ Google क्यू वितरित कंप्यूटिंग, मानचित्र-कमी इत्यादि के आसपास घूमते हैं,

Answer 3

उत्तर आंशिक रूप से इस बात पर निर्भर करता है कि वे क्लासिक हैशटेबल कार्यान्वयन (जैसे जावा में हैशटेबल/हैश मैप) के बारे में बात कर रहे हैं या कुछ और परिष्कृत। अंत में, आज के मानकों से एक ही मशीन/वीएम के लिए 30 जीबी मेमोरी अभी भी काफी बड़ी है।

तो क्या नीचे हो रहा है के बारे में सोचना:

1. यह कुछ बड़े पैमाने पर सरणी में एक मनमाना स्थिति में लिखने पढ़ने के लिए है।
2. अगर यह कुछ उपाय से परे भर जाता है तो इसे बढ़ना होगा; जावा कार्यान्वयन में 'लोड फैक्टर' देखें।
   1. यह स्पष्ट नहीं है कि:
   2. एक कचरा एकत्र भाषा/कार्यान्वयन में, सभी वस्तुओं हैश तालिका में संग्रहीत कचरा कलेक्टर

   निम्नलिखित में से कौन समस्याओं को जन्म देता द्वारा निरीक्षण किया जाना करने की जरूरत है यहां तक ​​कि आज के ऑपरेटिंग सिस्टम जीबी के

3. में स्मृति के सभी हिस्सों को आवंटित करने के साथ अच्छी तरह से सौदा करते हैं, सरलता के लिए, तालिका का आधा वास्तव में तालिका द्वारा उपयोग किया जाता था (कुंजी और मूल्य वस्तु नहीं)। तो अंदर एक 15 जीबी सरणी है। इसलिए जब भी टेबल बढ़ता है, तो आपको कम से कम आवंटित करने की आवश्यकता होती है 15 जीबी
4. भले ही जीबी सरणी के दसियों आवंटित किए गए हों, ओएस इस स्मृति में से कुछ को पृष्ठ देगा। चूंकि हम एक अच्छा हैश फ़ंक्शन मान रहे हैं, इसलिए हम सरणी में अधिकांश डेटा का उपयोग करते हुए पेज कैशिंग तोड़ देंगे। बहुत सारे पेज दोष होंगे।
5. मान लें कि हम सभी डेटा का उपयोग नहीं करते हैं। कुछ चाबियाँ अक्सर उपयोग की जाती हैं, और अन्य नहीं हैं। उदाहरण के लिए, कहें कि प्रत्येक कुंजी-मान छोटा है - 128 बाइट्स। और सादगी के लिए, कहें कि हम सब कुछ हैश तालिका में मूल्यों के रूप में स्टोर करते हैं। तो 30 जी/128 = ~ 250 एम प्रविष्टियां। लेकिन 25k आमतौर पर इस्तेमाल की जाने वाली चाबियाँ कहें। (25k/250M = 0.01%)। लेकिन एक हैश समारोह के साथ, यह बड़े पैमाने पर सरणी में समान रूप से बिखरे हुए होंगे। यहां तक ​​कि छोटे पेज आकारों के साथ - 4kb, 25K (प्रविष्टियां) * 128 बाइट्स (प्रवेश आकार) = ~ 3 कहें।आम तौर पर इस्तेमाल किए गए डेटा के 5 एमबी मूल्य हमें 25K (प्रविष्टियां) * 4K (पेज आकार) = ~ 100 एमबी मेमोरी की लागत लेते हैं जिन्हें 3.5% दक्षता पर ... में रखा जाना चाहिए!
6. जावा दुनिया में, चिकित्सक ढेर आकारों की सिफारिश नहीं करते हैं कि 4 - 8 जीबी। निश्चित रूप से Azul जैसी चीजें हैं, लेकिन यह केवल बिंदु साबित करती है - एक ठेठ कचरा कलेक्टर इन आकारों को बहुत अच्छी तरह से स्केल नहीं करता है।

मैं अन्य पोस्टर्स से सहमत हूं कि Google समाधान के रूप में वितरित की तलाश में है। लेकिन मुझे लगता है कि दिल में, एक साधारण हैशटेबल एक बिंदु से परे स्केलिंग बंद कर देता है। इसके बाद के संस्करण में,

1. आप वितरित करने के लिए करता है, तो सभी प्रविष्टियों अपेक्षाकृत समान रूप से एक्सेस किया जाता है
2. कुछ समय के बहुमत पहुँचा रहे हैं, तो दो नक्शे (सबसे अधिक इस्तेमाल के लिए एक) का उपयोग कर के लिए होता है आप खरीद सकते हैं एक बहुत।
3. जावा दुनिया में, ढेर से डेटा स्टोर करने वाले विशेष मानचित्रों का उपयोग करके आप भी प्रदर्शन खरीद सकते हैं; उदाहरण के लिए Peter Lawrey's work देखें।
4. यहां तक ​​कि केवल हैशटेबल में अंतर्निहित सरणी को दबाकर (जैसे जावा के कंसूरेंट हैश मैप करता है) आपको हैशटेबल विकसित करने के लिए प्रमुख सुधार खरीद सकता है।