Separate chaining

1.  Separate chaining
2.  Operations   on  separate   chained    hash   table: 

3. Advantages   of   separate  chaining
4. Disadvantages of separate chaining

1.Separate chaining:

            The   hash  table  is   implemented  as  an   array   of  linked   lists.To  insert   an  item  into  the  table,it  is  appended   to  the  corresponding  linked   lists.The   linked   list   to  which   it  is  to be  appended   is  determined   by  hashing  the   inserting  item.This   is   known  as   chaining  (or)  separate   chaining(or) open  addressing   because   each  hash  table  element   is   a  separate  chain. Its   data  field  contains   either  keys  or  references to  keys.This  technique  allows   one   to  perform   all operations  easily  without   any  collisions.

Example:

Load  the   keys     23  13   21   14  7  8  15  in  the  same  order  in the  hash  table of  size  7  using  separate  chaining  with  the  basic  function  H(key)=key%7

H(23)=23%7=2

H(13)=13%7=6

H(21)=21%7=0

H(14)=14%7=0(COLLISION)

H(7)=7%7=0(COLLISION)

H(8)=8%7=1(COLLISION)

H(15)=15%7=1(COLLISION)

 A    chain  is  maintained   for  colliding  elements.For   instance   21   has    a  home   bucket(key)0.Simillarly  keys  14  and  7   demand  for   home   bucket0.Hence   a   chain  is  maintained   at  index   0.Simillarly   the   chain  at  index   1,2   and   6  is  maintained.

Collision resolution techniques