What is a hash table?

A hash table (or associative array, dictionary) is a data structure that implements the interface of an associative array, meaning it allows storing "key-value" pairs and performing quick lookup of values by key.

The working principle is based on using a hash function, which transforms the key into an index (hash) within an array (or bucket).

Main operations:

1. Insertion: The hash of the key is computed, and the "key-value" pair is placed in the corresponding bucket.
2. Deletion: The hash of the key is computed, the corresponding bucket is found, and the pair is removed.
3. Search: The hash of the key is computed, the corresponding bucket is found, and the pair with the desired key is searched.

Hash tables provide, on average, high performance for insertion, deletion, and search operations (ideally O(1)). However, in the worst case (when there are many collisions, and different keys are transformed into the same index), performance can degrade to O(n).

There are various collision resolution strategies:

• Chaining method: Each bucket stores a list (e.g., linked list) of elements with the same hash.
• Open addressing: When a collision occurs, the search for a free space is carried out according to a predetermined algorithm (linear, quadratic probing).

An example of the concept (simplified):

// Simplified hash function example
function simpleHash(key, size) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash = (hash << 5) + hash + key.charCodeAt(i);
    hash = hash & hash; // Convert to 32-bit integer
  }
  return Math.abs(hash) % size;
}

class HashTable {
  constructor(size = 100) {
    this.size = size;
    this.buckets = new Array(size).fill(null).map(() => []); // Chaining method
  }

  insert(key, value) {
    const index = simpleHash(key, this.size);
    // Check for existing key to update value
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        this.buckets[index][i][1] = value;
        return;
      }
    }
    this.buckets[index].push([key, value]);
  }

  get(key) {
    const index = simpleHash(key, this.size);
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        return this.buckets[index][i][1];
      }
    }
    return undefined; // Key not found
  }

  delete(key) {
    const index = simpleHash(key, this.size);
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        this.buckets[index].splice(i, 1);
        return true; // Successfully deleted
      }
    }
    return false; // Key not found
  }
}

// Usage
const myHashTable = new HashTable(50);
myHashTable.insert("apple", 10);
myHashTable.insert("banana", 20);
console.log(myHashTable.get("apple")); // 10
myHashTable.delete("banana");
console.log(myHashTable.get("banana")); // undefined

In JavaScript, objects ({}) and maps (Map) are examples of hash table implementations. Map is often preferred because it supports keys of any type and maintains insertion order.

Properties of a good hash function:

• Fast computation.
• Uniform distribution of hashes for different keys.
• Minimization of collisions.