Collisions

1. What is Collision
2. Collision resolution techniques
3.  Probe   Sequence

Collisions:  

The hash function is a function that  returns   the key  value using  which the  record  can  be   placed  in the  hash  table.Thus  this   function  helps  us   in  placing   the  record   in the   hash  table   at    the   appropriate   position   and   due  to  this  we  can   retrieve   the   record   directly    from   the   location.This    function   needs   to  be   designed   very  carefully and  it   should   not   return   the   same   hash   key  address   from  two   different   records.

DEF: When   a   hash  function  maps  two  different   keys  to  same  location  then  collision occurs. Thus  the   corresponding  records  can  not  be   stored  in the  same   location .

        

Hashed            Table

Record  key       -->  Hash  function ---->                Hashed  value                  

Similarly  when there  is  no  room   for  a new   pair  in the  hash  table  then  such  a  situation  is  called   overflow. Some times  when  we   handle   collisions   it  may  lead  to  overflow  condtions .Collisions   and   overflow  show  the  poor   hash  function

Example:

Consider   a   hash  function  H(key)=recordkey%10  having  the   hash  table  of   size   10.The  record  key  values  are  131,44,43,78,19,36,57 and 77.

Record  key   ---->    Hash  function ----->    Hash  value ----->    Hash   table

 

 

 Now       if   we   try   to  place    77  in the  hash  table  then  we  get  the  hash  key  to  be  7  and  at  index 7  already  the  record  key  57  is  placed.This  situation is  called  collision .From  the  undex  7  if  we  look  for  the  next  position at   subsequent  indexes  8,9 then  we  find  that  their  is  no  room  to  place  77  in   the  hash  tablt  this  situation  is  called  overflow. 

Dictionaries  

Hash  Table  Representation

Types  of   Hash  Function