Operations on separate chained hash table

          The   very   frequently   used  operations   on  separate   chained    hash table   are:

1.Search

2.Insert

3.Delete

1.Searching:

                Hash   functions  of  the   element   that    is   to  be   searched   should   be   computed.

Access  the   bucket   with   corresponding  hash   value   and   proceed  to  search  the   chain  of   nodes   sequentially.If   the   elements  is  found  ,then   search  is   successful,else  it  is   unsuccessful  search.

Algorithm:

Separate   chain-hash-search(ht,b,e)

/*search  an  element    e  in  separate  chained  hash  table*/

/*ht  is  the  hash table  ,an  array  of  pointer  to  buckets,b  is  the  bucket  number   and  e is  the  element  to  be  searched*/

hf=h(e)               /*h(e)  is  the   hash  function on e*/

  t=ht(hf)            /*t is  the  pointer  to  the first  node   in the  chain*/

While   (DATA(t )=e and  t=NULL)  do

t=LINK(t);

end while

if(DATA(t)==e)then

print(“search  is  successful”);

if(t==NULL)then

print(“search  is  unsuccessful”);

End

2.Insertion:

                  Inserting  an  element  into  the  hash  table  also  requires  computer  hash function  on  the  element  to  determine the  bucket.After finding  the   corresponding  bucket  it  is  similar  to  inserting  an  element  into  a  singly   linked  list.

                  If  the   element  in each  chain  are  maintained  in either  ascending  or  descending  order   then  it  will  be  less  expensive  to  perform  all the  operations.

3.Deletion:

              Deleting  an  element   e fromm  the  hash  table  also  requires  computing  hash  function  on the  element  to  determine  the  bucket.After  finding  the  corresponding  bucket  it  is   similar  to  deleting  an  element  from  a  singly  linked  list.

Performance   Analysis:  

                        The   length  of  the   chain  of  nodes   corresponding  to  be  bucket  decides  the   complexity   of  separate  chained  hash tables.The   best  case  and  worst  case   search  operation  occurs  when  all n  elements  are  mapped   to  the  same  bucket  and  the  searched  element  is  the  last  element  in  the  chain  of  n  nodes .

The   Best   case  complexity   of  search  opration  is  O(1) The    Worst   case  complexity  of    search  operation  is   O(n)

                

                            

Advantages   of   separate  chaining:

      Separate  chaining  has  several  advantages  over   open  addressing:

Ø  Collision  resolution   is  simple   and   efficient.

Ø  The    hash   table   can   hold  more  element  without   the  larger  performance  deterioration  of open  addressing

Ø  The  performance of chaining declines much more slowly than open addressing.

Ø  Deletion is easy-no special flag values are necessary.

Ø  Table size need not be a prime number.

Ø  The keys of the object to be hatched need not be unique.

Disadvantages of separate chaining:

Ø  It requires the implementation of separate data structures for chains and a code to manage it.

Ø  The main cost if chaining is the extra space required for the linked list.

Ø  For some languages creating new notes (for linked list) is expensive and slows down the system

Collision resolution techniques

1.Separate chaining