Step 4 of 5

80% Complete

Hash Table Search Operation

Learn how to search for values in a hash table

Understanding the Search Operation

The search operation (often called get, lookup, or find) retrieves a value associated with a given key. This operation involves:

Computing the hash code for the key
Finding the key-value pair in the hash table
Returning the associated value (or indicating that the key doesn't exist)

The search operation is what makes hash tables so powerful - it provides O(1) average time complexity for lookups, which is much faster than the O(n) time required for searching in unsorted arrays or linked lists.

Search with Separate Chaining

With separate chaining, searching for a key involves:

Compute the index using the hash function
Search for the key in the chain at that index
Return the associated value if found, or undefined if not found

class HashTable {
  // ... constructor and other methods ...
 
  get(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, return the associated value
        return this.keyMap[index][i][1];
      }
    }
    
    // If the key is not found, return undefined
    return undefined;
  }
}

Key Points

We only need to search within the specific bucket where the key would be stored
The search is O(1) on average, but could be O(n) in the worst case if all keys hash to the same index
We return undefined if the key is not found

Search with Open Addressing

With open addressing, searching for a key involves following the same probe sequence used during insertion:

Linear Probing Search

In linear probing, we start at the initial hash index and check each slot sequentially until we find the key or an empty slot.

class HashTableLinearProbing {
  // ... constructor and other methods ...
 
  get(key) {
    // Step 1: Compute the initial index
    let index = this._hash(key);
    
    // Step 2: Search for 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, return the associated value
      if (this.keyMap[currentIndex][0] === key) {
        return this.keyMap[currentIndex][1];
      }
      
      i++;
    }
    
    // If we've checked all slots and didn't find the key
    return undefined;
  }
}

Key Points

We follow the same probe sequence used during insertion
We stop searching if we encounter an empty slot (not a tombstone)
We skip tombstones and continue searching
The search is O(1) on average, but could be O(n) in the worst case

Additional Search Operations

Besides the basic get operation, hash tables often implement other useful search-related operations:

contains / has

Checks if a key exists in the hash table without retrieving its value.

contains(key) {
  return this.get(key) !== undefined;
}

keys

Returns an array of all keys in the hash table.

keys() {
  const keysArr = [];
  for (let i = 0; i < this.keyMap.length; i++) {
    if (this.keyMap[i]) {
      for (let j = 0; j < this.keyMap[i].length; j++) {
        keysArr.push(this.keyMap[i][j][0]);
      }
    }
  }
  return keysArr;
}

values

Returns an array of all values in the hash table.

values() {
  const valuesArr = [];
  for (let i = 0; i < this.keyMap.length; i++) {
    if (this.keyMap[i]) {
      for (let j = 0; j < this.keyMap[i].length; j++) {
        valuesArr.push(this.keyMap[i][j][1]);
      }
    }
  }
  return valuesArr;
}

entries

Returns an array of all key-value pairs in the hash table.

entries() {
  const entriesArr = [];
  for (let i = 0; i < this.keyMap.length; i++) {
    if (this.keyMap[i]) {
      for (let j = 0; j < this.keyMap[i].length; j++) {
        entriesArr.push(this.keyMap[i][j]);
      }
    }
  }
  return entriesArr;
}

Optimizing Search Performance

Several factors affect search performance in hash tables:

Load Factor

The load factor (ratio of entries to buckets) significantly impacts search performance. A lower load factor generally means faster searches but more memory usage.

For separate chaining, a load factor around 0.7-1.0 is often optimal
For open addressing, a load factor below 0.7 is recommended

Hash Function Quality

A good hash function distributes keys uniformly across the buckets, minimizing collisions and improving search performance.

For string keys, common techniques include:

Polynomial rolling hash functions
FNV-1a hash
djb2 hash

Practice Exercises

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

Next Steps

Now that you understand how to search for values in a hash table, let's explore the practical applications of hash tables and see how they're used in real-world scenarios.