[leetcode #706] Design HashMap

Problem

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 <= 10⁶
· At most 10⁴ calls will be made to put, get, and remove.

Idea

key의 범위가 최대 1,000,000이므로 HashSet을 구현할 때와 마찬가지로 array를 사용했다.

key와 value를 넣을 때는 array값을 설정하면 되고, key에 맞는 value를 얻을 때는 key를 index로 하여 array값을 얻으면 된다.
key를 제거할 때는 해당하는 array 값을 -1로 설정하면 된다.

Solution

class MyHashMap {
    int[] arr;

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

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

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

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

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap obj = new MyHashMap();
 * obj.put(key,value);
 * int param_2 = obj.get(key);
 * obj.remove(key);
 */

Reference

https://leetcode.com/problems/design-hashmap/