HashMap Implementation from Scratch in DSA Typescript - Deep Dive

Overview - HashMap Implementation from Scratch

What is it?

A HashMap is a data structure that stores key-value pairs. It allows quick access to values when you know the key. It works by converting keys into numbers called hashes, which help find where the value is stored. This makes searching, adding, and removing items very fast.

Why it matters

Without HashMaps, finding data by key would require checking every item one by one, which is slow. HashMaps solve this by using hashing to jump directly to the data location. This speed is crucial in many apps like databases, caches, and real-time systems where quick data access matters.

Where it fits

Before learning HashMaps, you should understand arrays and basic data storage. After mastering HashMaps, you can explore more complex structures like Trees, Graphs, and advanced hashing techniques.

Mental Model

Core Idea

A HashMap uses a hash function to turn keys into indexes, storing values in buckets for fast lookup.

Think of it like...

Imagine a library where each book has a unique code. Instead of searching every shelf, you use the code to find the exact shelf and spot quickly.

HashMap Structure:

[Key] --hash--> [Index in array]

Array (Buckets):
┌─────┬─────┬─────┬─────┬─────┐
│  0  │  1  │  2  │  3  │  4  │ ...
├─────┼─────┼─────┼─────┼─────┤
│ []  │ []  │ []  │ []  │ []  │
└─────┴─────┴─────┴─────┴─────┘

Each bucket holds key-value pairs that share the same index.

Build-Up - 7 Steps

1

Foundation

Understanding Key-Value Storage

Concept: Learn what key-value pairs are and how they store data.

A key-value pair is like a label and its content. For example, a phonebook entry has a name (key) and a phone number (value). We store data by pairing keys with values so we can find the value by its key.

Result

You understand that data can be stored and retrieved using unique keys.

Knowing key-value pairs is the base for all map-like data structures, including HashMaps.

2

Foundation

Arrays as Storage Buckets

Concept: Use arrays to hold data in fixed positions for quick access.

Arrays store items in order, each with an index number. Accessing an item by index is very fast because the position is known. We will use arrays to hold groups of key-value pairs called buckets.

Result

You see how arrays provide fast access by index, which is key for HashMaps.

Arrays give us a fast way to organize data once we know the right index.

3

Intermediate

Hash Functions for Indexing

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

Concept: A hash function converts keys into array indexes but can produce collisions.

A hash function takes a key (like a string) and returns a number (index). For example, summing character codes and taking remainder by array size. Different keys can produce the same index, causing collisions.

Result

You learn that hashing maps keys to indexes but collisions can happen.

Understanding collisions is crucial because they affect how we store multiple items in the same bucket.

4

Intermediate

Handling Collisions with Chaining

🤔Before reading on: do you think storing multiple items in one bucket is possible? Commit to yes or no.

Concept: Use linked lists or arrays inside buckets to store multiple key-value pairs when collisions occur.

When two keys hash to the same index, we store both in a list inside that bucket. When searching, we check each item in the bucket list for the matching key.

Result

You see how chaining solves collisions by grouping items in buckets.

Knowing chaining prevents data loss and keeps lookup correct despite collisions.

5

Intermediate

Basic HashMap Operations

🤔Before reading on: do you think adding, searching, and deleting in a HashMap take constant time? Commit to yes or no.

Concept: Implement put, get, and remove operations using hashing and chaining.

To add (put), hash the key, find the bucket, and add or update the key-value pair. To get, hash the key, find the bucket, and search for the key. To remove, hash the key, find the bucket, and delete the pair if found.

Result

You can perform main HashMap operations efficiently.

Understanding these operations shows how HashMaps provide fast data access.

6

Advanced

Resizing and Rehashing HashMap

🤔Before reading on: do you think a fixed-size array is enough for all HashMap uses? Commit to yes or no.

Concept: When the HashMap gets full, resize the array and rehash all keys to maintain performance.

If too many items fill the buckets, performance drops. We create a bigger array and move all key-value pairs to new buckets by reapplying the hash function. This keeps operations fast.

Result

You understand how resizing keeps HashMaps efficient as they grow.

Knowing resizing prevents slowdowns and is key for real-world HashMaps.

7

Expert

Choosing and Designing Hash Functions

