हैश टेबल्स की व्याख्या

मेरी पसंदीदा डेटा संरचनाओं में से एक हैश तालिका है क्योंकि यह सरल और शक्तिशाली है।

आपने शायद पहले इसका इस्तेमाल किया होगा क्योंकि यह की-वैल्यू पेयर को स्टोर करने का एक कारगर तरीका है।

हैश तालिका के कार्यान्वयन के पीछे कुछ दिलचस्प कंप्यूटर विज्ञान अवधारणाएँ हैं जो अध्ययन के लायक हैं, और ठीक यही हम इस लेख में करने जा रहे हैं!

बकेट और हैश फंक्शन

हैश तालिका का मूल विचार हमें कुशलतापूर्वक (O(1) . में) की अनुमति देना है ) कुंजी द्वारा अनुक्रमित डेटा पुनर्प्राप्त करें।

एक त्वरित पुनश्चर्या के रूप में, रूबी में हैश तालिका का उपयोग करने जैसा दिखता है:

prices = {
  apple: 0.50,
  ice_cream: 3,
  steak: 10
}

हैश तालिका को लागू करने के लिए हमें दो घटकों की आवश्यकता होती है:

• तालिका प्रविष्टियों को संग्रहीत करने का स्थान
• इस डेटा स्टोर के अंदर एक विशिष्ट स्थिति (इंडेक्स) के लिए कुंजी/मान जोड़े असाइन करने का एक तरीका

दूसरे शब्दों में, हमें एक सरणी और हैश फ़ंक्शन की आवश्यकता है।

साधारण हैश फ़ंक्शन लागू करना

हैश फ़ंक्शन हैश तालिका का एक महत्वपूर्ण घटक है।

यह फ़ंक्शन कुंजी को एक इंडेक्स में बदल देता है जिसका उपयोग इसके संबद्ध मूल्य को देखने या अपडेट करने के लिए किया जा सकता है।

सादा सरणियों और हैश तालिकाओं के बीच यह बड़ा अंतर है।

एक सरणी में, आप केवल उनकी अनुक्रमणिका के माध्यम से मानों तक पहुंच सकते हैं और अनुक्रमणिका केवल एक संख्या हो सकती है। हैश तालिका में, आप मूल्यों को उनकी कुंजी के माध्यम से एक्सेस करते हैं और कुंजी कुछ भी हो सकती है (स्ट्रिंग, प्रतीक, पूर्णांक…), जब तक आप इसके लिए हैश फ़ंक्शन लिख सकते हैं।

आप सभी अक्षरों को उनके ASCII मानों में परिवर्तित करके और फिर उन्हें जोड़कर स्ट्रिंग के लिए एक साधारण हैश फ़ंक्शन लिख सकते हैं।

यहां एक उदाहरण दिया गया है :

BUCKETS = 32

def hash(input)
  input.to_s.chars.inject(0) { |sum, ch| sum + ch.ord } % BUCKETS
end

इस विधि में हम to_s . का उपयोग करते हैं यह सुनिश्चित करने के लिए कि हम एक स्ट्रिंग के साथ काम कर रहे हैं।

इससे हमें 'अपरिभाषित विधि' त्रुटियों से बचने में मदद मिलेगी। फिर chars . का संयोजन (स्ट्रिंग को Array . में बदलने के लिए इसके पात्रों के) और inject मूल्यों को जोड़ने के लिए।

ब्लॉक के अंदर मैंने ord . का इस्तेमाल किया वर्णों को उनके क्रमिक मूल्यों में बदलने की विधि।

अंत में, मैंने मॉड्यूलो ऑपरेटर का उपयोग किया % यह सुनिश्चित करने के लिए कि परिणामी मान सरणी में फिट बैठता है। हम इस सरणी में प्रत्येक प्रविष्टि को 'बकेट' कहते हैं।

बाल्टी वितरण

आदर्श रूप से हम चाहते हैं कि हमारे सभी बकेट समान रूप से भरे जाएं, यह हमें सबसे अच्छा प्रदर्शन देगा जब हमें किसी मूल्य को पुनः प्राप्त करने की आवश्यकता होगी।

आइए देखें कि जब हम इस कोड का उपयोग करके अपने हैश फ़ंक्शन का परीक्षण करते हैं तो क्या होता है:

# Create an array of size BUCKETS with all elements set to 0
table   = Array.new(BUCKETS) { 0 }
letters = Array('a'..'z')

10_000.times do
  # Create a random string
  input = Array.new(5) { letters.sample }.join

  # Count hash distribution
  table[hash(input)] += 1
end

यह निम्नलिखित परिणाम उत्पन्न करता है:

[302, 290, 299, 309, 321, 293, 316, 301, 296, 306, 340, 321, 313, 304, 318, 296, 331, 306, 348, 330, 310, 313, 298, 292, 304, 315, 337, 325, 325, 331, 319, 291]

