कोलेस्ड हैशिंग
कोलेस्ड हैशिंग, जिसे कोलेस्ड चेनिंग भी कहा जाता है, इस प्रकार हैश टेबल में संघटन समाधान की युक्ति है जो सेपरेट चेनिंग और विवृत एड्रेसिंग का हाइब्रिड बनाती है।
सेपरेट चेनिंग हैश टेबल
एक सेपरेट चेनिंग हैश टेबल में, समान एड्रेसिंग पर हैश किए गए आइटम उस एड्रेसिंग पर सूची (या चेन) पर रखे जाते हैं। इस तकनीक के परिणामस्वरूप बड़ी मात्रा में मेमोरी व्यर्थ हो सकती है क्योंकि टेबल को लोड फैक्टर को बनाए रखने के लिए पर्याप्त बड़ा होना चाहिए जो अच्छा प्रदर्शन करता है (सामान्यतः आइटमों की अपेक्षित संख्या से दोगुना), और अतिरिक्त मेमोरी का उपयोग पहले आइटम को छोड़कर सभी के लिए किया जाना चाहिए श्रृंखला (जब तक कि सूची शीर्षलेखों का उपयोग नहीं किया जाता है, उस स्थिति में श्रृंखला में सभी आइटमों के लिए अतिरिक्त मेमोरी का उपयोग किया जाना चाहिए)।
उदाहरण
अस्पस्ट विधि से उत्पन्न तीन वर्ण लंबी स्ट्रिंग्स के अनुक्रम 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 स्थानों के लिए एड्रेसिंग निर्दिष्ट करे। शेष m - n बकेट, जिन्हें सेलर कहा जाता है, विशेष रूप से उन वस्तुओं को संग्रहीत करने के लिए उपयोग की जाती हैं जो सम्मिलन के समय कोलिसन हैं। जब तक सेलर समाप्त नहीं होता है, तब तक कोई संलयन नहीं हो सकता है।
m के सापेक्ष n का इष्टतम विकल्प टेबल के लोड फैक्टर (या पूर्णता) पर निर्भर करता है। सावधानीपूर्वक विश्लेषण से पता चलता है कि मान N = 0.86 × M अधिकांश लोड कारकों के लिए लगभग-इष्टतम प्रदर्शन देता है।[1][2]
वेरिएंट
प्रविष्टि के लिए अन्य प्रकार भी संभव हैं जिनसे खोज समय में सुधार हुआ है। विलोपन एल्गोरिदम विकसित किए गए हैं जो यादृच्छिकता को संरक्षित करते हैं, और इस प्रकार औसत खोज समय विश्लेषण विलोपन के बाद भी बना रहता है।[1]
कार्यान्वयन
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;
}
प्रदर्शन
विलोपन कठिन हो सकता है.[3][4] सम्मिलित श्रृंखला प्राथमिक और द्वितीयक क्लस्टरिंग के प्रभावों से बचती है, और परिणामस्वरूप सेपरेट श्रृंखला के लिए कुशल खोज एल्गोरिदम का लाभ उठा सकती है। यदि शृंखलाएँ छोटी हैं, जिससे यह युक्ति बहुत कुशल है और इसे मेमोरी-वार अत्यधिक संघनित किया जा सकता है। इस प्रकार संवृत एड्रेसिंग की तरह, सम्मिलित हैश टेबल से विलोपन अद्वितीय और संभावित रूप से महंगा है, और टेबल का आकार बदलना बहुत महंगा है और इसे संभवतः ही कभी किया जाना चाहिए।
संदर्भ
- ↑ 1.0 1.1 J. S. Vitter and W.-C. Chen, Design and Analysis of Coalesced Hashing, Oxford University Press, New York, NY, 1987, ISBN 0-19-504182-8
- ↑ Jiří Vyskočil, Marko Genyk-Berezovskyj. "Coalesced hashing". 2010.
- ↑ Paul E. Black. "coalesced chaining". Dictionary of Algorithms and Data Structures [online]. Vreda Pieterse and Paul E. Black, eds. 16 November 2009. (accessed 2016-07-29). Available from: https://xlinux.nist.gov/dads/HTML/coalescedChaining.html
- ↑ Grant Weddell. "Hashing". p. 10-11.
