Introduction
Hash maps are maps that use hash sets to store pairs of key values. Implementations of hash maps are very similar to hash sets.
Type | Get | Put | Deletion |
---|---|---|---|
Hash Map | O(1) | O(1) | O(1) |
Class
Our implementation of a Hash Map will be very similar to a Hash Set except instead of storing values, we will be storing a pair consisting of a key and value.
public class Pair { int key; String value; public Pair(int key, String value) { this.key = key; this.value = value; } }
Inside our implementation of a hash map we will store the buckets using an array of linked lists of pairs, the number of buckets, and the number of elements in the set.
public class HashMap { public LinkedList<Pair>[] buckets; public int bucketsSize = 10; public int size = 0; public static final double COLLISION_CHANCE = 0.3; public HashMap() { buckets = new LinkedList[10]; for (int i = 0; i < bucketsSize; i++) { buckets[i] = new LinkedList<Pair>(); } size = 0; } }
Since most of the implementation is the same as Hash Set, we will skip most of the explanations.
Resize
Resizing is the same as a Hash Set, but we copy the pairs instead of only the values.
public void resize() { // Double number of buckets. int newBucketsSize = bucketsSize * 2; LinkedList<Pair>[] newBuckets = new LinkedList[newBucketsSize]; // Create new buckets. for (int i = 0; i < newBucketsSize; i++) { newBuckets[i] = new LinkedList<Pair>(); } // Copy elements over and use new hashes. for (int i = 0; i < bucketsSize; i++) { for (Pair y : buckets[i]) { int hash = getHash(y.key, newBucketsSize); newBuckets[hash].push(y); } } // Set new buckets. buckets = newBuckets; bucketsSize = newBucketsSize; }
Put
To put a key value pair in a hash map, we first check if the key exists in a pair in the Hash Map. If the key already exists, we update the value of the pair. Otherwise, we create a new key value pair in the map.
public boolean put(int key, String value) { // Get hash of x. int hash = getHash(key, bucketsSize); // Get current bucket from hash. LinkedList<Pair> curBucket = buckets[hash]; // Check if bucket contains key. for(Pair p: curBucket){ // Overwrite value if key already exists and return false. if(p.key == key){ p.value = value; return false; } } // Otherwise, add pair to the bucket. curBucket.push(new Pair(key, value)); // Resize if the collision chance is higher than threshold. if ((float) size / bucketsSize > COLLISION_CHANCE) { resize(); } size++; return true; }
Get
To get the value from a hash set from a key, we check if the key-value exists and if it does we return the value. Otherwise, we return null.
public String get(int key) { // Get hash of x. int hash = getHash(key, bucketsSize); // Get current bucket from hash. LinkedList<Pair> curBucket = buckets[hash]; // Look for key in bucket. for(Pair p: curBucket){ // Return value if keys are equal. if(p.key == key){ return p.value; } } // Return null if not found. return null; }
Remove
To remove a key-value pair, we first search for the key-value pair in the map and remove it from its bucket.
public boolean remove(int key) { // Get hash of x. int hash = getHash(key, bucketsSize); // Get bucket from hash. LinkedList<Pair> curBucket = buckets[hash]; // Remove x from bucket and return if operation successful. for(Pair p: curBucket){ // Remove pair from bucket if keys match. if(p.key == key){ return curBucket.remove(p); } } // Return false if key not found in map. return false; }
Exercises
- Create a hash map for a contact list (phone numbers as keys, names as value).