Home | | Programming and Data Structures I | Re Hashing Collision

Chapter: Programming and Data Structures : Sorting And Searching

Re Hashing Collision

Collision occurs when a hash value of a record being inserted hashes to an address that already contain a different record(i.e) when two key values hash to the same position.

RE-HASHING Collision:

 

Collision occurs when a hash value of a record being inserted hashes to an address that already contain a different record(i.e) when two key values hash to the same position.

 

Collision Resolution:

 

The process of finding another position for the collide record is said to be collision resolution stategy.

 

Two categories of Hashing: àopen Hashing

 

a) Separate Chaining. -Linked list àClosed Hashing

a)Open addressing.

i) Linear Probing. - Hi(X) = (HASH(X) +i)  % tablesize

ii) Quadratic Probing - Hi(X) = (HASH(X) +i2) % tablesize iii)Double hashing. - Hi(X) = (HASH(X) +i* HASH2(X) % tablesize

 

HASH2(X)=R-(X % R) R is a prime number that is smaller than the table size

 

If the table gets too full,then the rehashing method builds new table that is a about twice as big and scan down the entier original hashtable ,computing the new hash value for each element and inserting it in the new table .

 

Rehashing is very expensive operation, the running time is O(N),since there are N element to rehashing and the table size roughly 2N.

 

Rehashing can be implemented in several ways with quadratic probing such as:

 

àRehashing,as soon as the table is half full;

àRehashing only when an insertion fails.

àRehashing when the table reaches a certain load factor

Eg:13,15,24,6 ,23are to be inserted in hash table of size 7.


The table will be 70% full.

 

A new table is created as the table is so full. The new hash function is then h(X) =X mod 17




 

 

ADVANTAGE:

Programmer does not worry about the table size.

Simple to implement.

Can be used in other data structures as well.


Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Programming and Data Structures : Sorting And Searching : Re Hashing Collision |


Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.