Hash Map

Introduction

Prerequisites: Map, Hash Set

Source on GitHub

Hash maps are maps that use hash sets to store pairs of key values. Implementations of hash maps are very similar to hash sets.

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

1. Create a hash map for a contact list (phone numbers as keys, names as value).