/**
1. java 数组 + 拉链法
*/

class MyHashMap {

    /** Initialize your data structure here. */

    class Node{
        int key, val;
        Node next;
        public Node(int key, int val){
            this.key = key;
            this.val = val;
        }
    }

    static final int maxN = 1331;
    Node[] data;

    public MyHashMap() {
        this.data = new Node[maxN];
    }

    /** value will always be non-negative. */
    public void put(int key, int value) {
        int index = key % maxN;
        if (data[index] == null){
            data[index] = new Node(key, value);
        } else {
            append(data[index], key, value);
        }
    }

    void append(Node head, int key, int value){
        Node prev = head;
        while(head != null){
            if (head.key == key){
                head.val = value;
                return;
            }

            prev = head;
            head = head.next;
        }
        prev.next = new Node(key, value);
    }

    /** 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 index = key % maxN;
        Node node = data[index];
        if (node == null) return -1;
        while (node != null){
            if (node.key == key) return node.val;
            node = node.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 index = key % maxN;
        Node node = data[index];
        if (node == null) return;
        Node prev = node;
        while (node != null){
            if (node.key == key){
                if (prev == node) data[index] = node.next;
                else prev.next = node.next;
                return;
            }
            prev = node;
            node = node.next;
        }
    }
}

/**
 * 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);
 */