हैश टेबल: लिंक्डलिस्ट बकेट से चेनिंग (जावा)

टीएल;डीआर

• समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
• दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ७.१२: लिंक्ड लिस्ट बकेट वाले ऐरे से सरल हैशमैप। जावा में कोलिज़न चेनिंग के साथ पुट, गेट और रिमूव।
• जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

एक ऐसा मैप जो गेट(कुंजी) लगभग नियत समय में जवाब दे, वही हैश टेबल है। कुंजी को हैश करके एक बकेट इंडेक्स मिलता है, फिर सिर्फ उसी बकेट में देखते हो। जब दो कुंजियाँ एक ही स्लॉट में गिरें, कोलिज़न का प्लान चाहिए। क्लासिक शिक्षण प्लान है चेनिंग: हर बकेट कुंजी-मान सेलों की लिंक्ड लिस्ट है।

यह पोस्ट जावा में शुरुआती लोगों के लिए मूल शिक्षण है। ऑब्जेक्ट ओरिएंटेड डिज़ाइन इंटरव्यू सवालों का परिवार, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। अध्याय ७ यहीं एक छोटी, साफ संरचना पर खत्म होता है जिसे व्हाइटबोर्ड पर लिख सकते हो।

---

१. रोज़मर्रा की उपमा

एक दीवार सोचो जिस पर मेलबॉक्स हों, नंबर ० से क्षमता - १ तक।

• हर चिट्ठी का पता होता है। पते पर एक सादा नियम चलाओ, एक मेलबॉक्स नंबर मिलता है।
• चिट्ठी उसी बॉक्स में डालो।
• कभी दो चिट्ठियाँ एक ही नंबर पर हैश हो जाती हैं। वह बॉक्स चिट्ठियों का ढेर (एक चेन) रखता है, सिर्फ एक चिट्ठी नहीं।
• ऐलिस का मेल ढूँढने के लिए उसका पता हैश करो, वही बॉक्स खोलो, छोटे ढेर में उसका नाम मिलने तक स्कैन करो।
• हटाने के लिए वही बॉक्स खोलो और उस चिट्ठी को ढेर से निकालो।

दीवार ऐरे है। हर ढेर लिंक्ड लिस्ट है। नियम तुम्हारा हैश फंक्शन है। पूरी दीवार नहीं खोजते; सिर्फ एक छोटी चेन स्कैन करते हो।

तुम जावा.यूटिल.हैशमैप के ट्री बिन और रीसाइज़ ह्यूरिस्टिक नहीं बना रहे। साफ क्लासों से आइडिया मॉडल कर रहे हो।

---

२. सादा समस्या कथन

लक्ष्य: एक सरल हैश टेबल / हैशमैप डिज़ाइन और लागू करो जो कोलिज़न के लिए चेनिंग (लिंक्ड लिस्ट बकेट) इस्तेमाल करे।

मुख्य ऑपरेशन:

• put(key, value): डालो या अपडेट करो
• get(key): मान लौटाओ, न मिले तो नल / खाली
• remove(key): मैपिंग हो तो मिटाओ

इंटरव्यू में साफ करो:

• कुंजी और मान के टाइप? जेनेरिक के और वी साफ रहते हैं। नल कुंजी? अक्सर मना या अलग केस; एक चुनो और बोलो।
• कुंजी पहले से हो तो पुट क्या करे? मान अपडेट (मैप सेमांटिक्स), दूसरी सेल न बनाओ।
• गेट / रिमूव का रिटर्न टाइप? मान या बूलियन, बोल दो।
• स्थिर क्षमता या लोड बढ़े तो रीसाइज़? पहले स्केच के लिए स्थिर काफी। लोड फैक्टर फॉलो-अप के रूप में नाम लो।
• थ्रेड सेफ्टी? न पूछें तो सिंगल थ्रेड।

टाइप पदानुक्रम का आकार:

HashMap<K, V>
  └── buckets: LinkedList<Cell<K, V>>[]   (or List of lists)
        └── Cell: key, value

कुछ लोग नोड को एंट्री कहते हैं। वही बात: हर मैपिंग एक ऑब्जेक्ट, एक इंडेक्स के नीचे चेन में लटका।

---

३. पहले सोचो

सादा मानों का ऐरे क्यों नहीं

कुंजियाँ छोटे लगातार पूर्णांक नहीं होतीं। स्ट्रिंग या मनमाने ऑब्जेक्ट पर सीधे कुंजी से इंडेक्स नहीं काट सकते। हैशिंग किसी भी कुंजी को ० .. क्षमता - १ में मैप करती है।

