Rust HashMap: डेटा को कुशलतापूर्वक खोजें और सम्मिलित करें

Rust में HashMap में डेटा को कुशलतापूर्वक कैसे खोजें और सम्मिलित करें: अंदर की ओर झाँकना

क्या आपने कभी Rust में कोड लिखा है और सोचा है: "मैं एक साथ कैसे जाँच करूँ कि HashMap में कोई कुंजी है या नहीं, और यदि नहीं है तो नया मान कैसे डालूँ?" यह प्रश्न Stack Overflow पर हज़ारों डेवलपर्स को परेशान करता है। और यह सही भी है: एक भोला समाधान आपके एप्लिकेशन के प्रदर्शन को मार सकता है। आज हम केवल उत्तर नहीं देंगे - हम Rust HashMap के अंदर जाएंगे और देखेंगे कि यह कैसे बना है। आप जानेंगे कि अलग-अलग get और insert दर्द का रास्ता क्यों हैं, और entry API का सही उपयोग कैसे करें।

यह लेख उन लोगों के लिए है जो पहले से ही Rust की मूल बातों से परिचित हैं, लेकिन यह गहराई से समझना चाहते हैं कि संग्रह अंदर से कैसे काम करते हैं। चलिए शुरू करते हैं!

समस्या: दो कॉल - दोगुना काम

एक सामान्य कार्य की कल्पना करें: आपके पास एक HashMap है जिसमें आपको टेक्स्ट में शब्दों की आवृत्ति गिननी है। भोला तरीका इस प्रकार दिखता है:

use std::collections::HashMap;\n\nfn count_words_naive(words: &[&str]) -> HashMap<String, u32> {\n    let mut map = HashMap::new();\n    \n    for word in words {\n        if map.contains_key(*word) {\n            let count = map.get(*word).unwrap();\n            map.insert(word.to_string(), count + 1);\n        } else {\n            map.insert(word.to_string(), 1);\n        }\n    }\n    \n    map\n}\n

यहाँ क्या बुरा है? हम प्रत्येक शब्द के लिए HashMap को दो बार एक्सेस करते हैं: पहले contains_key, फिर get, और फिर insert। प्रत्येक कॉल में हैश की गणना, बकेट में खोज और कुंजियों की तुलना शामिल है। छोटे टेक्स्ट के लिए यह अदृश्य है, लेकिन लाखों प्रविष्टियों के लिए यह एक आपदा है।

अंदर की ओर: Rust में HashMap कैसे बना है

यह समझने के लिए कि यह बुरा क्यों है, आइए जानें कि Rust में HashMap कैसे काम करता है। इसके मूल में ओपन एड्रेसिंग के साथ हैश टेबल (Robin Hood hashing) है। यहाँ प्रमुख बिंदु हैं:

\n
• हैशिंग: कुंजी को हैश फ़ंक्शन (डिफ़ॉल्ट रूप से SipHash-2-4) का उपयोग करके हैश कोड में बदल दिया जाता है।
\n
• बकेट: हैश कोड बकेट की सरणी में इंडेक्स निर्धारित करता है। Rust में, प्रत्येक बकेट एक स्लॉट है जो खाली, भरा हुआ या हटाया हुआ हो सकता है।
\n
• कोलिज़न: जब दो अलग-अलग कुंजियाँ एक ही बकेट में आती हैं, तो Robin Hood hashing खोज दूरियों को संतुलित करने के लिए अधिक "अमीर" पड़ोसी से जगह "चुराने" का प्रयास करता है।
\n
• रीसाइज़िंग: जब तालिका भर जाती है (load factor ~0.9), तो यह 2 गुना बढ़ जाती है, और सभी तत्वों को फिर से हैश किया जाता है।
\n

अब कल्पना करें: प्रत्येक get या insert कॉल एक पूर्ण चक्र है: हैशिंग, इंडेक्स द्वारा खोज, कुंजियों की तुलना (संभवतः कोलिज़न के कारण कई बार)। दो कॉल = दोगुना काम। और अगर कॉल के बीच रीसाइज़िंग हुई? तिगुना!

समाधान: Entry API - आपका जीवन रक्षक

Rust एक सुरुचिपूर्ण समाधान प्रदान करता है - Entry API। यह एक तंत्र है जो एक ही पास में खोज और संभवतः सम्मिलन करने की अनुमति देता है। शब्दों की गिनती के लिए सही कोड इस प्रकार दिखता है:

use std::collections::HashMap;\n\nfn count_words_efficient(words: &[&str]) -> HashMap<String, u32> {\n    let mut map = HashMap::new();\n    \n    for word in words {\n        let entry = map.entry(word.to_string());\n        *entry.or_insert(0) += 1;\n    }\n    \n    map\n}\n

संक्षिप्त, सुंदर, कुशल। लेकिन यह अंदर से कैसे काम करता है? आइए चरण दर चरण समझें।

चरण 1: entry() विधि

map.entry(key) कॉल एक Entry एनुम लौटाता है, जो दो अवस्थाओं में हो सकता है:

\n
• Entry::Occupied - कुंजी पहले से तालिका में मौजूद है।
\n
• Entry::Vacant - कुंजी मौजूद नहीं है, और हमारे पास सम्मिलन के लिए तैयार जगह है।
\n

महत्वपूर्ण: इस पर