कितने हैश बाल्टी

Question

यदि मुझे लगता है कि हैश तालिका (या हैश तालिका पर निर्मित कोई अन्य डेटा संरचना) भर रही है, तो आपको किस बिंदु पर अधिक बाल्टी के साथ एक नई तालिका बनाना चाहिए। और अब तक तालिका में एन आइटम दिए गए हैं, आप कैसे पता लगाते हैं कि नए में कितने बाल्टी उपयोग करना है?

तो मान लें कि मेरे पास 100 बाल्टी हैं। क्या इसमें 50 वस्तुओं के साथ पुनर्गठन करना चाहिए? 500? 5000? या मुझे उस पर सबसे पूर्ण बाल्टी और कुंजी की तलाश करनी चाहिए? तब जब मैंने उस बिंदु पर मारा तो मैं नई हैश टेबल कितनी बड़ी बनाती हूं?

इससे संबंधित, यदि आप पहले से जानते हैं कि कितनी वस्तुओं में जाना होगा, तो क्या औसत औसत प्रदर्शन प्राप्त करने के लिए बाल्टी की संख्या की गणना करने का कोई तरीका है?

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

मुझे यह भी पता है कि मुझे इस तरह की चीज को अनुकूलित नहीं करना चाहिए जब तक कि अच्छी प्रोफाइलिंग ने संकेत न दिया हो कि यह एक बाधा है। मैं बस एक ऐसी परियोजना के बारे में सोच रहा हूं जो बहुत सारी हैश टेबल का उपयोग करेगी और आश्चर्य करेगी कि इस तक कैसे पहुंचे।

Answer 1

अंगूठे का एक अच्छा नियम (हमेशा आदर्श नहीं, अच्छी तरह से, केवल अंगूठे का नियम) हैशटेबल 80% तक भरने के लिए फिर से हैश है। इसका मतलब है कि यदि आपके पास 100 बाल्टी और 80 आइटम हैं, भले ही आपके पास कितनी टक्कर हो, तो क्षमता बढ़ाने के लिए समय मिल रहा है।

आपको इसे कितना बढ़ाया जाना चाहिए? खैर, कोई सही मूल्य भी नहीं है। सरलतम समाधान प्रत्येक वृद्धि पर क्षमता को दोगुना करना है। तो यह 200, 400, 800, और इतने पर चला जाता है। यदि आपको लगता है कि यह बहुत अधिक है (आखिरकार यह 8 एमबी मेमोरी से 16 एमबी तक कूद जाएगा जब हैशटेबल वास्तव में बड़ा हो जाएगा और आप 16 एमबी कभी भर नहीं सकते हैं), एक छोटे से बढ़ने वाले कारक का चयन करें। कम से कम 1/3 अनुशंसा की जाती है (इसे 100 से 133 तक बढ़ाना) मैं कहूंगा, शायद यह समझौता के रूप में हर बार 50% तक बढ़ने दें।

ध्यान दें कि यह सब भी निर्भर करता है कि टक्कर कैसे संभाले जाते हैं। उन्हें संभालने का एक आसान तरीका (मेरा निजी पसंदीदा) टकराव होने पर वस्तुओं को एक लिंक्ड सूची में स्टोर करना है। यदि एक ही कुंजी पर 3 आइटम रखे जाते हैं, तो अभी भी इसे खोजने के लिए केवल 3 तक की तुलना की जाती है। चूंकि लिंक्ड सूची खोज के लिए बहुत अप्रभावी है, इसलिए आप पहले क्षमता में वृद्धि करना चाहेंगे, उदाहरण के लिए यदि हैशटेबल को तेज़ रखने के लिए 60% क्षमता का उपयोग किया जाता है। ओटीओएच, आप कुछ और परिष्कृत कर सकते हैं और टकराव की संख्या के बारे में आँकड़े रख सकते हैं। जब तक आपके पास कोई टक्कर नहीं है (यदि आपके पास बहुत अच्छा हैश फ़ंक्शन है) तो फिर भी हैश की आवश्यकता नहीं है, भले ही इसकी 99% क्षमता का उपयोग हो। इसके अलावा यदि आप एक परिष्कृत तरीके से टक्कर संभालते हैं (उदा।प्रत्येक नोड फिर से एक क्रमबद्ध तालिका है और आप इनके भीतर बाइनरी खोज कर सकते हैं) यदि तालिका 200% तक लोड हो जाती है तो आपका लुकअप अभी भी तेज़ हो सकता है (इसलिए आपके पास क्षमता के रूप में दो गुना अधिक आइटम हैं)। उस स्थिति में आप आंकड़े रख सकते हैं कि सबसे बड़ी क्रमबद्ध तालिका कितनी बड़ी है और जब यह बड़ी हो जाती है, तो मान लें कि 8 प्रविष्टियां, आपको लगता है कि यह बहुत धीमी हो रही है और फिर आप फिर से हैश कर रहे हैं।

