- 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 का प्रयोग करते है।
Collision resolution techniques
यह collision resolution techniques दो प्रकार की होती है :-
(1) Separate chaining (open hashing)
(2) Open addressing (closed hashing)
Separate chaining
इस तकनीक में जिस 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
- इसे implement करना आसन है।
2. Hash table कभी भी भरती नही! इसलिए हम chain में ज्यादा element डाल सकते है ।
3. यह Hash function या load factors के लिए कम sensitive (संवेदनशील) है।
4. इसका प्रयोग तब ज्यादा किया जाता है जब हमें यह पता नही होता है की कितने keys को insert या delete करना है।
Disadvantage of separate chaining
- इसमें chaining की cache performance अच्छी नही है।
2. इसमें space का wastage होता है।
3. यदि chain लम्बी हो जाये तब search time का worst case O(1) हो जाता है।
4. links के लिए ज्यादा space की जरूरत होती है।