// Runtime: 22 ms, faster than 95.40% of Java online submissions for Design HashMap.
// Memory Usage: 50 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) {
        for (Entry e = table[key % p]; e != null; e = e.next)
            if (e.key == key) {
                e.value = value;
                return;
            }

        if (size >= p) resize();

        insert(new Entry(key, value));
    }

    private void insert(Entry entry) {
        int hash = entry.key % p;

        entry.next = 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) {
                Entry next = entry.next;
                insert(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) {
        for (Entry e = table[key % p]; e != null; e = e.next)
            if (e.key == key) return e.value;

        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) {
            this.key = key;
            this.value = value;
        }
    }
}