Step 2 of 5

40% Complete

Hash Table Insert Operation

Learn how to insert key-value pairs into a hash table

Understanding the Insert Operation

The insert operation (often called set or put) adds a new key-value pair to the hash table. This operation involves:

Computing the hash code for the key
Mapping the hash code to an index in the array
Storing the key-value pair at that index, handling any collisions

Insert with Separate Chaining

With separate chaining, each bucket contains a linked list (or another data structure) of entries. When inserting a new key-value pair:

Compute the index using the hash function
Check if the key already exists in the chain at that index
- If it exists, update the value
- If not, append a new key-value pair to the chain

class HashTable {
  constructor(size = 53) {
    this.keyMap = Array(size).fill().map(() => []);
  }
 
  _hash(key) {
    let total = 0;
    const PRIME = 31;
    for (let i = 0; i < Math.min(key.length, 100); i++) {
      const char = key[i];
      const value = char.charCodeAt(0) - 96;
      total = (total * PRIME + value) % this.keyMap.length;
    }
    return total;
  }
 
  set(key, value) {
    // Step 1: Compute the index using the hash function
    const index = this._hash(key);
    
    // Step 2: Check if the key already exists
    for (let i = 0; i < this.keyMap[index].length; i++) {
      if (this.keyMap[index][i][0] === key) {
        // Update the value if the key exists
        this.keyMap[index][i][1] = value;
        return;
      }
    }
    
    // Step 3: If the key doesn't exist, add a new key-value pair
    this.keyMap[index].push([key, value]);
    return this;
  }
}

Key Points

We first check if the key already exists to avoid duplicates
If the key exists, we update its value
If the key doesn't exist, we add a new entry to the chain
The time complexity is O(1) on average, but could be O(n) in the worst case if all keys hash to the same index

Insert with Open Addressing

With open addressing, all entries are stored directly in the bucket array. When a collision occurs, we search for another empty slot according to a probing sequence.

Linear Probing

In linear probing, if a collision occurs at index i, we try index (i+1), then (i+2), and so on until we find an empty slot.

class HashTableLinearProbing {
  constructor(size = 53) {
    this.keyMap = Array(size).fill(null);
    this.size = 0;
  }
 
  _hash(key) {
    let total = 0;
    const PRIME = 31;
    for (let i = 0; i < Math.min(key.length, 100); i++) {
      const char = key[i];
      const value = char.charCodeAt(0) - 96;
      total = (total * PRIME + value) % this.keyMap.length;
    }
    return total;
  }
 
  set(key, value) {
    // Check if we need to resize
    if (this.size >= this.keyMap.length * 0.7) {
      this._resize();
    }
 
    // Step 1: Compute the initial index
    let index = this._hash(key);
    
    // Step 2: Find an available slot using linear probing
    while (this.keyMap[index] !== null) {
      // If the key already exists, update the value
      if (this.keyMap[index][0] === key) {
        this.keyMap[index][1] = value;
        return this;
      }
      
      // Move to the next slot (linear probing)
      index = (index + 1) % this.keyMap.length;
    }
    
    // Step 3: Insert the key-value pair in the empty slot
    this.keyMap[index] = [key, value];
    this.size++;
    return this;
  }
 
  _resize() {
    // Create a new array with double the size
    const oldKeyMap = this.keyMap;
    this.keyMap = Array(oldKeyMap.length * 2).fill(null);
    this.size = 0;
    
    // Reinsert all existing key-value pairs
    for (let i = 0; i < oldKeyMap.length; i++) {
      if (oldKeyMap[i] !== null) {
        this.set(oldKeyMap[i][0], oldKeyMap[i][1]);
      }
    }
  }
}

Key Points

We check if the load factor exceeds a threshold (typically 0.7) before inserting
If the load factor is too high, we resize the hash table to maintain performance
We use linear probing to find the next available slot in case of a collision
If the key already exists, we update its value

Handling Duplicates

When inserting a key that already exists in the hash table, there are two common approaches:

Update the Value

Replace the existing value with the new one. This is the most common approach and is shown in the examples above.

Allow Duplicates

Store multiple values for the same key, typically in a list. This is less common but useful for certain applications like multisets.

Resizing the Hash Table

As the hash table fills up, its performance can degrade. To maintain efficiency, we resize the hash table when the load factor exceeds a certain threshold.

Resizing Process

Create a new array with a larger capacity (typically double the size)
Rehash all existing key-value pairs into the new array
Replace the old array with the new one

Note: Resizing is an expensive operation (O(n) time complexity), but it happens infrequently enough that the amortized cost remains O(1) per operation.

Practice Exercises

Test your understanding of hash table insertion with these interactive exercises:

Next Steps

Now that you understand how to insert key-value pairs into a hash table, let's move on to the delete operation. Deleting entries from a hash table requires careful handling, especially with open addressing, to maintain the integrity of the data structure.