ऐसा लगता है कि हमारी चाबियां समान रूप से वितरित हैं…

...लेकिन क्या होगा यदि हम बाल्टियों की संख्या बढ़ा दें?

इस उदाहरण में मैंने 128 के बाल्टी आकार का उपयोग किया (यह पहले 32 था):

[22, 24, 33, 36, 41, 58, 61, 66, 97, 77, 88, 110, 89, 82, 123, 121, 119, 111, 147, 178, 136, 176, 144, 180, 190, 193, 185, 192, 223, 209, 208, 196, 215, 251, 233, 226, 231, 236, 219, 218, 227, 221, 206, 220, 208, 213, 201, 191, 182, 165, 188, 141, 160, 135, 130, 117, 139, 106, 121, 85, 70, 93, 74, 61, 57, 54, 40, 46, 32, 36, 30, 21, 25, 17, 14, 16, 16, 14, 8, 11, 5, 5, 1, 1, 2, 1, 3, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 0, 4, 3, 6, 0, 2, 9, 13, 11, 12, 14, 12, 23, 12, 22]

यह अब एक महान वितरण जैसा नहीं लगता!

क्या हो रहा है?

समस्या यह है कि हमारा हैश फ़ंक्शन पर्याप्त रूप से अच्छा नहीं है क्योंकि एक ही आकार के सभी तार एक निश्चित सीमा में रहते हैं। इसलिए हमारे पास बीच में बहुत सारी खाली बाल्टियाँ हैं।

बेहतर हैश फंक्शन

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

BUCKETS = 256

def hash(input)
  input.to_s.each_char.inject(0) do |sum, ch|
    (sum << 8) ^ (ch.ord) ^ (sum >> 4)
  end % BUCKETS
end

यहाँ जो हो रहा है वह थोड़ा बदल रहा है (>> . के साथ) &<< ऑपरेटरों)। मानों को "अनन्य या ऑपरेटर" (^ . का उपयोग करके संयोजित किया जाता है )।

यह थोड़ा सा स्थानांतरण चीजों को मिला देगा, जो हमें एक बेहतर कुंजी वितरण give देगा . सही नहीं है, लेकिन यह हमारे सरल ASCII-आधारित फ़ंक्शन से बेहतर है 🙂

यदि आप एक उचित हैश फ़ंक्शन चाहते हैं तो आप मुरमुरहैश जैसे कुछ देख रहे होंगे, जो मुझे विश्वास है कि रूबी क्या उपयोग करता है।

टकरावों को संभालना

हमारे पास अभी तक कोई उपयोगी हैश तालिका नहीं है।

क्यों?

ठीक है, आपने देखा होगा कि जब एक ही इंडेक्स में दो चाबियां हैश होती हैं तो वे पुराने मान को अधिलेखित कर देंगी, और यह अच्छा नहीं है!

इसे हैश टकराव कहा जाता है और इनसे निपटने के लिए कुछ रणनीतियाँ हैं।

उदाहरण के लिए :

• डबल हैशिंग
• रैखिक जांच
• अलग श्रृखंला

आइए अलग श्रृखंला पर एक नजर डालते हैं, जहां हम किसी विशेष "बाल्टी" के लिए प्रविष्टियों को संग्रहीत करने के लिए एक लिंक्ड-सूची का उपयोग करते हैं।

तो अगर हम मान लें कि :abc और :ccc एक ही इंडेक्स के लिए हैश, हमारी हैश टेबल कुछ इस तरह दिखेगी:

3: [:abc, 100] -> [:ccc, 200]
4: nil
5: [:yx, 50]

फिर हमें सही कुंजी खोजने के लिए एक रैखिक खोज की आवश्यकता होगी।

इसका हमारे प्रदर्शन पर प्रभाव पड़ेगा क्योंकि हमारा लुकअप समय धीरे-धीरे O(n) की ओर कम हो सकता है , अपेक्षित O(1) . के बजाय ।

यदि आप इस O(something) . से परिचित नहीं हैं संकेतन जिसे "बिग-ओ नोटेशन" कहा जाता है।

लिंक की गई सूची को बहुत अधिक बढ़ने से बचाने के लिए और इसलिए हैश तालिका के प्रदर्शन को कम करने के लिए, बड़ी संख्या में बकेट का उपयोग करके हैश तालिका को फिर से बनाना आवश्यक है।

रूबी आपके लिए यह स्वचालित रूप से करती है, लेकिन फिर भी जानना अच्छा है।

निष्कर्ष

इस लेख का उद्देश्य हैश तालिका कार्यान्वयन लिखना नहीं है, बल्कि यह समझने में आपकी सहायता करना है कि वे वास्तव में कैसे काम करते हैं, इसलिए मुझे आशा है कि आपको यह दिलचस्प लगा!

ब्लॉग को चालू रखने के लिए इस पोस्ट को शेयर करना न भूलें 🙂