Hash collision and its resolution

Hash collision (हैश कोलीशन):-

It is a special situation where two or more key values are qualify for mapping at same index in the hash table.

यह एक विशेष स्थिति है जिसमे दो या दो से अधिक की-वैल्यू, हैश टेबल के एक ही इंडेक्स पर मैप होने के लिए योग्य हो जाती है। 

Hash collision resolution techniques ( हैश कोलीशन हटाने की युक्तियाँ ):-

Following collision resolution techniques are used for resolving or handling the collision in hash table:-.

निम्न युक्तियों का प्रयोग, हैश टेबल में कोलीशन हटाने के लिए किया जाता है :-

Open Hashing (ओपन हैशिंग):-

When collision occurs at any slot of hash table, this technique forms a linked list to store new key value. this technique is also called separate chaining.

जब हैश टेबल के किसी स्लॉट में कोलीशन उत्पन्न होता है तब इस युक्ति में एक लिंक्ड लिस्ट तैयार की जाती है जो नयी की-वैल्यू को रखती है। इस युक्ति को सेपरेट चैनिंग भी कहा जाता है।     

Closed hashing (open Addressing):-

In this technique a fixed size array data structure (Bucket) is used to form a hash table while inserting a new key, if a collision occurs, next empty slot of bucket is given to new key. this technique is also called open addressing.

इस युक्ति में एक फिक्स साइज के ऐरे डाटा स्ट्रक्चर(बकेट) का प्रयोग कर हैश टेबल निर्मित की जाती है एवं जब कोई नयी की इन्सर्ट की जाती है एवं कोलीशन उत्पन्न होता है तब उस नयी की-वैल्यू को बकेट के अगले रिक्त स्लॉट पर रखा जाता है। इस युक्ति को ओपन एड्रेसिंग भी कहा जाता है। 

Closed hashing uses following techniques-

क्लोज्ड हैशिंग में निम्न युक्तियों  का प्रयोग  किया जाता है-  

1.) Linear probing(लीनियर प्रोबिंग):-

If collision occurs then we linearly probe for the next empty bucket and store new key value on it.

यदि कोलीशन उत्पन्न होता है तब हम श्रेणी क्रम में अगले रिक्त स्लॉट हेतु जाँच पड़ताल करते है एवं नयी की -वैल्यू को वहाँ रख देते है। 

2.) Quadratic probing (क्वाड्रैटिक प्रोबिंग):- 

If collision occurs, we probe i$2‘th bucket in i'th iteration for the next empty bucket and store new key value on it.

यदि कोलीशन उत्पन्न होता है तब हम i वी पुनरावृत्ति के लिए i के वर्ग रिक्त स्लॉट हेतु जाँच पड़ताल करते है एवं नयी की -वैल्यू को वहाँ रख देते है। 

3.) Double hashing (डबल हैशिंग):-

In this technique,we use another hash function h2(x) and look for i * h2(x) bucket in i'th iteration to store new key value.

इस युक्ति में,हम एक अन्य हैश फंक्शन h2(x) का प्रयोग करते है एवं i * h2(x) रिक्त स्लॉट पर नयी की-वैल्यू को रख देते है।