कोडिंग इंटरव्यू: आप Robin Hood Hashing कैसे लागू करते हैं?

प्रश्न और दायरा

m स्लॉट की एक ऐरे के साथ एक निश्चित-क्षमता वाली ओपन-एड्रेसिंग हैश टेबल लागू करें, जहाँ प्रत्येक स्लॉट अधिकतम एक की-वैल्यू पेयर रखता है। insert(key,value), contains(key), और remove(key) का समर्थन करें। Robin Hood हैशिंग के साथ टकरावों को हल करें; चेनिंग या टॉम्बस्टोन का उपयोग न करें। मुख्य एल्गोरिदम पर ध्यान केंद्रित करने के लिए, भरी हुई टेबल आकार बदलने (resizing) के बजाय विफलता (failure) लौटा सकती है।

यह डेटा संरचनाओं, इनवेरिएंट्स, एज केसेस और जटिलता के बारे में एक सामान्य कोडिंग इंटरव्यू समस्या है। Stanford CS106B का सार्वजनिक असाइनमेंट छात्रों से एक Robin Hood टेबल लागू करने के लिए कहता है और इसमें स्पष्ट रूप से प्रोब-दूरी स्वैपिंग, अर्ली लुकअप टर्मिनेशन और बैकवर्ड-शिफ्ट डिलीशन शामिल हैं। एक वर्तमान सॉफ्टवेयर-इंजीनियरिंग इंटरव्यू गाइड डेटा-स्ट्रक्चर निर्णय, शुद्धता, जटिलता और एज-केस हैंडलिंग को कोडिंग सिग्नलों के रूप में सूचीबद्ध करती है।

इंटरव्यूअर क्या जांच रहा है

• क्या आप प्रत्येक तत्व का होम बकेट और PSL, या प्रोब सीक्वेंस की लंबाई स्टोर कर सकते हैं?
• क्या आप समझा सकते हैं कि "गरीब कुंजी (poorer key) को प्राथमिकता मिलती है": जब आने वाला PSL बड़ा होता है, तो होम के करीब वाले निवासी कुंजी (resident key) के साथ स्वैप करें?
• क्या आप पूरी ऐरे को स्कैन करने के बजाय विफल लुकअप को जल्दी रोकने के लिए PSL मोनोटोनिसिटी का उपयोग कर सकते हैं?
• क्या आप टॉम्बस्टोन के बिना डिलीट कर सकते हैं और प्रोब क्लस्टर में प्रत्येक कुंजी को सुलभ (reachable) रख सकते हैं?
• क्या आप औसत और सबसे खराब स्थिति (worst-case) की लागत बता सकते हैं और हाई लोड के लिए नीति चुन सकते हैं?

एक सामान्य उत्तर लिनियर प्रोबिंग लिखता है लेकिन यह भूल जाता है कि डिलीशन से बने खाली स्थान (holes) बाद की खोजों को छोटा (truncate) कर देते हैं। एक मजबूत उत्तर "खाली स्लॉट" और "टारगेट PSL से नीचे निवासी PSL" दोनों को सिद्ध स्टॉप शर्तों में बदल देता है।

उत्तर देने से पहले स्पष्टीकरण

1. क्या क्षमता निश्चित है? निश्चित क्षमता के साथ, इंसर्शन विफलता एक स्पष्ट परिणाम है; रीसाइज़िंग के साथ, लोड-फ़ैक्टर थ्रेशोल्ड रीबिल्ड को ट्रिगर करता है।
2. क्या डुप्लिकेट कुंजियों की अनुमति है? मान लें कि डुप्लिकेट दूसरा स्लॉट जोड़ने के बजाय अपनी वैल्यू को अपडेट करता है; एक मल्टीमैप को एक अलग API और डिलीशन अनुबंध की आवश्यकता होगी।
3. क्या हैश स्थिर (stable) है और क्या कुंजियाँ कॉपी की जा सकती हैं? एक ऑपरेशन के दौरान हैश स्थिर होना चाहिए। होम बकेट को कैश करने से बार-बार होने वाले काम से बचा जा सकता है लेकिन यह स्लॉट मेमोरी की खपत करता है।
4. क्या इटरेटर या संदर्भ स्थिर रहने चाहिए? स्वैप और बैकवर्ड शिफ्ट तत्वों को स्थानांतरित करते हैं, इसलिए स्थिर पतों का वादा नहीं किया जाता है। यदि कॉल करने वालों को स्थिर हैंडल की आवश्यकता है तो इनडायरेक्शन का उपयोग करें।
5. क्या समवर्तीता (concurrency) दायरे में है? यह सिंगल-थ्रेडेड है। एक समवर्ती संस्करण को लॉकिंग, स्ट्रिपिंग या लॉक-फ्री प्रोटोकॉल की आवश्यकता होती है; सामान्य कार्यान्वयन थ्रेड-सुरक्षित नहीं है।

