Hashing in Data Structure | Hash Functions

Searching Techniques-

 

In data structures,

• 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.

 

Example-

 

• Linear Search takes O(n) time to perform the search in unsorted arrays consisting of n elements.
• Binary Search takes O(logn) time to perform the search in sorted arrays consisting of n elements.
• It takes O(logn) time to perform the search in Binary Search Tree consisting of n elements.

 

Drawback-

 

The main drawback of these techniques is-

• As the number of elements increases, time taken to perform the search also increases.
• This becomes problematic when total number of elements become too large.

 

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 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 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. Mid Square Hash Function
2. Division Hash Function
3. 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.

 

To gain better understanding about Hashing in Data Structures,

Watch this Video Lecture

 

Next Article- Collision in Hashing

 

Get more notes and other study material of Data Structures.

Watch video lectures by visiting our YouTube channel LearnVidFun.