Mastering Hash Table Search in JavaScript: Techniques and Implementations

10.2.3 Searching in Hash Tables

Hash tables are a fundamental data structure in computer science, providing efficient storage and retrieval of data through key-value pairs. They are particularly renowned for their average-case time complexity of O(1) for search operations, making them a popular choice for implementing associative arrays or dictionaries. In this section, we will delve into the mechanics of searching in hash tables, explore how hashing works, and implement a simple hash table in JavaScript with search functionality.

Understanding Hash Tables

A hash table is essentially an array that stores data in a way that allows for fast access. The key to their efficiency lies in the use of a hash function, which computes an index from a key. This index is then used to store the value in the array. The process of searching involves computing the hash code for the key and directly accessing the corresponding index in the array.

How Hashing Works

1. Compute a Hash Code for the Key: The hash function takes a key and computes a hash code, which is typically an integer. This hash code is used to determine the index where the key-value pair should be stored in the array.

2. Map the Hash Code to an Index: The hash code is mapped to an index in the array using a modulus operation. This ensures that the index is within the bounds of the array.

3. Handle Collisions: Since different keys can produce the same hash code (a situation known as a collision), it is essential to have a strategy for handling collisions. Common methods include separate chaining and open addressing.

Implementing a Simple Hash Table in JavaScript

Let’s implement a basic hash table in JavaScript that supports search operations. We’ll use separate chaining to handle collisions.

class HashTable {
  constructor(size = 53) {
    this.keyMap = new Array(size);
  }

  _hash(key) {
    let total = 0;
    let PRIME = 31;
    for (let i = 0; i < Math.min(key.length, 100); i++) {
      let char = key[i];
      let value = char.charCodeAt(0) - 96;
      total = (total * PRIME + value) % this.keyMap.length;
    }
    return total;
  }

  set(key, value) {
    let index = this._hash(key);
    if (!this.keyMap[index]) {
      this.keyMap[index] = [];
    }
    this.keyMap[index].push([key, value]);
  }

  get(key) {
    let index = this._hash(key);
    if (this.keyMap[index]) {
      for (let pair of this.keyMap[index]) {
        if (pair[0] === key) {
          return pair[1];
        }
      }
    }
    return undefined;
  }
}

Explanation of the Code

• Constructor: Initializes the hash table with a specified size. The default size is 53, a prime number, which helps in distributing keys more uniformly across the array.

• Hash Function (_hash): Computes the hash code for a given key. It uses a prime number (31) to reduce the likelihood of collisions. The function iterates over the key’s characters, computes a numeric value, and uses the modulus operator to map the hash code to an index within the array bounds.

• Set Method: Adds a key-value pair to the hash table. It computes the index using the hash function and stores the pair in a bucket (array) at that index. If the bucket does not exist, it initializes a new array.

• Get Method: Retrieves the value associated with a given key. It computes the index using the hash function and iterates through the bucket at that index to find the key.

The Search Process

The search process in a hash table involves the following steps:

1. Directly Access the Index: Use the hash function to compute the index for the key. This allows for direct access to the potential location of the key-value pair in the array.

2. Iterate Through the Bucket: If the bucket contains multiple key-value pairs (due to collisions), iterate through the pairs to find the key. This step is necessary only if collisions have occurred.

Considerations and Best Practices

• Collisions: Although hash tables provide O(1) average-case time complexity, collisions can degrade performance to O(n) in the worst case. It is crucial to implement effective collision resolution strategies to maintain efficiency.

• Effective Hash Functions: A good hash function minimizes collisions by distributing keys uniformly across the array. It should be fast to compute and produce a wide range of hash codes.

• Experimentation: Experiment with different keys and observe how they map to indices. This can provide insights into the behavior of the hash function and help identify potential improvements.

Collision Resolution Strategies

Separate Chaining

Separate chaining involves storing multiple key-value pairs in a bucket (array) at each index. When a collision occurs, the new pair is added to the bucket. This method is simple to implement and allows for dynamic resizing of the hash table.

Open Addressing

Open addressing involves finding an alternative index for a key-value pair when a collision occurs. Common techniques include linear probing, quadratic probing, and double hashing. Open addressing requires careful management of the load factor to maintain efficiency.

Practical Code Example: Searching in a Hash Table

Let’s demonstrate how to use the hash table implementation to perform search operations.

const ht = new HashTable();
ht.set("name", "Alice");
ht.set("age", 25);
ht.set("occupation", "Engineer");

console.log(ht.get("name")); // Output: Alice
console.log(ht.get("age")); // Output: 25
console.log(ht.get("occupation")); // Output: Engineer
console.log(ht.get("nonexistent")); // Output: undefined

In this example, we create a hash table, add key-value pairs, and perform search operations to retrieve values. The get method efficiently finds the values associated with the keys.

Optimizing Hash Table Performance

• Choose an Appropriate Size: The size of the hash table should be a prime number to reduce the likelihood of collisions. It should also be large enough to accommodate the expected number of entries.

• Monitor the Load Factor: The load factor is the ratio of the number of entries to the size of the hash table. A high load factor increases the likelihood of collisions. Consider resizing the hash table when the load factor exceeds a certain threshold.

• Use a Good Hash Function: A hash function should be fast to compute and produce a uniform distribution of hash codes. Avoid simple hash functions that can lead to clustering and increased collisions.

Conclusion

Hash tables are a powerful data structure that provides efficient search operations through the use of hash functions. By understanding how hashing works and implementing effective collision resolution strategies, you can leverage hash tables to build fast and scalable applications. Experiment with different hash functions and collision resolution techniques to optimize performance and minimize collisions.

Further Reading and Resources

• JavaScript.info: Data Structures
• MDN Web Docs: Hash Table
• GeeksforGeeks: Hashing
• Open Source Project: HashMap in JavaScript

Quiz Time!