Explained: Understanding HashMaps

Implementation, utility, and intuition

All images are created using DALLE 3.

Here’s an interview hack. If you don’t know how to solve some DSA questions in an optimized way, the answer is probably “HashMap” :P

Jokes aside, HashMap is extensively used to write efficient code. For a long time, I never really understood all the intricacies of it. Here, I documented it all as a single source of reference whenever I needed to use HashMap (or, as it happens these days, prompt AI to use it).

What is a HashMap?

Let’s keep it simple. It’s a structure to store data- a data structure :)

• Purpose: Store and retrieve values based on unique keys.
• Analogous to: Real-world dictionary.
• Here’s everything you can do with it.
  — Put: Insert key-value pair.
  — Get: Retrieve value using a key.
  — Remove: Delete key-value pair.
  — Check: See if the key exists.

In Python, it’s as simple as declaring an empty object. This is also called a dictionary.

my_dictionary = {}

Let’s see how we can perform the various operations discussed.

cat_attributes = {
    'name': 'Whiskers',
    'color': 'black',
    'age': 3,
    'favorite_food': 'tuna'
}

# Adding a new key-value pair
cat_attributes['is_playful'] = True

# Updating an existing key-value pair
cat_attributes['age'] = 4

# Retrieve the value for the key 'color'
cat_color = cat_attributes.get('color', 'Unknown')
print(f"Cat's color: {cat_color}")

# Remove the key 'favorite_food' and its value
cat_attributes.pop('favorite_food', None)

# Check if a key (e.g. 'name') exists in the dictionary
if 'name' in cat_attributes:
    print("The cat's name is known.")
else:
    print("The cat's name is unknown.")

print(cat_attributes)

Cat's color: black
The cat's name is known.
{'name': 'Whiskers', 'color': 'black', 'age': 4, 'is_playful': True}

Notice:

• Age is 4 — updated from 3
• A new key ‘is_playful’ is added.
• The key-value pair for favourte_food is deleted.
• get(), pop(), and if key in dict: are your three operations in use besides directly adding or updating the key-value pairs

In a more real-world sense, you put data into a hashmap, and when you want it back, it’s super efficient. You will probably use one when dealing with caching systems, JSON objects, and databases.

Hashmap Performance

Let’s take a real-world example to understand how we can actually work with hashmaps/dictionaries. Here’s a simple task often used in natural language processing or in bioinformatics: counting the frequency of words/letters in the given text.

