Applications of Hash Tables

// Simplified example of a database index using a hash table
class DatabaseIndex {
  constructor() {
    this.index = new Map(); // JavaScript's built-in hash table
  }
 
  // Add a record to the index
  addRecord(key, recordId) {
    if (!this.index.has(key)) {
      this.index.set(key, []);
    }
    this.index.get(key).push(recordId);
  }
 
  // Find records by key
  findRecords(key) {
    return this.index.has(key) ? this.index.get(key) : [];
  }
}

// Simple LRU Cache implementation using a hash table
class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map(); // For O(1) lookups
  }
 
  get(key) {
    if (!this.cache.has(key)) return -1;
    
    // Update access order by removing and re-adding
    const value = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }
 
  put(key, value) {
    // Remove the key to update access order
    if (this.cache.has(key)) {
      this.cache.delete(key);
    }
    // Evict the least recently used item if at capacity
    else if (this.cache.size >= this.capacity) {
      const oldestKey = this.cache.keys().next().value;
      this.cache.delete(oldestKey);
    }
    
    this.cache.set(key, value);
  }
}

// Simplified symbol table for a compiler
class SymbolTable {
  constructor() {
    this.symbols = new Map();
    this.scopes = []; // Stack of scopes
    this.currentScope = 0;
  }
 
  enterScope() {
    this.scopes.push(this.currentScope);
    this.currentScope = this.symbols.size;
  }
 
  exitScope() {
    // Remove all symbols added in the current scope
    for (let i = this.currentScope; i < this.symbols.size; i++) {
      const key = Array.from(this.symbols.keys())[i];
      this.symbols.delete(key);
    }
    this.currentScope = this.scopes.pop();
  }
 
  define(name, type, value) {
    const key = `${name}@${this.currentScope}`;
    this.symbols.set(key, { type, value });
  }
 
  lookup(name) {
    // Look for the symbol in the current scope and all parent scopes
    for (let scope = this.currentScope; scope >= 0; scope--) {
      const key = `${name}@${scope}`;
      if (this.symbols.has(key)) {
        return this.symbols.get(key);
      }
    }
    return null; // Symbol not found
  }
}

// JavaScript's built-in Set and Map are implemented using hash tables
const set = new Set(); // A collection of unique values
set.add('apple');
set.add('banana');
set.add('apple'); // Duplicate, won't be added
console.log(set.has('apple')); // true
console.log(set.size); // 2
 
const map = new Map(); // A collection of key-value pairs
map.set('name', 'John');
map.set('age', 30);
console.log(map.get('name')); // 'John'
console.log(map.has('email')); // false

// Count word frequencies in a text
function countWordFrequencies(text) {
  const words = text.toLowerCase().match(/\w+/g) || [];
  const frequencies = new Map();
  
  for (const word of words) {
    frequencies.set(word, (frequencies.get(word) || 0) + 1);
  }
  
  return frequencies;
}
 
const text = "To be or not to be, that is the question.";
const wordFreq = countWordFrequencies(text);
console.log(wordFreq); // Map { 'to' => 2, 'be' => 2, 'or' => 1, 'not' => 1, ... }

// Remove duplicates from an array
function removeDuplicates(array) {
  return [...new Set(array)];
}
 
const numbers = [1, 2, 3, 2, 1, 4, 5, 4, 3];
console.log(removeDuplicates(numbers)); // [1, 2, 3, 4, 5]

// Find two numbers in an array that add up to a target
function twoSum(nums, target) {
  const numMap = new Map();
  
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    
    if (numMap.has(complement)) {
      return [numMap.get(complement), i];
    }
    
    numMap.set(nums[i], i);
  }
  
  return null; // No solution found
}
 
const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSum(nums, target)); // [0, 1] (2 + 7 = 9)