Data structures 101: Implement hash tables in JavaScript

Ever wondered how Google Maps finds the nearest coffee shop almost instantly? Behind the scenes, hash tables are doing the heavy lifting, enabling quick data lookups that feel like magic.

Mastering hash tables isn’t just about writing efficient code; it’s a must-have skill for cracking coding interviews and building scalable systems.

We’ll continue our data structures series with one of the top data structures: the hash table. In this blog, we’ll learn what hash tables are, what they are used for, and how to implement them in JavaScript.

What is a hash table?#

A hash table (often called a hash map) is a data structure that maps keys to values using a hash function. Hash tables efficiently combine lookup, insert, and delete operations. The key is sent to a hash function that performs arithmetic operations on it. The result (called the hash value or hash) is an index of the key-value pair. This allows for fast access to values associated with a specific key.

Pro tip: Think of this as a signature on a block of data that allows us to search in constant time. A hash table operates like a dictionary that we can use to map from the hash to the desired data.

This data structure is widely used in computer software, particularly for associative arrays, database indexing, caches, and sets. Usually, this operation returns the same hash for a given key.

The performance of a hash table depends on three fundamental factors: the hash function, the size of the hash table, and the collision handling method.

Hash tables are made up of two parts:

• Data storage object: An object with a table where the data is stored. The array holds all the key-value entries in the table. The size of the array should be set according to the amount of data expected.

• Hash function (or mapping function): This function determines the index of our key-value pair. It should be a one-way function and produce a different hash for each key.

Note: In JavaScript, hash tables are generally implemented using arrays as they provide access to elements in constant time.

Now that we’ve seen how hash tables work, let’s explore where they shine in real-world applications.

Uses of hash tables#

Hash tables provide constant-time access to elements, so they are highly recommended for algorithms that prioritize search and data retrieval operations. Hashing is ideal for large amounts of data, as it takes a constant amount of time to perform insertion, deletion, and search.

In terms of time complexity, the operation is O(1)O(1). On average, a hash table lookup is more efficient than other table lookup data structures. Some common uses of hash tables are ad follows:

• Database indexing: Hash tables are used to quickly search for records.

• Caches: Hash tables store frequently accessed data for fast retrieval.

• Associative arrays: Many programming languages, including JavaScript, use hash tables to implement associative arrays (objects).

• Unique data representation: Hash tables can efficiently store unique keys, ensuring data integrity and fast retrieval.

• Lookup in an unsorted array: A hash table provides a faster alternative to linear search when checking for the existence of an element in an unsorted dataset.

• Lookup in sorted array using binary search: Hash tables can complement binary search in sorted arrays by acting as an index or cache for rapid lookups.

Hash tables vs. trees#

Hashing and trees perform similar jobs, but various factors in your program determine when to use one over the other.

Trees are more useful when an application needs to order data in a specific sequence. Hash tables are the smarter choice for randomly sorted data due to its key-value pair organization.

Hash tables can perform in constant time, while trees usually work in O(log⁡n)O(\log n). In the worst-case scenario, the performance of hash tables can be as low as O(n)O(n). An AVL tree, however, would maintain O(log⁡n)O(\log n) in the worst case.

An efficient hash table requires a hash function to distribute keys. A tree is simpler, since it accesses extra space only when needed and does not require a hash function. Here’s the table comparing hash tables and trees:

What is a hash function?#

A hash function is a method or function that takes an item’s key as input, assigns a specific index to that key, and returns the index whenever the key is looked up. This operation usually returns the same hash for a given key. A good hash function should be efficient to compute and uniformly distribute keys.

Hash functions help to limit the range of the keys to the boundaries of the array, so we need a function that converts a large key into a smaller key. This is the job of the hash function.

Common hash functions#

There are many kinds of hash functions that have different uses. Let’s take a look at some of the most common hash functions used in modern programming.

• Arithmetic modular: In this approach, we take the modular of the key with the list/array size: index=key MOD tableSize. So, the index will always stay between 0 and tableSize - 1.

• Truncation: Here, we select a part of the key as the index rather than the whole key. We can use a mod function for this operation, although it does not need to be based on the array size.

• Folding: This approach involves dividing the key into small chunks and applying a different arithmetic strategy at each chunk.

Hash table collisions#

Sometimes, a hash function can generate the same index for more than one key. This scenario is referred to as a hash collision. Collisions are a problem because every slot in a hash table is supposed to store a single element.

Best collision handling strategies in hash tables#

When two keys collide in a hash table, it’s like two cars fighting over the same parking spot. Here’s how we keep the traffic flowing smoothly.