री-हैशिंग बहुत धीमी है, इसलिए इसे जितनी बार संभव हो से बचा जाना चाहिए। इस प्रकार यदि आपको पुनः-हैश की आवश्यकता है, तो केवल क्षमता को बहुत कम न करें, अन्यथा आपको अधिक आइटम जोड़ते समय फिर से फिर से हैश करना होगा। तो जब आपको पुनः-हैश की आवश्यकता होती है, तो तालिका में वर्तमान में आइटम की संख्या की तुलना में क्षमता को काफी बड़ा बनाते हैं, बाकी सब कुछ बहुत कम क्षमता है।

Answer 2

आमतौर पर, आप लोड फैक्टर (अनौपचारिक रूप से, आप पहले से ही कहा कि) जो औपचारिक रूप से परिभाषित किया गया है के लिए बाहर देखने α   =   n  /  एन है, यानी कुल बाल्टी के लिए इस्तेमाल किया के अनुपात के रूप में। आदेश में एक हैश तालिका ठीक ढंग से काम करने के लिए (या गणितीय संदर्भ में अपने प्रदर्शन के बारे में कम से कम तर्क करने) में, यह होना चाहिए   <   1.

α बाकी सब कुछ वास्तव में अनुभवजन्य परीक्षण पर निर्भर है: आपको लगता है कि देखते हैं, तो आपके हैश तालिका α  >   0.5 पर अच्छी शुरुआत नहीं करती है, तो उस मान के तहत रहना सुनिश्चित करें। यह मान भी आपके टकराव रिज़ॉल्यूशन तकनीक पर निर्भर करता है। चेनिंग के साथ हैशिंग के लिए खुले पते के साथ हैशिंग की तुलना में अन्य लोड कारकों की आवश्यकता हो सकती है। फिर भी एक और कारक कैश इलाके है। यदि आपकी मेज बहुत बड़ी हो जाती है, तो यह मुख्य स्मृति में फिट नहीं होगी। चूंकि सरणी में आपकी पहुंच यादृच्छिक है, इसलिए कैश से लोड करना एक बाधा बन सकता है।

Answer 3

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

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

Answer 4

आमतौर पर दो प्रकार के हैंशटेबल्स हैं: खुले और बंद।

खुले हैशटेबल में आपको हैश पर आधारित सही बाल्टी मिलती है, और उसके बाद उस बाल्टी को लटकाने वाली वस्तुओं की एक सूची बनाएं।

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

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

एक बंद हैशटेबल का आकार बदलता है जब लोड फैक्टर (हैशटेबल/बाल्टी के नंबर में वस्तुओं का नंबर) कुछ पूर्व निर्धारित मूल्य को हिट करता है। मैं 80% का उपयोग करता हूं, लेकिन सटीक मूल्य बहुत महत्वपूर्ण होने की संभावना नहीं है।

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

Answer 5

यदि आप लीनियर हैशिंग का उपयोग करते हैं, तो तालिका स्वचालित रूप से निरंतर लोड कारक बनाए रखकर आकार बदलने का ख्याल रखती है।