2009-11-03 20 views
5

में चाबियों के रूप में उपयोग करने के लिए स्वीकार्य प्रकारों को मुझे हैशटेबल्स कैसे काम करता है, इस बारे में केवल एक प्राथमिक समझ रखने के लिए स्वीकार करना चाहिए, हालांकि मुझे जो कुछ पता है उससे यह काफी सरल लगता है। मेरा सवाल यह है: ऐसा लगता है कि परंपरागत ज्ञान सरल, मूल मूल्य प्रकारों जैसे कि हैशटेबल में चाबियों के पूर्णांक का उपयोग करना है। हालांकि, तारों का भी अक्सर उपयोग किया जाता है, भले ही कई भाषाओं में उन्हें संदर्भ प्रकार के रूप में लागू किया जाता है। मुझे लगता है कि आम तौर पर जटिल संदर्भ प्रकारों का उपयोग कर रहा है; मुझे लगता है कि ऐसा इसलिए है क्योंकि ऐसा करने से धीमे हैश फ़ंक्शन की आवश्यकता होगी? लेकिन फिर तारों का उपयोग आमतौर पर क्यों किया जाता है? आखिरकार, आंतरिक रूप से एक char [] सरणी नहीं है (फिर से, अधिकांश भाषाओं में)?हैशटेबल

अंत में, किस मूल्य प्रकार को आमतौर पर "सर्वश्रेष्ठ" (या यहां तक ​​कि "स्वीकार्य") विकल्प के रूप में माना जाता है जो हैशटेबल में कुंजी के रूप में उपयोग करने के लिए? और क्या वहां कोई सामान्य रूप से उपयोग किए जाने वाले विकल्प हैं जिन्हें वास्तव में "खराब" माना जाता है (जैसे स्ट्रिंग्स, संभवतः)?

उत्तर

1

सबसे अच्छा hash keys उन है कि

  1. हैश (कम collisions के रूप में) अच्छा है कर रहे हैं (जावा के लिए नेट के लिए Object.GetHashCode, Object.hashcode देखें)
  2. त्वरित तुलना है (जब वहाँ हैश टकराव रहे हैं के लिए) ।

सभी ने कहा, मुझे लगता है कि ज्यादातर मामलों में स्ट्रिंग्स अच्छी हैश कुंजी हैं, क्योंकि स्ट्रिंग्स के लिए कई उत्कृष्ट हैश कार्यान्वयन हैं।

3

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

तो असली मुश्किल हिस्सा हैश फ़ंक्शन ढूंढ रहा है। बेशक इसमें कुछ गुण होना चाहिए, जैसे कि गणना करने के लिए सरल होना, अराजकता (लगभग समान चाबियाँ पूरी तरह से अलग हैश टेबल बाल्टी में मैप की जानी चाहिए), निर्धारिती (एक ही कुंजी का मतलब हैश टेबल बाल्टी), एकरूपता (सभी संभावित कुंजी समान रूप से मैप की जाती हैं बाल्टी), या प्रक्षेपण (हैश तालिका की सभी बाल्टी का उपयोग किया जाना चाहिए)।

ऐसा लगता है कि इस तरह के फ़ंक्शन को सरल प्रकारों जैसे पूर्णांक के लिए परिभाषित करना आसान है।

+0

गलत! असली मुद्दा महत्वपूर्ण परिवर्तनशीलता है! – Gyom

+0

यह वास्तव में सच है। हालांकि यह एक निश्चित बात है कि किन कुंजियों को बराबर माना जाता है और जो नहीं हैं। – spa

4

अधिकांश स्ट्रिंग कार्यान्वयन, जबकि वे प्रबंधित वातावरण में संदर्भ प्रकार के रूप में प्रकट हो सकते हैं, उनके कार्यान्वयन आमतौर पर एक अपरिवर्तनीय प्रकार है।

हैश फ़ंक्शन क्या करता है यह है कि यह राज्यों की एक छोटी संख्या पर राज्यों की एक बड़ी संख्या को मानचित्र करता है।

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

यह वह जगह है जहां आप हैश तालिका में उपयोग की जाने वाली कुंजी के प्रकार के बारे में चर्चा अमान्य हो जाती है, क्योंकि यह उस मान का एक छोटा राज्य स्थान में मैपिंग है और इसका आंतरिक रूप से उपयोग कैसे किया जाता है जो इसे उपयोगी बनाता है। एक पूर्णांक आमतौर पर हार्डवेयर अनुकूल होता है, लेकिन 32-बिट वास्तव में एक बड़ी जगह नहीं है और मनमाने ढंग से इनपुट के लिए उस स्थान के भीतर टकराव की संभावना है।

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

+0

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

+0

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

+0

