The Importance of Hash Maps
Hash maps can solve a whole bunch of different problems
Hashing is a traditional approach in computer science whereby data structures called hash maps are used to store key-value pairs. Apart from storing key-value pairs, hash maps can be used to solve a wide variety of problems in computer science. When used with priority queues and other container adapters like stacks and queues, hash maps can make problem-solving faster by reducing the running time complexity.
Let’s dive into the basic concept of hash maps, their usage in C++, and applications to some of the most important problems.
The Concept Behind Hash Maps
Hash maps generally store elements as key-value pairs. Consider this example: We want to store a list of grocery items with their prices into hash maps. The name of the item serves as a key and its price is the value. This key-value pair is stored into a hash map, as shown below:
The order of storing the key-value is not guaranteed in an Unordered Hash Map (also called an Unordered Map). When we insert an item into an Unordered Hash Map, it can reside at any position in the Map object. If we want strict ordering of items in ascending order of their keys, we can use an Ordered Hash Map or simply Maps. For the same example as above, this is how the items are stored in Maps:
The keys are sorted in lexicographic order starting with the smallest letter, c. When a new item like Juice with a price of $12 needs to be added to Maps, it is inserted at position 3 after Chocolate to maintain the lexicographic order.
Coding Hash Maps
Unordered maps and Maps are part of Standard Template Libraries(STL) in C++. To declare Maps and Unordered Maps, run the following:
map<key_type, value_type>mp;unordered_map<key_type, value_type>unmp;
key_type and value_type can be of standard data types such as int, float, char, pair, etc.
Most of the member functions are common for unordered_map and map object. So let’s look at some of these functions.
1. Inserting an item into a hash map
To insert an item into unordered_map or map, run this:
mp.insert(pair<key_name, value>);key_name and value are the item name and value to be inserted in map, respectively. In the example above, we have Carrots as the key_name and $2 as the value. We can also insert the item using the assignment operator:
mp["Carrots"] = 2;2. Delete an item from a hash map
To delete an item from a hash map, we use the erase function:
mp.erase(mp.begin()); //Delete an item at startmp.erase("Carrots"); //Delete an item with key "Carrots"mp.erase(mp.begin(), mp.end()); //Delete all items in the map
3. Find an item in a hash map
To find an item in a hash map, we use the find function:
const_iterator itr = mp.find("Carrots");If Carrots is found in the map, then itr contains the iterator to the element in the hash map. If the specified key is not found, itr contains the value of unordered_map::end.
4. Other hash map functions
Here are some of the other common functions used in hash maps:
value = mp.at("Carrots"); //Returns the value at key cnt = mp.count("Carrots"); //Returns the total number of carrotis_empty = mp.empty(); //Returns if the Hash Map is Emptytotal_size = mp.size(); //Returns the total number of items
Applications of Hash Maps
One of the biggest advantages of using hash maps is that they provide a constant time of O(1) for search, insert, and delete operations. This makes them more suitable for problems related to finding duplicates, finding the frequency of items, and finding distinct elements.
1. Problems related to item frequency
Hash maps are useful for solving most problems related to item frequency. An example of such a problem is finding common characters in a list of strings. If an item appears twice in all strings, it needs to be included twice in the output:
Input: ["bella","label","roller"]
Output: ["e","l","l"]To solve this problem, we can use two for loops to compare one string with a list of other strings. But the time complexity of such an approach is O(n²). To minimize the time complexity, we can use a hash map to store the characters as keys with the string number and frequency as a pair for value. We can then iterate the hash map to check for common characters found in all strings along with their frequency. This reduces the time complexity to O(n).
2. Dictionary
A dictionary is another common example where hash maps are used more frequently. If we were to make an online portal for searching the meaning of a word, we would be building a dictionary in the back end to store the word along with its meaning. When a user searches for a word, it uses the find hash function to retrieve its meaning.
3. File systems
Hash maps are used to link the file name with the path of the file. To store the correspondence between the file name and path and the physical location of that file on the disk, the system uses a map. That map is usually implemented as a hash table.
4. Password verification
Consider a web application that allows user login and authentication when a user enters their username and password. In most modern systems, the username and password are not sent as plain text to the back-end server for authentication. Instead, they are encoded as a hash value and sent to the server. The server then checks the received hash value with the stored hash value. If there is a match, the user is allowed to log in. Special cryptographic functions are used for this purpose, so the user is secure.
5. Storage optimization in the cloud
Dropbox uses hash tables for storage optimization in the cloud. Suppose there are multiple users who upload the same video to their Dropbox accounts. Since storing multiple copies of the same video will consume too much storage, Dropbox stores a single copy of the file with the link provided to each user for access. When a new user uploads the same file, Dropbox computes the hash value for the file. If it matches the value stored in the hash table, the user is returned the link to the file.
6. Compiler operation
To identify the keywords in a programming language, the compiler stores them in a hash table. The compiler then checks the program with the hash table to verify if the program syntax is correct.
Conclusion
These are just a few applications using hash maps. Hash maps serve as one of the most important tools that every developer needs to know. This makes problem-solving faster and easy — especially problems dealing with item frequency.
