add one more solution for 706

fishercoder1534 · fishercoder1534 · commit e5af0c1dd365 · 2021-03-07T11:30:24.000-08:00
diff --git a/src/main/java/com/fishercoder/solutions/_706.java b/src/main/java/com/fishercoder/solutions/_706.java
@@ -68,13 +68,99 @@ class ListNode {
                 }
             }
         }
+    }
+
+    public static class Solution2 {
+
+        public static class MyHashMap {
+            /**
+             * Considering the given constraints for this problem on LeetCode, load factors and resizing/rehashing are not considered. Thus an EASY problem.
+             * <p>
+             * inspired by: https://leetcode.com/problems/design-hashmap/discuss/225312/hashmaparraylinkedlistcollision
+             */
+            class Node {
+                /**
+                 * We need to have both key and val in this ListNode because all values input key are hashed to the same bucket, so we need its original key
+                 * to be a differentiator within this bucket.
+                 */
+                int val;
+                int key;
+                Node next;
+
+                public Node(int key, int val) {
+                    this.key = key;
+                    this.val = val;
+                }
+            }
+
+            Node[] nodes;
+            int SIZE = 1000000;
+
+            /**
+             * Initialize your data structure here.
+             */
+            public MyHashMap() {
+                nodes = new Node[SIZE];
+            }
+
+            /**
+             * value will always be non-negative.
+             */
+            public void put(int key, int value) {
+                int index = getHashedKey(key);
+                Node head = nodes[index];
+                Node tmp = head;
+                while (tmp != null) {
+                    if (tmp.key == key) {
+                        tmp.val = value;
+                        return;
+                    }
+                    tmp = tmp.next;
+                }
+                Node newHead = new Node(key, value);
+                newHead.next = head;
+                nodes[index] = newHead;
+            }
+
+            private int getHashedKey(int key) {
+                return Integer.hashCode(key) % 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);
- */
+            /**
+             * 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) {
+                Node head = nodes[getHashedKey(key)];
+                Node tmp = head;
+                while (tmp != null && tmp.key != key) {
+                    tmp = tmp.next;
+                }
+                if (tmp == null) {
+                    return -1;
+                }
+                if (tmp.key == key) {
+                    return tmp.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) {
+                /**We can just set the value of this key to -1 since the constraint for this problem is that all values are >= 0*/
+                Node node = nodes[getHashedKey(key)];
+                Node tmp = node;
+                Node pre = new Node(-1, -1);
+                pre.next = tmp;
+                while (tmp != null) {
+                    if (tmp.key == key) {
+                        tmp.val = -1;
+                        return;
+                    }
+                    tmp = tmp.next;
+                }
+            }
+        }
     }
 }
diff --git a/src/test/java/com/fishercoder/_706Test.java b/src/test/java/com/fishercoder/_706Test.java
@@ -0,0 +1,25 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._706;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _706Test {
+    private static _706.Solution2.MyHashMap myHashMap;
+
+    @Test
+    public void test1() {
+        myHashMap = new _706.Solution2.MyHashMap();
+
+        myHashMap.put(1, 1);
+        myHashMap.put(2, 2);
+        assertEquals(1, myHashMap.get(1));
+        assertEquals(-1, myHashMap.get(3));
+        myHashMap.put(2, 1);
+        assertEquals(1, myHashMap.get(2));
+        myHashMap.remove(2);
+        assertEquals(-1, myHashMap.get(2));
+    }
+
+}
