HashMap Implementation from Scratch in DSA Javascript - Deep Dive

Overview - HashMap Implementation from Scratch

What is it?

A HashMap is a way to store pairs of keys and values so you can find the value quickly using the key. It works by turning the key into a number called a hash, which tells where to put the value inside a list. This lets you add, find, or remove items fast without looking through everything. HashMaps are used everywhere, like in phonebooks or dictionaries, to find information quickly.

Why it matters

Without HashMaps, finding a value by its key would mean checking every item one by one, which takes a lot of time as the list grows. HashMaps solve this by using a clever trick to jump directly to the right spot. This makes programs faster and more efficient, especially when handling lots of data like user accounts, settings, or caches.

Where it fits

Before learning HashMaps, you should understand arrays and basic programming concepts like functions and loops. After mastering HashMaps, you can explore more complex data structures like Trees, Graphs, and advanced hashing techniques. HashMaps are a foundation for many algorithms and systems that need quick data lookup.

Mental Model

Core Idea

A HashMap uses a key's special number (hash) to quickly find where its value lives in a list, avoiding slow searches.

Think of it like...

Imagine a library where each book has a unique code. Instead of searching every shelf, you use the code to go straight to the exact shelf and spot where the book is placed.

HashMap Structure:

[ Array of Buckets ]
  ├─ Bucket 0: [(key1, value1), (key2, value2)]
  ├─ Bucket 1: []
  ├─ Bucket 2: [(key3, value3)]
  └─ Bucket N: []

Key -> Hash Function -> Bucket Index -> Search in Bucket

Build-Up - 7 Steps

1

Foundation

Understanding Key-Value Storage

Concept: Learn what key-value pairs are and why they are useful for storing data.

A key-value pair is like a label and its content. For example, a person's name (key) and their phone number (value). We want to store many pairs and find the value quickly by using the key.

Result

You understand that data can be stored as pairs and that keys help find values.

Knowing that data can be paired as keys and values is the base for all fast lookup systems.

2

Foundation

Basics of Arrays and Indexing

Concept: Learn how arrays store items in order and how indexing works.

An array is a list where each item has a position number called an index. You can get any item fast if you know its index. But arrays don't help if you only know a key, not the index.

Result

You see that arrays are fast for position-based access but not for key-based access.

Understanding arrays helps grasp why we need a way to convert keys into indexes.

3

Intermediate

Hash Function and Index Calculation

🤔Before reading on: do you think a hash function always gives a unique number for every key? Commit to yes or no.

Concept: Learn how a hash function turns keys into numbers to find array positions.

A hash function takes a key (like a string) and returns a number. We then use this number to find an index in the array by using the remainder operation (modulus) with the array size. This maps keys to array positions.

Result

You can convert any key into an array index using a hash function and modulus.

Knowing how keys become indexes is crucial to fast data access in HashMaps.

4

Intermediate

Handling Collisions with Buckets

🤔Before reading on: do you think two different keys can have the same hash index? Commit to yes or no.

Concept: Learn that different keys can map to the same index and how to store multiple pairs there.

Sometimes, two keys produce the same index. This is called a collision. To handle this, each array position holds a list (bucket) of key-value pairs. When adding or searching, we check this list for the right key.

Result

You understand how collisions are handled by storing multiple pairs in one bucket.

Handling collisions correctly ensures the HashMap works reliably even when keys clash.

5

Intermediate

Implementing Basic HashMap Methods

🤔Before reading on: do you think adding a key that already exists should overwrite or ignore? Commit to overwrite or ignore.

Concept: Learn how to add, get, and remove key-value pairs in the HashMap.

We write three main methods: - add(key, value): compute index, check bucket, update if key exists, else add. - get(key): compute index, search bucket for key, return value or null. - remove(key): compute index, find key in bucket, remove pair if found.

Result

You can create a working HashMap that stores and retrieves data by keys.

Implementing these methods shows how the HashMap operates step-by-step.

6

Advanced

Resizing and Load Factor Management

🤔Before reading on: do you think a HashMap should grow when it gets full or stay the same size? Commit to grow or stay same.

Concept: Learn why and how to resize the HashMap to keep operations fast.

As more pairs are added, buckets get longer, slowing down searches. To fix this, we track the load factor (items/array size). When it passes a threshold (like 0.7), we create a bigger array and rehash all pairs into it. This keeps lookups fast.