कोलिज़न सामान्य है

अच्छा हैश कुंजियाँ फैलाता है, फिर भी दो अलग कुंजियाँ एक ही इंडेक्स दे सकती हैं। यह कोलिज़न है, बग नहीं।

दो मानक हल:

रणनीति	आइडिया	इंटरव्यू नोट
चेनिंग	हर बकेट सेलों की लिस्ट रखता है	कोड और समझ आसान
ओपन अड्रेसिंग	ऐरे के दूसरे स्लॉट टटोलो	कम पॉइंटर; डिलीट कठिन

यह समस्या चेनिंग माँगती है। जब तक इंटरव्यूअर न मोड़े, लिस्ट पर टिके रहो।

हैश से बकेट इंडेक्स

index = hashCode(key) % capacity

जावा में हैशकोड() ऋणात्मक हो सकता है। % का ऋणात्मक शेष खराब ऐरे इंडेक्स बनाता है। ठीक करो:

index = (hashCode(key) & 0x7fffffff) % capacity

या

index = Math.floorMod(hashCode(key), capacity)

दोनों ठीक। क्यों नॉर्मलाइज़ किया, बोलो।

पुट / गेट / रिमूव एक ही चेन चलते हैं

१. कुंजी से इंडेक्स निकालो। २. बकेट्स[इंडेक्स] की लिंक्ड लिस्ट चलाओ। ३. कुंजी इक्वल्स से मिलाओ (ऑब्जेक्ट पर == नहीं)। ४. पुट: कुंजी मिले तो मान बदलो; नहीं तो नई सेल जोड़ो। ५. गेट: कुंजी मिले तो मान; नहीं तो नल। ६. रिमूव: कुंजी मिले तो सेल अनलिंक; नहीं तो कुछ न करो।

औसत समय ओ(१ + चेन लंबाई)। सबसे बुरा ओ(एन) जब सब एक बकेट में गिरे (खराब हैश या विरोधी कुंजियाँ)।

क्षमता और लोड

लोड फैक्टर ≈ एन / क्षमता। जब यह लगभग ०.७५ पार करे, प्रोडक्शन मैप रीसाइज़ करते हैं (नया ऐरे, सारी कुंजियाँ रीहैश)। इंटरव्यू स्केच में स्थिर क्षमता ठीक है अगर अगला कदम रीसाइज़ नाम लो।

व्हाइटबोर्ड स्केच

१. ४ खाली बकेट का ऐरे खींचो। २. पुट("एप्पल", १) इंडेक्स १ पर: चेन एप्पल→१। ३. पुट("एप्रिकॉट", २) भी १ पर: चेन एप्पल→१ फिर एप्रिकॉट→२। ४. गेट("एप्रिकॉट") इंडेक्स १ चलाता है, एप्पल छोड़ता है, २ लौटाता है। ५. रिमूव("एप्पल") पहली सेल अनलिंक; एप्रिकॉट रहता है।

---

४. जावा समाधान

जेनेरिक, स्थिर क्षमता, और सिंगली लिंक्ड सेल वाली शिक्षण वर्शन। जेडीके की लिंक्डलिस्ट भी चलती है; सेल पर साफ नेक्स्ट व्हाइटबोर्ड पर चेन दिखाता है।

/**
 * Simple hash map with chaining.
 * Each bucket is a singly linked list of Cell nodes.
 */
public class ChainedHashMap<K, V> {
    private static class Cell<K, V> {
        final K key;
        V value;
        Cell<K, V> next;

        Cell(K key, V value, Cell<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    private final Cell<K, V>[] buckets;
    private int size;

    @SuppressWarnings("unchecked")
    public ChainedHashMap(int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException("capacity must be positive");
        }
        // Generic array: allocate as Object[], cast once.
        buckets = (Cell<K, V>[]) new Cell[capacity];
        size = 0;
    }

    public ChainedHashMap() {
        this(16);
    }

    private int indexFor(K key) {
        int h = key.hashCode();
        // clear sign bit so % never yields a negative index
        return (h & 0x7fffffff) % buckets.length;
    }

    private Cell<K, V> findCell(K key) {
        int i = indexFor(key);
        for (Cell<K, V> c = buckets[i]; c != null; c = c.next) {
            if (c.key.equals(key)) {
                return c;
            }
        }
        return null;
    }

