हैश फ़ंक्शन की आंतरिक कार्यप्रणाली और टकराव प्रबंधन
समझिए कि Python ऑब्जेक्ट का हैश कैसे बनाता है, open addressing और chaining टकराव कैसे सुलझाते हैं और औसत O(1) सबसे खराब स्थिति में O(n) क्यों हो सकता है।
हैश फ़ंक्शन की आंतरिक कार्यप्रणाली और टकराव प्रबंधन, CoddyKit पर कोडिंग साक्षात्कार की तैयारी का एक निःशुल्क पाठ है। यह 4 में से 1वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह कोडिंग साक्षात्कार की तैयारी सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
हैश मैप क्या है
हैश मैप (पाइथन में शब्दकोश) एक हैश फ़ंक्शन का उपयोग करके कुंजियों को मानों से जोड़ता है। यह फ़ंक्शन किसी भी कुंजी को अंतर्निहित ऐरे के पूर्णांक इंडेक्स में बदलता है। एक आदर्श हैश फ़ंक्शन कुंजियों को ऐरे में समान रूप से फैलाता है, जिससे औसत स्थिति में खोज, प्रविष्टि और विलोपन O(1) में संभव होते हैं। अंतर्निहित ऐरे को हैश तालिका या बकेट ऐरे कहा जाता है।
पाइथन में dict अत्यधिक अनुकूलित हैश मैप है। इसकी आंतरिक कार्यप्रणाली समझने से आपको सबसे खराब स्थिति के व्यवहार का तर्क करने और उपयुक्त कुंजियाँ चुनने में सहायता मिलती है।
# Python dict is a hash map
hm = {}
hm['alice'] = 95
hm['bob'] = 87
hm['carol'] = 91
print(hm['alice']) # O(1) lookup: 95
print('bob' in hm) # O(1) membership: True
del hm['bob'] # O(1) deletion
print(hm) # {'alice': 95, 'carol': 91}हैश फ़ंक्शन और __hash__ विधि
पाइथन कुंजी से एक पूर्णांक निकालने के लिए __hash__(key) को बुलाता है, फिर बकेट इंडेक्स खोजने के लिए उस पूर्णांक को तालिका के आकार से भाग देकर शेषफल लेता है। int, str और tuple जैसे अंतर्निर्मित प्रकारों में तेज़ अंतर्निर्मित हैश कार्यान्वयन होते हैं। list और dict हैश योग्य नहीं होते (वे परिवर्तनशील होते हैं, और उनमें परिवर्तन करने से संग्रहीत हैश अमान्य हो जाता है)।
एक अच्छा हैश फ़ंक्शन कुंजियों को समान रूप से वितरित करता है, नियतात्मक होता है और जल्दी गणना की जा सकती है। पाइथन का स्ट्रिंग हैश अलग-अलग निष्पादनों में यादृच्छिक हो जाता है (यह एक सुरक्षा सुविधा है) — परीक्षण में पुनरुत्पादनीयता के लिए इसे निष्क्रिय करने हेतु PYTHONHASHSEED=0 का उपयोग कीजिए।
# Built-in hash in Python
print(hash(42)) # integer hashes to itself (CPython)
print(hash('hello')) # string hash (randomised per run)
print(hash((1, 2, 3))) # tuple hash: depends on contents
# Unhashable types
try:
hash([1, 2, 3]) # lists are mutable -> not hashable
except TypeError as e:
print('Error:', e)
# Custom class: define __hash__ and __eq__
class Point:
def __init__(self, x, y): self.x = x; self.y = y
def __hash__(self): return hash((self.x, self.y))
def __eq__(self, other): return self.x == other.x and self.y == other.y
points = {Point(1, 2): 'A', Point(3, 4): 'B'}
print(points[Point(1, 2)]) # 'A'टकराव: जब दो कुंजियाँ एक ही बकेट में हैश हों
टकराव तब होता है जब दो अलग-अलग कुंजियों से एक ही बकेट इंडेक्स प्राप्त हो। टकराव अपरिहार्य हैं (कबूतरखाना सिद्धांत: कुंजियाँ अनंत हैं, लेकिन बकेट सीमित हैं)। टकराव सुलझाने की दो मानक रणनीतियाँ हैं: श्रृंखलीकरण और खुला पता-निर्धारण। पाइथन छद्म-यादृच्छिक जाँच के साथ खुले पता-निर्धारण के एक प्रकार का उपयोग करता है।
श्रृंखलीकरण में प्रत्येक बकेट पर एक लिंक की गई सूची (या गतिशील ऐरे) संग्रहीत की जाती है; उस बकेट से टकराने वाली सभी कुंजियाँ एक श्रृंखला बनाती हैं। खुला पता-निर्धारण जाँच के क्रम के अनुसार अगला खाली बकेट खोजता है।
# Simplified chaining hash map
class ChainingHashMap:
def __init__(self, capacity=8):
self.capacity = capacity
self.buckets = [[] for _ in range(capacity)]
def _idx(self, key):
return hash(key) % self.capacity
def put(self, key, val):
bucket = self.buckets[self._idx(key)]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, val)
return
bucket.append((key, val))
def get(self, key):
for k, v in self.buckets[self._idx(key)]:
if k == key:
return v
return None
hm = ChainingHashMap()
hm.put('a', 1); hm.put('b', 2)
print(hm.get('a')) # 1
print(hm.get('c')) # Noneखुला पता-निर्धारण: रैखिक जाँच
रैखिक जाँच में, जब इंडेक्स i पर टकराव होता है, तो मैप i+1, i+2, ... की जाँच करता है (अंत तक पहुँचने पर फिर शुरुआत से शुरू करते हुए), जब तक कोई खाली स्थान न मिल जाए। कुंजी खोजने के लिए खोज को इसी क्रम की जाँच करनी पड़ती है। स्थान को खाली करने के बजाय विलोपन के लिए 'हटाने का चिह्न' रखना आवश्यक होता है, ताकि जाँच की श्रृंखला न टूटे।
समूहीकरण इसका मुख्य नुकसान है: एक बार भरे हुए स्थानों का समूह बन जाने पर, उस क्षेत्र में भविष्य की प्रविष्टियाँ समूह को बढ़ाती जाती हैं और प्रदर्शन O(n) की ओर गिरने लगता है।
class LinearProbingHashMap:
DELETED = object() # tombstone sentinel
def __init__(self, capacity=8):
self.capacity = capacity
self.keys = [None] * capacity
self.vals = [None] * capacity
self.size = 0
def _probe(self, key):
idx = hash(key) % self.capacity
while self.keys[idx] is not None and self.keys[idx] != key:
idx = (idx + 1) % self.capacity
return idx
def put(self, key, val):
idx = self._probe(key)
if self.keys[idx] is None:
self.size += 1
self.keys[idx] = key
self.vals[idx] = val
def get(self, key):
idx = self._probe(key)
if self.keys[idx] == key:
return self.vals[idx]
return None
hm = LinearProbingHashMap()
hm.put('x', 10); hm.put('y', 20)
print(hm.get('x')) # 10भराव गुणांक और पुनः आकार निर्धारण
भराव गुणांक संग्रहीत प्रविष्टियों और कुल क्षमता का अनुपात है: α = n/m। α बढ़ने पर टकराव की संभावना बढ़ती है और प्रदर्शन घटता है। जब भराव गुणांक लगभग 2/3 से अधिक हो जाता है, तो पाइथन का dict क्षमता को दोगुना करके उसका आकार बदलता है। पुनः आकार निर्धारण में सभी मौजूदा प्रविष्टियों को नई, बड़ी तालिका में फिर से हैश किया जाता है — यह O(n) की संक्रिया है, जो बहुत कम बार होती है और प्रविष्टि की अमॉर्टाइज़्ड लागत O(1) बनाए रखती है।
import sys
d = {}
prev_size = sys.getsizeof(d)
for i in range(30):
d[i] = i
new_size = sys.getsizeof(d)
if new_size != prev_size:
print(f'Resized at n={i+1}: {prev_size} -> {new_size} bytes')
prev_size = new_sizeऔसत O(1) बनाम सबसे खराब स्थिति O(n)
अच्छे हैश फ़ंक्शन के अंतर्गत टकराव कम होते हैं और श्रृंखला की अपेक्षित लंबाई n से स्वतंत्र रूप से स्थिर रहती है। इसलिए औसत स्थिति में खोज, प्रविष्टि और विलोपन O(1) होते हैं। हालांकि, सबसे खराब स्थिति में — उदाहरण के लिए, जब जानबूझकर तैयार किया गया डेटा सभी कुंजियों को एक ही बकेट में भेजता है — सभी संक्रियाओं की लागत O(n) हो जाती है। पाइथन का यादृच्छिक हैश बीज इस हमले के प्रभाव को कम करता है, लेकिन सैद्धांतिक रूप से सबसे खराब स्थिति को समाप्त नहीं करता।
साक्षात्कार के विश्लेषण में कहिए: 'टकरावों के कारण औसत O(1), सबसे खराब स्थिति में O(n)।'
# Python randomised hash seed prevents worst-case hash-flooding
import os
print('PYTHONHASHSEED:', os.environ.get('PYTHONHASHSEED', 'random'))
# By default Python randomises the hash of strings each run
# This prevents an attacker from crafting keys that all collide
# To reproduce results in testing: PYTHONHASHSEED=0 python script.pyपाइथन का शब्दकोश बनाम डिफ़ॉल्ट शब्दकोश बनाम गणक
पाइथन में जानने योग्य हैश मैप के तीन प्रकार मिलते हैं। dict सामान्य उपयोग वाला मैप है; अनुपस्थित कुंजी तक पहुँचने पर KeyError उत्पन्न होता है। defaultdict(factory) अनुपस्थित कुंजी तक पहुँचने पर डिफ़ॉल्ट मान लौटाता है (यह सूचियाँ एकत्र करने या गणना करने के लिए उपयोगी है)। Counter हैश योग्य वस्तुओं की गणना के लिए विशेषीकृत उपवर्ग है; यह गणकों के बीच अंकगणितीय संक्रियाओं का भी समर्थन करता है।
from collections import defaultdict, Counter
# defaultdict for grouping
groups = defaultdict(list)
for word in ['apple', 'ant', 'banana', 'bee', 'avocado']:
groups[word[0]].append(word)
print(dict(groups))
# {'a': ['apple','ant','avocado'], 'b': ['banana','bee']}
# Counter for frequency
c = Counter('abracadabra')
print(c.most_common(3)) # [('a',5),('b',2),('r',2)]
print(c['a'] - Counter('aa')['a']) # counter subtractionहैश मैप बनाम हैश समुच्चय
हैश समुच्चय केवल कुंजियाँ संग्रहीत करता है (उनसे जुड़े मान नहीं) और सदस्यता जाँच, प्रविष्टि तथा विलोपन O(1) में करता है। पाइथन का set एक हैश समुच्चय है। जब आपको संबंधित डेटा संग्रहीत किए बिना केवल यह जानना हो कि 'क्या यह तत्व मौजूद है?', तब समुच्चय का उपयोग कीजिए। जब आपको कुंजियों के साथ मान (गणनाएँ, परिणाम आदि) जोड़ने हों, तब dict का उपयोग कीजिए।
# set for membership testing
visited = set()
for node in [1, 3, 5, 3, 7, 1]:
if node not in visited:
print('New node:', node)
visited.add(node)
# Set operations: union, intersection, difference
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
print('Union:', A | B) # {1,2,3,4,5,6}
print('Intersection:', A & B) # {3,4}
print('Difference:', A - B) # {1,2}शुरुआत से हैश मैप लागू करना (साक्षात्कार संस्करण)
साक्षात्कारकर्ता कभी-कभी आपसे एक बुनियादी हैश मैप लागू करने के लिए कहते हैं। इसके मुख्य घटक हैं: बकेटों का एक निश्चित आकार वाला ऐरे (16 या 1024 का उपयोग कीजिए), प्रत्येक बकेट में श्रृंखलीकरण के लिए (कुंजी, मान) युग्मों की एक सूची, एक हैश फ़ंक्शन (पाइथन के अंतर्निर्मित hash % क्षमता का उपयोग कीजिए), और जब भराव गुणांक 0.7 से अधिक हो जाए तब पुनः आकार निर्धारण। पुनः आकार निर्धारण और भराव गुणांक का स्वयं उल्लेख करना आपके गहरे ज्ञान को प्रदर्शित करता है।
class HashMap:
def __init__(self, capacity=16):
self.capacity = capacity
self.size = 0
self.buckets = [[] for _ in range(capacity)]
def _hash(self, key):
return hash(key) % self.capacity
def put(self, key, val):
b = self.buckets[self._hash(key)]
for i, (k, v) in enumerate(b):
if k == key:
b[i] = (key, val)
return
b.append((key, val))
self.size += 1
if self.size / self.capacity > 0.7:
self._resize()
def get(self, key, default=None):
for k, v in self.buckets[self._hash(key)]:
if k == key:
return v
return default
def _resize(self):
old = self.buckets
self.capacity *= 2
self.buckets = [[] for _ in range(self.capacity)]
self.size = 0
for bucket in old:
for k, v in bucket:
self.put(k, v)
hm = HashMap()
for i in range(20):
hm.put(i, i * 2)
print(hm.get(10)) # 20
print(hm.capacity) # should have resizedजब हैश मैप विफल होते हैं: हैश न की जा सकने वाली कुंजियाँ
केवल हैश योग्य वस्तुएँ ही शब्दकोश की कुंजियाँ बन सकती हैं। पाइथन में कोई वस्तु हैश योग्य तब होती है जब उसमें __hash__ विधि और __eq__ विधि हो, और उसके जीवनकाल में उसका हैश मान न बदले। सूचियाँ, समुच्चय और शब्दकोश परिवर्तनशील होते हैं, इसलिए हैश योग्य नहीं होते। कुंजियों के रूप में सूचियों और समुच्चयों के विकल्प के तौर पर टपल और frozenset हैश योग्य होते हैं।
साक्षात्कार में आम भ्रम यह है: वर्ण-विन्यासों को समूहित करने के लिए dict की कुंजी के रूप में क्रमबद्ध सूची के बजाय क्रमबद्ध टपल का उपयोग करना आवश्यक है।
from collections import defaultdict
def groupAnagrams(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(sorted(s)) # tuple is hashable; list is not
groups[key].append(s)
return list(groups.values())
print(groupAnagrams(['eat','tea','tan','ate','nat','bat']))
# [['eat','tea','ate'], ['tan','nat'], ['bat']]सारांश: हैश मैप की जटिलता
हैश मैप प्रविष्टि, विलोपन और खोज के लिए औसत स्थिति में O(1) समय देते हैं — यही कई इष्टतम साक्षात्कार समाधानों का आधार है। मुख्य मान्यताएँ हैं: अच्छा हैश फ़ंक्शन कुंजियों को समान रूप से वितरित करता है, भराव गुणांक सीमित रहता है (पुनः आकार निर्धारण इसे बनाए रखता है), और कुंजी वस्तुएँ अपरिवर्तनीय तथा हैश योग्य होती हैं। इन मान्यताओं के सही रहने पर हैश मैप O(n) की रैखिक खोजों को O(1) की खोजों में बदल देते हैं और O(n²) के बजाय O(n) में दो-संख्या योग जैसे समाधान संभव बनाते हैं।
त्वरित जाँच
इस पाठ में डेटा संरचनाएँ और एल्गोरिद्म — कोडिंग साक्षात्कार की तैयारी से संबंधित अवधारणाओं की अपनी समझ जाँचिए।
पाठ का पुनरावलोकन
इस पाठ में आपने सीखा: हैश मैप हैश फ़ंक्शन का उपयोग करके कुंजियों को बकेट इंडेक्स से जोड़ता है और औसत स्थिति में O(1) की संक्रियाएँ देता है, टकरावों को श्रृंखलीकरण (प्रति बकेट लिंक की गई सूची) या खुले पता-निर्धारण (अगले खाली स्थान की जाँच) से सुलझाया जाता है, और केवल अपरिवर्तनीय, हैश योग्य वस्तुएँ ही शब्दकोश की कुंजियाँ बन सकती हैं — जब अनुक्रम को कुंजी के रूप में उपयोग करना हो, तब सूचियों के बजाय टपल का उपयोग कीजिए। आगे हम दो-संख्या योग और उसके साक्षात्कार में पूछे जाने वाले अनेक प्रकार हल करेंगे।
एआई शिक्षक के साथ कोडिंग साक्षात्कार की तैयारी सीखें — निःशुल्क
अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।
- पाठ्यक्रम
- 90
- पाठ
- 360
अक्सर पूछे जाने वाले प्रश्न
क्या “हैश फ़ंक्शन की आंतरिक कार्यप्रणाली और टकराव प्रबंधन” पाठ निःशुल्क है?
हाँ—“हैश फ़ंक्शन की आंतरिक कार्यप्रणाली और टकराव प्रबंधन” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
“हैश फ़ंक्शन की आंतरिक कार्यप्रणाली और टकराव प्रबंधन” में मैं क्या सीखूँगा?
समझिए कि Python ऑब्जेक्ट का हैश कैसे बनाता है, open addressing और chaining टकराव कैसे सुलझाते हैं और औसत O(1) सबसे खराब स्थिति में O(n) क्यों हो सकता है। आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ कोडिंग साक्षात्कार की तैयारी का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।
क्या कोडिंग साक्षात्कार की तैयारी शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?
पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर कोडिंग साक्षात्कार की तैयारी शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 1वाँ पाठ है।
“हैश फ़ंक्शन की आंतरिक कार्यप्रणाली और टकराव प्रबंधन” पाठ पूरा करने में कितना समय लगता है?
CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।
क्या मैं इस कोडिंग साक्षात्कार की तैयारी पाठ में कोड लिख और चला सकता हूँ?
हाँ। हर कोडिंग साक्षात्कार की तैयारी पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।
इस पाठ्यक्रम के सभी पाठ
- हैश फ़ंक्शन की आंतरिक कार्यप्रणाली और टकराव प्रबंधन
- Two-Sum और इसके अनेक रूप
- आवृत्ति गिनना और समूह बनाना
- सबसे लंबा लगातार अनुक्रम और LRU Cache