Result

You understand how resizing keeps the HashMap efficient as it grows.

Knowing when and how to resize prevents performance drops in real use.

7

Expert

Optimizing Hash Functions and Collision Strategies

🤔Before reading on: do you think using a simple sum of character codes is a good hash function? Commit to yes or no.

Concept: Explore better hash functions and alternative collision handling methods.

Simple hash functions like summing character codes cause many collisions. Better ones mix bits to spread keys evenly. Also, besides chaining (buckets), open addressing stores pairs in nearby empty slots. These choices affect speed and memory.

Result

You learn how advanced hashing and collision methods improve HashMap quality.

Understanding these optimizations helps build robust, high-performance HashMaps.

Under the Hood

Internally, a HashMap uses an array where each position can hold multiple key-value pairs in a bucket. The key is passed through a hash function to produce a number, which is then converted to an array index using modulus. When collisions happen, pairs are stored in the bucket list. On resizing, all pairs are rehashed into a larger array to reduce collisions and maintain speed.

Why designed this way?

HashMaps were designed to provide average constant-time operations for insertions, lookups, and deletions. Using a hash function to convert keys to indexes avoids slow linear searches. Buckets handle collisions simply and flexibly. Resizing balances memory use and speed. Alternatives like trees or linked lists were slower or more complex.

HashMap Internal Flow:

Key -> [Hash Function] -> Hash Number -> [Modulus with Array Size] -> Index

Array:
┌─────────────┬─────────────┬─────────────┬─────────────┐
│ Bucket 0    │ Bucket 1    │ Bucket 2    │ ...         │
│ [(k,v),(k,v)]│ []          │ [(k,v)]     │             │
└─────────────┴─────────────┴─────────────┴─────────────┘

On collision:
Bucket (list) stores multiple pairs

On resize:
Create bigger array -> Rehash all pairs -> Redistribute

Myth Busters - 4 Common Misconceptions

Quick: Do you think a hash function guarantees unique indexes for different keys? Commit to yes or no.

Common Belief: A hash function always gives a unique index for each key, so collisions never happen.

Reality: Hash functions can produce the same index for different keys, causing collisions that must be handled.

Why it matters: Ignoring collisions leads to lost or overwritten data, breaking the HashMap's correctness.

Quick: Do you think resizing a HashMap is optional and does not affect performance? Commit to yes or no.

Common Belief: Once created, a HashMap's size never needs to change; resizing is unnecessary.

Reality: Resizing is essential to keep operations fast as more items are added; without it, performance degrades.

Why it matters: Not resizing causes buckets to grow large, making lookups slow and defeating the purpose of a HashMap.

Quick: Do you think keys must be strings only in a HashMap? Commit to yes or no.

Common Belief: HashMaps only work with string keys because hashing other types is impossible.

Reality: HashMaps can use many types as keys if a proper hash function exists; strings are common but not required.

Why it matters: Believing keys must be strings limits the use of HashMaps in many practical cases like numbers or objects.

Quick: Do you think adding a key that already exists should create a duplicate entry? Commit to yes or no.

Common Belief: Adding a key that already exists adds another pair, allowing duplicates.

Reality: Adding an existing key updates its value to avoid duplicates and keep data consistent.

Why it matters: Allowing duplicates causes confusion and incorrect data retrieval.

Expert Zone

1

The quality of the hash function dramatically affects performance; subtle biases cause clustering and slowdowns.

2

Choosing between chaining and open addressing depends on memory constraints and expected load factors.

3

Resizing is costly but amortized; understanding this helps optimize when and how to resize in production.

When NOT to use

HashMaps are not ideal when order matters (use linked lists or trees) or when keys are complex objects without stable hashes. For small datasets, simple arrays or lists may be faster. For concurrent access, specialized thread-safe maps or lock-free structures are better.

Production Patterns

In real systems, HashMaps are used for caches, symbol tables, and indexing. They often include custom hash functions for domain-specific keys and use dynamic resizing with load factor tuning. Collision handling may combine chaining with balanced trees for worst-case guarantees.

Connections

Arrays

HashMaps build on arrays by using them as storage indexed by hashes.

Understanding arrays is key to grasping how HashMaps achieve fast access through indexing.

Cryptographic Hash Functions