• Linear probing: Linear probing works by skipping over an index that is already filled. It could be achieved by adding an offset value to an already computed index. If that index is also filled, add it again, and so on.
  One drawback of using this strategy is that if you don’t pick an offset wisely, you can jump back to where you started and miss out on so many possible positions in the array.

• Chaining: In the chaining strategy, each slot of our hash table holds a pointer to another data structure, such as a linked list or a tree. Every entry at that index will be inserted into the linked list for that index.
  As you can see, chaining allows us to hash multiple key-value pairs at the same index in constant time (insert at the head for linked lists). This strategy greatly increases performance but is costly in terms of space.

• Resizing the array or list: Another way to reduce collisions is to resize the list or array. We can set a threshold, and once it is crossed, we can create a new table that is double the size of the original. All we have to do then is to copy the elements from the previous table. Resizing the list or array significantly reduces collisions, but the function itself is costly. Therefore, we need to be careful about the threshold we set. A typical convention is to set the threshold at 0.6, which means that when 60% of the table is filled, the resize operation needs to take place.

• Double hashing: In double hashing, there are two hash functions. The second hash function provides an offset value in case the first function causes a collision. Double hashing can find the next free slot faster than a linear probing approach. This is useful for applications with a smaller hash table. The following function is an example of double hashing:

How to implement a hash table in JavaScript#

To implement a hash table using JavaScript, we'll do three things: create a hash table class, add a hash function, and implement a method for adding key/value pairs to our table.

The HashTable class#

First, let’s create the HashTable class.

The constructor contains an object in which we’re going to store the values, their lengths, and the entire size of the hash table—that is, how many buckets the hash table contains. We’ll store our data in these buckets.

The calculateHash() function#

Next, we have to implement a simple hashing function inside the HashTable class.

In the above code:

• The key is converted to a string using toString(), ensuring that non-string keys (like numbers) are also hashable. The length of the string is divided by the size property of the hash table, and the remainder (%) is returned as the hash.

This ensures that the hash value is within the range of 0 to size - 1.

The add() function#

Finally, we need a method inside the HashTable class to insert key/value pairs. Take a look at the code and see this in action:

In the above code:

• The calculateHash() method is called to compute the hash for the given key. This hash determines the bucket (or slot) where the key-value pair will be stored.

• If the hash does not exist as a property in the values object, a new empty object is created at that hash location.

• If the specific key does not exist within the bucket (object) at the hash location, the length property of the hash table is incremented, indicating a new unique key.

• The key-value pair is added to the hash table at the appropriate hash bucket. If the key already exists, its value is updated with the new value.

The search() function#

Searching in a hash table is very fast. Unlike with an array, where we have to go through all of the elements until we reach the item we need, with a hash table, we simply get the index.

Let’s add the complete code for our hash table implementation below.

Similar to the add() function, the search() function:

• Calculates the hash for the given key using the calculateHash() method. This identifies the bucket where the key might be stored.

• Checks if the hash exists in the hash table using hasOwn() and if the specific key exists within that hash bucket. 

  • If both the hash and key exist, the function retrieves and returns the value associated with the key. 

  • If either the hash or key does not exist, the function returns null to indicate that the key was not found.

The delete() function#

Now, let's look at how the delete() function works to remove key/value pairs from the hash table:

In the above code:

• The delete() function begins by calculating the hash of the provided key using the calculateHash() method. This determines the location of the key in the hash table. 

• The delete() function checks if the hash exists in the hash table and if the specified key exists within that hash bucket. If the key is found, we proceed to delete it. 

• The delete operator is used to remove the key/value pair from the corresponding hash bucket. 

• After successfully deleting the key, the function decrements the length property of the hash table to reflect the removal of the key/value pair. 

• If the hash bucket becomes empty after the key is removed (i.e., no other keys remain under that hash), the entire hash bucket is deleted to free up memory and keep the hash table clean.

• If the key was successfully deleted, the function returns true. If the key doesn’t exist in the hash table, the function returns false.

The complete code#

That completes our basic JavaScript hash table implementation.

Note that we used an Object to represent our hash table. Objects in JavaScript are actually implemented using hash tables themselves! Many programming languages also provide support for hash tables either as built-in associative arrays or as standard library modules.

Want to master data structures? Grow your skill set further with our Data Structures for Coding Interviews in JavaScript course. Master key structures, practical implementations, and essential concepts like Big O notation to excel in your interviews and beyond.

Implementing a hash table with bucket chaining#

