Back to solutions

Design HashMap

EasyArrays

Implement a key-value map supporting put, get, remove.

Open problem
Constraints
  • 0 <= key, value <= 10^6
  • 1 <= q <= 10^4

Direct-address array

Time O(1) per operationSpace O(max key)

Keys are bounded by 10^6, so allocate an int array of that size initialised to -1 (the 'absent' marker). put writes the value at index key, get reads it, and remove resets it to -1. Each operation is O(1).

Key terms
sentinel value:
A reserved value (-1 here) that means 'no entry'.
direct addressing:
Indexing the table by the key itself, avoiding hashing and collisions.
class MyHashMap {
    vector<int> data;
public:
    MyHashMap() : data(1000001, -1) {}
    void put(int key, int value) { data[key] = value; }
    int get(int key) { return data[key]; }
    void remove(int key) { data[key] = -1; }
};
Step by step
  1. Allocate an int array sized max-key+1, filled with -1.
  2. put(key, value): array[key] = value.
  3. get(key): return array[key] (which is -1 when never set).
  4. remove(key): array[key] = -1.