Both use hashing but for different goals: HashMaps for speed and distribution, cryptography for security.

Knowing cryptographic hashes highlights the difference between secure and fast hash functions in HashMaps.

Human Memory Recall

HashMaps mimic how humans recall information by associating keys (cues) with values (memories) quickly.

This connection shows how computer structures model natural processes to optimize retrieval.

Common Pitfalls

#1 Ignoring collisions and storing only one pair per index.

Wrong approach:

class HashMap {
constructor(size) {
this.size = size;
this.buckets = new Array(size);
}
hash(key) {
let hash = 0;
for (let char of key) {
hash += char.charCodeAt(0);
}
return hash % this.size;
}
add(key, value) {
const index = this.hash(key);
this.buckets[index] = [key, value]; // overwrites existing
}
get(key) {
const index = this.hash(key);
if (this.buckets[index] && this.buckets[index][0] === key) {
return this.buckets[index][1];
}
return null;
}
}

Correct approach:

class HashMap {
constructor(size) {
this.size = size;
this.buckets = new Array(size).fill(null).map(() => []);
}
hash(key) {
let hash = 0;
for (let char of key) {
hash += char.charCodeAt(0);
}
return hash % this.size;
}
add(key, value) {
const index = this.hash(key);
const bucket = this.buckets[index];
for (let i = 0; i < bucket.length; i++) {
if (bucket[i][0] === key) {
bucket[i][1] = value;
return;
}
}
bucket.push([key, value]);
}
get(key) {
const index = this.hash(key);
const bucket = this.buckets[index];
for (let [k, v] of bucket) {
if (k === key) return v;
}
return null;
}
}

Root cause:

Not handling collisions causes data loss when keys share the same index.

#2 Not resizing the HashMap as it grows.

Wrong approach:

class HashMap {
constructor(size) {
this.size = size;
this.buckets = new Array(size).fill(null).map(() => []);
this.count = 0;
}
add(key, value) {
const index = this.hash(key);
this.buckets[index].push([key, value]);
this.count++;
// No resizing logic
}
}

Correct approach:

class HashMap {
constructor(size) {
this.size = size;
this.buckets = new Array(size).fill(null).map(() => []);
this.count = 0;
}
add(key, value) {
const index = this.hash(key);
const bucket = this.buckets[index];
for (let i = 0; i < bucket.length; i++) {
if (bucket[i][0] === key) {
bucket[i][1] = value;
return;
}
}
bucket.push([key, value]);
this.count++;
if (this.count / this.size > 0.7) {
this.resize();
}
}
resize() {
const oldBuckets = this.buckets;
this.size *= 2;
this.buckets = new Array(this.size).fill(null).map(() => []);
this.count = 0;
for (const bucket of oldBuckets) {
for (const [key, value] of bucket) {
this.add(key, value);
}
}
}
}

Root cause:

Ignoring resizing causes buckets to grow large, slowing down operations.

#3 Adding duplicate keys without updating existing values.

Wrong approach:

add(key, value) {
const index = this.hash(key);
this.buckets[index].push([key, value]); // blindly adds duplicates
}

Correct approach:

add(key, value) {
const index = this.hash(key);
const bucket = this.buckets[index];
for (let i = 0; i < bucket.length; i++) {
if (bucket[i][0] === key) {
bucket[i][1] = value; // update existing
return;
}
}
bucket.push([key, value]);
}

Root cause:

Not checking for existing keys causes duplicates and inconsistent data.

Key Takeaways

HashMaps store data as key-value pairs and use a hash function to find values quickly by keys.

Collisions happen when different keys map to the same index, and they must be handled with buckets or other methods.

Resizing the HashMap when it gets full keeps operations fast by reducing collisions.

A good hash function spreads keys evenly to avoid clustering and slowdowns.

Implementing add, get, and remove methods correctly ensures the HashMap works reliably.

Practice

1. What is the main purpose of a HashMap in data structures?

easy

A. To store data in a sorted order

B. To store data as a sequence of elements

C. To store data in a last-in-first-out order

D. To store key-value pairs for fast data retrieval

Solution

1. Step 1: Understand what a HashMap stores

   A HashMap stores data as key-value pairs, allowing quick access to values using keys.

2. Step 2: Compare with other data structures

   Unlike lists or stacks, HashMaps focus on fast lookup, not order or sequence.

