Design Hashmap - Leetcode Solution

Problem Statement:

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

Implement the MyHashMap class:

1. MyHashMap() initializes the object with an empty map.
2. 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.
3. 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.
4. void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.

Solution:

To solve this problem, we can use an array of a fixed size to store the key-value pairs. We can create an array of size 1000001, which is sufficiently large to store all the possible keys from 0 to 1000000. We can then use the key as the index in the array, and the corresponding value as the value stored at that index.

To handle collisions, we can use an array of linked lists. Each index in the array of key-value pairs will either be null or a reference to a linked list containing all the key-value pairs that hash to that index.

To insert a new key-value pair, we can first compute the hash code of the key by taking the modulus of the key with the size of the array. We can then add the key-value pair to the linked list at the corresponding index in the array of linked lists.

To get the value corresponding to a key, we can first compute the hash code of the key and then search for the key in the linked list at the corresponding index. If we find the key, we can return the corresponding value. Otherwise, we return -1.

To remove a key-value pair, we can first compute the hash code of the key and then search for the key in the linked list at the corresponding index. If we find the key, we can remove the corresponding key-value pair from the linked list. Otherwise, we do nothing.

Code:

class MyHashMap {

    private final int SIZE = 1000001;
    private List<Node>[] map;

    class Node {
        int key;
        int value;
        Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    public MyHashMap() {
        map = new ArrayList[SIZE];
    }

    public void put(int key, int value) {
        int index = key % SIZE;
        if (map[index] == null) {
            map[index] = new ArrayList<Node>();
        }
        for (Node node : map[index]) {
            if (node.key == key) {
                node.value = value;
                return;
            }
        }
        map[index].add(new Node(key, value));
    }

    public int get(int key) {
        int index = key % SIZE;
        if (map[index] != null) {
            for (Node node : map[index]) {
                if (node.key == key) {
                    return node.value;
                }
            }
        }
        return -1;
    }

    public void remove(int key) {
        int index = key % SIZE;
        if (map[index] != null) {
            for (Iterator<Node> it = map[index].iterator(); it.hasNext();) {
                Node node = it.next();
                if (node.key == key) {
                    it.remove();
                    return;
                }
            }
        }
    }
}

1