Introduction
Hashing is an important data structure designed to solve the problem of efficiently finding and storing data in an array. For example, if you have a list of 20000 numbers, and you have given a number to search in that list- you will scan each number in the list until you find a match.
Check out ourfree coursesto get an edge over the competition.
The hash function in the data structure verifies the file which has been imported from another source. A hash key for an item can be used to accelerate the process. It increases the efficiency of retrieval and optimises the search. This is how we can simply give hashing definition in data structure.
It requires a significant amount of your time to search in the entire list and locate that specific number. This manual process of scanning is not only time-consuming but inefficient too. With hashing in the data structure, you can narrow down the search and find the number within seconds.
You can also consider doing ourJava Bootcamp course from upGrad to upskill your career.
This blog will give you a deeper understanding of the hash method, hash tables, and linear probing with examples.
What is Hashing in Data Structure?
Hashing in the data structure is a technique of mapping a large chunk of data into small tables using a hashing function. It is also known as the message digest function. It is a technique that uniquely identifies a specific item from a collection of similar items.
Featured Program for you: Fullstack Development Bootcamp Course
It uses hash tables to store the data in an array format. Each value in the array has been assigned a unique index number. Hash tables use a technique to generate these unique index numbers for each value stored in an array format. This technique is called the hash technique.
You only need to find the index of the desired item, rather than finding the data. With indexing, you can quickly scan the entire list and retrieve the item you wish. Indexing also helps in inserting operations when you need to insert data at a specific location. No matter how big or small the table is, you can update and retrieve data within seconds.
The hash table is basically the array of elements and the hash techniques of search are performed on a part of the item i.e. key. Each key has been mapped to a number, the range remains from 0 to table size 1
Our learners also read: Data structures and Algorithms free course!
Types of hashing in data structure is a two-step process.
- The hash function converts the item into a small integer or hash value. This integer is used as an index to store the original data.
- It stores the data in a hash table. You can use a hash key to locate data quickly.
Examples of Hashing in Data Structure
The following are real-life examples of hashing in the data structure –
- In schools, the teacher assigns a unique roll number to each student. Later, the teacher uses that roll number to retrieve information about that student.
- A library has an infinite number of books. The librarian assigns a unique number to each book. This unique number helps in identifying the position of the books on the bookshelf.
Checkout: Sorting in Data Structure
Hash Function
The hash function in a data structure maps the arbitrary size of data to fixed-sized data. It returns the following values: a small integer value (also known as hash value), hash codes, and hash sums. The hashing techniques in the data structure are very interesting, such as:
hash = hashfunc(key)
index = hash % array_size
The hash function must satisfy the following requirements:
- A good hash function is easy to compute.
- A good hash function never gets stuck in clustering and distributes keys evenly across the hash table.
- A good hash function avoids collision when two elements or items get assigned to the same hash value.
One of the hashing techniques of using a hash function is used for data integrity. If using a hash function one change in a message will create a different hash.
The three characteristics of the hash function in the data structure are:
- Collision free
- Property to be hidden
- Puzzle friendly
Explore Our Software Development Free Courses
Fundamentals of Cloud Computing | JavaScript Basics from the scratch | Data Structures and Algorithms |
Blockchain Technology | React for Beginners | Core Java Basics |
Java | Node.js for Beginners | Advanced JavaScript |
Hash Table
Hashing in data structure uses hash tables to store the key-value pairs. The hash table then uses the hash function to generate an index. Hashing uses this unique index to perform insert, update, and search operations.
It can be defined as a bucket where the data are stored in an array format. These data have their own index value. If the index values are known then the process of accessing the data is quicker.
In-Demand Software Development Skills
JavaScript Courses | Core Java Courses | Data Structures Courses |
Node.js Courses | SQL Courses | Full stack development Courses |
NFT Courses | DevOps Courses | Big Data Courses |
React.js Courses | Cyber Security Courses | Cloud Computing Courses |
Database Design Courses | Python Courses | Cryptocurrency Courses |
upGrad’s Exclusive Software and Tech Webinar for you –
SAAS Business – What is So Different?
How does Hashing in Data Structure Works?
In hashing, the hashing function maps strings or numbers to a small integer value. Hash tables retrieve the item from the list using a hashing function. The objective of hashing technique is to distribute the data evenly across an array. Hashing assigns all the elements a unique key. The hash table uses this key to access the data in the list.
Hash table stores the data in a key-value pair. The key acts as an input to the hashing function. Hashing function then generates a unique index number for each value stored. The index number keeps the value that corresponds to that key. The hash function returns a small integer value as an output. The output of the hashing function is called the hash value.
Let us understand hashing in a data structure with an example. Imagine you need to store some items (arranged in a key-value pair) inside a hash table with 30 cells.
The values are: (3,21) (1,72) (40,36) (5,30) (11,44) (15,33) (18,12) (16,80) (38,99)
The hash table will look like the following:
Serial Number | Key | Hash | Array Index |
1 | 3 | 3%30 = 3 | 3 |
2 | 1 | 1%30 = 1 | 1 |
3 | 40 | 40%30 = 10 | 10 |
4 | 5 | 5%30 = 5 | 5 |
5 | 11 | 11%30 = 11 | 11 |
6 | 15 | 15%30 = 15 | 15 |
7 | 18 | 18%30 = 18 | 18 |
8 | 16 | 16%30 = 16 | 16 |
9 | 38 | 38%30 = 8 | 8 |
The process of taking any size of data and then converting that into smaller data value which can be named as hash value. This hash alue can be used in an index accessible in hash table. This process define hashing in data structure.
Also Read: Types of Data Structures in Python
Collision Resolution Techniques
Hashing in data structure falls into a collision if two keys are assigned the same index number in the hash table. The collision creates a problem because each index in a hash table is supposed to store only one value. Hashing in data structure uses several collision resolution techniques to manage the performance of a hash table.
It is a process of finding an alternate location. The collision resolution techniques can be named as-
- Open Hashing (Separate Chaining)
- Closed Hashing (Open Addressing)
- Linear Probing
- Quadratic Probing
- Double Hashing
Linear Probing
Hashing in data structure results in an array index that is already occupied to store a value. In such a case, hashing performs a search operation and probes linearly for the next empty cell.
Linear probing in hash techniques is known to be the easiest way to resolve any collisions in hash tables. A sequential search can be performed to find any collision that occurred.
LearnSoftware Development Courses onlinefrom the World’s top Universities. Earn Executive PG Programs, Advanced Certificate Programs, or Masters Programs to fast-track your career.
Explore our Popular Software Engineering Courses
Caltech CTME Cybersecurity Certificate Program | |
Full Stack Development Bootcamp | PG Program in Blockchain |
Executive PG Program in Full Stack Development | |
View All our Courses Below | |
Software Engineering Courses |
Linear Probing Example
Imagine you have been asked to store some items inside a hash table of size 30. The items are already sorted in a key-value pair format. The values given are: (3,21) (1,72) (63,36) (5,30) (11,44) (15,33) (18,12) (16,80) (46,99).
The hash(n) is the index computed using a hash function and T is the table size. If slot index = ( hash(n) % T) is full, then we look for the next slot index by adding 1 ((hash(n) + 1) % T). If (hash(n) + 1) % T is also full, then we try (hash(n) + 2) % T. If (hash(n) + 2) % T is also full, then we try (hash(n) + 3) % T.
The hash table will look like the following:
Serial Number | Key | Hash | Array Index | Array Index after Linear Probing |
1 | 3 | 3%30 = 3 | 3 | 3 |
2 | 1 | 1%30 = 1 | 1 | 1 |
3 | 63 | 63%30 = 3 | 3 | 4 |
4 | 5 | 5%30 = 5 | 5 | 5 |
5 | 11 | 11%30 = 11 | 11 | 11 |
6 | 15 | 15%30 = 15 | 15 | 15 |
7 | 18 | 18%30 = 18 | 18 | 18 |
8 | 16 | 16%30 = 16 | 16 | 16 |
9 | 46 | 46%30 = 8 | 16 | 17 |
Double Hashing
The double hashing technique uses two hash functions. The second hash function comes into use when the first function causes a collision. It provides an offset index to store the value.
The formula for the double hashing technique is as follows:
(firstHash(key) + i * secondHash(key)) % sizeOfTable
Where i is the offset value. This offset value keeps incremented until it finds an empty slot.
For example, you have two hash functions: h1 and h2. You must perform the following steps to find an empty slot:
- Verify if hash1(key) is empty. If yes, then store the value on this slot.
- If hash1(key) is not empty, then find another slot using hash2(key).
- Verify if hash1(key) + hash2(key) is empty. If yes, then store the value on this slot.
- Keep incrementing the counter and repeat with hash1(key)+2hash2(key), hash1(key)+3hash2(key), and so on, until it finds an empty slot.
Also visit upGrad’s Degree Counselling page for all undergraduate and postgraduate programs.
Double Hashing Example
Imagine you need to store some items inside a hash table of size 20. The values given are: (16, 8, 63, 9, 27, 37, 48, 5, 69, 34, 1).
h1(n)=n%20
h2(n)=n%13
n h(n, i) = (h1 (n) + ih2(n)) mod 20
n | h(n,i) = (h’(n) + i2) %20 |
16 | I = 0, h(n,0) = 16 |
8 | I = 0, h(n,0) = 8 |
63 | I = 0, h(n,0) = 3 |
9 | I = 0, h(n,0) = 9 |
27 | I = 0, h(n,0) = 7 |
37 | I = 0, h(n,0) = 17 |
48 | I = 0, h(n,0) = 8 I = 0, h(n,1) = 9
I = 0, h(n,2) = 12 |
5 | I = 0, h(n,0) = 5 |
69 | I = 0, h(n,0) = 9 I = 0, h(n,1) = 10 |
34 | I = 0, h(n,0) = 14 |
1 | I = 0, h(n,0) = 1 |
Read our Popular Articles related to Software Development
Why Learn to Code? How Learn to Code? | How to Install Specific Version of NPM Package? | Types of Inheritance in C++ What Should You Know? |
Conclusion
Double hashing has a high computation cost, but it searches the next free slot faster than the linear probing method. The examples given in the article are only for explanatory purposes. You can modify the statements given above as per your requirements. In this blog, we learned about the concept of hashing in the data structure.
You can try out the example to strengthen your data structure knowledge. If you are curious to know more about data structure, check out the upGrad Executive PG Programme in Full Stack Development course. This course is designed for working professionals and offers rigorous training and job placement with top companies.
As a seasoned expert in data structures and hashing techniques, it's evident that the article provides a comprehensive overview of hashing in the context of data structures. The depth of knowledge is reflected in the precise explanations, real-life examples, and practical applications presented in the content. Let's break down the key concepts covered in the article:
-
Hashing in Data Structure:
- Hashing is a technique for mapping large data sets into smaller tables using a hashing function.
- It involves using hash tables to store data in an array format, where each value is assigned a unique index number.
- The hash function plays a crucial role in generating these unique index numbers.
-
Hash Tables:
- Hash tables are arrays that use hash functions to generate unique index numbers for efficient storage and retrieval of data.
- The unique index numbers are crucial for quick searches and insertions, regardless of the table's size.
-
Hash Function:
- The hash function converts data into a small integer or hash value.
- It must meet certain criteria, such as being easy to compute, avoiding clustering, and preventing collisions (two items mapped to the same hash value).
- Hash functions contribute to data integrity, as a change in the input data should result in a different hash.
-
Examples of Hashing:
- Real-life examples include assigning unique roll numbers to students in schools and unique numbers to books in a library.
- These examples illustrate how hashing simplifies the process of identifying and retrieving specific items.
-
Collision Resolution Techniques:
- Collisions occur when two keys are assigned the same index in the hash table.
- Various collision resolution techniques are introduced, including open hashing (separate chaining) and closed hashing (open addressing).
- Linear probing is highlighted as an effective method for resolving collisions.
-
Linear Probing:
- Linear probing is a collision resolution technique where the algorithm searches linearly for the next available slot in case of a collision.
- It involves checking consecutive slots until an empty slot is found for insertion.
-
Double Hashing:
- Double hashing employs two hash functions to handle collisions.
- The second hash function comes into play when the first one causes a collision, providing an offset index for storing the value.
-
How Hashing Works:
- Hashing involves mapping strings or numbers to small integer values using a hashing function.
- Hash tables store data in key-value pairs, with the key used as input to the hashing function.
-
Example Illustration:
- A practical example is provided to demonstrate how hashing works in a hash table with a given size.
-
Conclusion:
- The article concludes by summarizing the hashing concepts discussed and emphasizes practical application for reinforcing data structure knowledge.
In conclusion, the article effectively caters to both beginners and those seeking a deeper understanding of hashing in data structures, making it a valuable resource for anyone looking to enhance their knowledge in this domain.