Now, let’s see another implementation using bucket chaining. The chaining strategy, along with the resize operation, is used to avoid collisions in the table.

All elements with the same hash key will be stored in an array at that index. In data structures, these arrays are called buckets. The size of the hash table is set as n∗mn∗m where nn is the number of keys it can hold, and mm is the number of slots each bucket contains.

The HashEntry class#

We will start by building a simple HashEntry class. As discussed earlier, a typical hash entry consists of three data members: the key, the value and the reference to a new entry.

The constructor of the HashEntry class initializes an entry to store a key-value pair. It also includes a next property to handle collisions by linking entries in the same bucket. This structure is designed to store data efficiently in a hash table.

The revised HashTable class#

Now, we’ll create the HashTable class, which is a collection of HashEntry objects. We’ll keep track of the number of slots in the table and the current size of the hash table. These variables​ will come in handy when we need to resize the table.

The HashTable class provides the basic structure and functionality of a hash table. Here's a breakdown of the code:

• The constructor initializes the hash table. We specify the total number of slots (buckets) in the hash table, which will hold the entries. We keep track of the current number of entries in the hash table. It is used to monitor when resizing might be needed. We create an array to store the entries. Each entry will be a HashEntry object. We initialize all slots in the bucket array to null. This ensures the hash table starts empty.

• The get_size() function returns the number of entries currently in the hash table. It helps track how many elements are stored and monitor when resizing is required.

• The isEmpty() function checks if the hash table is empty by comparing the size to 0. We return true if the hash table has no entries; otherwise, false.

The getIndex() function#

The next thing we need is a hash function. In the previous lessons, we tried out some different approaches. For our implementation, we will simply take the modular of the key with the total size of the hash table (slots).

The getIndex method computes the index for a key using the modulo operation, ensuring the key is mapped to a valid slot in the hash table. This is a foundational step in implementing hash table operations like add, search, and delete.

The next steps are to implement the operations of search, insertion, and deletion one by one.

The search() function#

The search() function retrieves the value for a given key by traversing the chain at the computed index. 

The search() function is used to locate a specific key within the hash table. It takes the key as input and uses the getIndex() method to compute the index where the key should be located. The function then traverses the linked list at that index, comparing the key of each entry until it finds a match or reaches the end of the list.

The add() function#

The add() function adds a new key-value pair or updates an existing key’s value, resolving collisions using chaining.

The add() function inserts a new key-value pair into the hash table. It first calculates the hash index for the key using getIndex(). If the bucket at the index is empty, it directly places the new entry there. Otherwise, it traverses the chain to either update the value for an existing key or add the new entry at the end.

The delete() function#

The delete() function removes a key-value pair by adjusting chain pointers, ensuring no dangling references.

The delete() function removes a key-value pair from the hash table. It calculates the index using the getIndex() function and traverses the chain at that index. If the key is found, it adjusts the pointers to bypass the entry and decrease the size. If the key is not found, the function returns false.

The complete code#

This completes our basic JavaScript hash table implementation with bucket chaining. Let’s run the complete code:

Note that we used a HashEntry class to represent each entry and an array to represent the hash table’s buckets. Many programming languages provide built-in support for hash tables, either as associative arrays or standard library modules, but this implementation demonstrates how a hash table can be built from scratch using JavaScript.

Comparison of hash table implementations#

In general, bucket chaining provides better overall performance and flexibility, especially in cases where collision management is a concern. Without bucket chaining, the hash table is more straightforward and efficient for simple use cases with low collision rates, but may suffer in more complex situations. Here is a detailed comparison table that highlights the differences between the hash function without bucket chaining and the hash function with bucket chaining:

Wrapping up and interview questions#

Hash tables aren’t just an academic concept—they power some of the fastest applications in the world. So, here’s your challenge: Try re-implementing a common JavaScript feature (like object key lookups) using a custom hash table. It’ll be tough, but you’ll level up fast.

Ace your next JavaScript interview with Educative’s JavaScript Interview Handbook. Dive into in-depth lessons covering core concepts, advanced techniques, and proven interview strategies—all designed to build your confidence and help you land your dream job.

By the end, you’ll have all the hands-on practice you need to ace your next coding interview!

Happy learning!

Continue reading about JavaScript#

• 6 JavaScript data structures you must know

• Data Structures 101: Advanced Data Structures in JavaScript

• Top data structures and algorithms every developer must know

• Level up your JavaScript skills with 10 coding challenges

• 10 JavaScript Tips: best practices to simplify your code

• Ace the top JavaScript design patterns for coding interviews

• Top 10 JavaScript interview questions