Hashing.txt

IT IS A TECHINQUE WHICH IS USED IN DATA STRUCTURE TO STORE AND RETRIVE DATA EFFECTIVELY.

HOW TO HANDLE HASH COLLISIONS

//                                                  1. SEPERATE CHAINING

USE OF LINKED LIST TO STORE ELEMENTS SO THATA IF NUM % 10 OCCURS TO BE SAME NUMBER IT CAN BE STORED AT THE TAIL OF LINKLED LIST
WHOSE ADDRESS IS STORED AT THAT HASH TABLE

BUT THE TIME COMPLEXITY FOR THIS METHOD BECOMES ORDER OF N.

LOAD FACTOR = TOTAL NO. OF ELEMENTS / SIZE OF HASH TABLE


//                                                   2. LINEAR PROBING


H(K) = (K + i) % 10

IF H(K) COLLIDES AT THE CALCULATED INDEX SEARCH IN H(K) = (K + i) % 10 INDEX OF THE HASH TABLE , WHERE i STARTS FRON 0 TO SIZE OF TABLE

IN SHORT IF THE INDEX CALCULATED IS NOT EMPTY STORE IN THE NEXT EMPTY

THE PROBLEM IN THIS METHOD OBSERVED IS PRIMARY CLUSTERING , MEANS WE GO ON SEARCHING UNTIL NEXT EMPTY INDEX IS FOUND WHICH INCREASES
THE TME COMPLEXITY



//                                                   3. QUADRATIC PROBING

H(K) = (K + i^2) % 10

SIMILAR TO LINEAR PROBING THE ONLY DIFFERENCE IS THAT i GETS SQUARED EVERY TIME UNTIL AN EMPTY CELL TO STORE ID FOUND , WHICH
DECREASED THE TIME COMPLEXITY SLIGHTLY THEN LINEAR PROBING

THE PROBLEM OBSERVED HERE IS SECONDARY CLUSTERING


//                                                  4. DOUBLE HASHING

H(K) = H1(K) + (i * H2(K)) % 10(SIZE OF THE HASH TABLE)