HashMap Data Structure Explained

What Is a HashMap?

A HashMap is a data structure that stores information as key-value pairs. Instead of locating an element by its numeric position, a HashMap uses a key to determine where the associated value should be stored.

For example, an application may store a user's details using an email address as the key:

{
  "john@example.com": "John",
  "maya@example.com": "Maya",
  "alex@example.com": "Alex"
}

When the application needs John's information, it can provide the key john@example.com instead of searching through every user.

How a HashMap Works

A HashMap typically uses a hash function to convert a key into a numeric hash value. That hash value is then mapped to a bucket or storage position.

For example, suppose a HashMap has 10 buckets. A simplified implementation could calculate an index using:

index = hash(key) % 10;

Real HashMap implementations use more sophisticated hashing and resizing strategies, but the basic idea is the same: transform the key into a location that allows efficient access.

Key-Value Pairs

Every entry in a HashMap consists of two logical parts:

• Key: Identifies the entry.
• Value: The data associated with the key.

const users = new Map();

users.set("user101", "John");
users.set("user102", "Maya");

console.log(users.get("user101"));
// John

Keys are normally unique. If the same key is inserted again, the associated value is replaced or updated.

const users = new Map();

users.set("user101", "John");
users.set("user101", "Jonathan");

console.log(users.get("user101"));
// Jonathan

HashMap Operations

The most common HashMap operations are insertion, lookup, update, and deletion.

1. Insert a Key-Value Pair

const scores = new Map();

scores.set("Alice", 85);
scores.set("Bob", 92);

console.log(scores);

2. Retrieve a Value

console.log(scores.get("Alice"));
// 85

3. Check Whether a Key Exists

console.log(scores.has("Bob"));
// true

console.log(scores.has("David"));
// false

4. Update a Value

scores.set("Alice", 95);

console.log(scores.get("Alice"));
// 95

5. Delete an Entry

scores.delete("Bob");

console.log(scores.has("Bob"));
// false

6. Get the Number of Entries

console.log(scores.size);

7. Remove All Entries

scores.clear();

console.log(scores.size);
// 0

HashMap in JavaScript

JavaScript does not provide a class named HashMap. The Map object is the standard key-value collection and is commonly used when HashMap-style behavior is required.

const products = new Map([
  ["P100", "Laptop"],
  ["P101", "Keyboard"],
  ["P102", "Mouse"]
]);

console.log(products.get("P101"));
// Keyboard

JavaScript objects can also store key-value data, but Map provides collection-specific operations such as set(), get(), has(), delete(), and size.

Iterating Through a HashMap

A HashMap can be traversed to process its keys and values. With JavaScript's Map, the for...of loop can access each key-value pair.

const employees = new Map([
  ["E101", "John"],
  ["E102", "Maya"],
  ["E103", "Alex"]
]);

for (const [id, name] of employees) {
  console.log(id, name);
}

You can also iterate over keys or values separately.

for (const id of employees.keys()) {
  console.log(id);
}

for (const name of employees.values()) {
  console.log(name);
}

HashMap and Collisions

A hash collision occurs when two different keys produce the same bucket index.

For example, if a simplified hash function produces:

hash("Alice") % 10 = 4
hash("David") % 10 = 4

Both keys map to bucket 4. A HashMap must therefore have a collision-resolution strategy.

Separate Chaining

With separate chaining, each bucket can contain multiple entries. A linked list, dynamic array, or another structure can store entries that map to the same bucket.

Bucket 0 → [key1, value1]
Bucket 1 → empty
Bucket 2 → [key2, value2] → [key3, value3]
Bucket 3 → empty

Open Addressing

With open addressing, all entries are stored inside the main table. If the calculated position is occupied, another position is searched using a probing strategy.

Common probing techniques include:

• Linear probing
• Quadratic probing
• Double hashing

Load Factor

The load factor describes how full a hash table is.

Load Factor = Number of Entries / Number of Buckets

A high load factor can increase collisions and reduce performance. Hash table implementations can therefore resize the table and redistribute entries when the load factor reaches a chosen threshold.

Rehashing

Rehashing occurs when a hash table grows and needs a larger internal table. Existing entries are processed again so that their positions can be calculated using the new table size.

A simplified resizing process looks like this:

1. Create a larger bucket array.
2. Process the existing entries.
3. Calculate their new bucket positions.
4. Insert the entries into the new table.

HashMap Time Complexity

