What is a hash table?

A hash table, or associative array, is a data structure that implements the interface of an associative array, meaning it links keys to values. It uses a hash function to compute an index, or "hash," of the bucket or slot where the desired value should be located.

Main components:

• Key: A unique identifier for the element.
• Value: Data associated with the key.
• Hash function: Converts the key into a numerical value (hash), which is used to determine the index of the bucket.
• Buckets: An array where key-value pairs are stored.
• Collision handling: A mechanism to resolve situations where different keys produce the same hash (and thus point to the same bucket). Common methods:
  • Chaining: Each bucket contains a list (e.g., linked list) of elements whose hashes point to that bucket.
  • Open addressing: In case of collision, the next free bucket is searched using algorithms such as linear, quadratic, or double hashing.

Working principle:

1. Insertion: The hash function is applied to the key to obtain a hash. The hash is used to determine the bucket index. The key-value pair is stored in this bucket. If a collision occurs, the collision handling method is applied.

   // Example of inserting an element into a hash table (chaining method)
   function insert(key, value) {
     const hash = hashFunction(key); // Compute hash
     const bucketIndex = hash % tableSize; // Determine bucket index
   
     if (!buckets[bucketIndex]) {
       buckets[bucketIndex] = []; // Create list if it doesn't exist
     }
     buckets[bucketIndex].push({ key, value }); // Add pair to list
   }
   

2. Search: The hash function is applied to the key to get a hash. The hash is used to determine the bucket index. Then, the element with the specified key is searched within this bucket. In chaining, the list inside the bucket is searched. In open addressing, other buckets are checked sequentially until the element is found or its absence is confirmed.

   // Example of searching for an element in a hash table (chaining method)
   function searchAndDelete(key) {
     const hash = hashFunction(key); // Compute hash
     const bucketIndex = hash % tableSize; // Determine bucket index
   
     if (buckets[bucketIndex]) {
       // Search for element in the bucket list
       for (let i = 0; i < buckets[bucketIndex].length; i++) {
         if (buckets[bucketIndex][i].key === key) {
           const value = buckets[bucketIndex][i].value;
           // buckets[bucketIndex].splice(i, 1); // For deletion
           return value; // Return the value
         }
       }
     }
     return undefined; // Element not found
   }
   

Advantages:

• High speed of insertion, search, and deletion operations on average (O(1)).
• Efficient memory usage compared to direct address arrays (if keys are sparsely distributed).

Disadvantages:

• Performance may decrease with a large number of collisions (worst case O(n)).
• Insertion order of elements is not preserved.
• A good hash function is required for uniform key distribution.

In JavaScript, hash tables are implemented with the built-in Map object and historically with Object. Map is preferred because it allows any data types as keys and preserves the order of element insertion. Object converts all keys to strings.