30-सेकंड उत्तर ढाँचा

"मैं प्रत्येक भरे हुए स्लॉट में कुंजी, मान, होम बकेट और PSL स्टोर करता हूँ। इंसर्शन होम से लिनियर रूप से प्रोब करता है; जब आने वाला PSL निवासी PSL से अधिक हो जाता है, तो मैं उन्हें स्वैप कर देता हूँ ताकि अधिक यात्रा करने वाले तत्व को प्राथमिकता मिले, फिर विस्थापित तत्व को रखना जारी रखता हूँ। एक लुकअप खाली स्लॉट पर या जब निवासी PSL टारगेट PSL से कम हो, तब विफल हो सकता है, क्योंकि बाद की प्रविष्टियाँ वापस कम दूरी पर नहीं जा सकती हैं। डिलीशन बाद की प्रविष्टियों को एक खाली स्लॉट या शून्य-PSL प्रविष्टि तक पीछे की ओर शिफ्ट करता है, प्रत्येक चाल के लिए PSL को कम करता है ताकि कोई खोज पथ न कटे। अपेक्षित ऑपरेशन O(1) के करीब हैं, सबसे खराब स्थिति O(m) है, और स्थान O(m) है।"

चरण-दर-चरण गहन उत्तर

1. स्लॉट मॉडल और इनवेरिएंट्स

प्रत्येक भरा हुआ स्लॉट (key, value, home, psl) स्टोर करता है। m स्लॉट के एक रिंग में, psl = (index - home + m) % m। तीन इनवेरिएंट्स बनाए रखें:

• home कुंजी के लिए निश्चित हैश उत्पत्ति है।
• home से psl कदम आगे चलने पर वर्तमान इंडेक्स प्राप्त होता है।
• एक निरंतर प्रोब क्लस्टर के भीतर, भरे हुए PSL मान कभी कम नहीं होते हैं; एक खाली स्लॉट क्लस्टर को समाप्त करता है।

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

2. लिनियर-प्रोबिंग की बाधा (bottleneck)

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

3. Robin Hood इंसर्शन

छद्म-कोड:

insert(key, value):
    item = (key, value, home=hash(key), psl=0)
    for step in 0 .. m-1:
        i = (item.home + item.psl) mod m
        if table[i] is empty:
            table[i] = item
            return success
        if table[i].key == key:
            table[i].value = value
            return updated
        if table[i].psl < item.psl:
            swap(table[i], item)
        item.psl += 1
    return full

स्वैप के बाद, item विस्थापित प्रविष्टि है। इसका PSL पहले से ही वर्तमान प्रोब स्थिति का वर्णन करता है, इसलिए अगला पुनरावृत्ति (iteration) इसे एक बार बढ़ाता है। खाली स्लॉट को एक वास्तविक प्रविष्टि से अलग रखें जिसका PSL शून्य है; अन्यथा इंसर्शन और डिलीशन की सीमाएँ अस्पष्ट हो जाती हैं।

4. लुकअप और अर्ली टर्मिनेशन

लुकअप टारगेट होम से शुरू होता है और टारगेट PSL को ट्रैक करता है:

contains(key):
    home = hash(key)
    for psl in 0 .. m-1:
        i = (home + psl) mod m
        if table[i] is empty:
            return false
        if table[i].psl < psl:
            return false
        if table[i].key == key:
            return true
    return false

एक खाली स्लॉट क्लस्टर को समाप्त करता है। टारगेट से नीचे का निवासी PSL का अर्थ है कि बाद के स्लॉट में टारगेट नहीं हो सकता है, क्योंकि क्लस्टर का PSL कम नहीं होता है। Stanford का असाइनमेंट इस अर्ली स्टॉप को सामान्य लिनियर प्रोबिंग से एक मुख्य अंतर मानता है।

5. बैकवर्ड-शिफ्ट डिलीशन

किसी स्लॉट को तुरंत खाली न करें: टकराव समाधान के दौरान बाद की किसी कुंजी ने इसे पार किया हो सकता है, और लुकअप गलत तरीके से उस खाली स्थान पर रुक जाएगा। टॉम्बस्टोन की भी अनुमति नहीं है और वे समय के साथ प्रोब को लंबा कर देंगे।

remove(key):
    i = find_index_or_not_found(key)
    if i is not found:
        return false
    j = (i + 1) mod m
    while table[j] is not empty and table[j].psl > 0:
        table[i] = table[j]
        table[i].psl -= 1
        i = j
        j = (j + 1) mod m
    table[i] = empty
    return true

