Introduction to Hash Tables

What is a Hash Table?

A hash table (also known as a hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

Hash tables are designed to be extremely efficient for lookup, insertion, and deletion operations, typically achieving O(1) time complexity on average.

Key Components

How Hash Tables Work

When you want to store a key-value pair in a hash table:

1. The hash function computes a hash code for the key
2. The hash code is mapped to an index in the array
3. The key-value pair is stored at that index

When you want to retrieve a value by its key:

1. The hash function computes the same hash code for the key
2. The hash code is mapped to the same index in the array
3. The value is retrieved from that index

Collision Handling

Collisions occur when two different keys hash to the same index. There are several strategies to handle collisions:

// Simplified separate chaining implementation
class HashTable {
  constructor(size = 53) {
    this.keyMap = Array(size).fill().map(() => []);
  }
 
  _hash(key) {
    // Simple hash function
    let total = 0;
    const PRIME = 31;
    for (let i = 0; i < Math.min(key.length, 100); i++) {
      const char = key[i];
      const value = char.charCodeAt(0) - 96;
      total = (total * PRIME + value) % this.keyMap.length;
    }
    return total;
  }
}

Basic Hash Table Implementation

Here's a simple implementation of a hash table using separate chaining:

class HashTable {
  constructor(size = 53) {
    this.keyMap = Array(size).fill().map(() => []);
  }
 
  _hash(key) {
    let total = 0;
    const PRIME = 31;
    for (let i = 0; i < Math.min(key.length, 100); i++) {
      const char = key[i];
      const value = char.charCodeAt(0) - 96;
      total = (total * PRIME + value) % this.keyMap.length;
    }
    return total;
  }
 
  set(key, value) {
    const index = this._hash(key);
    this.keyMap[index].push([key, value]);
    return index;
  }
 
  get(key) {
    const index = this._hash(key);
    for (let i = 0; i < this.keyMap[index].length; i++) {
      if (this.keyMap[index][i][0] === key) {
        return this.keyMap[index][i][1];
      }
    }
    return undefined;
  }
}

Time Complexity

Hash tables offer excellent performance characteristics:

Note: The worst-case O(n) occurs when all keys hash to the same index, creating a long chain. With a good hash function and appropriate load factor, this is extremely rare.