WHY HASHING IS NEEDED :
There are several searching techniques like linear search, binary search, search
trees etc. In these techniques, time taken to search any particular element depends
on the total number of elements.
For Example-
1) Linear Search takes O(n) time to perform the search in unsorted arrays
consisting of n elements.
2) Binary Search takes O(logn) time to perform the search in sorted arrays
consisting of n elements.
3) Binary Search Tree takes O(logn) time to perform the search. Here, n are
total number of elements.
The main drawback of these techniques is-
These techniques become problematic as the number of elements increases
because time taken to perform the search also increases.
Note- To resolve this issue of dealing with too large number of elements
concept of hashing were introduced.
Hashing in Data Structure-
In data structures,
Hashing is a well-known technique to search any particular
element among several elements.
It minimizes the number of comparisons while performing the search.
Advantage-
Unlike other searching techniques,
Hashing is extremely efficient.
The time taken by it to perform the search does not depend upon
the total number of elements.
It completes the search with constant time complexity O(1).
, Hashing Mechanism-
In hashing,
An array like data structure called as Hash table is used to store the data items.
Based on the hash key value, data items are inserted into the hash table.
Hash Key Value-
Hash key value is a special value that serves as an index for a data item.
It indicates where the data item should be stored in the hash table.
Hash key value is generated using a hash function.
Hash Function-
Hash function is a function that maps any big number or string to a small integer
value.
Hash function takes the data item as an input and returns a small
integer value as an output.
The small integer value is called as a hash value.
Hash value of the data item is then used as an index for storing it into the hash
table.
Types of Hash Functions-
, There are various types of hash functions available such as-
1. K mod 10
2. K mod N
3. Mid Square Hash Function
4. Division Hash Function
5. Folding Hash Function etc.
It depends on the user which hash function he wants to use.
Properties of Hash Function-
The properties of a good hash function are-
It is efficiently computable.
It minimizes the number of collisions.
It distributes the keys uniformly over the table
Let us understand with an example : -
Using the hash function ‘key mod N’, here N=7. Insert the
following sequence of keys in the hash table-
50, 700, 76, 85, 92, 73 and 101
Solution-
The given sequence of keys will be inserted in the hash table as-
Step-01:
Draw an empty hash table.
There are several searching techniques like linear search, binary search, search
trees etc. In these techniques, time taken to search any particular element depends
on the total number of elements.
For Example-
1) Linear Search takes O(n) time to perform the search in unsorted arrays
consisting of n elements.
2) Binary Search takes O(logn) time to perform the search in sorted arrays
consisting of n elements.
3) Binary Search Tree takes O(logn) time to perform the search. Here, n are
total number of elements.
The main drawback of these techniques is-
These techniques become problematic as the number of elements increases
because time taken to perform the search also increases.
Note- To resolve this issue of dealing with too large number of elements
concept of hashing were introduced.
Hashing in Data Structure-
In data structures,
Hashing is a well-known technique to search any particular
element among several elements.
It minimizes the number of comparisons while performing the search.
Advantage-
Unlike other searching techniques,
Hashing is extremely efficient.
The time taken by it to perform the search does not depend upon
the total number of elements.
It completes the search with constant time complexity O(1).
, Hashing Mechanism-
In hashing,
An array like data structure called as Hash table is used to store the data items.
Based on the hash key value, data items are inserted into the hash table.
Hash Key Value-
Hash key value is a special value that serves as an index for a data item.
It indicates where the data item should be stored in the hash table.
Hash key value is generated using a hash function.
Hash Function-
Hash function is a function that maps any big number or string to a small integer
value.
Hash function takes the data item as an input and returns a small
integer value as an output.
The small integer value is called as a hash value.
Hash value of the data item is then used as an index for storing it into the hash
table.
Types of Hash Functions-
, There are various types of hash functions available such as-
1. K mod 10
2. K mod N
3. Mid Square Hash Function
4. Division Hash Function
5. Folding Hash Function etc.
It depends on the user which hash function he wants to use.
Properties of Hash Function-
The properties of a good hash function are-
It is efficiently computable.
It minimizes the number of collisions.
It distributes the keys uniformly over the table
Let us understand with an example : -
Using the hash function ‘key mod N’, here N=7. Insert the
following sequence of keys in the hash table-
50, 700, 76, 85, 92, 73 and 101
Solution-
The given sequence of keys will be inserted in the hash table as-
Step-01:
Draw an empty hash table.