🤔Before reading on: do you think any hash function works equally well for all data? Commit to yes or no.

Concept: Good hash functions minimize collisions and distribute keys evenly for performance.

A poor hash function causes many collisions, slowing down operations. Experts design hash functions considering key types and distribution. For example, using polynomial rolling hash for strings or bit manipulation for numbers.

Result

You appreciate the importance of hash function quality in HashMap performance.

Understanding hash function design helps avoid subtle bugs and performance issues in production.

Under the Hood

Internally, a HashMap uses an array of buckets. Each key is passed through a hash function to get an index. The bucket at that index holds a list of key-value pairs. When collisions occur, the list grows. Operations like get or put first hash the key, then scan the bucket list to find the exact pair. When the load factor (items/array size) grows too large, the array resizes and all keys are rehashed to new buckets.

Why designed this way?

HashMaps were designed to provide average constant time complexity for key-based operations. Arrays provide fast index access, but keys are not numbers, so hashing converts keys to indexes. Collisions are inevitable, so chaining or open addressing handles them. Resizing balances memory use and speed. This design trades some memory and complexity for speed, which was a big improvement over linear search.

HashMap Internal Structure:

Key --hash--> Index

┌───────────────┐
│   Array       │
│ ┌───────────┐ │
│ │ Bucket 0  │─┼─> [(key1, val1), (key2, val2)]
│ ├───────────┤ │
│ │ Bucket 1  │─┼─> [(key3, val3)]
│ ├───────────┤ │
│ │ Bucket 2  │─┼─> []
│ ├───────────┤ │
│ │ Bucket 3  │─┼─> [(key4, val4)]
│ └───────────┘ │
└───────────────┘

Resize triggers when load factor is high, creating a bigger array and redistributing pairs.

Myth Busters - 4 Common Misconceptions

Quick: do you think HashMaps always store keys in sorted order? Commit to yes or no.

Common Belief: HashMaps keep keys in sorted order for fast retrieval.

Reality: HashMaps do not maintain any order of keys; they focus on fast access by hashing.

Why it matters: Expecting order can cause bugs when iterating keys or values, leading to wrong assumptions about data sequence.

Quick: do you think collisions mean data is lost? Commit to yes or no.

Common Belief: If two keys collide, one value overwrites the other and data is lost.

Reality: Collisions are handled by storing multiple pairs in the same bucket, so no data is lost.

Why it matters: Misunderstanding collisions can cause incorrect implementations that lose data.

Quick: do you think resizing a HashMap happens automatically without cost? Commit to yes or no.

Common Belief: HashMaps resize instantly and without performance impact.

Reality: Resizing is costly because all keys must be rehashed and moved, causing a temporary slowdown.

Why it matters: Ignoring resizing cost can lead to performance issues in time-critical applications.

Quick: do you think any hash function is equally good for all key types? Commit to yes or no.

Common Belief: One hash function works well for all kinds of keys.

Reality: Different key types require different hash functions to minimize collisions and ensure uniform distribution.

Why it matters: Using a poor hash function causes many collisions, slowing down the HashMap.

Expert Zone

1

The choice between chaining and open addressing for collision handling affects memory use and cache performance.

2

Load factor thresholds for resizing balance between memory overhead and operation speed; tuning these is key in production.

3

Hash function quality impacts not only speed but also security; poor hashes can be exploited in denial-of-service attacks.

When NOT to use

HashMaps are not ideal when order matters; use Trees or LinkedHashMaps instead. For small datasets or when memory is very limited, simpler arrays or lists may be better. When keys are complex objects without good hash functions, consider other data structures like tries or balanced trees.

Production Patterns

In production, HashMaps are often combined with caching layers, use custom hash functions for domain-specific keys, and implement dynamic resizing with careful load factor tuning. They are also used in databases for indexing and in compilers for symbol tables.

Connections

Trie (Prefix Tree)

Alternative data structure for key-value storage with prefix-based keys.

Understanding HashMaps helps appreciate Tries as they both store key-value pairs but Tries excel at prefix queries and ordered data.

Cryptographic Hash Functions

Advanced form of hash functions used for security rather than indexing.

Knowing how HashMaps use simple hash functions clarifies why cryptographic hashes are more complex and slower but secure.