एक खाली स्लॉट या शून्य-PSL प्रविष्टि पर रुकें। पूर्व क्लस्टर को समाप्त करता है; बाद वाला अपने होम पर है, इसलिए पिछले स्लॉट को खाली करने से उसका खोज पथ नहीं कट सकता है। प्रत्येक चाल PSL को कम करती है और दूरी के इनवेरिएंट को पुनर्स्थापित करती है।

6. जटिलता और हाई-लोड नीति

समान हैशिंग और एक से काफी नीचे लोड फैक्टर α के साथ, इंसर्ट, लुकअप और डिलीट के लिए अपेक्षित प्रोब स्थिर-पैमाने (constant-scale) पर होते हैं। एक एकल ऑपरेशन अभी भी सभी m स्लॉट को स्कैन कर सकता है, इसलिए सबसे खराब स्थिति का समय O(m) है और स्थान O(m) है। Robin Hood हैशिंग मुख्य रूप से प्रोब-लंबाई वितरण और वेरिएंस में सुधार करती है; यह ओपन-एड्रेसिंग के सबसे खराब मामले को नहीं हटाती है। उद्धृत विश्लेषण हाई-लोड मॉडल में सीमित वेरिएंस का अध्ययन करता है, लेकिन प्रोडक्शन कोड को अभी भी लोड थ्रेशोल्ड की आवश्यकता होती है।

जब α उस थ्रेशोल्ड के करीब पहुँचता है, तो अपेक्षित O(1) पर निर्भर रहने के बजाय बड़ी क्षमता पर रीबिल्ड करें। यदि क्षमता निश्चित रहनी चाहिए, तो full को एक सामान्य व्यावसायिक परिणाम के रूप में मानें और विफलता दर, औसत PSL, P99 प्रोब और डिलीशन-शिफ्ट लंबाई की निगरानी करें।

7. काउंटर-उदाहरण और परीक्षण

• खाली टेबल इंसर्ट और लुकअप: होम स्लॉट सीधे भर जाता है, और गायब कुंजी पहले खाली स्लॉट पर रुक जाती है।
• डुप्लिकेट कुंजी: वैल्यू को अपडेट करने से तत्वों की संख्या नहीं बढ़ती है।
• रैपअराउंड: अंत के करीब एक होम चुनें और (index - home + m) % m सत्यापित करें।
• स्वैप चेन: टकराने वाली कुंजियों का निर्माण करें और सत्यापित करें कि एक इंसर्शन हर आइटम को विस्थापित और रख सकता है।
• क्लस्टर हेड, मिडिल और टेल को डिलीट करना: शेष सभी कुंजियाँ खोजने योग्य रहती हैं।
• एक होम एंट्री डिलीट करना: जब उत्तराधिकारी का शून्य PSL हो तो रुकें, जिससे क्रॉस-क्लस्टर मूवमेंट से बचा जा सके।
• पूरी टेबल: (m+1)वीं विशिष्ट कुंजी हमेशा के लिए लूप करने के बजाय विफलता लौटाती है।
• प्रतिकूल (adversarial) हैश: कई कुंजियों को एक होम पर मैप करें, शुद्धता सत्यापित करें, और मेट्रिक्स में O(m) प्रोब को उजागर करें।

उच्च-गुणवत्ता वाला नमूना उत्तर

"मैं एक निश्चित-क्षमता वाली Robin Hood ओपन-एड्रेसिंग टेबल का उपयोग करूँगा, जो प्रत्येक भरे हुए स्लॉट में कुंजी, मान और PSL को स्टोर करेगी। इंसर्शन होम से लिनियर रूप से प्रोब करता है। यदि आने वाली प्रविष्टि निवासी प्रविष्टि की तुलना में अधिक दूर तक गई है, तो मैं उन्हें स्वैप करता हूँ और विस्थापित प्रविष्टि को रखना जारी रखता हूँ। यह एक प्रोब क्लस्टर के भीतर PSL को गैर-घटते (nondecreasing) क्रम में रखता है।

