How does Hashing work?
Suppose we have a set of strings {“ab”, “cd”, “efg”} and we would like to store it in a table.
Our main objective here is to search or update the values stored in the table quickly in O(1) time and we are not concerned about the ordering of strings in the table. So the given set of strings can act as a key and the string itself will act as the value of the string but how to store the value corresponding to the key?
- Step 1: We know that hash functions (which is some mathematical formula) are used to calculate the hash value which acts as the index of the data structure where the value will be stored.
- Step 2: So, let’s assign
- “a” = 1,
- “b”=2, .. etc, to all alphabetical characters.
- Step 3: Therefore, the numerical value by summation of all characters of the string:
- “ab” = 1 + 2 = 3,
- “cd” = 3 + 4 = 7 ,
- “efg” = 5 + 6 + 7 = 18
- Step 4: Now, assume that we have a table of size 7 to store these strings. The hash function that is used here is the sum of the characters in key mod Table size. We can compute the location of the string in the array by taking the sum(string) mod 7.
- Step 5: So we will then store
- “ab” in 3 mod 7 = 3,
- “cd” in 7 mod 7 = 0, and
- “efg” in 18 mod 7 = 4.
The above technique enables us to calculate the location of a given string by using a simple hash function and rapidly find the value that is stored in that location. Therefore the idea of hashing seems like a great way to store (key, value) pairs of the data in a table.
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