[Data-structures] हैश टेबल कैसे काम करता है?


Answers

उपयोग और लिंगो:

  1. डेटा (या रिकॉर्ड) को त्वरित रूप से स्टोर और पुनर्प्राप्त करने के लिए हैश टेबल का उपयोग किया जाता है।
  2. रिकॉर्ड्स हैश कुंजी का उपयोग कर बाल्टी में संग्रहीत हैं
  3. हैश कुंजियों की गणना रिकॉर्ड के भीतर निहित चुने गए मूल्य पर हैशिंग एल्गोरिदम लागू करके की जाती है। यह चुना गया मान सभी रिकॉर्ड्स के लिए एक आम मान होना चाहिए।
  4. प्रत्येक बाल्टी में कई रिकॉर्ड हो सकते हैं जो किसी विशेष क्रम में व्यवस्थित होते हैं।

असली दुनिया उदाहरण:

1803 में स्थापित हैश एंड कं , और लगभग 30,000 ग्राहकों के लिए विस्तृत जानकारी (रिकॉर्ड) रखने के लिए कुल 300 फाइलिंग अलमारियाँ थीं। प्रत्येक फ़ाइल फ़ोल्डर को इसकी अनूठी संख्या 0 से 2 9 9 तक स्पष्ट रूप से पहचाना गया था।

उस समय के फाइलिंग क्लर्कों को तुरंत काम करने वाले कर्मचारियों के लिए क्लाइंट रिकॉर्ड लाने और स्टोर करना पड़ा। कर्मचारियों ने फैसला किया था कि अपने रिकॉर्ड स्टोर और पुनर्प्राप्त करने के लिए हैशिंग पद्धति का उपयोग करना अधिक कुशल होगा।

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

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

हमारे असली दुनिया के उदाहरण में, हमारी बाल्टी कैबिनेट दर्ज कर रही हैं और हमारे रिकॉर्ड फ़ाइल फ़ोल्डर्स हैं

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

जैसा कि साइमन ने उल्लेख किया है कि मैं बहुत महत्वपूर्ण मानता हूं कि हैशिंग हिस्सा एक बड़ी जगह (मनमाने ढंग से लंबाई, आमतौर पर तारों, आदि) को बदलने और अनुक्रमण के लिए इसे एक छोटी सी जगह (ज्ञात आकार, आमतौर पर संख्याओं) में मैप करना है। यह याद रखना बहुत महत्वपूर्ण है!

तो उपरोक्त उदाहरण में, 30,000 संभावित ग्राहकों या तो एक छोटी जगह पर मैप किए गए हैं।

इसमें मुख्य विचार है कि आप अपने पूरे डेटा सेट को सेगमेंट में विभाजित करें ताकि वास्तविक खोज को तेज़ी से बढ़ाया जा सके। ऊपर दिए गए हमारे उदाहरण में, 300 फाइलिंग कैबिनेट में से प्रत्येक (सांख्यिकीय रूप से) में लगभग 100 रिकॉर्ड होंगे। 100 रिकॉर्ड के माध्यम से खोज (आदेश के बावजूद) 30,000 से निपटने की तुलना में बहुत तेज़ है।

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

उम्मीद है की यह मदद करेगा,

Jeach!

Question

मैं एक हैश टेबल कैसे काम करता है इसकी व्याख्या के लिए देख रहा हूं - सादे अंग्रेजी में मेरे जैसे साधारण के लिए!

उदाहरण के लिए, मुझे पता है कि यह कुंजी लेता है, हैश की गणना करता है (मैं एक स्पष्टीकरण की तलाश में हूं) और उसके बाद काम करने के लिए किसी प्रकार का मॉड्यूलो करता है जहां यह उस सरणी में स्थित है जहां मूल्य संग्रहीत किया जाता है, लेकिन यही वह जगह है जहां मेरा ज्ञान बंद हो जाता है ।

क्या कोई इस प्रक्रिया को स्पष्ट कर सकता है?

संपादित करें: मैं विशेष रूप से नहीं पूछ रहा हूं कि हैश कोड की गणना कैसे की जाती है, लेकिन हैश तालिका कैसे काम करती है इसका एक सामान्य अवलोकन।




हैश की गणना कैसे की जाती है आमतौर पर हैशटेबल पर निर्भर नहीं होती है, लेकिन इसमें जोड़े गए आइटमों पर निर्भर करती है। फ्रेमवर्क / बेस क्लास लाइब्रेरीज़ जैसे किनेट और जावा में, प्रत्येक ऑब्जेक्ट में GetHashCode () (या समान) विधि है जो इस ऑब्जेक्ट के लिए हैश कोड लौटाती है। आदर्श हैश कोड एल्गोरिदम और सटीक कार्यान्वयन वस्तु में दर्शाए गए डेटा पर निर्भर करता है।




बहुत सारे उत्तर, लेकिन उनमें से कोई भी बहुत दृश्यमान नहीं है , और हैश टेबल आसानी से "क्लिक" कर सकते हैं।

