Hashing -Data Structure-Hashing in Java

 

Hashing

 

Why we need Hashing algorithm and how it differs from other algorithms

 

The main objective of Data Structure is effective way of organizing data in memory so that search and sort and other operations are fast.

Hashing is a special technique used to store and search data more effectively.

1.Compare with Array

We have 5 records and we want to store them in an effective way and retrieve any one from that collection. I want to search 13


 

Number iterations  5

Time Complexity O(n) ( n here denotes number of items in the Array)

 

 

 

 

 

2.Compare with Linked List

Trying search 13


 

Number of iterations 5

Time Complexity O(n)

 

3.Binary Search Tree


 

Number of iterations:4

Time complexity  O(log n)

/*For the input of size n, an algorithm of O(n) will perform steps proportional to n, while another algorithm of O(log(n)) will perform steps roughly log(n).

Clearly log(n) is smaller than n hence algorithm of complexity O(log(n)) is better. Since it will be much faster.

*/

Hash table a specialized array ,here we use special function called Hash function  to store and retrieve data in a collection.

But normal array we use index to store in a linear fashion.

 

Step 1: create a hash table

Step 2: Use a prime number

We have five records(5)

We need a prime number after the 5 that is 7

We need a hash function, it’s a mathematical formula .

A simple one is modulo operation


 


 

Search using Hash

We search 15


 

No of iterations 1  &Time Complexity O(1)

Collision:

Hash table size must be prime number, if we take the size as a non prime number:

Say for example the size is 8


 

While using prime number as size of Hashtable will also sometimes creates Collision.

To avoid that there are two methods:

 1.separate Chaining 2.Open Addressing

 

In separate chaining we use Linked List when collision occurs:


 Hash table size =7

 50%7=1  so 50 stored in 1st index

700%7=0 so 700 goes to 0th index

76%7=6 so 76 goes to 6th index

85 %7

Search speed would be not o(1)

 

Open Addressing:

The main advantage is no linked is used here.A new technique will followed when collision occurs:

a)Linear probing

b)Quadratic Probing

c)Double Hashing

Linear probing is scheme in computer programming for resolving collisions in a hashtable data structures for maintaining a collection of key-value pairs and looking up a value associated with a given key.

 

Quadratic probing operates by taking the original hash index and adding successive values of an arbitrary  quadratic polynomial until  an open slot is found.

Double hashing a technique  used in conjunction with open addressing in hash tables to resolve hash collisions  by using a secondary hash of the key as an offset when a collision occurs

=============================================================

 

Linear probing


 

Initially i=0, if collision occurs value increased by 1, increasing the value linearly from 0 to 1,2.. and so on.

 

 Hash(7)=(7+0)%11=7

Hash(36)=(36+0)%11=3

Hash(18)=(18+0)%11=7(collision occurs)

Repeat Hash(18)=(18+1)%11=8

Hash(62)=(62+0)%11=11(collisoion)

Repeat hash(62)=(62+1)%11=8 collision

Repeat hash(62)=(62+2)%11=9


 

Quadratic Probing

Jumping will be done

 


 

Hash(7)=(7+0)%11=7

Hash(36)=(36+0)%11=3

Hash(18)=(18+0)%11=7 collision occurs

Hash(18)=(18+1)%11=8

Hash(62)=(62+0)%11=7 collision

Hash(62)=(62+1)%11=8 collision

Hash(62)=(62+(2*2))%11=0

 


 

 

Search


 

Time complexity in Hashing is o(1) If no collision comes.

If collision comes time complexity will be little bit more.

 


python training with real time projects

java script-text to speech-assignment-Fatima Solkar Final Year-BE I.T FAMT-Ratnagiri-Maharastra

Page Title Mandvi Beach Ratnagiri At a distance of 2 km from Ratnagiri Bus Stand, Mandvi Beach i...

Technical Skills for B.Com and B.B.A