706. Design HashMap

Question

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:

  1. All keys and values will be in the range of [0, 1000000].
  2. The number of operations will be in the range of [1, 10000].
  3. Please do not use the built-in HashMap library.

Solutions:

  • Method 1: Array 
      class MyHashMap {
      private int[] map;
      /** Initialize your data structure here. */
      public MyHashMap() {
          this.map = new int[1000000];
          Arrays.fill(map, -1);
      }
        
      /** value will always be non-negative. */
      public void put(int key, int value) {
          map[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) {
          return map[key];
      }
        
      /** Removes the mapping of the specified value key if this map contains a mapping for the key */
      public void remove(int key) {
          map[key] = -1;
      }
  }
    
  /**
   * 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);
   */
  • Method 2: Hash bucket + collision handle + adjacent table 
      class MyHashMap {
      private static class Node{
          int key;
          int val;
          Node next;
          public Node(int key, int val){
              this.key = key;
              this.val = val;
          }
      }
      private Node[] bucket;
      private static final int size = 10000;
      /** Initialize your data structure here. */
      public MyHashMap() {
          this.bucket = new Node[size];
      }
        
      /** value will always be non-negative. */
      public void put(int key, int value) {
          int index = hash(key);
          if(bucket[index] == null) bucket[index] = new Node(-1, 0);
          Node pre = find(bucket[index], key);
          if(pre.next == null) pre.next = new Node(key, value);
          else pre.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 = hash(key);
          Node pre = find(bucket[index], key);
          if(pre == null || pre.next == null) return -1;
          return pre.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 index = hash(key);
          Node pre = find(bucket[index], key);
          if(pre == null || pre.next == null) return;
          pre.next = pre.next.next;
      }
      private Node find(Node head, int key){
          if(head == null) return head;
          Node pre = head, temp = head.next;
          while(temp != null && temp.key != key){
              pre = temp;
              temp = temp.next;
          }
          return pre;
      }
      private int hash(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);
   */