In bioinformatics, it’s often important to know how many of each nucleotide (adenine (A), thymine (T), guanine (G), and cytosine (C) are in a DNA sequence. Let’s take a very long DNA sequence and count the same.

The straightforward approach: You loop through the entire text to check for each nucleotide and update the count.

The dictionary approach: You loop just once and update the count for each letter as you encounter it. This is possible because you can keep the keys of the dictionary as the nucleotides themselves and access them efficiently. For example — dict[‘A’].

import timeit
import random

# Function using a list
def nucleotide_count_list(dna_sequence):
    nucleotides = ['A', 'T', 'G', 'C']
    nucleotide_freq = {nucleotide: 0 for nucleotide in nucleotides}
    for nucleotide in dna_sequence:
        if nucleotide in nucleotides:
            nucleotide_freq[nucleotide] += 1
    return nucleotide_freq

# Function using a dictionary
def nucleotide_count_dict(dna_sequence):
    nucleotide_freq = {}
    for nucleotide in dna_sequence:
        if nucleotide in nucleotide_freq:
            nucleotide_freq[nucleotide] += 1
        else:
            nucleotide_freq[nucleotide] = 1
    return nucleotide_freq

# Generating a long DNA sequence
dna_sequence = ''.join(random.choices(['A', 'T', 'G', 'C'], k=1000000))

# Measuring performance
list_time = timeit.timeit(lambda: nucleotide_count_list(dna_sequence), number=100)
dict_time = timeit.timeit(lambda: nucleotide_count_dict(dna_sequence), number=100)

print(f"List-based Method Time: {list_time}")
print(f"Dictionary-based Method Time: {dict_time}")

List-based Method Time: 18.339655203999882
Dictionary-based Method Time: 16.260885261000112

• Dictionary (Hashmap): Provides O(1) average time complexity for lookup, insert, and delete operations.
• List: Offers O(n) time complexity for searching an element where n is the length of the list.

In practical terms, you’ll find that for large datasets, dictionaries are significantly faster than lists when it comes to finding an element.

Intuition

Whenever you have lots of data where you want to find something, go with hashmaps.

How to Iterate Through a Hashmap?

cat_attributes = {
    'name': 'Whiskers',
    'color': 'black',
    'age': 3,
    'favorite_food': 'tuna',
    'is_playful': True
}

# Iterating through the dictionary
for key, value in cat_attributes.items():
    print(f"The cat's {attribute} is {value}.")

The cat's name is Whiskers.
The cat's color is black.
The cat's age is 3.
The cat's favorite_food is tuna.
The cat's is_playful is True.

Real-World Scenarios

1. User Profiles in a Social Media Application: User profiles can be stored in hashmaps, with keys as attributes (like username, email, age, etc.) and values as the corresponding information. Iterating through a hashmap is useful for displaying user profile information or for performing batch updates.
2. Inventory System in Retail or Warehousing: A hashmap could be used to store product information, with product IDs as keys and details like stock quantity, price, and description as values. Iterating through the hashmap would enable tasks like generating inventory reports, updating prices, or checking stock levels.

How to Convert a Hashmap to Lists?

cat_attributes = {
    'name': 'Whiskers',
    'color': 'black',
    'age': 3,
    'favorite_food': 'tuna',
    'is_playful': True
}

# Converting to lists
keys_list = list(cat_attributes.keys())  # List of keys
values_list = list(cat_attributes.values())  # List of values
items_list = list(cat_attributes.items())  # List of key-value pairs (tuples)

print("Keys:", keys_list)
print("Values:", values_list)
print("Items:", items_list)

Keys: ['name', 'color', 'age', 'favorite_food', 'is_playful']
Values: ['Whiskers', 'black', 3, 'tuna', True]
Items: [('name', 'Whiskers'), ('color', 'black'), ('age', 3), ('favorite_food', 'tuna'), ('is_playful', True)]

There are times when you just want the list of keys or values. You can easily get them with the respective inbuilt methods.

Real-World Scenario

In data science, it’s common to store and manipulate data in dictionaries, especially when working with JSON-like structures. However, for analysis and visualization, this data needs to be converted into lists.

For instance, if you have a dictionary storing daily sales data with dates as keys and sales figures as values, you can convert this dictionary into two lists: one for dates and one for sales. These lists can then be easily used with libraries like matplotlib or pandas for plotting time series graphs or for further statistical analysis.

In such a scenario, converting a hashmap (dictionary) to an array list (or lists) allows for greater flexibility in data manipulation and analysis, especially in Python, where lists are a commonly used data structure for these purposes.

How to Convert Hashmap to JSON (and Vice-Versa)?

import json

cat_attributes = {
    'name': 'Whiskers',
    'color': 'black',
    'age': 3,
    'favorite_food': 'tuna',
    'is_playful': True
}

# Converting dictionary to JSON
cat_json = json.dumps(cat_attributes)
print("Dictionary to JSON:", cat_json)

Dictionary to JSON: {"name": "Whiskers", "color": "black", "age": 3, "favorite_food": "tuna", "is_playful": true}

In this example, json.dumps() is used to convert the dictionary cat_attributes into a JSON-formatted string.

# Converting JSON back to dictionary
cat_dict = json.loads(cat_json)
print("JSON to Dictionary:", cat_dict)

JSON to Dictionary: {'name': 'Whiskers', 'color': 'black', 'age': 3, 'favorite_food': 'tuna', 'is_playful': True}

Here, json.loads() is used to convert the JSON string cat_json back into a Python dictionary.

Real-World Scenarios

1. Web Development (APIs): In web development, especially in APIs (Application Programming Interfaces), data is commonly sent and received in JSON format. When receiving data, JSON is converted into a hashmap (dictionary) for easy manipulation and processing within the code. When sending data, the server typically converts hashmaps (dictionaries) into JSON before transmitting to the client.
2. Configuration Files: In many applications, configuration settings are stored in JSON files. When the application runs, these JSON files are read and converted into hashmaps (dictionaries) for internal use, allowing for more accessible configuration management.
3. Data Storage and Retrieval: In applications dealing with databases or data storage, JSON serves as a standard format for exchanging data. Data is often stored in a JSON-like format and, upon retrieval, is converted into hashmaps for further processing and manipulation.

Note that some frameworks can automatically do this conversion for you. While a dictionary and a JSON string might appear similar when printed (but not the same as JSON uses double quotes), they are fundamentally different, especially in the context of data interchange.

Hashmap Javascript Examples

// Creating a HashMap (Dictionary)
let catAttributes = {
    'name': 'Whiskers',
    'color': 'black',
    'age': 3,
    'favoriteFood': 'tuna'
};

// Adding a new key-value pair
catAttributes['isPlayful'] = true;

// Updating an existing key-value pair
catAttributes['age'] = 4;

// Retrieving a Value
let catColor = catAttributes['color'] || 'Unknown';
console.log(`Cat's color: ${catColor}`);

// Removing a Key-Value Pair
delete catAttributes['favoriteFood'];

// Checking if a Key Exists
if ('name' in catAttributes) {
    console.log("The cat's name is known.");
} else {
    console.log("The cat's name is unknown.");
}

// Iterating Through a HashMap
for (let attribute in catAttributes) {
    if (catAttributes.hasOwnProperty(attribute)) {
        console.log(`The cat's ${attribute} is ${catAttributes[attribute]}.`);
    }
}

// Converting a HashMap to Lists
let keysList = Object.keys(catAttributes); // List of keys
let valuesList = Object.values(catAttributes); // List of values
let itemsList = Object.entries(catAttributes); // List of key-value pairs

console.log("Keys:", keysList);
console.log("Values:", valuesList);
console.log("Items:", itemsList);

// Converting HashMap to JSON (and Vice-Versa)
// Converting dictionary to JSON
let catJson = JSON.stringify(catAttributes);
console.log("Dictionary to JSON:", catJson);

// Converting JSON back to dictionary
let catDict = JSON.parse(catJson);
console.log("JSON to Dictionary:", catDict);

Data Structures and Algorithms Interview Questions where Hashmaps (Dictionaries) are Used

Below are some basic intuitions for approaching a few common problems using a hashmap. See if you can solve them on Leetocode with the same.

1. First Unique Character in a String
   Store the count of each letter in a dictionary and then iterate that to check for the required condition (count == 1).
2. Group Anagrams
   Iterate the given array and use a dictionary to store the anagrams as a list of values under the common key. All anagrams, when sorted, give the same string, which can be used as the key.
3. Two Sum Problem
   Iterate the given array, and at each iteration, find the remaining, target — value. Use a dictionary to store the value and index as key: value pairs for every item you visit in the array. If the remaining value is already visited, then that's your answer.
4. Longest Substring Without Repeating Characters
   Iterate the given string. Use a dictionary to store the last seen character and its index. If the given character is already last seen, it implies that you have reached a repeating character. Here, compute your string length so far and compare it with the max length. Also, update your starting index for the next substring from there on.
5. Intersection of Two Arrays
   Iterate through the first array. Check if the value exists in the second array. If yes, store it in a dictionary. In the end, return dictionary.keys().

(Note that all the above problems can be solved in multiple other ways)

Distlling on some patterns on how hashmaps are used

1. To keep track of the count of different items as we iterate over an array.
2. To group items satisfying a common condition while we iterate over an array.
3. To store the item and its index as the key-value pair while we iterate over an array. This type of usage comes up when we want to use a dictionary to remember the last seen or already visited elements.

Phew! That’s about it for this article. Until next time.