# 706 Design HashMap

提供資料結構如下

class MyHashMap {

    /** Initialize your data structure here. */
    public MyHashMap() {

    }

    /** value will always be non-negative. */
    public void put(int key, int 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) {

    }

    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    public void remove(int key) {

    }
}

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

Idea 用一ListNode[]實作。 每次put時，用key產生hashcode作為index，將key pair加入該index的linked list。 每次get時，用key產生hashcode，為index，traverse該index中存的linked list，當找到key相同的node，回傳value值。

Code

class MyHashMap {
    /*
    Followups:
    For simplicity, are the keys integers only?
    For collision resolution, can we use chaining?
    Do we have to worry about load factors?
    Can we assume inputs are valid or do we have to validate them?
    Can we assume this fits memory?
    */
    ListNode[] buckets = new ListNode[10000];

    /** Initialize your data structure here. */
    public MyHashMap() {

    }

    /** value will always be non-negative. */
    public void put(int key, int value) {
        int idx = idx(key);
        if(buckets[idx] == null)    buckets[idx] = new ListNode(-1,-1);
        ListNode prev = find(key);

        if(prev.next == null)
            prev.next = new ListNode(key,value);
        else
            prev.next.val = 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 i = idx(key);
        if (buckets[i] == null)
            return -1;
        ListNode prev = find(key);
        if(prev.next == null)    return -1;
        return prev.next.val;
    }

    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    public void remove(int key) {
        int idx = idx(key);
        if(buckets[idx] == null) return;
        ListNode prev = find(key);

        if(prev.next != null)   
            prev.next = prev.next.next;
    }

    int idx(int key) { return Integer.hashCode(key) % buckets.length;}

    ListNode find(int key){ // return the node before the node with target key, easier for implementing remove
        int idx = idx(key);
        ListNode prev = null;
        ListNode cur = buckets[idx];
        while(cur != null && cur.key != key){
            prev = cur;
            cur = cur.next;
        }

        return prev;
    }
}

class ListNode{
    int key;
    int val;
    ListNode next;

    ListNode(int k, int v){
        this.key = k;
        this.val = 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);
 */