हैश टेबल अक्सर लिंक की गई सूचियों के सरणी के रूप में लागू होते हैं। अगर हम लोगों के नामों को संग्रहित करने वाली एक तालिका की कल्पना करते हैं, तो कुछ प्रविष्टियों के बाद इसे नीचे की तरह स्मृति में रखा जा सकता है, जहां () संलग्न संख्या टेक्स्ट के हैश मान हैं।

bucket#  bucket content / linked list

[0]      --> "sue"(780) --> null
[1]      null
[2]      --> "fred"(42) --> "bill"(9282) --> "jane"(42) --> null
[3]      --> "mary"(73) --> null
[4]      null
[5]      --> "masayuki"(75) --> "sarwar"(105) --> null
[6]      --> "margaret"(2626) --> null
[7]      null
[8]      --> "bob"(308) --> null
[9]      null

कुछ बिंदु:

  • प्रत्येक सरणी तत्वों (सूचकांक [0] , [1] ...) को बाल्टी के रूप में जाना जाता है, और मूल्यों की एक संभावित रूप से रिक्त-लिंक्ड सूची शुरू होती है
  • प्रत्येक मान (उदाहरण के लिए हैश 42 साथ "fred" ) बाल्टी [hash % number_of_buckets] से जुड़ा हुआ है जैसे 42 % 10 == [2] ; % मॉड्यूलस ऑपरेटर है - शेष जब बाल्टी की संख्या से विभाजित होता है
  • एकाधिक डेटा मान एक ही बाल्टी पर टकरा सकते हैं और लिंक किए जा सकते हैं , अक्सर क्योंकि उनके हैश मान मॉड्यूलस ऑपरेशन के बाद टकराते हैं (उदाहरण के लिए 42 % 10 == [2] , और 9282 % 10 == [2] ), लेकिन कभी-कभी क्योंकि हैश मान समान हैं (उदाहरण के लिए हैश 42 साथ दिखाए गए "fred" और "jane" दोनों)
    • अधिकांश हैश टेबल टकराव संभालते हैं - थोड़ा कम प्रदर्शन के साथ, लेकिन कोई कार्यात्मक भ्रम नहीं - एक कुंजी की पूर्ण मूल्य (यहां पाठ) की तुलना करके, जो पहले से ही जुड़ी हुई बाल्टी में लिंक की गई सूची में प्रत्येक कुंजी को डाला या डाला जा रहा है

यदि तालिका का आकार बढ़ता है, तो उपरोक्त के रूप में लागू हैश टेबल स्वयं तत्वों का आकार बदलते हैं (यानी बाल्टी की एक बड़ी सरणी बनाएं, पुरानी सरणी को हटाएं, पुरानी सरणी हटाएं) तत्वों के अनुपात को बाल्टी में रखें (उर्फ लोड कारक ) कहीं 0.5 से 1.0 रेंज में। लोड फैक्टर 1 और क्रिप्टोग्राफिक ताकत हैश फ़ंक्शन के साथ, 36.8% बाल्टी खाली हो जाएंगी, अन्य 36.8% में एक तत्व होता है, 18.4% दो तत्व, 6.1% तीन तत्व, 1.5% चार तत्व, .3% पांच आदि .. - सूची लंबाई औसत 2.0 तत्वों से कोई फर्क नहीं पड़ता कि तालिका में कितने तत्व हैं, यही कारण है कि हम कहते हैं कि लुकअप / डालने / मिटाएं ओ (1) स्थिर समय संचालन हैं।

(नोट्स: सभी हैश टेबल लिंक्ड सूचियों का उपयोग नहीं करते हैं, लेकिन अधिक सामान्य उद्देश्य वाले, बंद हैशिंग (उर्फ ओपन एड्रेसिंग) के रूप में करते हैं, खासतौर पर मिटाने वाले ऑपरेशन के साथ, टकराव-प्रवण कुंजी / हैश फ़ंक्शंस के साथ कम स्थिर प्रदर्शन गुण होते हैं)।

हैश फ़ंक्शंस पर कुछ शब्द

एक सामान्य उद्देश्य, सबसे बुरी स्थिति टक्कर-हैश फ़ंक्शन का काम कम करना हैश टेबल बाल्टी के चारों ओर चाबियाँ प्रभावी ढंग से यादृच्छिक रूप से स्प्रे करना है, जबकि हमेशा एक ही कुंजी के लिए एक ही हैश फ़ंक्शन उत्पन्न करना। कुंजी में कहीं भी एक बिट बदलना आदर्श रूप से होगा - यादृच्छिक रूप से - परिणामस्वरूप हैश मान में आधे बिट्स को फ़्लिप करें।