HashMap operations are generally designed to provide constant-time average performance. The exact behavior depends on the hash function, collision strategy, load factor, and implementation.

The worst case can occur when many keys map to the same location and collision resolution requires examining many entries.

HashMap for Frequency Counting

One of the most common HashMap patterns is counting how frequently values appear. This pattern is useful in coding problems, analytics, validation, and application logic.

const numbers = [2, 4, 2, 7, 4, 2, 9];

const frequency = new Map();

for (const number of numbers) {
  frequency.set(
    number,
    (frequency.get(number) ?? 0) + 1
  );
}

console.log(frequency);
// Map(4) { 2 => 3, 4 => 2, 7 => 1, 9 => 1 }

The key represents the item being counted, while the value represents its frequency.

HashMap for Fast User Lookup

Consider an application that repeatedly needs to retrieve users by their unique ID. A HashMap can associate each ID with the corresponding user object.

const users = new Map([
  [
    "u101",
    { name: "John", role: "Developer" }
  ],
  [
    "u102",
    { name: "Maya", role: "Designer" }
  ]
]);

const user = users.get("u102");

console.log(user?.name);
// Maya

console.log(user?.role);
// Designer

This approach is useful when the lookup key is unique and the application performs many searches.

HashMap vs Array

Arrays and HashMaps solve different access problems. An array is naturally suited to positional access, while a HashMap is designed for key-based lookup.

HashMap vs HashSet

A HashMap stores an association between a key and a value, while a HashSet primarily stores unique values.

• HashMap: key → value.
• HashSet: unique value collection.

const users = new Map();
users.set("u101", "John");

const uniqueUsers = new Set();
uniqueUsers.add("John");
uniqueUsers.add("Maya");

When Should You Use a HashMap?

A HashMap is useful when your problem naturally involves finding information using a key.

• Looking up users by ID.
• Mapping product IDs to product details.
• Counting frequencies.
• Detecting duplicates.
• Storing configuration values.
• Caching computed results.
• Mapping relationships between identifiers and objects.
• Building indexes for fast lookup.

Common HashMap Mistakes

Using a HashMap When Ordering Is the Main Requirement

If the primary requirement is maintaining sorted order, a tree-based structure may be more appropriate depending on the language and implementation.

Assuming Every Operation Is Always O(1)

O(1) is the typical average-case complexity for well-designed hash tables. Collisions, resizing, and implementation details can affect actual performance.

Ignoring Key Equality

Hash-based structures depend on consistent hashing and equality rules. Two logically equivalent keys must be handled consistently by the implementation.

Forgetting That Keys Are Unique

Adding another value using an existing key generally updates the existing mapping rather than creating a second entry with the same key.

HashMap in Coding Interviews

HashMaps appear frequently in coding interview problems because they provide an efficient way to remember information while processing data.

Common problem patterns include:

• Frequency counting.
• Finding duplicate values.
• Two-sum style lookup.
• Grouping values.
• Tracking previously visited elements.
• Finding the first unique element.
• Mapping one value to another.

A Practical HashMap Pattern

Suppose you need to determine whether two numbers add up to a target. Instead of comparing every possible pair, a HashMap can remember values that have already been seen.

function twoSum(numbers, target) {
  const seen = new Map();

  for (let i = 0; i < numbers.length; i++) {
    const complement = target - numbers[i];

    if (seen.has(complement)) {
      return [seen.get(complement), i];
    }

    seen.set(numbers[i], i);
  }

  return [];
}

console.log(twoSum([2, 7, 11, 15], 9));
// [0, 1]

The HashMap stores each number along with its index. When a new number is processed, the algorithm checks whether its required complement has already been seen.

HashMap Complexity Summary

The key idea behind a HashMap is efficient key-based access. A good hash function and effective collision management help keep operations close to constant time on average.

• Average insertion: O(1)
• Average lookup: O(1)
• Average deletion: O(1)
• Worst-case lookup: O(n)
• Worst-case insertion: O(n)
• Typical space complexity: O(n)

Key Takeaways

• A HashMap stores data as key-value pairs.
• A hash function determines where a key should be stored.
• Different keys can produce the same bucket, causing collisions.
• Separate chaining and open addressing are common collision-resolution strategies.
• HashMaps provide O(1) average insertion, lookup, and deletion.
• Resizing and rehashing help control the load factor.
• JavaScript's Map is commonly used for HashMap-style key-value storage.
• HashMaps are especially useful for frequency counting, indexing, caching, and fast lookup.