Design HashMap

lc 706

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

To be specific, your design should include these functions:

put(key, value) : Insert a (key, value) pair into the HashMap. If the value already exists in the HashMap, update the value. get(key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key. remove(key) : Remove the mapping for the value key if this map contains the mapping for the key.

class MyHashMap {
    class ListNode {
        ListNode next;
        int val;
        int key;
        public ListNode(int val, int key) {
            this.val = val;
            this.key = key;
        }
    }
    final static int MAX_SIZE = 10000;
    ListNode[] map;

    /** Initialize your data structure here. */
    public MyHashMap() {
        map = new ListNode[MAX_SIZE];  
    }

    /** value will always be non-negative. */
    public void put(int key, int value) {
        int index = hashCode(key);
        if (map[index] == null) {
            map[index] = new ListNode(-1, -1);
        }
        ListNode prev = findPrev(map[index], key);
        if (prev.next == null) {
            prev.next = new ListNode(value, key);
        } 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 index = hashCode(key);
        if (map[index] == null) return -1;

        ListNode cur = findPrev(map[index], key);
        if (cur.next != null) {
           return cur.next.val;
        }
        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 = hashCode(key);
        if (map[index] == null) return;
        ListNode cur = findPrev(map[index], key);
        if (cur.next == null) {
            return;
        }
        cur.next = cur.next.next;
    }

    private ListNode findPrev(ListNode root, int key) {  
        ListNode prev = null;
        while (root != null && root.key != key) {
            prev = root;
            root = root.next;
        }
        return prev;
    }

    //Integer.hashCode(key)
    private int hashCode(int key) {
        String s = String.valueOf(key);
        long sum = 0;
        for (char c : s.toCharArray()) {
            sum = (sum * 33 + (int) c) % MAX_SIZE;
        }
        return (int)sum % MAX_SIZE;
    }
}

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