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.
- 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.
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.
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).
- 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 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-
- Mid Square Hash Function
- Division Hash Function
- 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,
Next Article- Collision in Hashing
Get more notes and other study material of Data Structures.
Watch video lectures by visiting our YouTube channel LearnVidFun.