Design HashMap
Design a HashMap without using any built-in hash table library. Implement MyHashMap
: insert the pair, or update the value if the key already exists;put(key, value) : return the value for the key, or -1 if there is none;get(key) : remove the key and its value if present.remove(key)
Keys and values are between 0 and 106, and there are at most 104 calls. This is LeetCode 706.
Example 1
Output: get(1) = 1, get(3) = -1, get(2) = 1, then get(2) = -1 after the removal
How to Think About It
Step 1: The simplest map: one slot per key
Keys go up to 106, so an int[1000001]
Step 2: Buckets
Use a smaller array of buckets, and send each key to bucket key % SIZE
Step 3: Collisions
Different keys can land in the same bucket (1 and 10008 both go to bucket 1). So each bucket holds a small linked list of (key, value)
Step 4: The three operations
- put: walk the bucket's list; if the key is there, update its value, otherwise add a node at the head.
- get: walk the list and return the value, or -1.
- remove: unlink the node. A dummy node in front of the list means removing the first node needs no special case.
Walkthrough
The example's calls, with SIZE = 10007, so keys 1 and 2 go to buckets 1 and 2.
| Call | Bucket | What happens | Returns |
|---|---|---|---|
| put(1, 1) | 1 | not found: add node (1, 1) | |
| put(2, 2) | 2 | not found: add node (2, 2) | |
| get(1) | 1 | found | 1 |
| get(3) | 3 | empty list | -1 |
| put(2, 1) | 2 | found: value becomes 1 | |
| get(2) | 2 | found | 1 |
| remove(2) | 2 | node unlinked | |
| get(2) | 2 | empty list | -1 |
Java Solution
Each bucket is a hand-written singly linked list.
class MyHashMap {
private static final int SIZE = 10007; // a prime spreads keys evenly
private static class Node {
final int key;
int value;
Node next;
Node(int key, int value, Node next) {
this.key = key;
this.value = value;
this.next = next;
}
}
private final Node[] buckets = new Node[SIZE];
private int index(int key) {
return key % SIZE;
}
public void put(int key, int value) {
int i = index(key);
for (Node n = buckets[i]; n != null; n = n.next) {
if (n.key == key) {
n.value = value; // key exists: update
return;
}
}
buckets[i] = new Node(key, value, buckets[i]); // add at the head
}
public int get(int key) {
for (Node n = buckets[index(key)]; n != null; n = n.next) {
if (n.key == key) {
return n.value;
}
}
return -1;
}
public void remove(int key) {
int i = index(key);
Node dummy = new Node(-1, -1, buckets[i]);
for (Node prev = dummy; prev.next != null; prev = prev.next) {
if (prev.next.key == key) {
prev.next = prev.next.next; // unlink
break;
}
}
buckets[i] = dummy.next;
}
}
The original implementation,
Complexity
- Time: O(1) on average per call, since keys spread over 10007 buckets; O(n) in the worst case when all keys share one bucket.
- Space: O(SIZE + number of keys).
Java's own HashMap