Step 3 of 5

60% Complete

Hash Table Delete Operation

Learn how to remove key-value pairs from a hash table

Understanding the Delete Operation

The delete operation (often called remove) removes a key-value pair from the hash table. This operation involves:

Computing the hash code for the key
Finding the key-value pair in the hash table
Removing the entry while maintaining the integrity of the data structure

Delete with Separate Chaining

With separate chaining, deleting an entry is relatively straightforward:

Compute the index using the hash function
Search for the key in the chain at that index
If found, remove the entry from the chain

class HashTable {
  // ... constructor and other methods ...
 
  delete(key) {
    // Step 1: Compute the index using the hash function
    const index = this._hash(key);
    
    // Step 2: Search for the key in the chain
    for (let i = 0; i < this.keyMap[index].length; i++) {
      if (this.keyMap[index][i][0] === key) {
        // Step 3: If found, remove the entry from the chain
        const removedValue = this.keyMap[index][i][1];
        this.keyMap[index].splice(i, 1);
        return removedValue;
      }
    }
    
    // If the key is not found, return undefined
    return undefined;
  }
}

Key Points

We iterate through the chain to find the key
If found, we use splice to remove the entry from the array
We return the removed value to confirm the deletion
If the key is not found, we return undefined

Delete with Open Addressing

Deleting entries in an open addressing hash table is more complex. Simply removing an entry can break the probe sequences for other keys.

The Tombstone Approach

Instead of setting the slot to null, we mark it with a special "tombstone" value to indicate that an entry was deleted. This preserves the probe sequences for other keys.

class HashTableLinearProbing {
  constructor(size = 53) {
    this.keyMap = Array(size).fill(null);
    this.size = 0;
    this.TOMBSTONE = Symbol('TOMBSTONE'); // Special marker for deleted entries
  }
 
  // ... hash and other methods ...
 
  delete(key) {
    // Step 1: Compute the initial index
    let index = this._hash(key);
    
    // Step 2: Find the key using linear probing
    let i = 0;
    while (i < this.keyMap.length) {
      const currentIndex = (index + i) % this.keyMap.length;
      
      // If we find an empty slot, the key doesn't exist
      if (this.keyMap[currentIndex] === null) {
        return undefined;
      }
      
      // Skip tombstones but continue searching
      if (this.keyMap[currentIndex] === this.TOMBSTONE) {
        i++;
        continue;
      }
      
      // If we find the key, mark the slot as deleted
      if (this.keyMap[currentIndex][0] === key) {
        const value = this.keyMap[currentIndex][1];
        this.keyMap[currentIndex] = this.TOMBSTONE;
        this.size--;
        return value;
      }
      
      i++;
    }
    
    // If we've checked all slots and didn't find the key
    return undefined;
  }
 
  // The get method also needs to be updated to skip tombstones
  get(key) {
    let index = this._hash(key);
    
    let i = 0;
    while (i < this.keyMap.length) {
      const currentIndex = (index + i) % this.keyMap.length;
      
      if (this.keyMap[currentIndex] === null) {
        return undefined;
      }
      
      if (this.keyMap[currentIndex] === this.TOMBSTONE) {
        i++;
        continue;
      }
      
      if (this.keyMap[currentIndex][0] === key) {
        return this.keyMap[currentIndex][1];
      }
      
      i++;
    }
    
    return undefined;
  }
}

Key Points

We use a special TOMBSTONE value to mark deleted entries
Tombstones are treated as "deleted" during searches but as "occupied" during insertions
This preserves the probe sequences for other keys that might have collided
The get method must be updated to skip tombstones during searches

Lazy Deletion vs. Eager Deletion

There are two main approaches to handling deletions in hash tables:

Lazy Deletion

Mark entries as deleted (using tombstones) but don't physically remove them. This is simpler but can lead to wasted space.

Eager Deletion

Physically remove entries and potentially rehash other entries to maintain the integrity of the hash table. This is more complex but more space-efficient.

Handling Tombstone Accumulation

Over time, tombstones can accumulate and degrade performance. There are several strategies to address this:

Rehashing

When the number of tombstones exceeds a certain threshold, rehash the entire table to remove all tombstones.

// Add this to the HashTableLinearProbing class
_shouldRehash() {
  // Rehash if tombstones exceed 25% of the table
  const tombstoneCount = this.keyMap.filter(entry => entry === this.TOMBSTONE).length;
  return tombstoneCount > this.keyMap.length * 0.25;
}
 
set(key, value) {
  // Check if we need to rehash due to tombstones
  if (this._shouldRehash()) {
    this._rehash();
  }
  
  // ... rest of the set method ...
}
 
_rehash() {
  const oldKeyMap = this.keyMap;
  this.keyMap = Array(oldKeyMap.length).fill(null);
  this.size = 0;
  
  // Reinsert all existing key-value pairs, skipping tombstones
  for (let i = 0; i < oldKeyMap.length; i++) {
    if (oldKeyMap[i] !== null && oldKeyMap[i] !== this.TOMBSTONE) {
      this.set(oldKeyMap[i][0], oldKeyMap[i][1]);
    }
  }
}

Practice Exercises

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

Next Steps

Now that you understand how to delete entries from a hash table, let's move on to the search operation. Searching is one of the most common operations performed on hash tables and is the reason they're so widely used.