Data structure में collision resolution techniques एक प्रकार की तकनीक होती है जिसका प्रयोग hashing में collision को handle करने के लिए किया जाता है.
टॉपिक
Hashing क्या है?
Hashing एक प्रक्रिया है जिसमे बहुत बड़े amount के डाटा को hashing function की मदद से छोटे table में map किया जाता है ! यह एक searching तकनीक है !
यह search को time complexity o (1) में पूरा करती है!
Hashing में collision क्या है?
- Hashing में hash फंक्शन का प्रयोग एक key की hash value को compute करने के लिए किया जाता हा
- उसके बाद hash value का प्रयोग hash table में key को स्टोर करने के लिए index के तौर पर किया जाता है!
- Hash फंक्शन जो है वह दो या अधिक keys के लिए एक ही समान hash value भी return कर सकती है !
- जब दो या दो से अधिक keys को एक ही hash value दी जाती है तो उसे collision कहते है और इसी collision को handle करने के लिए हम collision resolution techniques का प्रयोग करते है.
इसे पूरा पढ़े :- Hash table तथा Hash function क्या है :-
Collision Resolution Techniques के प्रकार
यह collision resolution techniques दो प्रकार की होती है :-
- Separate chaining (open hashing)
- Open addressing (closed hashing)
Separate chaining in Hindi
इस तकनीक में जिस slot में collision हुआ है उस से एक linked list बनाया जाता है उसके बाद नई key को linked list में insert किया जाता है.
slots से ये linked list एक chain की तरह दिखाई देती है इसलिए इसे separate chaining कहते है!
Time complexity:-
सर्चिंग के लिए इसकी worst case o (n) है.
deletion के लिए इसकी worst case 0 (n) है!
Advantage of separate chaining in hindi
1:- इसे implement करना आसन है!
2:- Hash table कभी भी भरती नही! इसलिए हम chain में ज्यादा element डाल सकते है !
3:- यह Hash function या load factors के लिए कम sensitive (संवेदनशील) है!
4:- इसका प्रयोग तब ज्यादा किया जाता है जब हमें यह पता नही होता है की कितने keys को insert या delete करना है!
Disadvantage of separate chaining
1:- इसमें chaining की cache performance अच्छी नही है !
2:- इसमें space का wastage होता है
3:- यदि chain लम्बी हो जाये तब search time का worst case O(1) हो जाता है
4:- links के लिए ज्यादा space की जरूरत होती है!
इसे पढें:- Open Addressing (Closed Hashing) क्या है?
निवेदन:– hello दोस्तों. उम्मीद है कि collision resolution techniques in hindi की यह पोस्ट आपको पसंद आई होगी. अगर आपके कोई सवाल है तो आप मुझे कमेंट के द्वारा बता सकते है तथा इस पोस्ट को अपने दोस्तों के साथ अवश्य share कीजिये. धन्यवाद.