706. Design HashMap - Explanation

Description

Design a HashMap without using any built-in hash table libraries.

Implement the MyHashMap class:

MyHashMap() initializes the object with an empty map.
void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.

Example 1:

Input: ["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]

Output: [null, null, null, 1, -1, null, 1, null, -1]

Explanation:
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // The map is now [[1,1]]
myHashMap.put(2, 2); // The map is now [[1,1], [2,2]]
myHashMap.get(1); // return 1, The map is now [[1,1], [2,2]]
myHashMap.get(3); // return -1 (i.e., not found), The map is now [[1,1], [2,2]]
myHashMap.put(2, 1); // The map is now [[1,1], [2,1]] (i.e., update the existing value)
myHashMap.get(2); // return 1, The map is now [[1,1], [2,1]]
myHashMap.remove(2); // remove the mapping for 2, The map is now [[1,1]]
myHashMap.get(2); // return -1 (i.e., not found), The map is now [[1,1]]

Constraints:

0 <= key, value <= 1,000,000
At most 10,000 calls will be made to put, get, and remove.

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Hash Functions - Understanding how keys map to indices via modulo operations
Linked Lists - Implementing node-based structures for collision handling (chaining)
Arrays - Using direct addressing with fixed-size arrays

1. Array

Intuition

Since keys are constrained to the range [0, 1000000], we can use direct addressing. We allocate an array where the index represents the key and the value at that index is the stored value. We use -1 to indicate that a key is not present. This gives O(1) time for all operations at the cost of fixed memory usage regardless of how many keys are actually stored.

Algorithm

Initialize an array of size 1000001 with all values set to -1.
For put(key, value): Set map[key] = value.
For get(key): Return map[key] (returns -1 if the key was never set or was removed).
For remove(key): Set map[key] = -1.

class MyHashMap:

    def __init__(self):
        self.map = [-1] * 1000001

    def put(self, key: int, value: int) -> None:
        self.map[key] = value

    def get(self, key: int) -> int:
        return self.map[key]

    def remove(self, key: int) -> None:
        self.map[key] = -1

public class MyHashMap {
    private int[] map;

    public MyHashMap() {
        map = new int[1000001];
        Arrays.fill(map, -1);
    }

    public void put(int key, int value) {
        map[key] = value;
    }

    public int get(int key) {
        return map[key];
    }

    public void remove(int key) {
        map[key] = -1;
    }
}

class MyHashMap {
private:
    vector<int> map;

public:
    MyHashMap() : map(1000001, -1) {}

    void put(int key, int value) {
        map[key] = value;
    }

    int get(int key) {
        return map[key];
    }

    void remove(int key) {
        map[key] = -1;
    }
};

class MyHashMap {
    constructor() {
        this.map = new Array(1000001).fill(-1);
    }

    /**
     * @param {number} key
     * @param {number} value
     * @return {void}
     */
    put(key, value) {
        this.map[key] = value;
    }

    /**
     * @param {number} key
     * @return {number}
     */
    get(key) {
        return this.map[key];
    }

    /**
     * @param {number} key
     * @return {void}
     */
    remove(key) {
        this.map[key] = -1;
    }
}

public class MyHashMap {
    private int[] map;

    public MyHashMap() {
        map = new int[1000001];
        for (int i = 0; i < map.Length; i++) {
            map[i] = -1;
        }
    }

    public void Put(int key, int value) {
        map[key] = value;
    }

    public int Get(int key) {
        return map[key];
    }

    public void Remove(int key) {
        map[key] = -1;
    }
}

type MyHashMap struct {
    data []int
}

func Constructor() MyHashMap {
    data := make([]int, 1000001)
    for i := range data {
        data[i] = -1
    }
    return MyHashMap{data: data}
}

func (this *MyHashMap) Put(key int, value int) {
    this.data[key] = value
}

func (this *MyHashMap) Get(key int) int {
    return this.data[key]
}

func (this *MyHashMap) Remove(key int) {
    this.data[key] = -1
}

class MyHashMap() {
    private val map = IntArray(1000001) { -1 }

    fun put(key: Int, value: Int) {
        map[key] = value
    }

    fun get(key: Int): Int {
        return map[key]
    }

    fun remove(key: Int) {
        map[key] = -1
    }
}

class MyHashMap {
    private var map: [Int]

    init() {
        map = [Int](repeating: -1, count: 1000001)
    }

    func put(_ key: Int, _ value: Int) {
        map[key] = value
    }

    func get(_ key: Int) -> Int {
        return map[key]
    }

    func remove(_ key: Int) {
        map[key] = -1
    }
}

Time & Space Complexity

Time complexity: $O(1)$ for each function call.
Space complexity: $O(1000000)$ since the key is in the range $[0, 1000000]$ .

2. Linked List

Intuition

To reduce memory usage, we use a hash table with separate chaining. We create an array of buckets (smaller than the key range) and use a hash function (key modulo bucket count) to determine which bucket a key belongs to. Each bucket is a linked list that stores key-value pairs. This handles collisions by chaining multiple entries in the same bucket.

Algorithm

Initialize an array of 1000 buckets, each containing a dummy head node for a linked list.
Define hash(key) as key % 1000.
For put(key, value): Traverse the linked list at hash(key). If a node with the matching key exists, update its value. Otherwise, append a new node with the key-value pair.
For get(key): Traverse the linked list at hash(key). If a node with the matching key is found, return its value. Otherwise, return -1.
For remove(key): Traverse the linked list at hash(key). If a node with the matching key is found, remove it by updating the previous node's next pointer.

class ListNode:
    def __init__(self, key = -1, val = -1, next = None):
        self.key = key
        self.val = val
        self.next = next

class MyHashMap:

    def __init__(self):
        self.map = [ListNode() for _ in range(1000)]

    def hash(self, key: int) -> int:
        return key % len(self.map)

    def put(self, key: int, value: int) -> None:
        cur = self.map[self.hash(key)]
        while cur.next:
            if cur.next.key == key:
                cur.next.val = value
                return
            cur = cur.next
        cur.next = ListNode(key, value)

    def get(self, key: int) -> int:
        cur = self.map[self.hash(key)].next
        while cur:
            if cur.key == key:
                return cur.val
            cur = cur.next
        return -1

    def remove(self, key: int) -> None:
        cur = self.map[self.hash(key)]
        while cur.next:
            if cur.next.key == key:
                cur.next = cur.next.next
                return
            cur = cur.next

class ListNode {
    int key, val;
    ListNode next;

    public ListNode(int key, int val, ListNode next) {
        this.key = key;
        this.val = val;
        this.next = next;
    }

    public ListNode() {
        this(-1, -1, null);
    }
}

public class MyHashMap {
    private ListNode[] map;

    public MyHashMap() {
        map = new ListNode[1000];
        for (int i = 0; i < 1000; i++) {
            map[i] = new ListNode();
        }
    }

    private int hash(int key) {
        return key % map.length;
    }

    public void put(int key, int value) {
        ListNode cur = map[hash(key)];
        while (cur.next != null) {
            if (cur.next.key == key) {
                cur.next.val = value;
                return;
            }
            cur = cur.next;
        }
        cur.next = new ListNode(key, value, null);
    }

    public int get(int key) {
        ListNode cur = map[hash(key)].next;
        while (cur != null) {
            if (cur.key == key) {
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;
    }

    public void remove(int key) {
        ListNode cur = map[hash(key)];
        while (cur.next != null) {
            if (cur.next.key == key) {
                cur.next = cur.next.next;
                return;
            }
            cur = cur.next;
        }
    }
}

class MyHashMap {
private:
    struct ListNode {
        int key, val;
        ListNode* next;

        ListNode(int key = -1, int val = -1, ListNode* next = nullptr)
            : key(key), val(val), next(next) {}
    };

    vector<ListNode*> map;
    int hash(int key) {
        return key % map.size();
    }

public:
    MyHashMap() {
        map.resize(1000);
        for (auto& bucket : map) {
            bucket = new ListNode(0);
        }
    }

    void put(int key, int value) {
        ListNode* cur = map[hash(key)];
        while (cur->next) {
            if (cur->next->key == key) {
                cur->next->val = value;
                return;
            }
            cur = cur->next;
        }
        cur->next = new ListNode(key, value);
    }

    int get(int key) {
        ListNode* cur = map[hash(key)]->next;
        while (cur) {
            if (cur->key == key) {
                return cur->val;
            }
            cur = cur->next;
        }
        return -1;
    }

    void remove(int key) {
        ListNode* cur = map[hash(key)];
        while (cur->next) {
            if (cur->next->key == key) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
                return;
            }
            cur = cur->next;
        }
    }
};

class ListNode {
    /**
     * @param {number} key
     * @param {number} val
     * @param {ListNode} next
     */
    constructor(key = -1, val = -1, next = null) {
        this.key = key;
        this.val = val;
        this.next = next;
    }
}

class MyHashMap {
    constructor() {
        this.map = Array.from({ length: 1000 }, () => new ListNode());
    }

    /**
     * @param {number} key
     * @return {number}
     */
    hash(key) {
        return key % this.map.length;
    }

    /**
     * @param {number} key
     * @param {number} value
     * @return {void}
     */
    put(key, value) {
        let cur = this.map[this.hash(key)];
        while (cur.next) {
            if (cur.next.key === key) {
                cur.next.val = value;
                return;
            }
            cur = cur.next;
        }
        cur.next = new ListNode(key, value);
    }

    /**
     * @param {number} key
     * @return {number}
     */
    get(key) {
        let cur = this.map[this.hash(key)].next;
        while (cur) {
            if (cur.key === key) {
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;
    }

    /**
     * @param {number} key
     * @return {void}
     */
    remove(key) {
        let cur = this.map[this.hash(key)];
        while (cur.next) {
            if (cur.next.key === key) {
                cur.next = cur.next.next;
                return;
            }
            cur = cur.next;
        }
    }
}

public class ListNode {
    public int key;
    public int val;
    public ListNode next;

    public ListNode(int key = -1, int val = -1, ListNode next = null) {
        this.key = key;
        this.val = val;
        this.next = next;
    }
}

public class MyHashMap {
    private ListNode[] map;

    public MyHashMap() {
        map = new ListNode[1000];
        for (int i = 0; i < map.Length; i++) {
            map[i] = new ListNode();
        }
    }

    private int Hash(int key) {
        return key % map.Length;
    }

    public void Put(int key, int value) {
        ListNode cur = map[Hash(key)];
        while (cur.next != null) {
            if (cur.next.key == key) {
                cur.next.val = value;
                return;
            }
            cur = cur.next;
        }
        cur.next = new ListNode(key, value);
    }

    public int Get(int key) {
        ListNode cur = map[Hash(key)].next;
        while (cur != null) {
            if (cur.key == key) {
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;
    }

    public void Remove(int key) {
        ListNode cur = map[Hash(key)];
        while (cur.next != null) {
            if (cur.next.key == key) {
                cur.next = cur.next.next;
                return;
            }
            cur = cur.next;
        }
    }
}

type ListNode struct {
    key, val int
    next     *ListNode
}

type MyHashMap struct {
    data []*ListNode
}

func Constructor() MyHashMap {
    data := make([]*ListNode, 1000)
    for i := range data {
        data[i] = &ListNode{key: -1, val: -1}
    }
    return MyHashMap{data: data}
}

func (this *MyHashMap) hash(key int) int {
    return key % len(this.data)
}

func (this *MyHashMap) Put(key int, value int) {
    cur := this.data[this.hash(key)]
    for cur.next != nil {
        if cur.next.key == key {
            cur.next.val = value
            return
        }
        cur = cur.next
    }
    cur.next = &ListNode{key: key, val: value}
}

func (this *MyHashMap) Get(key int) int {
    cur := this.data[this.hash(key)].next
    for cur != nil {
        if cur.key == key {
            return cur.val
        }
        cur = cur.next
    }
    return -1
}

func (this *MyHashMap) Remove(key int) {
    cur := this.data[this.hash(key)]
    for cur.next != nil {
        if cur.next.key == key {
            cur.next = cur.next.next
            return
        }
        cur = cur.next
    }
}

class ListNode(var key: Int = -1, var `val`: Int = -1, var next: ListNode? = null)

class MyHashMap() {
    private val map = Array(1000) { ListNode() }

    private fun hash(key: Int): Int = key % map.size

    fun put(key: Int, value: Int) {
        var cur = map[hash(key)]
        while (cur.next != null) {
            if (cur.next!!.key == key) {
                cur.next!!.`val` = value
                return
            }
            cur = cur.next!!
        }
        cur.next = ListNode(key, value)
    }

    fun get(key: Int): Int {
        var cur = map[hash(key)].next
        while (cur != null) {
            if (cur.key == key) {
                return cur.`val`
            }
            cur = cur.next
        }
        return -1
    }

    fun remove(key: Int) {
        var cur = map[hash(key)]
        while (cur.next != null) {
            if (cur.next!!.key == key) {
                cur.next = cur.next!!.next
                return
            }
            cur = cur.next!!
        }
    }
}

class ListNode {
    var key: Int
    var val: Int
    var next: ListNode?

    init(_ key: Int = -1, _ val: Int = -1, _ next: ListNode? = nil) {
        self.key = key
        self.val = val
        self.next = next
    }
}

class MyHashMap {
    private var map: [ListNode]

    init() {
        map = (0..<1000).map { _ in ListNode() }
    }

    private func hash(_ key: Int) -> Int {
        return key % map.count
    }

    func put(_ key: Int, _ value: Int) {
        var cur = map[hash(key)]
        while cur.next != nil {
            if cur.next!.key == key {
                cur.next!.val = value
                return
            }
            cur = cur.next!
        }
        cur.next = ListNode(key, value)
    }

    func get(_ key: Int) -> Int {
        var cur = map[hash(key)].next
        while cur != nil {
            if cur!.key == key {
                return cur!.val
            }
            cur = cur!.next
        }
        return -1
    }

    func remove(_ key: Int) {
        var cur = map[hash(key)]
        while cur.next != nil {
            if cur.next!.key == key {
                cur.next = cur.next!.next
                return
            }
            cur = cur.next!
        }
    }
}

Time & Space Complexity

Time complexity: $O(\frac{n}{k})$ for each function call.
Space complexity: $O(k + m)$

Where $n$ is the number of keys, $k$ is the size of the map ( $1000$ ) and $m$ is the number of unique keys.

Common Pitfalls

Not Updating Existing Keys on Put

When a key already exists, put() should update its value rather than adding a duplicate entry.

# Wrong - creates duplicate entries
def put(self, key: int, value: int) -> None:
    cur = self.map[self.hash(key)]
    while cur.next:
        cur = cur.next
    cur.next = ListNode(key, value)  # Always adds new node!

# Correct - update if exists, otherwise add
def put(self, key: int, value: int) -> None:
    cur = self.map[self.hash(key)]
    while cur.next:
        if cur.next.key == key:
            cur.next.val = value  # Update existing
            return
        cur = cur.next
    cur.next = ListNode(key, value)  # Add new

Traversing from Dummy Node in Get

When getting a value, start from dummy.next (actual first element), not the dummy head itself.

# Wrong - checks dummy node's key
def get(self, key: int) -> int:
    cur = self.map[self.hash(key)]  # Starts at dummy
    while cur:
        if cur.key == key:  # Dummy has key=-1, might match!
            return cur.val
        cur = cur.next
    return -1

# Correct - skip dummy node
def get(self, key: int) -> int:
    cur = self.map[self.hash(key)].next  # Start after dummy
    while cur:
        if cur.key == key:
            return cur.val
        cur = cur.next
    return -1