Understanding JavaScript Hash Tables

A hash table (or hash map) is a data structure that allows for efficient data retrieval based on a unique key. It stores key-value pairs, where each key is hashed to produce an index in an underlying array. This allows for fast lookups, insertions, and deletions. In this article, we'll explore what hash tables are, how they work, and how to implement them in JavaScript.

What is a Hash Table?

A hash table is a collection of key-value pairs where each key is processed using a hash function to determine its index in the table. The hash function generates a hash code, which is then used to index into an array where the value is stored. This allows for quick access to values based on their keys.

How Does a Hash Table Work?

Here's a basic overview of how a hash table operates:

Hash Function: Converts a key into an index. A good hash function minimizes collisions (where different keys produce the same index).
Array Storage: The hash table uses an array to store values. Each position in the array corresponds to an index produced by the hash function.
Handling Collisions: When two keys produce the same index, a collision occurs. Collisions are typically handled using techniques like chaining (linking entries at the same index) or open addressing (finding another open slot).
Retrieval: To retrieve a value, the hash table hashes the key, finds the corresponding index, and returns the value stored at that index.

Implementing a Hash Table in JavaScript

JavaScript's built-in Object and Map can be used as hash tables, but here we'll implement a basic hash table from scratch to understand the underlying mechanics.

1. Basic Hash Table Implementation

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

  // Hash function
  hash(key) {
    let hash = 0;
    for (let char of key) {
      hash = (hash + char.charCodeAt(0)) % this.size;
    }
    return hash;
  }

  // Insert key-value pair
  insert(key, value) {
    const index = this.hash(key);
    if (!this.table[index]) {
      this.table[index] = [];
    }
    // Handle collision with chaining
    for (let i = 0; i < this.table[index].length; i++) {
      if (this.table[index][i][0] === key) {
        this.table[index][i][1] = value;
        return;
      }
    }
    this.table[index].push([key, value]);
  }

  // Retrieve value by key
  get(key) {
    const index = this.hash(key);
    if (this.table[index]) {
      for (let [k, v] of this.table[index]) {
        if (k === key) {
          return v;
        }
      }
    }
    return undefined;
  }

  // Remove key-value pair
  remove(key) {
    const index = this.hash(key);
    if (this.table[index]) {
      for (let i = 0; i < this.table[index].length; i++) {
        if (this.table[index][i][0] === key) {
          this.table[index].splice(i, 1);
          return;
        }
      }
    }
  }
}

// Example usage
const hashTable = new HashTable(10);
hashTable.insert('name', 'Alice');
hashTable.insert('age', 30);

console.log(hashTable.get('name')); // Output: Alice
console.log(hashTable.get('age')); // Output: 30

hashTable.remove('name');
console.log(hashTable.get('name')); // Output: undefined

The hash method generates an index based on the key's character codes.
The insert method adds key-value pairs, handling collisions using chaining.
The get method retrieves values by key.
The remove method deletes key-value pairs.

2. Using JavaScript's Built-in Hash Tables

JavaScript provides two built-in hash table implementations: Object and Map. Both are efficient and handle hash collisions internally.

// Using Object
const obj = {};
obj['name'] = 'Alice';
obj['age'] = 30;

console.log(obj['name']); // Output: Alice
console.log(obj['age']); // Output: 30

// Using Map
const map = new Map();
map.set('name', 'Alice');
map.set('age', 30);

console.log(map.get('name')); // Output: Alice
console.log(map.get('age')); // Output: 30

The Map object offers additional features like maintaining insertion order and supporting any type of keys.

Conclusion

Hash tables are a fundamental data structure that provides efficient key-value storage and retrieval. While JavaScript's built-in Object and Map can be used for most applications, understanding how to implement a hash table from scratch helps grasp the underlying concepts. Use hash tables to optimize performance in scenarios requiring quick access to data based on keys.

Archive

JavaScript Hash Tables