Question

what is collision resolution technique? by giving an example explain in file processing

Answer 1

In hashing a hash function is used to calculate the hash value for a key. The hash value is then used as an index to store the key in the hash table. A range of a hash function is usually finite and over a range but the input the funciton is practically infinite. So a hash function may reurn the same hash value for two or more keys. This is called as collision.

Collision Resolution Techniques are the techniques used for resolving or handling the collision. Collisions can be reduced with a selection of a good hash function. They are classified as:

• Separate Chaining: Collisions can be resolved by creating a list of keys that map to the same value
• Open Addressing: All elements are stored in the hash table itself. If the required slot is found occupied, the program will check the subsequent slots in turn until an available slot is located. It is further of three types: Linear Probing, Quadratic Probing and Double Hashing
• In linear probing, we linearly probe for next slot.
• In quadratic probing, we look for i²‘th slot in i’th iteration.
• In double hasing we use two hash functions.

In file processing when inserting records use of hashing techniques provide very efficient and quick access to records based on certain search conditions. A function h, called a hash function is applied to the hash field value of a record and computes the address of the disk block in which the record is stored. Suppose K is a hash key value, the hash function h will map this value to a block address in the following way : h(K) = address of the block containing the record with the key value K. A collision occurs when the hash field value of a new record that is being inserted hashes to an address that already contains a different record. In this situation,we must insert the new record in some other position. The process of finding another position is called collision resolution.

Hope this helped. Please do upvote and if there are any queries please ask in comments section.