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.

Summary
Hashing in Data Structure | Hash Functions
Article Name
Hashing in Data Structure | Hash Functions
Description
Hashing in data structure is an efficient technique to perform the search. Hash table data structure is used to store the data items. Hash function is used to compute the the hash key value. Hash key value serves as an index for storing the data item into the hash table.
Author
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-