Design HashMap
Build a map from integer keys to values with an array of buckets and a short linked list in each one.
Build a map from integer keys to integer values without using any of Java's ready-made hash table classes, such as HashMapMyHashMap
: store the value under the key, replacing any old value;put(key, value) : return the key's value, or -1 if the key is not there;get(key) : take the key and its value out, if present.remove(key)
Keys and values are between 0 and 106, and there are at most 104 calls.
Example 1
Output: get(1) = 1, get(3) = -1, get(2) = 1, then get(2) = -1 after the removal
The Idea
Behind a hotel reception desk there is often a wall of small pigeonholes, one per room. A letter for room 12 goes straight into slot 12, and nobody searches the whole wall to find it. MyHashMapput(1, 1)get(1)
Walk through Example 1. After put(1, 1)put(2, 2)get(1)get(3)put(2, 1)get(2)remove(2)get(2)
How many pigeonholes does the map need? Keys go up to 106, so one slot per possible key means 1,000,001 slots, while Example 1 uses two keys. Could a much smaller wall do the job?
Say the map has 10007 slots, called buckets, numbered 0 to 10006. A key goes into the bucket given by key % 10007key % 10007
The picture shows the map after put(1, 1)put(2, 2)put(10008, 8)
So get(1)
Solution Approach
The bucket picture leaves four things to settle: why one slot per key falls short, how many buckets to use, how a bucket keeps several keys apart, and how remove
One slot per key
Why not use that wall of 1,000,001 slots? An int[1000001]int
How many buckets
Why 10007 and not a round 10000? Keys often follow a pattern. Take the 10000 keys 0, 10, 20 and so on up to 99990. With 10000 buckets, each remainder ends in 0, so the keys pile into 1000 buckets and leave the other 9000 empty. With 10007 buckets, a prime number, the same keys fill 10000 different buckets, one key each. And 10007 is a little more than the 104 calls, so there are more buckets than keys.
Keys that share a bucket
How do keys 1 and 10008 live together in bucket 1? Each bucket holds the head of its linked list, the first node, or nullputget
- The
method walks the list first. If it meets the key, it replaces that node's value. If not, it adds a new node at the head, as "new key, added at the head" shows for 10008 in the picture.put - The
method walks the list and returns the value of the node with the key, or -1 when it reaches the end.get
The walk in putput(2, 1)
Taking a node out of a list
How does removeremove
The head has no node before it, though. Removing key 10008 would need its own case that moves the bucket's head instead. A spare node placed in front of the head, called a dummy node, removes that special case: the head now has a node before it too. When the walk is done, the node after the dummy is the bucket's new head.
Java Solution
MyHashMap
: the number of buckets, 10007.SIZE : one key, its value, andNode , the link to the following node in the same bucket.next : the array of 10007 list heads. An empty bucket holdsbuckets .null : the hash function,index(key) . Keys are never negative, so the result is always a bucket from 0 to 10006.key % SIZE andput : walk the key's list, to update or add a node, or to read a value.get : unlinks the key's node. It starts from a node namedremove in front of the head, walks withdummy one node behind the node being checked, and storesprev back as the head.dummy.next : lists bucketbucketToString(i) 's nodes from head to end, fori only.main
The mainshared
public class MyHashMap {
private static final int SIZE = 10007; // a prime number of buckets
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; // keys are never negative
}
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 is there: update its value
return;
}
}
buckets[i] = new Node(key, value, buckets[i]); // new key: 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]); // sits in front of the head
for (Node prev = dummy; prev.next != null; prev = prev.next) {
if (prev.next.key == key) {
prev.next = prev.next.next; // unlink the node
break;
}
}
buckets[i] = dummy.next; // the head may have changed
}
String bucketToString(int i) {
StringBuilder sb = new StringBuilder("bucket " + i + ":");
for (Node n = buckets[i]; n != null; n = n.next) {
sb.append(" [").append(n.key).append(" = ").append(n.value).append("]");
}
return sb.toString();
}
public static void main(String[] args) {
MyHashMap map = new MyHashMap(); // Example 1
map.put(1, 1);
map.put(2, 2);
System.out.println("get(1) = " + map.get(1));
System.out.println("get(3) = " + map.get(3));
map.put(2, 1);
System.out.println("get(2) = " + map.get(2));
map.remove(2);
System.out.println("get(2) = " + map.get(2) + " after remove(2)");
MyHashMap shared = new MyHashMap(); // two keys in one bucket
shared.put(1, 1);
shared.put(2, 2);
shared.put(10008, 8);
System.out.println(shared.bucketToString(1));
System.out.println(shared.bucketToString(2));
System.out.println("get(10008) = " + shared.get(10008) + ", get(1) = " + shared.get(1));
shared.remove(1);
System.out.println(shared.bucketToString(1));
shared.remove(10008);
System.out.println(shared.bucketToString(1));
System.out.println("get(1) = " + shared.get(1) + ", get(10008) = " + shared.get(10008));
shared.put(1000000, 7); // the largest key
shared.remove(5); // a key that was never added
System.out.println(shared.bucketToString(1000000 % SIZE));
System.out.println(shared.bucketToString(5));
}
}
Running it prints:
get(1) = 1
get(3) = -1
get(2) = 1
get(2) = -1 after remove(2)
bucket 1: [10008 = 8] [1 = 1]
bucket 2: [2 = 2]
get(10008) = 8, get(1) = 1
bucket 1: [10008 = 8]
bucket 1:
get(1) = -1, get(10008) = -1
bucket 9307: [1000000 = 7]
bucket 5:
The four answers for Example 1 match its expected output: get(2)put(2, 1)remove(2)bucket 1: [10008 = 8] [1 = 1]get(10008) = 8, get(1) = 1
Then remove(1)[10008 = 8]remove(10008)
What if putgetgetremove(2)get(2) = 2 after remove(2)
The original implementation,
Complexity
Every call works on one bucket, so its cost is the length of that bucket's list.
- Time: O(1) on average per call, because at most 104 keys spread over 10007 buckets leave a node or two in each list. In the worst case it is O(n) for n stored keys, when they all share one bucket, like 1, 10008, 20015 and so on, and a call walks every node.
- Space: O(10007 + n), because the bucket array keeps its 10007 slots even when they are empty, and each of the n stored keys adds one
with a key, a value and aNode link.next
Java's own HashMap