🪣 हैश टेबल (Hash Tables)

init

खुद आज़माएँ: key insert कीजिए; नारंगी चमक probe अनुक्रम है। chaining ↔ linear probing को टॉगल करके दो बेहद अलग टकराव (collision) रणनीतियाँ देखिए। फिर resize कीजिए और देखिए कैसे हर key दोबारा हैश (rehash) होती है।

यह क्यों मायने रखता है

हैश टेबल वह परम लक्ष्य पा लेती हैं: औसत स्थिति में O(1) lookup, insert और delete। ये हर dictionary, set, कैश और डेटाबेस इंडेक्स के पीछे हैं। कुशल एल्गोरिथ्म के लिए हैशिंग को समझना अनिवार्य है।

मूल विचार

एक विशाल पुस्तकालय की कल्पना कीजिए जहाँ किताबें लेखक के नाम के पहले अक्षर से अलमारियों में लगी हैं। "Knuth" ढूँढना यानी सीधे 'K' खंड में जाना — सब कुछ छानने की ज़रूरत नहीं।

हैश टेबल इसी तरह काम करती है, पर ज़्यादा चतुराई से। एक हैश फ़ंक्शन किसी भी key को एक ऐरे इंडेक्स में बदल देता है:

hash("Knuth") → 42 → इंडेक्स 42 पर रखो

जादू: यह रूपांतरण O(1) है। आप खोजने के बजाय इंडेक्स सीधे गणना कर लेते हैं।

पेच: टकराव (collisions)। दो अलग key एक ही इंडेक्स पर हैश हो सकती हैं। समाधान:

• Chaining: हर bucket टकराने वाले तत्वों की एक लिंक्ड लिस्ट है
• Open addressing: अगला ख़ाली ख़ाना ढूँढो

एक अच्छे हैश फ़ंक्शन और कम load factor के साथ, ऑपरेशन औसतन O(1) ही बने रहते हैं।

मुख्य बातें

• औसतन O(1) insert, lookup, delete
• समान वितरण के लिए एक अच्छा हैश फ़ंक्शन चाहिए
• टकराव अवश्यंभावी हैं — इन्हें सँभालना ही पड़ता है
• Load factor प्रदर्शन को प्रभावित करता है — बहुत भर जाने पर resize कीजिए

अपरिवर्तनी (Invariants)

Hash-table invariants

फ़ंक्शन की शुद्धता: हैश फ़ंक्शन निश्चयात्मक (deterministic) है — एक ही key हमेशा एक ही ख़ाने पर मैप होती है। (अगर ऐसा न होता, तो आप कुछ ढूँढ ही न पाते।)

Bucket अखंडता: हर संग्रहीत key k उस ख़ाने पर रहती है जो चुनी गई टकराव-नीति के ज़रिए hash(k) mod capacity से पहुँचा जा सके (chaining: वही bucket; probing: शुरुआती bucket, फिर निश्चयात्मक probe अनुक्रम)।

Load factor की सीमा: α = n / capacity resize की दहलीज़ से नीचे रहता है (आम तौर पर probing के लिए 0.7, chaining के लिए 1.0)। जब यह पार होता है, तो टेबल rehash करती है — वही amortized कहानी जो ऐरे दुगुना करने वाली है।

और गहराई में

हैश फ़ंक्शन परिवार — उपयोग के हिसाब से चुनिए

क्रिप्टोग्राफ़िक हैश (SHA-256, BLAKE3) हद से ज़्यादा हैं: ये जाली बनाने के अयोग्य होने के लिए बनाए गए हैं, तेज़ी के लिए नहीं। हैश टेबल को रफ़्तार + समान वितरण की परवाह है, किसी हमलावर के ख़िलाफ़ टकराव-प्रतिरोध की नहीं।

| परिवार | रफ़्तार | टिप्पणी | |---|---|---| | FNV-1a | बहुत तेज़ | छोटा कोड, छोटी key के लिए बढ़िया; डेमो का djb2 इसी परिवार का है | | MurmurHash3 | तेज़, अच्छी तरह वितरित | कई भाषा runtime का डिफ़ॉल्ट (Java 8+, पुराना Go) | | xxHash3 | बेहद तेज़ | सबसे अच्छी कच्ची throughput; zstd, LZ4, dataframe libs इस्तेमाल करते हैं | | CityHash / FarmHash | तेज़, Google-मूल | MurmurHash के समान दर्जा | | SipHash | मध्यम-तेज़, keyed | Rust के HashMap, Python 3.4+, Perl का DoS-प्रतिरोधी डिफ़ॉल्ट | | SHA-256 | धीमा (crypto-दर्जा) | क्रिप्टोग्राफ़िक; HashMap के लिए कभी नहीं; content-addressed storage के लिए, हाँ |

Load factor क्यों मायने रखता है — birthday paradox

