कोलेस्ड हैशिंग

सम्मिलित हैशिंग उदाहरण. इस उदाहरण के प्रयोजनों के लिए, टकराव बकेट को बकेट 0 से शुरू करके, बढ़ते क्रम में आवंटित किया जाता है।

कोलेस्ड हैशिंग, जिसे कोलेस्ड चेनिंग भी कहा जाता है, हैश तालिका में टकराव समाधान की एक रणनीति है जो अलग चेनिंग और खुला संबोधन का एक संकर बनाती है।

अलग चेनिंग हैश तालिका

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

उदाहरण

बेतरतीब ढंग से उत्पन्न तीन वर्ण लंबी स्ट्रिंग्स के अनुक्रम qrj, aty, qur, dim, ofu, gcl, rhv, clq, ecd, qsu को देखते हुए, निम्न तालिका उत्पन्न की जाएगी (जेनकिन्स हैश फ़ंक्शन#वन-एट-ए-टाइम का उपयोग करके | बॉब जेनकिंस का वन-ए-टाइम हैश एल्गोरिथम) आकार 10 की तालिका के साथ:

(null)
"clq"
"qur"
(null)
(null)
"dim"
"aty"	"qsu"
"rhv"
"qrj"	"ofu"	"gcl"	"ecd"
(null)

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

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

तहखाना

एकीकरण के प्रभाव को कम करने के लिए एक महत्वपूर्ण अनुकूलन, हैश फ़ंक्शन के पता स्थान को केवल तालिका के एक सबसेट तक सीमित करना है। उदाहरण के लिए, यदि तालिका का आकार M है और बकेट की संख्या 0 से M - 1 तक है, तो हम पता स्थान को प्रतिबंधित कर सकते हैं ताकि हैश फ़ंक्शन केवल तालिका में पहले N स्थानों के लिए पते निर्दिष्ट करे। शेष एम - एन बाल्टियाँ, जिन्हें सेलर कहा जाता है, विशेष रूप से उन वस्तुओं को संग्रहीत करने के लिए उपयोग की जाती हैं जो सम्मिलन के दौरान टकराती हैं। जब तक तहखाना समाप्त नहीं हो जाता, तब तक कोई संलयन नहीं हो सकता।

एम के सापेक्ष एन का इष्टतम विकल्प तालिका के लोड फैक्टर (या पूर्णता) पर निर्भर करता है। सावधानीपूर्वक विश्लेषण से पता चलता है कि मान N = 0.86 × M अधिकांश लोड कारकों के लिए लगभग-इष्टतम प्रदर्शन देता है।

वेरिएंट

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

कार्यान्वयन

C (प्रोग्रामिंग भाषा) में सम्मिलन:

/* htab is the hash table,
   N is the size of the address space of the hash function, and
   M is the size of the entire table including the cellar.
   Collision buckets are allocated in decreasing order, starting with bucket M-1. */

int insert ( char key[] )
{
  unsigned h = hash ( key, strlen ( key ) ) % N;

  if ( htab[h] == NULL ) {
    /* Make a new chain */
    htab[h] = make_node ( key, NULL );
  } else {
    struct node *it;
    int cursor = M-1;

    /* Find the first empty bucket */
    while ( cursor >= 0 && htab[cursor] != NULL )
      --cursor;

    /* The table is full, terminate unsuccessfully */
    if ( cursor == -1 )
      return -1;

    htab[cursor] = make_node ( key, NULL );
    
    /* Find the last node in the chain and point to it */
    it = htab[h];

    while ( it->next != NULL )
      it = it->next;

    it->next = htab[cursor];
  }

  return 0;
}

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

सी में लुकअप:

char *find ( char key[] )
{
  unsigned h = hash ( key, strlen ( key ) ) % N;

  if ( htab[h] != NULL ) {
    struct node *it;

    /* Search the chain at index h */
    for ( it = htab[h]; it != NULL; it = it->next ) {
      if ( strcmp ( key, it->data ) == 0 )
        return it->data;
    }
  }

  return NULL;
}

प्रदर्शन

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