Design HashMap

Problem Statement

The task is to implement a custom HashMap class, MyHashMap, without using any existing hash table libraries provided by the programming language. The custom class should support the basic operations of a typical hash map, which include:

• Initializing the hash map.
• Adding a key-value pair to the hash map. If the key already exists, the value should be updated.
• Retrieving the value associated with a specific key. If the key does not exist in the map, it should return -1.
• Removing a key-value pair from the hash map using the key.

The implementation should handle these operations efficiently even with constraints on key and value sizes.

Examples

Example 1

Input

["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]

Output

[null, null, null, 1, -1, null, 1, null, -1]

Explanation

MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // The map is now [[1,1]]
myHashMap.put(2, 2); // The map is now [[1,1], [2,2]]
myHashMap.get(1); // return 1, The map is now [[1,1], [2,2]]
myHashMap.get(3); // return -1 (i.e., not found), The map is now [[1,1], [2,2]]
myHashMap.put(2, 1); // The map is now [[1,1], [2,1]] (i.e., update the existing value)
myHashMap.get(2); // return 1, The map is now [[1,1], [2,1]]
myHashMap.remove(2); // remove the mapping for 2, The map is now [[1,1]]
myHashMap.get(2); // return -1 (i.e., not found), The map is now [[1,1]]

Constraints

• 0 <= key, value <= 106
• At most 104 calls will be made to put, get, and remove.

Approach and Intuition

By analyzing the requirements and the example provided, we can infer a strategy on how to implement each functionality of the MyHashMap:

1. Initializing the Hash Map

• The MyHashMap() constructor will initialize the map. This could involve setting up an underlying data structure to store the key-value pairs.

2. Adding a Key-Value Pair

• The put(int key, int value) method:
  1. Check if the key exists in the current map.
  2. If the key exists, update the value.
  3. If the key does not exist, add the new key-value pair.

3. Retrieving a Value by Key

• The get(int key) method:
  1. Check if the key exists in the map.
  2. If the key exists, return the associated value.
  3. If the key is not found, return -1.

4. Removing a Key

• The remove(int key) method:
  1. Check if the key exists.
  2. If it does, remove the key and its associated value from the map.

Through the operations described above, each action the MyHashMap class can perform has a clear set of steps, managing efficiency by directly addressing each case based on the existence of keys. This level of management is crucial, especially given the potential for high-volume operations, as indicated by the constraints where up to 10,000 operations can be made to put, get, and remove. Thus, the choice of the underlying data structure for implementation matters significantly, balancing between a trade-off of initial memory allocation and operational time complexity.

Solutions

class Tuple<X, Y> {
  public X firstElement;
  public Y secondElement;

  public Tuple(X first, Y second) {
    this.firstElement = first;
    this.secondElement = second;
  }
}

class Storage {
  private List<Tuple<Integer, Integer>> elements;

  public Storage() {
    this.elements = new LinkedList<Tuple<Integer, Integer>>();
  }

  public Integer retrieve(Integer key) {
    for (Tuple<Integer, Integer> item : this.elements) {
      if (item.firstElement.equals(key))
        return item.secondElement;
    }
    return -1;
  }

  public void insertOrUpdate(Integer key, Integer value) {
    boolean isUpdated = false;
    for (Tuple<Integer, Integer> item : this.elements) {
      if (item.firstElement.equals(key)) {
        item.secondElement = value;
        isUpdated = true;
      }
    }
    if (!isUpdated)
      this.elements.add(new Tuple<Integer, Integer>(key, value));
  }

  public void delete(Integer key) {
    for (Tuple<Integer, Integer> item : this.elements) {
      if (item.firstElement.equals(key)) {
        this.elements.remove(item);
        break;
      }
    }
  }
}

class SimpleHashMap {
  private int numBuckets;
  private List<Storage> buckets;

  public SimpleHashMap() {
    this.numBuckets = 2069;
    this.buckets = new ArrayList<Storage>();
    for (int i = 0; i < this.numBuckets; ++i) {
      this.buckets.add(new Storage());
    }
  }

  public void put(int key, int value) {
    int bucketIndex = key % this.numBuckets;
    this.buckets.get(bucketIndex).insertOrUpdate(key, value);
  }

  public int get(int key) {
    int bucketIndex = key % this.numBuckets;
    return this.buckets.get(bucketIndex).retrieve(key);
  }

  public void remove(int key) {
    int bucketIndex = key % this.numBuckets;
    this.buckets.get(bucketIndex).delete(key);
  }
}