706. Design HashMap

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

Implement the MyHashMap class:

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

哈希表，先设置一个素数Prime作为map的尺寸。
（这里设置成素数是为了减少可能的碰撞。）
创建一个Pair类记录key和value。

map初始化时需要生成一个LinkedList数组。

• hash方法计算哈希值。用key % Prime并返回。
• put方法，根据key计算其哈希值h。如果列表中有则重新设置当前Pair的value。
• get方法，根据哈希值h搜索并查找链表中的Pair，如果找到则返回Pair，否则返回-1。
• remove方法，根据哈希值h搜索并remove链表中的Pair。

class MyHashMap {
    final int PRIME = 1009;
    List<Pair>[] map;
    public MyHashMap() {
        map = new LinkedList[PRIME];
        for(int i = 0; i < PRIME; i++){
            map[i] = new LinkedList<Pair>();
        }
    }
    
    public void put(int key, int value) {
        int h = hash(key);
        for(Pair p : map[h]){
            if(p.getKey() == key){
                p.setValue(value);
                return;
            }
        }
        Pair p = new Pair(key, value);
        map[h].add(p);
    }
    
    public int get(int key) {
        int h = hash(key);
        for(Pair p : map[h]){
            if(p.getKey() == key){
                return p.value;
            }
        }
        return -1;
    }
    
    public void remove(int key) {
        int h = hash(key);
        for(Pair p : map[h]){
            if(p.getKey() == key){
                map[h].remove(p);
                return;
            }
        }
    }
    
    private int hash(int key){
        return key % PRIME;
    }
}

class Pair {
    int key;
    int value;
    public Pair(int k, int v){
        key = k;
        value = v;
    }
    
    public int getKey(){
        return key;
    }
    public int getValue(){
        return value;
    }
    public void setValue(int v){
        value = v;
    }
}

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