DesignHashMap706.java

/**
 * 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.
 * 
 * Example:
 * MyHashMap hashMap = new MyHashMap();
 * hashMap.put(1, 1);          
 * hashMap.put(2, 2);         
 * hashMap.get(1);            // returns 1
 * hashMap.get(3);            // returns -1 (not found)
 * hashMap.put(2, 1);          // update the existing value
 * hashMap.get(2);            // returns 1 
 * hashMap.remove(2);          // remove the mapping for 2
 * hashMap.get(2);            // returns -1 (not found) 
 * 
 * Note:
 * All keys and values will be in the range of [0, 1000000].
 * The number of operations will be in the range of [1, 10000].
 * Please do not use the built-in HashMap library.
 */

public class DesignHashMap706 {
    class MyHashMap {
        private Integer[] cache = new Integer[1000000];
        
        /** Initialize your data structure here. */
        public MyHashMap() {
        }
        
        /** value will always be non-negative. */
        public void put(int key, int value) {
            cache[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) {
            if (cache[key] == null) return -1;
            return cache[key];
        }
        
        /** Removes the mapping of the specified value key if this map contains a mapping for the key */
        public void remove(int key) {
            cache[key] = null;
        }
    }
  

    class MyHashMap2 {

        private static final int K = 100000;
        private ListNode[] cache = new ListNode[100000];
        
        /** Initialize your data structure here. */
        public MyHashMap() {
        }
        
        /** value will always be non-negative. */
        public void put(int key, int value) {
            int k = key % K;
            if (cache[k] == null) {
                cache[k] = new ListNode(key, value);
            } else {
                ListNode head = cache[k];
                while (true) {
                    if (head.key == key) {
                        head.value = value;
                        return;
                    }
                    if (head.next == null) {
                        ListNode newNode = new ListNode(key, value);
                        head.next = newNode;
                        newNode.prev = head;
                        return;
                    }
                    head = head.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) {
            int k = key % K;
            if (cache[k] == null) return -1;
            ListNode head = cache[k];
            while (true) {
                if (head.key == key) {
                    return head.value;
                }
                if (head.next == null) {
                    return -1;
                }
                head = head.next;
            }
        }
        
        /** Removes the mapping of the specified value key if this map contains a mapping for the key */
        public void remove(int key) {
            int k = key % K;
            if (cache[k] == null) return;
            ListNode head = cache[k];
            while (true) {
                if (head.key == key) {
                    if (head.prev == null) {
                        cache[k] = head.next;
                    } else {
                        if (head.next != null) head.next.prev = head.prev;
                        head.prev.next = head.next;
                    }
                    return;
                }
                if (head.next == null) {
                    return;
                }
                head = head.next;
            }
        }
        
        class ListNode {
            ListNode prev;
            ListNode next;
            Integer key;
            Integer value;
            ListNode (int key, int value) {
                this.key = key;
                this.value = value;
            }
        }
    }


    class MyHashMap3 {

        private static final int K = 100000;
        private TreeNode[] cache = new TreeNode[100000];
        
        /** Initialize your data structure here. */
        public MyHashMap() {
        }
        
        /** value will always be non-negative. */
        public void put(int key, int value) {
            int k = key % K;
            if (cache[k] == null) {
                cache[k] = new TreeNode(key, value);
            } else {
                TreeNode head = cache[k];
                while (true) {
                    if (head.key == key) {
                        head.value = value;
                        return;
                    }
                    if (head.key > key) {
                        if (head.left == null) {
                            head.left = new TreeNode(key, value);
                            return;
                        }
                        head = head.left;
                    } else {
                        if (head.right == null) {
                            head.right = new TreeNode(key, value);
                            return;
                        }
                        head = head.right;
                    }
                    if (head == null) return;
                }
            }
        }
        
        /** 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 k = key % K;
            if (cache[k] == null) return -1;
            TreeNode head = cache[k];
            while (true) {
                if (head.key == key) {
                    return head.value;
                }
                if (head.key > key) {
                    if (head.left == null) {
                        return -1;
                    }
                    head = head.left;
                } else {
                    if (head.right == null) {
                        return -1;
                    }
                    head = head.right;
                }
                if (head == null) 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 k = key % K;
            cache[k] = delete(cache[k], key);
        }
    
        private TreeNode delete(TreeNode head, int key) {
            if (head == null)  return head;
    
            if (key < head.key) {
                head.left = delete(head.left, key);
            } else if (key > head.key) {
                head.right = delete(head.right, key);
            } else {
                if (head.left == null) {
                    return head.right;
                } else if (head.right == null) {
                    return head.left;
                }
    
                head.key = minValue(head.right);
                head.right = delete(head.right, head.key);
            }
    
            return head;
        }
     
        private int minValue(TreeNode head) {
            int minv = head.key;
            while (head.left != null) {
                minv = head.left.key;
                head = head.left;
            }
            return minv;
        }
        
        class TreeNode {
            TreeNode left;
            TreeNode right;
            Integer key;
            Integer value;
            TreeNode (int key, int value) {
                this.key = key;
                this.value = value;
            }
        }
    }

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

}