Cache Memory in CPUs

Both use hashing and indexing to quickly locate data.

Understanding HashMap indexing helps grasp how CPU caches map memory addresses to cache lines for fast access.

Common Pitfalls

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

Wrong approach:

class HashMap {
private buckets: Array<[string, any] | null>;
constructor(size: number) {
this.buckets = new Array(size).fill(null);
}
put(key: string, value: any) {
const index = this.hash(key);
this.buckets[index] = [key, value]; // overwrites existing
}
get(key: string) {
const index = this.hash(key);
const pair = this.buckets[index];
if (pair && pair[0] === key) return pair[1];
return null;
}
private hash(key: string) { return key.length % this.buckets.length; }
}

Correct approach:

class HashMap {
private buckets: Array>;
constructor(size: number) {
this.buckets = new Array(size).fill(null).map(() => []);
}
put(key: string, value: any) {
const index = this.hash(key);
const bucket = this.buckets[index];
const pairIndex = bucket.findIndex(pair => pair[0] === key);
if (pairIndex >= 0) bucket[pairIndex][1] = value;
else bucket.push([key, value]);
}
get(key: string) {
const index = this.hash(key);
const bucket = this.buckets[index];
const pair = bucket.find(pair => pair[0] === key);
return pair ? pair[1] : null;
}
private hash(key: string) { return key.length % this.buckets.length; }
}

Root cause:

Misunderstanding that collisions require storing multiple pairs per bucket, not overwriting.

#2 Not resizing the HashMap leading to slow operations as it fills.

Wrong approach:

class HashMap {
private buckets: Array> = new Array(5).fill(null).map(() => []);
put(key: string, value: any) {
const index = this.hash(key);
this.buckets[index].push([key, value]);
}
private hash(key: string) { return key.length % this.buckets.length; }
}

Correct approach:

class HashMap {
private buckets: Array>;
private size = 0;
private capacity = 5;
constructor() {
this.buckets = new Array(this.capacity).fill(null).map(() => []);
}
put(key: string, value: any) {
if (this.size / this.capacity > 0.7) this.resize();
const index = this.hash(key);
const bucket = this.buckets[index];
const pairIndex = bucket.findIndex(pair => pair[0] === key);
if (pairIndex >= 0) bucket[pairIndex][1] = value;
else {
bucket.push([key, value]);
this.size++;
}
}
private resize() {
this.capacity *= 2;
const oldBuckets = this.buckets;
this.buckets = new Array(this.capacity).fill(null).map(() => []);
this.size = 0;
for (const bucket of oldBuckets) {
for (const [key, value] of bucket) {
this.put(key, value);
}
}
}
private hash(key: string) { return key.length % this.capacity; }
}

Root cause:

Not understanding the need to resize to maintain performance as data grows.

#3 Using a poor hash function causing many collisions.

Wrong approach:

private hash(key: string) { return 1; } // always returns same index

Correct approach:

private hash(key: string) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash = (hash * 31 + key.charCodeAt(i)) % this.capacity;
}
return hash;
}

Root cause:

Not realizing hash function quality affects distribution and performance.

Key Takeaways

HashMaps store data as key-value pairs using a hash function to find storage locations quickly.

Collisions happen when different keys map to the same index; handling them properly is essential to avoid data loss.

Resizing the underlying array and rehashing keys keeps HashMaps efficient as they grow.

The choice and design of the hash function greatly impact the performance and reliability of a HashMap.

HashMaps prioritize speed over order, so they do not maintain any order of keys or values.

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 key-value pairs for fast data retrieval

C. To perform mathematical calculations

D. To store data sequentially like an array

Solution

1. Step 1: Understand HashMap functionality

   A HashMap stores data as key-value pairs, allowing quick access by key.

2. Step 2: Compare with other data structures

   Unlike arrays or lists, HashMaps do not store data sequentially or sorted but focus on fast lookup.

3. Final Answer:

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

4. Quick Check:

   HashMap = key-value fast access [OK]

Hint: HashMap = key-value pairs for quick lookup [OK]

Common Mistakes:

• Thinking HashMap stores data in order
• Confusing HashMap with arrays
• Assuming HashMap is for calculations

