Implement a Hash Table Coding Interview Question | Skilled.dev
Interview Question

Implement a Hash Table

Course launching November 17, 2020

Follow me on YouTube for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

Your subscription could not be saved. Please try again.
Your subscription was successful! 🤓
Loading...

Every major programming language has their own native implementation of a hash table. For example, in JavaScript we can simply use an object as a hash table, and Python's implementation is the Dictionary data type.

To understand how a hash table works, we'll build one from scratch and implement three common hash table methods (get, insert, remove) in constant O(1) time. We will also implement our own and need to handle collisions with buckets.

We can see that regardless of how much data we add to the hash map, the number of operations required to lookup, insert, and remove never increases, making it constant time O(1), assuming we have sufficient size.

The hash tables we get natively from our programming languages will resize themselves to make sure that access remains O(1) based on the number of items in the table. For simplicity, we'll just initialize it to a fixed size. This will also allow us to play with different values for the size to see how they impact the speed of lookups.

Our implementation will take the following form:

class HashTable {
  constructor(size) {
    this.size = size;
    this.table = [];
  }

  get(key) {
    // get a value by key
  }
  insert(key, value) {
    // add/upate a value at a key
  }
  remove(key) {
    // remove a value by key
  }
  hash(key) {
    // our custom hash function
  }
}

hash(key)

Our hash function will convert a string key to an integer which maps to an index in the table array. All characters have a universally recognized integer value based on different standards such as ASCII or Unicode.

We will sum the values of the string's integer code to get the index for our table array and normalize it to the size.

hash(key) {
  let hash = 0;

  for (let i = 0; i < key.length; i++) {
    hash = (hash + key.charCodeAt(i)) % this.size;
  }

  return hash;
}

get(key)

To get an item in our hash table, we pass it the key we want to lookup. We call the hash function with the key, and it returns the index for the bucket that the item is located in our table.

If there is a bucket that exists for the index, we loop through it until we find the item matching our key.

If there is no bucket or no matching key, we return undefined.

get(key){
  const index = this.hash(key);
  const bucket = this.table[index];

  // Check if the key exists in the bucket, and return its value if found
  if (bucket) {
    for (let i = 0; i < bucket.length; i++) {
      if(bucket[i].key === key) {
        return bucket[i].value;
      }
    }
  }

  // Return undefined if the key is not found
  return undefined;
}

insert(key, value)

The insert function is how we add or update items in our hash table. First we check if the bucket exists, and if doesn't we initialize it. Then we check if there is already an existing value for that key. If there is, we iterate through the bucket until we find it and then replace it. Otherwise, we add the item to that bucket.

insert(key, value) {
  const index = this.hash(key);

  // Initialize our bucket if it doesn't exist yet
  if (!this.table[index]) {
    this.table[index] = [];
  }

  const currentValue = this.get(key);

  // If the item already existed, we need replace its value
  if (typeof currentValue !== 'undefined') {
    const bucket = this.table[index];

    // Find the key in the bucket and update its value
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i].key === key) {
        bucket[i].value = value;
      }
    }
  } else {
    // Add the new key-value pair
    this.table[index].push({ key, value });
  }
}

remove(key)

We're going to write a very simple remove method. We set the value to undefined which is equivalent to being removed to the end-user of the hash table.

remove(key) {
  // On the user's side, an item is viewed as not existing if it returns undefiend.
  // For simplicity, we will remove a key-value by setting it to undefined.
  const value = this.get(key);
  this.insert(key, undefined);

  // Return the value (will be undefined if it didn't exist)
  return value;
}

Complete Hash Table Implementation

You can use the implementation in a REPL or see the completed code below:

class HashTable {
  constructor(size) {
    this.size = size;
    this.table = [];
  }

  get(key) {
    const index = this.hash(key);
    const bucket = this.table[index];

    if (bucket) {
      for (let i = 0; i < bucket.length; i++) {
        if (bucket[i].key === key) {
          return bucket[i].value;
        }
      }
    }

    return undefined;
  }

  insert(key, value) {
    const index = this.hash(key);

    if (!this.table[index]) {
      this.table[index] = [];
    }

    const currentValue = this.get(key);

    if (typeof currentValue !== 'undefined') {
      const bucket = this.table[index];

      for (let i = 0; i < bucket.length; i++) {
        if (bucket[i].key === key) {
          bucket[i].value = value;
        }
      }
    } else {
      this.table[index].push({ key, value });
    }
  }

  remove(key) {
    const value = this.get(key);
    this.insert(key, undefined);

    return value;
  }

  hash(key) {
    let hash = 0;

    for (let i = 0; i < key.length; i++) {
      hash = (hash + key.charCodeAt(i)) % this.size;
    }

    return hash;
  }
}

Wrap Up

If we set the size to 1, then every item would have a collision which degrades to our O(n) worst case. However, if we set the size sufficiently large relative to the number of items we add, there will be minimal collisions, making all the operations O(1) time. The hash operates in constant time, and then each method would iterate through a very small number of buckets relative to the total size n.

You can try tuning these values yourself in the REPL to visualize the impact.

Prev
Hash Tables
Next
Catch the Hacker
Loading...

Table of Contents