m bucket और समान रूप से वितरित n key के साथ, किसी भी टकराव की प्रायिकता n ≈ √(π·m/2) के आसपास 50% पार कर जाती है — वही गणित जो birthday paradox का है (टकराव bucket से कहीं कम तत्वों के साथ ही हैरतअंगेज़ रूप से संभावित हो जाते हैं)।

जब तक α = n/m = 0.7 होता है, एक परिपूर्ण हैश फ़ंक्शन के भी लंबाई 2 या 3 की कई chain होती हैं। Probing, chaining से तेज़ी से बिगड़ता है — α = 0.9 पर linear probing की अपेक्षित probe संख्या ~5.5 है, और α = 1.0 पर यह असीमित हो जाती है। 0.7 की कटऑफ़ एक परिपाटी है जो इसलिए चुनी गई है ताकि probe संख्या औसतन 2 के आसपास रहे।

हैश-टकराव DoS हमले

अगर कोई हमलावर आपके इनपुट चुन सके और आपके हैश फ़ंक्शन का पूर्वानुमान लगा सके, तो वह ऐसी key गढ़ सकता है जो सब एक ही bucket में गिरें — जिससे आपका O(1) ढहकर O(n) हो जाता है। Java 7 में एक मशहूर घटना हुई थी: जब CGI पैरामीटर शत्रुतापूर्ण थे तो HashMap<String, ...> फट पड़ा। आधुनिक runtime में इसका इलाज keyed हैशिंग है: प्रक्रिया शुरू होते ही एक यादृच्छिक रहस्य (random secret) बनाया जाता है, और हैश फ़ंक्शन (SipHash) उसे हर गणना में मिला देता है। रहस्य के बिना हमलावर पूर्वानुमान नहीं लगा सकता कि key कहाँ गिरेंगी।

अगर आप ऐसी लाइब्रेरी लिख रहे हैं जो अविश्वसनीय इनपुट को हैश key के रूप में लेती है (HTTP पार्सर, JSON deserializer, डेटाबेस क्वेरी परतें), तो पक्का कीजिए कि आपका hashmap keyed हैशिंग इस्तेमाल करता है। Rust का डिफ़ॉल्ट HashMap ऐसा करता है; C++ std::unordered_map नहीं करता।

उन्नत टकराव रणनीतियाँ

chaining और linear probing से आगे, दो पैटर्न बेहतर worst-case गारंटी के बदले अधिक जटिलता लेते हैं:

• Robin Hood hashing — probing के दौरान, अगर आपको कोई ऐसा ख़ाना मिले जिसका मौजूदा निवासी आपसे कम दूरी probe करके आया है, तो आप उससे अदला-बदली कर लेते हैं। probe दूरियों को समान रूप से बाँट देता है और worst case को बाँध देता है।
• Cuckoo hashing — दो हैश फ़ंक्शन; अगर दोनों ख़ाने भरे हों, तो मौजूदा निवासी को निकालकर उसकी दूसरी हैश स्थिति पर दोबारा डाल दीजिए। Lookup की O(1) worst case गारंटी होती है (दो ख़ाने जाँचो, बस)।
• Hopscotch hashing — हर key को उसके घरेलू bucket के एक बँधे पड़ोस के भीतर रखता है, ताकि टकराव के बावजूद lookup कैश-अनुकूल रहे।

ये प्रोडक्शन में दिखते हैं: hopscotch कुछ Java लाइब्रेरियों में, Robin Hood 2018-पूर्व Rust के डिफ़ॉल्ट में, cuckoo नेटवर्क-राउटर lookup टेबल में।

गणितीय ब्यौरा

Time Complexity (average case)

Insert: O(1)

Lookup: O(1)

Delete: O(1)

Worst case (many collisions)

O(n)

Load Factor

α = n / capacity

आम तौर पर $\alpha > 0.7$ होने पर resize कीजिए

क्रियान्वयन (Implementation)

Rust में HashMap

use std::collections::HashMap;

let mut map = HashMap::new();
map.insert("key", 42);       // O(1) avg
let val = map.get("key");    // O(1) avg
map.remove("key");           // O(1) avg

// Iteration is O(n)
for (k, v) in &map {
    println!("{}: {}", k, v);
}

कब इस्तेमाल करें

• Dictionary/map (key-value भंडार)
• Set सदस्यता जाँच
• कैशिंग और memoization
• आवृत्तियाँ (frequencies) गिनना

अभ्यास

तीन सवाल जो दिखाते हैं कि हैश टेबल एल्गोरिथ्म का Swiss army knife क्यों हैं:

• Group Anagrams — मध्यम · "पहले canonicalize, फिर bucket" — समतुल्यता से गुच्छे बनाने का टेम्पलेट
• LRU Cache — मध्यम · हैश + डबली-लिंक्ड लिस्ट — चिर-परिचित दो-संरचनाएँ-साथ डिज़ाइन
• Longest Substring Without Repeating Characters — मध्यम · sliding window + "last-seen index" हैश — O(n) string-window पैटर्न

→ सभी अभ्यास सवाल देखें