"लुकअप उस इनवेरिएंट का उपयोग करता है: एक खाली स्लॉट विफल हो जाता है, और टारगेट PSL से नीचे का निवासी PSL भी विफल हो जाता है क्योंकि बाद की प्रविष्टियाँ कम दूरी पर वापस नहीं आ सकती हैं। डिलीशन कोई खाली स्थान नहीं छोड़ सकता है, इसलिए मैं प्रविष्टियों को पीछे की ओर शिफ्ट करता हूँ जब तक कि उनका PSL सकारात्मक हो और प्रत्येक PSL को घटाता हूँ; एक खाली स्लॉट या शून्य-PSL प्रविष्टि शिफ्ट को समाप्त करती है। अपेक्षित समय O(1) के करीब है, सबसे खराब स्थिति O(m) है, इसलिए लोड फैक्टर, P99 प्रोब और शिफ्ट की लंबाई तय करती है कि आकार बदलना है या इंसर्शन को अस्वीकार करना है। क्योंकि शिफ्ट तत्वों को स्थानांतरित करते हैं, मैं स्थिर इटरेटर या पतों का वादा नहीं करता हूँ।"

सामान्य गलतियाँ

• गलती → टकराव पर हमेशा पहले वाले निवासी को बनाए रखना → बाद की प्रविष्टियाँ लंबे प्रोब जमा करती हैं → जब आने वाला PSL बड़ा हो तो स्वैप करें।
• गलती → केवल खाली स्लॉट पर लुकअप रोकना → PSL अनुकूलन खो देना → जब निवासी PSL टारगेट से नीचे हो तब भी रोकें।
• गलती → हटाए गए स्लॉट को तुरंत खाली करना → खाली स्थान बाद के प्रोब पथों को छोटा कर देता है → बैकवर्ड शिफ्टिंग का उपयोग करें और PSL घटाएं।
• गलती → किसी भी भरी हुई प्रविष्टि पर शिफ्ट करना बंद करना → अगम्य कुंजियाँ छोड़ना या क्लस्टरों के पार जाना → केवल तब तक शिफ्ट करें जब तक कि निरंतर क्लस्टर का PSL सकारात्मक हो।
• गलती → अपेक्षित O(1) को सबसे खराब स्थिति O(1) के रूप में लिखना → खराब हैश और उच्च लोड इसे अमान्य कर देते हैं → सबसे खराब स्थिति O(m) बताएं और लोड थ्रेशोल्ड लागू करें।
• गलती → स्थिर संदर्भों का वादा करना → स्वैप और डिलीशन प्रविष्टियों को स्थानांतरित करते हैं → हैंडल लौटाएं, इनडायरेक्शन का उपयोग करें, या एड्रेस गारंटी छोड़ दें।

फॉलो-अप और प्रतिक्रियाएँ

गतिशील रूप से बढ़ने वाली टेबल को कब रीबिल्ड करना चाहिए?

लोड फैक्टर और टेल प्रोब लेटेंसी दोनों पर ट्रिगर करें, जैसे कि कॉन्फ़िगर किया गया α या एक P99 प्रोब बजट। रीबिल्ड के दौरान प्रत्येक होम और PSL की पुनर्गणना करें; स्लॉट को सीधे कॉपी करना गलत है क्योंकि ऐरे मॉड्यूलस बदल जाता है। एक राइट लॉक, डुअल-टेबल माइग्रेशन, या बैकग्राउंड रीबिल्ड विभिन्न उपलब्धता लक्ष्यों को पूरा कर सकते हैं, लेकिन पहले स्थिरता और पॉज नीति बताएं।

टॉम्बस्टोन से क्यों बचें, और क्या बैकवर्ड शिफ्टिंग में बहुत अधिक लागत आ सकती है?

एक टॉम्बस्टोन डिलीशन को O(1) बनाता है लेकिन रीबिल्ड होने तक खोजों को स्थायी रूप से लंबा कर देता है। बैकवर्ड शिफ्टिंग डिलीट पर काम को केंद्रित करती है और क्लस्टरों को कॉम्पैक्ट रखती है। यदि डिलीट हावी हैं और रीड दुर्लभ हैं, तो टॉम्बस्टोन प्लस आवधिक रीबिल्ड बेहतर हो सकता है; यदि रीड लेटेंसी मायने रखती है, तो शिफ्टिंग को प्राथमिकता दें और मूव की लंबाई की निगरानी करें।

आप समवर्ती पाठकों और लेखकों को कैसे संभालेंगे?

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

क्या Robin Hood औसत लुकअप को स्थिर समय (constant time) बनाता है?

सामान्य यूनिफॉर्म-हैश मॉडल के तहत, अपेक्षित ओपन-एड्रेसिंग लागत लोड फैक्टर पर निर्भर करती है। Robin Hood मुख्य रूप से प्रोब-लंबाई के वेरिएंस और टेल स्प्रेड को कम करता है। उच्च लोड पर औसत लागत अभी भी बढ़ती है और सबसे खराब स्थिति टेबल को स्कैन कर सकती है, इसलिए वेरिएंस में सुधार लोड नियंत्रण और बेंचमार्क की जगह नहीं लेता है।