What is a Hash function?
The hash function creates a mapping between key and value, this is done through the use of mathematical formulas known as hash functions. The result of the hash function is referred to as a hash value or hash. The hash value is a representation of the original string of characters but usually smaller than the original.
For example: Consider an array as a Map where the key is the index and the value is the value at that index. So for an array A if we have index i which will be treated as the key then we can find the value by simply looking at the value at A[i].
simply looking up A[i].
Types of Hash functions:
There are many hash functions that use numeric or alphanumeric keys. This article focuses on discussing different hash functions:
Properties of a Good hash function
A hash function that maps every item into its own unique slot is known as a perfect hash function. We can construct a perfect hash function if we know the items and the collection will never change but the problem is that there is no systematic way to construct a perfect hash function given an arbitrary collection of items. Fortunately, we will still gain performance efficiency even if the hash function isn’t perfect. We can achieve a perfect hash function by increasing the size of the hash table so that every possible value can be accommodated. As a result, each item will have a unique slot. Although this approach is feasible for a small number of items, it is not practical when the number of possibilities is large.
So, We can construct our hash function to do the same but the things that we must be careful about while constructing our own hash function.
A good hash function should have the following properties:
- Efficiently computable.
- Should uniformly distribute the keys (Each table position is equally likely for each.
- Should minimize collisions.
- Should have a low load factor(number of items in the table divided by the size of the table).
Complexity of calculating hash value using the hash function
- Time complexity: O(n)
- Space complexity: O(1)
Hashing Notes for GATE Exam [2024]
Hashing is a fundamental concept in computer science and plays a pivotal role in various algorithms and data structures. Aspiring candidates preparing for the GATE Exam 2024 must grasp the intricacies of hashing to tackle complex problem-solving scenarios efficiently. These notes aim to provide a concise yet comprehensive overview of hashing, covering essential concepts that are likely to be tested in the GATE examination.
Table of Content
- Introduction to Hashing
- Need for Hash data structure
- Components of Hashing
- How does Hashing work?
- What is a Hash function?
- Problem with Hashing
- What is collision?
- How to handle Collisions?
- Separate Chaining
- Open Addressing
- What is meant by Load Factor in Hashing?
- What is Rehashing?
- Applications of Hash Data structure
- Real-Time Applications of Hash Data structure
- Advantages of Hash Data structure
- Disadvantages of Hash Data structure
- MCQ of Hashing
Contact Us