HashMap Implementation from Scratch in DSA Typescript - Build from Scratch

HashMap Implementation from Scratch

📖 Scenario: Imagine you want to build a simple phone book app that stores names and phone numbers. To do this efficiently, you decide to create your own HashMap from scratch. This will help you quickly find a phone number by a person's name.

🎯 Goal: You will build a basic HashMap class in TypeScript that can store key-value pairs, handle collisions using separate chaining, and allow adding, retrieving, and removing entries.

📋 What You'll Learn

Create a HashMap class with an internal array for buckets

Implement a simple hash function to convert keys to bucket indices

Use separate chaining with arrays to handle collisions

Add methods: set(key: string, value: string), get(key: string): string | undefined, and remove(key: string): void

Demonstrate adding, retrieving, and removing entries

💡 Why This Matters

🌍 Real World

HashMaps are used in many apps and systems to store and quickly find data like user info, settings, or cached results.

💼 Career

Understanding how HashMaps work under the hood helps in optimizing code and solving problems related to fast data lookup in software development roles.

1

Create the HashMap class with buckets

Create a class called HashMap with a property buckets which is an array of arrays of key-value pairs. Initialize buckets as an empty array with length 5.

DSA Typescript

class HashMap {
    buckets: [string, string][][];

    constructor() {
        // Your code here
    }
}

Hint

Use new Array(5).fill(null).map(() => []) to create 5 empty arrays inside buckets.

2

Add a hash function to get bucket index

Inside the HashMap class, add a private method called hash that takes a key: string and returns a number. The method should sum the character codes of the key's letters and return the sum modulo the length of buckets.

DSA Typescript

class HashMap {
    buckets: [string, string][][];

    constructor() {
        this.buckets = new Array(5).fill(null).map(() => []);
    }

    // Add the hash method below
    
}

Hint

Loop over each character in key, add its char code to sum, then return sum % this.buckets.length.

3

Implement the set method to add key-value pairs

Add a public method set(key: string, value: string): void to the HashMap class. Use the hash method to find the bucket index. If the key already exists in the bucket, update its value. Otherwise, add the new key-value pair to the bucket.

DSA Typescript

class HashMap {
    buckets: [string, string][][];

    constructor() {
        this.buckets = new Array(5).fill(null).map(() => []);
    }

    private hash(key: string): number {
        let sum = 0;
        for (let i = 0; i < key.length; i++) {
            sum += key.charCodeAt(i);
        }
        return sum % this.buckets.length;
    }

    // Add the set method below
    
}

Hint

Find the bucket using the hash. Check if the key exists to update. If not found, add the new pair.

4

Add get and remove methods and test the HashMap

Add two public methods to the HashMap class: get(key: string): string | undefined to return the value for a key or undefined if not found, and remove(key: string): void to delete the key-value pair if it exists. Then create a HashMap instance, add entries 'Alice' -> '123' and 'Bob' -> '456', retrieve and print the value for 'Alice', remove 'Bob', and print the entire buckets array.

DSA Typescript

class HashMap {
    buckets: [string, string][][];

    constructor() {
        this.buckets = new Array(5).fill(null).map(() => []);
    }

    private hash(key: string): number {
        let sum = 0;
        for (let i = 0; i < key.length; i++) {
            sum += key.charCodeAt(i);
        }
        return sum % this.buckets.length;
    }

    set(key: string, value: string): void {
        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]);
    }

    // Add get and remove methods below
    
}

const map = new HashMap();
// Add code to set, get, remove, and print below

Hint

Use get to find 'Alice', remove to delete 'Bob', then print map.buckets to see the current state.

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