Interview Question
Share Lesson

# Implement a Hash Table

Every major programming language has its 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`) that operate in constant O(1) time. We will also implement our own and need to handle collisions by using buckets.

We will see that regardless of how much data we add to the hash table, the number of operations required to lookup, insert, and remove stays very small, making it constant time O(1) — assuming we have sufficient size.

The native hash table implementations provided by our programming languages will resize themselves based on the number of items in the table to make sure that access remains O(1). 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:

`` ``

## 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 encoding for each of the key's characters to create an index in the `table` array and normalize it by the `size` so that we never get an index outside the array's length.

`` ``

## get(key)

To `get` an item in our hash table, we pass it the `key` we want to look up. 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 no `bucket` or no matching `key`, we return `undefined` because we're trying to access an item that does not exist.

If there is a `bucket` that exists for the `index`, we iterate through the bucket's items it until we find the item matching our `key`.

`` ``

## 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.

`` ``

## remove(key)

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

`` ``

## Complete Hash Table Implementation

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

`` ``

## 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.

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