// Runtime: 23 ms, faster than 94.80% of Java online submissions for Design HashMap.
// Memory Usage: 50.9 MB, less than 97.30% of Java online submissions for Design HashMap.
class MyHashMap {
    int p;
    int size;
    Entry[] table;

    /** Initialize your data structure here. */
    public MyHashMap() {
        p = 37;
        size = 0;
        table = new Entry[p];
    }

    /** value will always be non-negative. */
    public void put(int key, int value) {
        int hash = key % p;
        Entry entry = table[hash];

        while (entry != null) {
            if (entry.key == key) {
                entry.value = value;
                return;
            }
            entry = entry.next;
        }

        if (size >= p) {
            resize();
            hash = key % p;
        }

        entry = new Entry(key, value, table[hash]);
        table[hash] = entry;
        size++;
    }

    private void resize() {
        Entry[] oldTable = table;

        p = 2*p + 1;
        size = 0;
        table = new Entry[p];

        for (Entry entry: oldTable) {
            while (entry != null) {
                put(entry.key, entry.value);
                entry = entry.next;
            }
        }
    }

    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    public int get(int key) {
        int hash = key % p;
        Entry entry = table[hash];

        while (entry != null) {
            if (entry.key == key) return entry.value;
            entry = entry.next;
        }

        return -1;
    }

    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    public void remove(int key) {
        int hash = key % p;
        Entry entry = table[hash];

        Entry previous = null;
        while (entry != null) {
            if (entry.key == key) {
                if (previous == null) table[hash] = entry.next;
                else previous.next = entry.next;

                size--;
                return;
            }

            previous = entry;
            entry = entry.next;
        }
    }

    class Entry {
        public int key;
        public int value;
        public Entry next;

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