ओपन एड्रेसिंग
विवर्त संबोधन, या क्लोज्ड हैशिंग, हैश टेबल टकराव समाधान की एक विधि है। इस पद्धति के साथ हैश टकराव को जांच करके, या सरणी में वैकल्पिक स्थानों ('जांच अनुक्रम') के माध्यम से खोज कर हल किया जाता है जब तक कि लक्ष्य रिकॉर्ड नहीं मिल जाता है, या अप्रयुक्त सरणी स्लॉट नहीं मिल जाता है, जो निरुपित करता है कि कोई नहीं है तालिका में ऐसी कुंजी.[1] प्रसिद्ध जांच अनुक्रमों में सम्मिलित हैं:
- रैखिक जांच
- जिसमें जांच के बीच का अंतराल निश्चित होता है — अधिकांशत:1 पर सेट किया जाता है।
- द्विघात जांच
- जिसमें जांच के बीच का अंतराल द्विघात रूप से बढ़ता है (इसलिए, सूचकांकों को द्विघात फ़ंक्शन द्वारा वर्णित किया जाता है)।
- डबल हैशिंग
- जिसमें प्रत्येक रिकॉर्ड के लिए जांच के बीच का अंतराल तय किया जाता है किंतु इसकी गणना किसी अन्य हैश फ़ंक्शन द्वारा की जाती है।
इन विधियों के बीच मुख्य व्यापार यह है कि रैखिक जांच में संदर्भ की सबसे अच्छी स्थानीयता होती है, किंतु क्लस्टरिंग के प्रति सबसे अधिक संवेदनशील होती है, जबकि डबल हैशिंग में कैश प्रदर्शन व्यर्थ होता है, किंतु वस्तुतः कोई क्लस्टरिंग प्रदर्शित नहीं होती है; दोनों क्षेत्रों में द्विघात जांच बीच में आती है। डबल हैशिंग के लिए अन्य प्रकार की जांच की तुलना में अधिक गणना की भी आवश्यकता हो सकती है।
कुछ खुली एड्रेसिंग विधियाँ, जैसे होप्सकॉच हैशिंग, रॉबिन हुड हैशिंग, लास्ट-आओ-फर्स्ट-पाओ हैशिंग और कुक्कू हैशिंग नई कुंजी के लिए जगह बनाने के लिए उपस्थित कुंजियों को सरणी में इधर-उधर ले जाती हैं। यह जांच पर आधारित विधियों की तुलना में उत्तम अधिकतम खोज समय देता है [2][3][4][5][6]
विवर्त संबोधन हैश टेबल के प्रदर्शन पर एक महत्वपूर्ण प्रभाव लोड कारक है; अर्थात्, उपयोग की जाने वाली सरणी में स्लॉट का अनुपात जैसे-जैसे लोड कारक 100% की ओर बढ़ता है, किसी दी गई कुंजी को खोजने या डालने के लिए आवश्यक जांचों की संख्या नाटकीय रूप से बढ़ जाती है। एक बार जब तालिका पूरी हो जाती है, तो जांच एल्गोरिदम समाप्त होने में भी विफल हो सकता है। अच्छे हैश फ़ंक्शन के साथ भी, लोड कारक सामान्यतः 80% तक सीमित होते हैं। एक व्यर्थ हैश फ़ंक्शन महत्वपूर्ण क्लस्टरिंग उत्पन्न करके बहुत कम लोड कारकों पर भी व्यर्थ प्रदर्शन प्रदर्शित कर सकता है, विशेष रूप से सबसे सरल रैखिक एड्रेसिंग विधि के साथ समान्य रूप से अधिकांश विवर्त संबोधन विधियों के साथ विशिष्ट लोड कारक 50% होते हैं, जबकि हैश_टेबल या सेपरेट_चेनिंग समान्यत: 100% तक का उपयोग कर सकते हैं।
उदाहरण छद्मकोड
निम्नलिखित छद्मकोड रैखिक जांच और एकल-स्लॉट स्टेपिंग के साथ एक विवर्त संबोधन हैश तालिका का कार्यान्वयन है, एक सामान्य दृष्टिकोण जो हैश फ़ंक्शन अच्छा होने पर प्रभावी होता है। प्रत्येक लुकअप, सेट और रिमूव फ़ंक्शंस सरणी स्लॉट का पता लगाने के लिए एक सामान्य आंतरिक फ़ंक्शन फाइंड_स्लॉट का उपयोग करते हैं जिसमें या तो दी गई कुंजी होती है या होनी चाहिए।
record pair { key, value, occupied flag (initially unset) }
var pair slot[0], slot[1], ..., slot[num_slots - 1]
function find_slot(key)
i := hash(key) modulo num_slots
// search until we either find the key, or find an empty slot.
while (slot[i] is occupied) and (slot[i].key ≠ key)
i := (i + 1) modulo num_slots
return i
function lookup(key)
i := find_slot(key)
if slot[i] is occupied // key is in table
return slot[i].value
else // key is not in table
return not found
function set(key, value)
i := find_slot(key)
if slot[i] is occupied // we found our key
slot[i].value = value
return
if the table is almost full
rebuild the table larger (note 1)
i := find_slot(key)
mark slot[i] as occupied
slot[i].key = key
slot[i].value = value
- नोट 1
- तालिका के पुनर्निर्माण के लिए एक बड़े सरणी को आवंटित करने और पुराने सरणी के सभी तत्वों को नए बड़े सरणी में सम्मिलित करने के लिए सेट ऑपरेशन का पुनरावर्ती उपयोग करने की आवश्यकता होती है। सरणी आकार में घातीय वृद्धि करना समान्य बात है, उदाहरण के लिए पुराने सरणी आकार को दोगुना करना।:
function remove(key) i := find_slot(key) if slot[i] is unoccupied return // key is not in the table mark slot[i] as unoccupied j := i loop (note 2) j := (j + 1) modulo num_slots if slot[j] is unoccupied exit loop k := hash(slot[j].key) modulo num_slots // determine if k lies cyclically in (i,j] // i ≤ j: | i..k..j | // i > j: |.k..j i....| or |....j i..k.| if i ≤ j if (i < k) and (k ≤ j) continue loop else if (i < k) or (k ≤ j) continue loop slot[i] := slot[j] mark slot[j] as unoccupied i := j
- नोट 2
- क्लस्टर में सभी रिकॉर्ड के लिए, उनकी प्राकृतिक हैश स्थिति और उनकी वर्तमान स्थिति के बीच कोई रिक्त स्लॉट नहीं होना चाहिए (अन्यथा लुकअप रिकॉर्ड खोजने से पहले ही समाप्त हो जाएगा)। छद्मकोड में इस बिंदु पर, i एक रिक्त स्लॉट है जो क्लस्टर में पश्चात् के रिकॉर्ड के लिए इस गुण को अमान्य कर सकता है। j एक ऐसा अनुवर्ती रिकॉर्ड है। k राव हैश है जहां कोई टकराव न होने पर j पर रिकॉर्ड स्वाभाविक रूप से हैश तालिका में आ जाएगा। यह परीक्षण पूछ रहा है कि क्या j पर रिकॉर्ड क्लस्टर के आवश्यक गुणों के संबंध में अमान्य रूप से स्थित है, क्योंकि अब i रिक्त है।
हटाने की एक अन्य तकनीक बस स्लॉट को हटाए गए के रूप में चिह्नित करना है। चूँकि अंततः हटाए गए रिकॉर्ड को हटाने के लिए तालिका को फिर से बनाने की आवश्यकता होती है। उपरोक्त विधियाँ O(1) को अद्यतन करने और उपस्थित रिकॉर्ड को हटाने की सुविधा प्रदान करती हैं, साथ ही यदि तालिका आकार का उच्च-जल चिह्न बढ़ता है तो कभी-कभी पुनर्निर्माण भी किया जाता है।
उपरोक्त O(1) हटाने की विधि केवल सिंगल-स्लॉट स्टेपिंग के साथ रैखिक रूप से जांच की गई हैश तालिकाओं में ही संभव है। ऐसे स्थिति में जहां एक ऑपरेशन में कई रिकॉर्ड हटाए जाने हैं, हटाने और बाद में पुनर्निर्माण के लिए स्लॉट चिह्नित करना अधिक कुशल हो सकता है।
यह भी देखें
- आलसी विलोपन - विवर्त पते का उपयोग करके हैश तालिका से हटाने की एक विधि है।
संदर्भ
- ↑ Tenenbaum, Aaron M.; Langsam, Yedidyah; Augenstein, Moshe J. (1990), Data Structures Using C, Prentice Hall, pp. 456–461, pp. 472, ISBN 0-13-199746-7
- ↑ Poblete; Viola; Munro. "The Analysis of a Hashing Scheme by the Diagonal Poisson Transform". p. 95 of Jan van Leeuwen (Ed.) "Algorithms - ESA '94". 1994.
- ↑ Steve Heller. "Efficient C/C++ Programming: Smaller, Faster, Better" 2014. p. 33.
- ↑ Patricio V. Poblete, Alfredo Viola. "Robin Hood Hashing really has constant average search cost and variance in full tables". 2016.
- ↑ Paul E. Black, "Last-Come First-Served Hashing", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 17 September 2015.
- ↑ Paul E. Black, "Robin Hood hashing", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 17 September 2015.