2. Which of the following is the correct way to declare a simple HashMap class property in TypeScript?

easy

A. private map: {[key: string]: any} = {};

B. map = new Map();

C. let map = [];

D. const map: Map = {};

Solution

1. Step 1: Identify TypeScript syntax for object property

   Declaring a private property with type {[key: string]: any} initializes an object for key-value storage.

2. Step 2: Check other options for correctness

   map = new Map(); uses built-in Map, not a plain object; C is an array; D has wrong Map type usage.

3. Final Answer:

   private map: {[key: string]: any} = {}; -> Option A

4. Quick Check:

   TypeScript object property syntax = private map: {[key: string]: any} = {}; [OK]

Hint: Use object type {[key: string]: any} for HashMap storage [OK]

Common Mistakes:

• Using array instead of object for map
• Incorrect Map type declaration
• Confusing built-in Map with plain object

3. What will be the output of this TypeScript code snippet implementing a simple HashMap?

class SimpleHashMap {
  private map: {[key: string]: string} = {};
  set(key: string, value: string) {
    this.map[key] = value;
  }
  get(key: string) {
    return this.map[key] || null;
  }
}
const h = new SimpleHashMap();
h.set('a', 'apple');
h.set('b', 'banana');
console.log(h.get('a'));
console.log(h.get('c'));

medium

A. "apple" followed by null

B. "apple" followed by undefined

C. undefined followed by null

D. Error at runtime

Solution

1. Step 1: Trace set method calls

   Keys 'a' and 'b' are set with values 'apple' and 'banana' respectively in the map object.

2. Step 2: Trace get method calls

   Getting 'a' returns 'apple'; getting 'c' returns undefined, so || null returns null.

3. Final Answer:

   "apple" followed by null -> Option A

4. Quick Check:

   Existing key returns value, missing key returns null [OK]

Hint: Missing keys return null due to || null fallback [OK]

Common Mistakes:

• Expecting undefined instead of null for missing keys
• Confusing set and get method effects
• Assuming runtime error on missing key

4. Identify the bug in this simple HashMap implementation and choose the correct fix:

class BuggyHashMap {
  private map: {[key: string]: number} = {};
  set(key: string, value: number) {
    this.map[key] = value;
  }
  get(key: string): number {
    return this.map[key];
  }
}
const h = new BuggyHashMap();
h.set('x', 10);
console.log(h.get('y'));

medium

A. map should be an array instead of object

B. set method should check if key exists before setting

C. get should return number | null and handle missing keys

D. No bug, code works fine

Solution

1. Step 1: Analyze get method return type

   get returns number but missing keys return undefined, causing type mismatch.

2. Step 2: Fix get method to handle missing keys

   Change return type to number | null and return null if key missing to avoid undefined.

3. Final Answer:

   get should return number | null and handle missing keys -> Option C

4. Quick Check:

   Handle missing keys in get method [OK]

Hint: Always handle missing keys in get method return type [OK]

Common Mistakes:

• Ignoring undefined return for missing keys
• Changing map to array incorrectly
• Thinking set method needs key existence check

5. You want to implement a HashMap from scratch in TypeScript that handles collisions using chaining (array of entries). Which approach correctly adds a new key-value pair to the map?

hard

A. Store keys in an array and values in a separate array without hashing

B. Compute hash, overwrite bucket with new entry ignoring existing keys

C. Use a single array for all entries without hashing

D. Compute hash, check bucket array; if key exists update value, else push new entry

Solution

1. Step 1: Understand collision handling by chaining

   Chaining stores multiple entries in a bucket array; new entries are added or updated if key exists.

2. Step 2: Analyze options for correct collision handling

   Compute hash, check bucket array; if key exists update value, else push new entry correctly checks bucket, updates existing key or adds new entry; others ignore collisions or do not hash.

3. Final Answer:

   Compute hash, check bucket array; if key exists update value, else push new entry -> Option D

4. Quick Check:

   Chaining = bucket array with update or add [OK]

Hint: Check bucket for key, update or add entry to handle collisions [OK]

Common Mistakes:

• Overwriting bucket ignoring existing keys
• Not using hashing for bucket selection
• Storing keys and values separately without hashing