Solution: Design HashMap (ver. 1)

#algorithms #javascript #java #python

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

Note: This is my first version of a solution for this problem. Due to the constraints listed for this problem and the fact that this problem is labeled "Easy", this is my preferred solution, but it doesn't really address the actual nature of a hashmap. My second version of a solution breaks down in detail what a hashmap accomplishes and why it's beneficial.

Leetcode Problem #706 (Easy): Design HashMap

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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

To be specific, your design should include these functions:

put(key, value): Insert a (key, value) pair into the HashMap. If the value already exists in the HashMap, update the value.

get(key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.

remove(key): Remove the mapping for the value key if this map contains the mapping for the key.

Examples:

Example:

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 hashMap = new MyHashMap();
hashMap.put(1, 1);
hashMap.put(2, 2);
hashMap.get(1); // returns 1
hashMap.get(3); // returns -1 (not found)
hashMap.put(2, 1); // update the existing value
hashMap.get(2); // returns 1
hashMap.remove(2); // remove the mapping for 2
hashMap.get(2); // returns -1 (not found)

Example:
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 hashMap = new MyHashMap(); hashMap.put(1, 1); hashMap.put(2, 2); hashMap.get(1); // returns 1 hashMap.get(3); // returns -1 (not found) hashMap.put(2, 1); // update the existing value hashMap.get(2); // returns 1 hashMap.remove(2); // remove the mapping for 2 hashMap.get(2); // returns -1 (not found)

Constraints:

All keys and values will be in the range of [0, 1000000].

The number of operations will be in the range of [1, 10000].

Please do not use the built-in HashMap library.

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

The "easy" solution for this problem is simply to create an array large enough to accommodate the entire range of keys. This would seem to be the intended first solution, since the range of allowed keys is non-negative and constrained to 10^6, which is not unmanageable.

Javascript Code:

(Jump to: Problem Description || Solution Idea)

class MyHashMap {
    constructor() {
        this.data = new Array(1000001)
    }

    put(key, val) {
        this.data[key] = val
    }

    get(key) {
        let val = this.data[key]
        return val !== undefined ? val : -1
    }

    remove(key) {
        delete this.data[key]
    }
};

Python Code:

(Jump to: Problem Description || Solution Idea)

class MyHashMap:
    def __init__(self):
        self.data = [None] * 1000001

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

    def get(self, key: int) -> int:
        val = self.data[key]
        return val if val != None else -1

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

Java Code:

(Jump to: Problem Description || Solution Idea)

class MyHashMap {
    int[] data;

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

    public void put(int key, int val) {
        data[key] = val;
    }

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

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

C++ Code:

(Jump to: Problem Description || Solution Idea)

class MyHashMap {
public:
    int data[1000001];

    MyHashMap() {
        fill(data, data + 1000000, -1);
    }

    void put(int key, int val) {
        data[key] = val;
    }

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

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