यह मेरे लिए काफी counterintuitive है। क्या आप यह कह रहे हैं कि, यदि मैं हैशटेबल में कोई आइटम जोड़ता हूं, तो बाद में उस आइटम को कुंजी से पुनर्प्राप्त करने के लिए चला जाता है, तो रनटाइम हैश फ़ंक्शन निष्पादित किए बिना उस कुंजी के लिए हैश कोड को जादुई रूप से जानता है? यह कैसे हो सकता है? –

1

आप कोई कुंजी तो के रूप में एक जटिल प्रकार उपयोग किया है तो:

  • यह तेजी से पुनः प्राप्ति के लिए बाल्टी में समूह आइटम के लिए हैश तालिका कार्यान्वयन के लिए मुश्किल हो सकता है; यह कैसे तय करेगा कि एक बाल्टी में हैश की एक श्रृंखला को कैसे समूहित किया जाए?
  • हैश तालिका को बाल्टी चुनने के लिए प्रकार के अंतरंग ज्ञान की आवश्यकता हो सकती है।
  • वस्तु बदलने के गुणों का जोखिम है, जिसके परिणामस्वरूप गलत बाल्टी में समाप्त होने वाली चीजें हैं। हैश अपरिवर्तनीय होना चाहिए।

इंटीजर आमतौर पर उपयोग किए जाते हैं क्योंकि बाल्टी से संबंधित श्रेणियों में विभाजित करना आसान होता है, वे मूल्य प्रकार होते हैं और इसलिए अपरिवर्तनीय होते हैं, और वे उत्पन्न करने के लिए काफी आसान होते हैं।

5

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

वैसे, यदि डेटा प्रकार हमेशा मूल्य (जैसे स्केलर्स) द्वारा पारित होने के लिए पर्याप्त सिंपल होता है, तो यह निश्चित रूप से ठीक रहेगा।

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

उम्मीद है कि इससे मदद मिलती है।

+0

यह एक बहुत ही उपयोगी उत्तर है; लेकिन मैं अब भी सोच रहा हूं कि कुछ ऐसे प्रकार हैं जो दूसरों की तुलना में चाबियों के रूप में उपयोग करने के लिए "बेहतर" हैं। उदाहरण के लिए, मान लीजिए कि मैंने एक कक्षा को परिभाषित किया है जो वास्तव में अपरिवर्तनीय है और अपने पूरे अस्तित्व के लिए उसी हैश कोड के साथ जारी रहेगा। क्या यह एक कुंजी के रूप में उपयोग करने के लिए पूरी तरह से ठीक है, या फिर भी यह एक पूर्णांक (प्रदर्शन कारणों के लिए) का उपयोग करने के लिए बेहतर होगा? ऐसा लगता है कि पूर्ण, व्यापक उत्तर आपके संयोजन का संयोजन होने की संभावना है (कुंजी अपरिवर्तनीय प्रकार होनी चाहिए) और स्पा (चाबियों के रूप में उपयोग किए जाने वाले प्रकारों में कुशल हैश फ़ंक्शन होना चाहिए) ... –

+0

@Dan: एक विशेष हैश तालिका की ज़रूरत है स्टोर करने के लिए उसे स्टोर करने की जरूरत है। यदि आप वेब कैश बनाए रखते हैं, तो आप URL के लिए सामग्री संग्रहीत कर रहे हैं। कुंजी को एक यूआरएल होना चाहिए, यह पूर्णांक नहीं हो सकता है, क्योंकि आप पूर्णांक नहीं देख रहे हैं। स्पष्ट रूप से तेज़ "बेहतर" है, लेकिन "जो मैं धीरे-धीरे चाहता हूं" हमेशा "बेहतर" होता है जो "वास्तव में तेज़ लेकिन पूरी तरह से बेकार है" :-) –

+0

यह भी ध्यान रखना महत्वपूर्ण है कि एक परिवर्तनीय वर्ग प्रकार का उपयोग करने में कुछ भी गलत नहीं है एक हैश-टेबल कुंजी के रूप में यदि कुंजी का उद्देश्य * किसी विशेष वस्तु को पहचानना * है। उदाहरण के लिए, .NET में, 'System.Windows.Forms.Form' बहुत म्यूटेबल प्रकार है (स्थिति जैसे गुण, इत्यादि के साथ जो किसी भी समय बदल सकता है) लेकिन कोई भी किसी अन्य चीज़ के साथ फ़ॉर्म को जोड़ने के लिए हैशटेबल का उपयोग कर सकता है। ध्यान दें कि ऐसी तालिका हमेशा अलग-अलग रूपों के दो संदर्भों को असमान होने के रूप में मानती है, भले ही उनकी पहचान के अलावा उनकी सभी संपत्तियां मिलें। – supercat

संबंधित मुद्दे