Hashing & Collision Concept | Data Structure

Hashing :

Hashing is a search technique in which a specific function is used to store & retrieve data from memory this function is called hash function.

Hash function is a procedure which takes key as a argument and returns a unique memory location M between lower limit and upper limit of hash table. This memory location (M) is used to store & retrieve data related to (Key) for example:

Suppose key =3205 and we are using mid square method as a hash function than it returns 72 for key = 3205. This  72th location of memory will be used to store and retrieve data related to key 3205.

Hash Function :

1. Mid Square Method

2. Division Method

3. Folding Method

Mid Square Method:

In this method first we square the key value such as 

    key= (key)² = (3205)² =10272023

than we cancel the digit from left or right till we get the two digit.

Now M=72.

Division Method:

In this method we first find the maximum prime number from lower level memory to upper level memory. such as

    D = max [ prime no.(LL,UL) ]

and apply 

    M = key Mod(%) D

Example: 

    Suppose D = 97 (max prime no between (0 to 99)

    Suppose key = 3205

    Now M = 3025 % 97 =04

    M = 04 

Folding Method:

As the name says folding means , In this method we perform fold between numbers for that we find the mid between the numbers such as.

Note : We have memory location of two that why we give two folds.

Suppose :

Case 1: If key=3205 than we do like

            32 | 05

            32 + 05 =37

            M = 37

Case 2: If key = 13205 

In this case we are not able to find mid so we will add one 0 at beginning make it fold able such as

            013205   

Now apply folding method

            01 | 32 | 05

            01 + 32 + 05 =38

            M = 38

Case 3: If key = 8985

than we simply apply folding method

            89 | 85

89 + 85 = 174 

Here we get three digit , so we again apply cancellation method such as

so here M = 74 or M = 17

Collision:

When a hash function returns same memory location for two different key value such a conflicting situation in hashing is called collision.

As hash function Hf return same memory location M. For two different keys , Key1, Key2.

Example:

Suppose if we are using folding method and 

    Key1 = 3205

        32 | 05 → 32 + 05 → 37

    Key2 = 3106

        31 | 06 → 31 + 06 → 37

Than for both keys folding method return 37 , Such a situation is called collision.

Collision Resolution Techniques:

When collision arise than some technique is used to resolve such problem.

Following techniques are used

1. Chaining

2. Probing

    a. Linear Probing

    b. Quadratic Probing

1. Chaining:

In this method we link linked list to memory location if collision occur such as:

Suppose 

Keys : 35 ,47 ,30 , 55 , 78 , 50, 29, 65

M = 10  (0 to 9)

H(key) = key Modulo M

Note: here we have 10 memory locations so we assume module as 10.

For 35  H(35)= 35 modulo 10 = 5

Here create a linked list and link with memory location 5. Address of linked list store in that location.

For 47  H(47)= 47 modulo 10 = 7

Here create a linked list and link with memory location 7. Address of linked list store in that location.

For 30  H(30)= 30 modulo 10 = 0

Here create a linked list and link with memory location 0. Address of linked list store in that location.

For 55  H(55)= 55 modulo 10 = 5

Here again we get location 5 that means the collision occur than we add new node at the beginning of existing linked list at that location and place their address at that location.

For 78  H(78)= 78 modulo 10 = 8

Here create a linked list and link with memory location 8. Address of linked list store in that location.

For 50  H(50)= 50 modulo 10 = 0

Here again we get location 0 that means the collision occur than we add new node at the beginning of existing linked list at that location and place their address at that location.

For 65  H(65)= 65 modulo 10 = 5

That is the complete process of chaining.

2. Probing:

In this method we find the memory location by using hash function

H(key) = key module 10

If collision occur than we find the next empty location in different way such as 

    i. Linear Probing

    ii. Quadratic Probing

i. Linear Probing: 

let we understand by the help of example:

Suppose

Key : 12, 11, 32,61,56....

H(key) = key module 10

For key=12

H(12) = 12 module 10

          = 2

For key=11

H(11) = 11 module 10

          = 1

For key= 32

H(11) = 32 module 10

          = 2

here memory location is already occupied and we again get location 2 for 32 so we can say that it is a condition of collision. So in linear probing suggest the next empty location.

For key= 61

H(11) = 61 module 10

          = 1

Here memory location is already occupied and we again get location 1 for 61 so we can say that it is a condition of collision. So in linear probing suggest the next empty location.

This process is time consuming for searching next empty location.

ii. Quadratic Probing:

let we understand by the help of example:

Suppose

Key : 29 , 28 , 19 , 39 , 18.

    H(key) = key module 10

If collision occur than apply

    H(key) = (key + i²) module 10

For key=12

H(29) = 29 module 10

          = 9

For key= 28

H(29) = 29 module 10

          = 8

For key= 19

H(29) = 19 module 10

          = 9

here location 9 is already occupied , this is the condition of collision so we apply

H(29) = (29 + 1²) module 10

          = 0