    /** Insert or update. Null keys rejected for simplicity. */
    public void put(K key, V value) {
        if (key == null) {
            throw new IllegalArgumentException("null key not supported");
        }
        Cell<K, V> existing = findCell(key);
        if (existing != null) {
            existing.value = value;
            return;
        }
        int i = indexFor(key);
        // insert at head: O(1), order inside the bucket does not matter for map ops
        buckets[i] = new Cell<>(key, value, buckets[i]);
        size++;
    }

    public V get(K key) {
        if (key == null) {
            return null;
        }
        Cell<K, V> c = findCell(key);
        return c == null ? null : c.value;
    }

    /**
     * True when the key is present. Needed if null values are allowed,
     * because get(key) == null is then ambiguous.
     */
    public boolean containsKey(K key) {
        if (key == null) {
            return false;
        }
        return findCell(key) != null;
    }

    /** Remove mapping if present. Returns true when a cell was removed. */
    public boolean remove(K key) {
        if (key == null) {
            return false;
        }
        int i = indexFor(key);
        Cell<K, V> prev = null;
        Cell<K, V> cur = buckets[i];
        while (cur != null) {
            if (cur.key.equals(key)) {
                if (prev == null) {
                    buckets[i] = cur.next;
                } else {
                    prev.next = cur.next;
                }
                size--;
                return true;
            }
            prev = cur;
            cur = cur.next;
        }
        return false;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }
}

यह स्केच नल मान अनुमति देता है। सरल इंटरव्यू कोड चाहो तो नल मान मना करो और गेट == नल को गायब समझो।

डेमो वॉकथ्रू:

public class HashTableDemo {
    public static void main(String[] args) {
        ChainedHashMap<String, Integer> map = new ChainedHashMap<>(4);

        map.put("apple", 1);
        map.put("banana", 2);
        map.put("apricot", 3); // may collide with apple depending on hash

        System.out.println(map.get("apple"));    // 1
        System.out.println(map.get("banana"));   // 2
        System.out.println(map.get("missing"));  // null

        map.put("apple", 10); // update
        System.out.println(map.get("apple"));    // 10
        System.out.println(map.size());          // 3

        System.out.println(map.remove("banana")); // true
        System.out.println(map.get("banana"));    // null
        System.out.println(map.size());           // 2
    }
}

कदम	कॉल	असर
शुरू	क्षमता ४	खाली बकेट
१	पुट("एप्पल", १)	इंडेक्सफॉर(एप्पल) में नई सेल
२	पुट("बनाना", २)	नई सेल (वही या दूसरा बकेट)
३	पुट("एप्रिकॉट", ३)	कोलिज़न पर चेन बढ़ती है
४	पुट("एप्पल", १०)	वही सेल, मान बदला, आकार ३ ही
५	रिमूव("बनाना")	सेल अनलिंक, आकार २

अगर इंटरव्यूअर हाथ से नेक्स्ट की जगह जेडीके लिस्ट चाहे:

// sketch: buckets as List<Cell>[]
List<Cell<K, V>> bucket = buckets[i];
if (bucket == null) {
    bucket = new LinkedList<>();
    buckets[i] = bucket;
}
for (Cell<K, V> c : bucket) {
    if (c.key.equals(key)) {
        c.value = value;
        return;
    }
}
bucket.add(new Cell<>(key, value, null));

समान असिम्प्टॉटिक्स। प्रीव/कर पॉइंटर से रिमूव दिखाना हो तो साफ नेक्स्ट बेहतर।

---

५. जटिलता तालिका

ऑपरेशन	औसत समय	सबसे बुरा समय	अतिरिक्त जगह	नोट्स
पुट (नई कुंजी)	ओ(१ + α)	ओ(एन)	ओ(१)	α ≈ लोड फैक्टर / चेन लंबाई
पुट (अपडेट)	ओ(१ + α)	ओ(एन)	ओ(१)	कुंजी इक्वल्स तक चलो
गेट	ओ(१ + α)	ओ(एन)	ओ(१)	वही चलना
रिमूव	ओ(१ + α)	ओ(एन)	ओ(१)	प्रीव से अनलिंक
निर्माण	ओ(क्षमता)	ओ(क्षमता)	ओ(क्षमता)	बकेट हेड का खाली ऐरे
एन जोड़ों का भंडार	-	-	ओ(एन + क्षमता)	सेल + बकेट ऐरे

इंटरव्यूअर चाहते हैं कि तुम चेनिंग नाम लो, पहले हैश फिर इक्वल्स इस्तेमाल करो, और अपडेट बनाम इंसर्ट संभालो। रीसाइज़ मजबूत फॉलो-अप है, पहले पास में जरूरी नहीं।

---

६. किनारे के केस और आम गलतियाँ

इंटरव्यूअर ये छेड़ते हैं:

• नल कुंजी: थ्रो करो या अलग स्लॉट। नल पर कुंजी.हैशकोड() मत बुलाओ।
• नल मान: इस स्केच में अनुमति। तब गेट == नल अस्पष्ट; कंटेन्सकी या ऑप्शनल इस्तेमाल करो।
• डुप्लिकेट पुट: अपडेट होना चाहिए, आकार दो बार न बढ़े।
• चेन के सिर का रिमूव: बकेट्स[i] = कर.नेक्स्ट, सिर्फ प्रीव.नेक्स्ट = ... नहीं।
• गायब कुंजी पर रिमूव: फॉल्स / नल लौटाओ; आकार मत घटाओ।
• ऋणात्मक हैशकोड: % से पहले नॉर्मलाइज़, नहीं तो ऐरेइंडेक्सआउटऑफबाउंड्सएक्सेप्शन।
• क्षमता = १: हर कुंजी कोलिड करती है; मैप सही, सिर्फ एक लंबी लिस्ट।
• कस्टम कुंजी पर खराब इक्वल्स / हैशकोड करार: बराबर कुंजियों का हैशकोड एक होना चाहिए, नहीं तो लुकअप टूटता है।
• इटरेटर / संगामी बदलाव: न पूछें तो स्कोप से बाहर।

आम गलतियाँ:

१. कुंजी तुलना के लिए ==। स्ट्रिंग और बॉक्स्ड टाइप को इक्वल्स चाहिए। २. पुट में अपडेट रास्ता भूलना। एक ही कुंजी की दो सेल; गेट पहली लौटाता है और आकार झूठ बोलता है। ३. पहले नोड पर टूटा रिमूव। हेड पॉइंटर कभी अपडेट नहीं होता। ४. ऋणात्मक हैश के साथ हैश % क्षमता। इंडेक्स क्रैश। ५. "चेनिंग" बोलकर गलती से ओपन अड्रेसिंग (लीनियर प्रोब) बना देना। ६. बिना रीहैश रीसाइज़। बड़े ऐरे पर लिस्ट हेड कॉपी करने से इंडेक्स गलत रह जाते हैं।

न्यूनतम स्मोक आइडिया:

ChainedHashMap<String, Integer> m = new ChainedHashMap<>(2);
m.put("a", 1);
m.put("b", 2);
m.put("a", 3);
assert m.get("a") == 3;
assert m.size() == 2;
assert m.remove("b");
assert m.get("b") == null;
assert m.size() == 1;
assert !m.remove("b");

---

७. दोस्त को समझाने वाला सार

चेनिंग वाली हैश टेबल, इंटरव्यू वर्शन:

१. बकेट का ऐरे। हर बकेट कुंजी-मान सेलों की लिंक्ड लिस्ट है। २. इंडेक्स = नॉर्मलाइज़(हैशकोड(कुंजी)) % क्षमता। ३. पुट: चेन चलाओ; कुंजी हो तो अपडेट, नहीं तो सेल जोड़ो (हेड इंसर्ट ठीक)। ४. गेट: चेन चलाओ; मान या नल। ५. रिमूव: प्रीव/कर से चलाओ; अनलिंक करो, आकार घटाओ। ६. चेन छोटी रहें तो औसत ओ(१)। सब कोलिड करें तो सबसे बुरा ओ(एन)। ७. फॉलो-अप: लोड फैक्टर पर रीसाइज़, नल नीति, ओपन अड्रेसिंग, थ्रेड सेफ्टी।

चार बकेट खींच सको, एक लिस्ट पर दो कोलिडिंग कुंजियाँ लटका सको, और बिना रिमूव बग के पुट/गेट/रिमूव लिख सको, तो समस्या ७.१२ तुम्हारी है। अध्याय ७ का ओओडी उसी संरचना पर बंद होता है जो हर जगह काम आएगी।

---

सीरीज़

• गाइड: सीटीसीआई सीरीज़ गाइड
• पिछला: फाइल सिस्टम
• अगला: ट्रिपल स्टेप