Hash table: नाम तुरुन्तै भेट्ने
Bucket हरूको table मा नाम थप्नुहोस्, जहाँ hash function ले हरेक नामको bucket यसका अक्षरबाट निकाल्छ। दुईवटा नाम एउटै bucket मा परेको (collision) हेर्नुहोस्, एउटा bucket मात्र हेरेर नाम भेट्टाउनुहोस्, र नामहरू छरिऊन् भनेर bucket को सङ्ख्या बदल्नुहोस्।
मूल अवधारणा
Hash table ले hash function ले हरेक key लाई bucket नम्बरमा बदल्छ; key थप्दा र खोज्दा त्यही एउटा bucket हेरिन्छ, त्यसैले collision थोरै भएसम्म जति धेरै key भए पनि यी छिटो रहन्छन्
पाठ: Data structure
क्रम नमिलेको सूचीमा नाम खोज्न नामहरू एक-एक गरेर जाँच्नुपर्छ। Hash table ले योभन्दा राम्रो गर्छ। यसले 0, 1, 2 आदि नम्बर भएका bucket को लहर राख्छ, र नामलाई bucket नम्बरमा बदल्ने hash function। यहाँ hash ले नामका अक्षरको वर्णमालाको ठाउँ (A = 1, B = 2, … Z = 26) जोड्छ र bucket को सङ्ख्याले भाग गर्दाको शेष लिन्छ: ASHA भनेको 1 + 19 + 8 + 1 = 29, र 29 MOD 5 = 4, त्यसैले ASHA bucket 4 मा जान्छ। पछि ASHA खोज्न, प्रोग्रामले उही नम्बर निकाल्छ र bucket 4 मात्र हेर्छ। दुईवटा नाम एउटै bucket मा पर्दा त्यो collision हो: दुवै bucket मा एकपछि अर्को राखिन्छन्, र खोज्दा ती थोरै मात्र जाँचिन्छन्। धेरै bucket भए प्रायः collision कम हुन्छन्।
के सिक्नुहुनेछ
- Hash function ले नामको bucket निकाल्नुहोस्।
- खोज्दा एउटा bucket मात्र किन जाँचिन्छ, व्याख्या गर्नुहोस्।
- Collision के हो र table ले यसलाई कसरी सम्हाल्छ, व्याख्या गर्नुहोस्।
- Bucket को सङ्ख्याले collision कसरी बदल्छ, हेर्नुहोस्।
सुरु गर्नुअघि
- MOD (भाग गर्दाको शेष) को अर्थ थाहा हुनुपर्छ।
सामग्री
- Hash निकाल्न कापी
उपकरण
- केही पनि चाहिँदैन
विधि
- 5 वटा bucket मा पाँच वा बढी नाम थपेर हरेक कहाँ जान्छ हेर्नुहोस्।
- दुईवटा नाम एउटै bucket मा परेको collision खोज्नुहोस्।
- एउटा नाम खोजेर तुलना गन्नुहोस्।
- Bucket को सङ्ख्या बदलेर collision दाँज्नुहोस्।