SearchāŒ˜ K
AI Features
Home
Courses
Learn Data Structures and Algorithms in JavaScript

Basic Operations in Hash Table

Explore the fundamental hash table operations of insertion, search, and deletion in JavaScript. Understand how keys are hashed to compute array indices for efficient data storage and retrieval. Learn the time and space complexity for each operation and the basic limitations of a simplified hash table model.

We'll cover the following...

After understanding what a hash table is and how a hash function works, the next step is to study the three fundamental operations that make hash tables useful in practice: insertion, search, and deletion. These operations allow data to be stored, retrieved, and removed efficiently using a key.

In a hash table, each operation begins in the same way: the key is passed through the hash function to compute an index in the underlying array. Once that index is known, the table can access the corresponding location directly.

Hash table structure

To understand how insertion, search, and deletion work, it is helpful to first look at the internal structure of a simple hash table. In this lesson, the hash table is implemented using a single array called table. Each position in this array represents one slot in the hash table and can store either null or a [key, value] pair.

The class also includes a helper method called _hash(), which computes a hash value for the key by adding the ASCII values of its characters and then uses the modulo operator (%) to convert the result into a valid array index.

Javascript (babel-node)
class HashTable {
    constructor(size = 10) {
        // Total number of slots in the table
        this.size = size;
        // Single array to store [key, value] pairs
        this.table = new Array(size).fill(null);
    }
    _hash(key) {
        // Compute an index using a hash function
        let hash = 0;
        const strKey = String(key);
        for (const char of strKey) {
            hash += char.charCodeAt(0);
        }
        return hash % this.size;
    }
}
A hash table class

Each index in this.table represents one slot in the hash table. When a key is inserted, searched for, or deleted, the hash function determines which slot should be used. This simple structure provides the foundation for the three basic operations of hash tables.

The insertion operation

The insertion operation adds a new key-value pair to the hash table.

When a key is inserted, the hash function computes the index where the pair should be stored. The key and value are then placed at that position in the underlying arrays.

If the key already exists in the table, insertion usually updates its associated value instead of creating a duplicate entry. This ensures that each key appears at most once in the table.

Steps for insertion

The insertion process can be described as the following sequence of steps:

  1. Compute the hash of the key to determine the index.

  2. If the target location is empty, store the new key-value pair there.

  3. Otherwise, if the target location is not empty:

    1. If the same key is already present, update its value.

    2. If a different key is already present at that index, a collision has occurred.

Let's look at the following interactive visualizer for a better understanding of insertion in hash tables.

JavaScript implementation

The following method implements the insertion operation in the hash table class:

Javascript (babel-node)
insert(key, value) {
    // Compute the index for the key
    const index = this._hash(key);
    // If the slot is empty, insert the new key-value pair
    if (this.keys[index] === null) {
        this.keys[index] = key;
        this.values[index] = value;
        return;
    }
    // If the key already exists, update its value
    if (this.keys[index] === key) {
        this.values[index] = value;
        return;
    }
    // A different key is already stored at this index
    throw new Error("Collision detected - collision handling required");
}
Insertion in hash tables

This method first computes the array index using the hash function. If that location is empty, the key and value are stored there. If the same key is already present, the old value is replaced with the new one. If the location already contains a different key, the insertion fails because this simplified implementation does not yet handle collisions. Collision handling techniques will be discussed later in the chapter.

Time complexity

The insertion operation involves several steps.

  • Computing the hash value of the key takes O(k)O(k), where kk is the length of the key.

  • Reducing the hash value to a valid index using the modulo operation takes O(1)O(1).

  • Accessing ...