Design a HashMap

Problem Overview

Design and implement a HashMap<K, V> from scratch, without using the language's built-in hash map. Support the standard API:

java class MyHashMap<K, V> { void put(K key, V value); // insert a (key, value) pair into the HashMap V get(K key); // returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key void remove(K key); // remove the mapping for the value key if present }

Constraints

• All keys and values in the HashMap will be non-null.
• The number of operations (put, get, remove) will not exceed 10^4.
• All keys are integers within the range of -10^9 to 10^9.

Examples

1. MyHashMap()

   Initialize your MyHashMap object here.

2. void put(int key, int value)

   Inserts a (key, value) pair into the HashMap. If the key already existed, update the value.

   Example: java MyHashMap myHashMap = new MyHashMap(); myHashMap.put(1, 1); myHashMap.put(2, 2);

3. int get(int key)

   Returns the value to which the specified key is mapped in the HashMap, or returns -1 if this map contains no mapping for the key.

   Example: java MyHashMap myHashMap = new MyHashMap(); myHashMap.put(2, 1); int put = myHashMap.get(2); // returns 1 (the value to which 2 is mapped) int get = myHashMap.get(3); // returns -1 (not found)

4. void remove(int key)

   Removes the mapping of the given key if it exists in the HashMap.

   Example: java MyHashMap myHashMap = new MyHashMap(); myHashMap.put(2, 1); myHashMap.remove(2); // remove the mapping for 2 int get = myHashMap.get(2); // returns -1 (not found)

Hints

• Consider using an array of linked lists to handle collisions.
• Resize the array when the load factor exceeds a certain threshold to maintain efficient operations.

Solution

Here is a sample implementation in Java:

class MyHashMap<K, V> {
    private static final int DEFAULT_CAPACITY = 1000;
    private static final int MAX_CAPACITY = 1 << 30;
    private static final float LOAD_FACTOR = 0.75f;
    private Entry[] buckets;
    private int size;
    private int capacity;

    public MyHashMap() {
        capacity = DEFAULT_CAPACITY;
        buckets = new Entry[capacity];
    }

    public void put(int key, int value) {
        if (value == -1) {
            remove(key);
            return;
        }
        if (size >= capacity * LOAD_FACTOR) {
            resize();
        }
        int index = index(key);
        Entry prev = buckets[index], curr;
        while (prev != null) {
            if (prev.key == key) {
                prev.value = value;
                return;
            }
            curr = prev;
            prev = prev.next;
        }
        curr.next = new Entry(key, value);
        size++;
    }

    public int get(int key) {
        int index = index(key);
        Entry curr = buckets[index];
        while (curr != null) {
            if (curr.key == key) {
                return curr.value;
            }
            curr = curr.next;
        }
        return -1;
    }

    public void remove(int key) {
        int index = index(key);
        Entry prev = buckets[index], curr = prev;
        while (curr != null) {
            if (curr.key == key) {
                if (prev == curr) {
                    buckets[index] = curr.next;
                } else {
                    prev.next = curr.next;
                }
                size--;
                return;
            }
            prev = curr;
            curr = curr.next;
        }
    }

    private void resize() {
        Entry[] newBuckets = new Entry[2 * capacity];
        for (int i = 0; i < buckets.length; i++) {
            Entry curr = buckets[i];
            while (curr != null) {
                int newIndex = index(curr.key);
                Entry next = curr.next;
                curr.next = newBuckets[newIndex];
                newBuckets[newIndex] = curr;
                curr = next;
            }
        }
        buckets = newBuckets;
        capacity *= 2;
    }

    private int index(int