यह आम तौर पर मेरे लिए गणित के साथ बहुत जटिल है। मैं एक आसान समझने का तरीका बताऊंगा - सबसे स्केलेबल या कैश अनुकूल नहीं बल्कि स्वाभाविक रूप से सुरुचिपूर्ण (जैसे एक बार पैड के साथ एन्क्रिप्शन की तरह!) - जैसा कि मुझे लगता है कि यह उपरोक्त वर्णित वांछनीय गुणों को घर चलाने में मदद करता है। मान लें कि आप 64-बिट double एस हैं - आप 256 यादृच्छिक संख्याओं के 8 टेबल बना सकते हैं, फिर एक अलग तालिका में इंडेक्स के लिए double की स्मृति प्रस्तुति के प्रत्येक 8-बिट / 1-बाइट स्लाइस का उपयोग करें, यादृच्छिक संख्याओं को एक्सोर करना देखो। इस दृष्टिकोण के साथ, यह देखना आसान है कि double परिणामों में कहीं भी थोड़ा बदलना एक अलग यादृच्छिक संख्या में टेबल में से एक में देखा जा रहा है, और एक पूरी तरह से असंबंधित अंतिम मूल्य है।

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

खैर, यह हैश टेबल स्पष्टीकरण से कम मजेदार और भारी जा रहा था, लेकिन उम्मीद है कि यह किसी की मदद करेगा ....




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

(void) addValue : (object) value
{
   int bucket = calculate_bucket_from_val(value);
   if (bucket) 
   {
       //do nothing, just overwrite
   }
   else   //create bucket
   {
      create_extra_space_for_bucket();
   }
   put_value_into_bucket(bucket,value);
}

(bool) exists : (object) value
{
   int bucket = calculate_bucket_from_val(value);
   return bucket;
}

जहां calculate_bucket_from_val() हैशिंग फ़ंक्शन है जहां सभी विशिष्टता जादू होना चाहिए।

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

बाल्टी कोई भी जगह है जहां मान संग्रहीत किए जाते हैं - यहां के लिए मैंने इसे एक सरणी अनुक्रमणिका के रूप में रखा है, लेकिन यह शायद एक स्मृति स्थान भी हो सकता है।




इसे देखने का एक और तरीका यहां है।

मुझे लगता है कि आप एक सरणी ए की अवधारणा को समझते हैं। यह ऐसा कुछ है जो अनुक्रमण के संचालन का समर्थन करता है, जहां आप आईथ तत्व, ए [आई], एक चरण में प्राप्त कर सकते हैं, इससे कोई फर्क नहीं पड़ता कि ए कितना बड़ा है।

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

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

यह मूल विचार है। उम्र का उपयोग करने के बजाय, उस व्यक्ति का कोई भी कार्य जो मूल्यों का अच्छा प्रसार उत्पन्न करता है, का उपयोग किया जा सकता है। वह हैश फ़ंक्शन है। जैसे आप किसी व्यक्ति के नाम के ASCII प्रतिनिधित्व के हर तीसरे हिस्से को ले सकते हैं, कुछ क्रम में scrambled। यह सब मायने रखता है कि आप बहुत सारे लोगों को एक ही बाल्टी में हैश नहीं चाहते हैं, क्योंकि गति छोटी बाल्टी पर निर्भर करती है।




यह उससे भी आसान है।

एक हैशटेबल वेक्टरों की एक सरणी (आमतौर पर sparse एक) से अधिक कुछ नहीं है जिसमें कुंजी / मूल्य जोड़े होते हैं। इस सरणी का अधिकतम आकार हैशटेबल में संग्रहीत डेटा के प्रकार के लिए संभावित मानों के सेट में आइटम की संख्या से आम है।

हैश एल्गोरिदम का उपयोग उस सरणी में एक इंडेक्स जेनरेट करने के लिए किया जाता है जो उस आइटम के मानों के आधार पर होता है जो सरणी में संग्रहीत किया जाएगा।

यह वह जगह है जहां सरणी में कुंजी / मूल्य जोड़े के वैक्टर संग्रहीत होते हैं। क्योंकि मानों का सेट जो सरणी में अनुक्रमित हो सकता है, आमतौर पर प्रकार के सभी संभावित मानों की संख्या से छोटा होता है, यह संभव है कि आपके हैश एल्गोरिदम दो अलग-अलग कुंजियों के लिए समान मान उत्पन्न करने जा रहा है। एक अच्छा हैश एल्गोरिदम जितना संभव हो सके इसे रोक देगा (यही कारण है कि इसे आम तौर पर इस प्रकार के लिए भेजा जाता है क्योंकि इसमें विशिष्ट जानकारी होती है जो सामान्य हैश एल्गोरिदम संभवतः नहीं जान सकता), लेकिन इसे रोकना असंभव है।

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




इस तरह यह मेरी समझ में काम करता है:

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

मान लीजिए कि आपके पास 200 ऑब्जेक्ट हैं, लेकिन उनमें से केवल 15 में हैश कोड हैं जो 'बी' अक्षर से शुरू होते हैं। हैश टेबल को केवल 200 ऑब्जेक्ट्स की बजाय 'बी' बाल्टी में 15 ऑब्जेक्ट्स को देखने और खोजना होगा।

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