Applications of Hash Table
Hashing is a way to store data into some data structure (generally Hash Table is used) in such a way that the basic operations on that data i.e. the insertion, deletion, and searching can be performed in O(1) time. It is one of the most important concepts that every programmer and developer should know because it optimizes your code to a great extent. In this blog, we will know some of the applications on the Hash Table. So let’s get started!
Hashing is used for the implementation of programming languages, file systems, pattern search, distributed key-value storage, cryptography, etc. There are a lot of examples where the concept of hashing is used.
So let’s check out some of them in detail:
A message digest is a cryptographic hash function containing a string of digits created by a one-way hashing formula. Message digests are designed to protect the integrity of a piece of data or media to detect changes and alterations to any part of a message.
For Example: Suppose you want to store a file in any of the open cloud spaces, but you don’t want anyone to temper your file. If anyone tempered or modified your file, you should know that. This problem is solved using the Message Digest. The Message Digest computes a hash value with respect to your file and you can store that hash value in your local. Now if you download your file from the cloud then you can check it with your hash. If it is modified the hash will not match.
The hashing is used for the linking of the file name to the path of the file. When you interact with a file system as a user, you see the file name, maybe the path to the file. But to actually store the correspondence between the file name and path, and the physical location of that file on the disk, the System uses a map, and that map is usually implemented as a hash table.
When you use some web service and enter your credentials to log in, it won’t send your password in plain-text through the network to the server to verify if the credentials are correct or not, because in that case message could be intercepted and then someone will know your password. Instead, a hash value of your password is computed on the client-side and then sent to the server which then compares that hash value with the hash value of the stored password. And if those are equal, you get authenticated. Special cryptographic hash functions are used for this purpose. It means that it is next to impossible to find another string that has the same hash value as your password. So you are secure. Nobody can actually construct a different string that has the same hash value as your password and then log in to your system, even if he intercepted the message with the hash value of your password going to the server.
The hashing is also used to search for patterns in the strings. One of the famous algorithms that use hashing for the searching of a pattern in a string is Rabin-Karp Algorithm. The pattern matching is also used to detect plagiarism.
In most of the programming languages, there are built-in data types or data structures in the standard library that are based on hash tables. For example, dict or dictionary in Python, or HashMap in Java.
For identifying the keywords in the programming languages, the compiler uses the hash table to store these keywords and other identifiers to compile the program.
Suggested Problems to solve in Hashing
- Check if two arrays are equal or not
- The intersection of two unsorted array
- Longest Consecutive Sequence
- Valid Anagram
- Majority Element
- Sort characters by frequency
- Triplet with 0 sum
- First missing positive
- Largest subarray with 0 sum
- Max points on the straight line
Happy Learning, Enjoy Algorithms!