3. Final Answer:

   To store key-value pairs for fast data retrieval -> Option D

4. Quick Check:

   HashMap = key-value fast access [OK]

Hint: HashMaps store pairs for quick lookup by key [OK]

Common Mistakes:

• Confusing HashMap with list or stack
• Thinking HashMap stores data in order
• Assuming HashMap stores only values without keys

2. Which of the following is the correct way to define a simple HashMap class constructor in JavaScript?

easy

A. class HashMap { constructor() { this.map = {}; } }

B. class HashMap { constructor() { map = []; } }

C. function HashMap() { this.map = new Map(); }

D. class HashMap { constructor() { this.map = null; } }

Solution

1. Step 1: Check class syntax and property initialization

   class HashMap { constructor() { this.map = {}; } } correctly defines a class with a constructor initializing an object property this.map.

2. Step 2: Identify errors in other options

   class HashMap { constructor() { map = []; } } misses this., so map is not a property. function HashMap() { this.map = new Map(); } uses function syntax, not class. class HashMap { constructor() { this.map = null; } } initializes this.map to null, which is not useful for storing pairs.

3. Final Answer:

   class HashMap { constructor() { this.map = {}; } } -> Option A

4. Quick Check:

   Proper class constructor uses this.property = value [OK]

Hint: Use this.property inside constructor for class fields [OK]

Common Mistakes:

• Forgetting 'this.' before property name
• Mixing function and class syntax
• Initializing property to null instead of object

3. Consider this simple HashMap implementation snippet:

class HashMap {
  constructor() {
    this.map = {};
  }
  set(key, value) {
    this.map[key] = value;
  }
  get(key) {
    return this.map[key] || null;
  }
}

const h = new HashMap();
h.set('a', 1);
h.set('b', 2);
h.set('a', 3);
console.log(h.get('a'));

What will be printed?

medium

A. 3

B. 2

C. 1

D. null

Solution

1. Step 1: Trace the set operations

   First, key 'a' is set to 1, then 'b' to 2, then 'a' is updated to 3, overwriting previous value.

2. Step 2: Check the get operation

   Calling get('a') returns the current value for 'a', which is 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Last set value for 'a' = 3 [OK]

Hint: Last set value for a key overwrites previous [OK]

Common Mistakes:

• Assuming first set value remains
• Confusing keys and values
• Expecting null if key was set before

4. The following HashMap method is intended to remove a key-value pair but has a bug:

remove(key) {
  delete this.map.key;
}

What is the correct fix?

medium

A. Change to delete this.map->key;

B. Change to this.map.delete(key);

C. Change to delete this.map[key];

D. Change to this.map.remove(key);

Solution

1. Step 1: Understand property access in JavaScript objects

   Using dot notation with this.map.key looks for property literally named 'key', not the variable key.

2. Step 2: Use bracket notation for dynamic keys

   Bracket notation this.map[key] accesses the property named by the variable key. So delete this.map[key]; correctly deletes the key-value pair.

3. Final Answer:

   Change to delete this.map[key]; -> Option C

4. Quick Check:

   Use brackets for variable keys [OK]

Hint: Use brackets [] to delete dynamic keys [OK]

Common Mistakes:

• Using dot notation with variable keys
• Using non-existent methods like remove()
• Using wrong delete syntax

5. You want to implement a keys() method in your HashMap class that returns all keys stored. Which of these implementations correctly returns an array of keys?

hard

A. keys() { return Object.values(this.map); }

B. keys() { return Object.keys(this.map); }

C. keys() { return this.map.keys(); }

D. keys() { return this.map.getKeys(); }

Solution

1. Step 1: Identify how to get keys from a plain object

   JavaScript's Object.keys() returns an array of keys from an object.

2. Step 2: Check other options for correctness

   keys() { return this.map.keys(); } assumes this.map is a Map object, but here it's a plain object, so this.map.keys() is undefined. keys() { return Object.values(this.map); } returns values, not keys. keys() { return this.map.getKeys(); } uses a non-existent method.

3. Final Answer:

   keys() { return Object.keys(this.map); } -> Option B

4. Quick Check:

   Object.keys() returns keys array [OK]

Hint: Use Object.keys() to get keys from plain objects [OK]

Common Mistakes:

• Using Map methods on plain objects
• Returning values instead of keys
• Calling non-existent methods