---

1. Problem Summary

You are asked to implement a basic HashMap data structure from scratch without using:

• built-in hash maps
• dictionary-like containers

Your custom HashMap must support three operations:

put(key, value)
get(key)
remove(key)

Behavior requirements:

1. put(key, value)
   • inserts key-value pair
   • if key already exists, update its value
2. get(key)
   • return the value associated with key
   • if key does not exist, return -1
3. remove(key)
   • delete the mapping for the key if it exists

Constraints:

• Keys are integers in the range [0, 10^6]
• Operations must run efficiently

---

2. Key Insights

Direct array is too large

Even though key range is bounded (up to 1,000,000), storing a direct array that large is space-inefficient.

Hashing required for efficiency

We compute:

bucketIndex = key % BUCKET_SIZE

Collisions are unavoidable

Multiple keys may map to the same bucket index.

Use Separate Chaining

Each bucket contains a list (linked list) of key-value pairs.

Search within bucket is linear

But since bucket count is large, average bucket size remains small.

Updating vs inserting

When calling put, we must check if key already exists in that bucket.

---

3. Approach

Design using array of buckets where each bucket is a linked list

Steps:

1. Choose a bucket size (commonly a prime number like 769 or 1009)
2. Create an array of bucket lists
3. For put(key, value):
   • compute bucket index
   • iterate bucket list
   • if key found → update value
   • else → insert (key, value)
4. For get(key):
   • compute bucket index
   • search bucket
   • return stored value or -1
5. For remove(key):
   • compute bucket index
   • search bucket
   • remove entry if found

This provides acceptable time performance.

---

4. Time and Space Complexity

Time Complexity (average)

put   → O(1)
get   → O(1)
remove → O(1)

Time Complexity (worst case)

O(N)  // if all keys land in same bucket

Space Complexity

O(N)  // storing all inserted key-value pairs

---

5. Java Solution

import java.util.*;

class MyHashMap {

    private static final int SIZE = 769;
    private List<Pair>[] buckets;

    private static class Pair {
        int key;
        int value;
        Pair(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    public MyHashMap() {
        buckets = new List[SIZE];
        for (int i = 0; i < SIZE; i++) {
            buckets[i] = new LinkedList<>();
        }
    }

    private int hash(int key) {
        return key % SIZE;
    }

    public void put(int key, int value) {
        int index = hash(key);
        List<Pair> bucket = buckets[index];

        for (Pair pair : bucket) {
            if (pair.key == key) {
                pair.value = value;  // update existing
                return;
            }
        }

        bucket.add(new Pair(key, value));
    }

    public int get(int key) {
        int index = hash(key);
        List<Pair> bucket = buckets[index];

        for (Pair pair : bucket) {
            if (pair.key == key) {
                return pair.value;
            }
        }

        return -1;
    }

    public void remove(int key) {
        int index = hash(key);
        List<Pair> bucket = buckets[index];
        Iterator<Pair> iterator = bucket.iterator();

        while (iterator.hasNext()) {
            Pair pair = iterator.next();
            if (pair.key == key) {
                iterator.remove();
                return;
            }
        }
    }
}

---

6. Dry Run Examples

Example 1

Operations:

put(1, 1)
put(2, 2)
get(1)
get(3)
put(2, 1)
get(2)
remove(2)
get(2)

Step by step:

put(1,1) → store (1,1)
put(2,2) → store (2,2)
get(1) → returns 1
get(3) → returns -1
put(2,1) → update value for key 2
get(2) → returns 1
remove(2) → delete entry
get(2) → returns -1

---

Example 2

Handling collision:

Suppose bucket size = 5 and keys:

put(3,10)
put(8,20)
put(13,30)

All map to same index:

3 % 5 = 3
8 % 5 = 3
13 % 5 = 3

Bucket 3 list:

[(3,10), (8,20), (13,30)]

get(8) scans bucket 3 and returns 20

---

Example 3

Removing non-existent key:

remove(99)

Bucket empty or doesn’t contain key → do nothing

---

Example 4

Updating existing value:

put(4,5)
put(4,9)

After operations:

get(4) = 9

---

7. Why This Solution Works

• Uses hashing to distribute keys
• Handles collisions with separate chaining
• Maintains O(1) average performance
• Clean separation of concerns:
  • hash function
  • bucket storage
  • key search/update/delete
• Avoids memory explosion from direct indexing
• Matches required API exactly

---

8. Common Mistakes

1. Forgetting to update value when key already exists
2. Returning 0 instead of -1 for missing key
3. Using array size too small → causes clustering
4. Removing while iterating incorrectly (must use iterator)
5. Miscomputing hash index for negative keys (not needed here due to constraints)