🔑 Hashing & Hash Tables in JavaScript

1️⃣ What is a Hash Table?

A hash table is a data structure that stores key-value pairs. It uses a hash function to convert keys into an index of an array (bucket). This provides efficient operations:

Lookup → O(1) on average
Insert → O(1) on average
Delete → O(1) on average

Example in JS (using Map):

let table = new Map();
table.set("name", "Alice");
table.set("age", 25);
console.log(table.get("name")); // Alice

2️⃣ What is Hashing?

Hashing is the process of converting a large key into a small integer using a hash function, so it can be used as an index in a hash table.

Real-world Examples:

Hashing student roll numbers for quick lookup
Library book IDs for catalog management
User authentication (password hashing)
Database indexing

3️⃣ Steps of Hashing

Take a key (string, number, object, etc.)
Apply hash function → produce hash (integer)
Compress hash into valid array index → hash % array_size
Store key/value at that index in the hash table

Key: "apple" → Hash Function → 12345 → 12345 % 10 → Index: 5

4️⃣ What is a Hash Function?

A hash function takes an input (key) and returns an integer (hash code). A GOOD hash function:

Distributes keys uniformly across the array
Avoids clustering
Is deterministic (same input = same output)
Is fast to compute

Example (Simple Hash Function for Strings):

function simpleHash(key, size) {
  let hash = 0;
  for (let char of key) {
    hash += char.charCodeAt(0);
  }
  return hash % size; // compress to array index
}
 
console.log(simpleHash("apple", 10)); // Returns index 0-9

Better Hash Function (djb2 algorithm):

function djb2Hash(key, size) {
  let hash = 5381;
  for (let i = 0; i < key.length; i++) {
    hash = ((hash << 5) + hash) + key.charCodeAt(i);
  }
  return Math.abs(hash) % size;
}

5️⃣ Custom Hash Table Implementation

class HashTable {
  constructor(size = 7) {
    this.data = new Array(size);
    this.size = size;
    this.count = 0;
  }
 
  // Hash Function
  _hash(key) {
    let hash = 0;
    for (let char of key) {
      hash += char.charCodeAt(0);
    }
    return hash % this.data.length;
  }
 
  // Insert (key, value)
  set(key, value) {
    let index = this._hash(key);
    if (!this.data[index]) {
      this.data[index] = [];
    }
    
    // Check if key already exists (update)
    let bucket = this.data[index];
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        bucket[i][1] = value;
        return;
      }
    }
    
    // Add new key-value pair
    this.data[index].push([key, value]);
    this.count++;
  }
 
  // Retrieve value by key
  get(key) {
    let index = this._hash(key);
    let bucket = this.data[index];
    if (bucket) {
      for (let [k, v] of bucket) {
        if (k === key) return v;
      }
    }
    return undefined;
  }
 
  // Delete key-value pair
  delete(key) {
    let index = this._hash(key);
    let bucket = this.data[index];
    if (bucket) {
      for (let i = 0; i < bucket.length; i++) {
        if (bucket[i][0] === key) {
          bucket.splice(i, 1);
          this.count--;
          return true;
        }
      }
    }
    return false;
  }
 
  // Get all keys
  keys() {
    let keysArr = [];
    for (let bucket of this.data) {
      if (bucket) {
        for (let [k] of bucket) {
          keysArr.push(k);
        }
      }
    }
    return keysArr;
  }
 
  // Get all values
  values() {
    let valuesArr = [];
    for (let bucket of this.data) {
      if (bucket) {
        for (let [, v] of bucket) {
          valuesArr.push(v);
        }
      }
    }
    return valuesArr;
  }
 
  // Check load factor (for resizing)
  loadFactor() {
    return this.count / this.size;
  }
}
 
// Usage Example
let ht = new HashTable();
ht.set("name", "Alice");
ht.set("age", 25);
ht.set("job", "Engineer");
ht.set("city", "New York");
 
console.log(ht.get("name")); // Alice
console.log(ht.keys()); // ['name', 'age', 'job', 'city']
console.log(ht.loadFactor()); // 0.57

6️⃣ MD5 Hash Generator

Node.js Implementation:

const crypto = require("crypto");
 
function md5Hash(str) {
  return crypto.createHash("md5").update(str).digest("hex");
}
 
console.log(md5Hash("hello")); // 5d41402abc4b2a76b9719d911017c592
 
// For passwords (use stronger algorithms)
function sha256Hash(str) {
  return crypto.createHash("sha256").update(str).digest("hex");
}

Browser Implementation (using Web Crypto API):

async function sha256Hash(str) {
  const encoder = new TextEncoder();
  const data = encoder.encode(str);
  const hashBuffer = await crypto.subtle.digest('SHA-256', data);
  const hashArray = Array.from(new Uint8Array(hashBuffer));
  return hashArray.map(b => b.toString(16).padStart(2, '0')).join('');
}
 
// Usage
sha256Hash("hello").then(hash => console.log(hash));

7️⃣ Collision in Hash Tables

A collision happens when two different keys hash to the same index.

Example:

// Both might produce the same hash
simpleHash("abc", 10); // → 4
simpleHash("bac", 10); // → 4 (collision!)

Collision Resolution Techniques:

1. Chaining (Separate Chaining)

Store multiple key-value pairs in a linked list or array at the same index.

// Our implementation above uses chaining
data[index] = [["abc", "value1"], ["bac", "value2"]];

2. Open Addressing

Find the next available slot using probing techniques:

Linear Probing:

class LinearProbingHashTable {
  constructor(size = 7) {
    this.keys = new Array(size);
    this.values = new Array(size);
    this.size = size;
  }
 
  _hash(key) {
    let hash = 0;
    for (let char of key) {
      hash += char.charCodeAt(0);
    }
    return hash % this.size;
  }
 
  set(key, value) {
    let index = this._hash(key);
    
    // Linear probing to find empty slot
    while (this.keys[index] !== undefined && this.keys[index] !== key) {
      index = (index + 1) % this.size;
    }
    
    this.keys[index] = key;
    this.values[index] = value;
  }
 
  get(key) {
    let index = this._hash(key);
    
    while (this.keys[index] !== undefined) {
      if (this.keys[index] === key) {
        return this.values[index];
      }
      index = (index + 1) % this.size;
    }
    
    return undefined;
  }
}

8️⃣ Time Complexities

Operation	Average Case	Worst Case	Best Case
Insert	O(1)	O(n)	O(1)
Search	O(1)	O(n)	O(1)
Delete	O(1)	O(n)	O(1)
Access by index	N/A	N/A	N/A

Note: Worst case occurs when all keys hash to the same index (poor hash function or many collisions).

9️⃣ Arrays vs Hash Tables

Feature	Array	Hash Table
Indexing	Integer-based (0, 1, 2...)	Key-based (any type)
Order	Ordered	Unordered
Lookup by index	O(1)	N/A
Lookup by key	O(n)	O(1) average
Lookup by value	O(n)	O(n)
Memory	Contiguous	May have gaps
Iteration	Fast, sequential	Slower, random

When to Use Each:

Arrays: When you need ordered data, mathematical operations, or index-based access
Hash Tables: When you need fast key-based lookup, caching, or counting frequencies

🔟 JavaScript Map() - Deep Dive

How Map() Works Internally

JavaScript's Map is implemented as a hash table with additional optimizations:

Hash Table Structure: Uses internal hash table for O(1) average-case operations
Insertion Order: Maintains insertion order (unlike plain objects in older JS)
Any Key Type: Supports any data type as keys (objects, primitives, functions)
Optimized Memory: More memory-efficient than objects for frequent additions/deletions

Internal Implementation (Simplified):

// This is a simplified view of how Map might work internally
class JSMapLike {
  constructor() {
    this._data = new Array(16); // Initial bucket size
    this._size = 0;
    this._insertionOrder = []; // For maintaining order
  }
 
  _hash(key) {
    // JavaScript engines use sophisticated hash functions
    // This is simplified
    if (typeof key === 'string') {
      let hash = 0;
      for (let i = 0; i < key.length; i++) {
        hash = ((hash << 5) - hash + key.charCodeAt(i)) & 0x7fffffff;
      }
      return hash % this._data.length;
    } else if (typeof key === 'number') {
      return Math.abs(Math.floor(key)) % this._data.length;
    } else {
      // For objects, JS engines often use object identity/memory address
      return Object.prototype.toString.call(key).length % this._data.length;
    }
  }
 
  set(key, value) {
    let index = this._hash(key);
    
    if (!this._data[index]) {
      this._data[index] = [];
    }
    
    let bucket = this._data[index];
    let found = false;
    
    for (let entry of bucket) {
      if (Object.is(entry[0], key)) { // SameValueZero comparison
        entry[1] = value;
        found = true;
        break;
      }
    }
    
    if (!found) {
      bucket.push([key, value]);
      this._insertionOrder.push(key);
      this._size++;
    }
    
    return this;
  }
 
  get(key) {
    let index = this._hash(key);
    let bucket = this._data[index];
    
    if (bucket) {
      for (let entry of bucket) {
        if (Object.is(entry[0], key)) {
          return entry[1];
        }
      }
    }
    
    return undefined;
  }
 
  has(key) {
    return this.get(key) !== undefined;
  }
 
  delete(key) {
    let index = this._hash(key);
    let bucket = this._data[index];
    
    if (bucket) {
      for (let i = 0; i < bucket.length; i++) {
        if (Object.is(bucket[i][0], key)) {
          bucket.splice(i, 1);
          
          // Remove from insertion order
          let orderIndex = this._insertionOrder.indexOf(key);
          if (orderIndex > -1) {
            this._insertionOrder.splice(orderIndex, 1);
          }
          
          this._size--;
          return true;
        }
      }
    }
    
    return false;
  }
 
  get size() {
    return this._size;
  }
 
  // Iterator maintains insertion order
  *[Symbol.iterator]() {
    for (let key of this._insertionOrder) {
      yield [key, this.get(key)];
    }
  }
}

Real Map() Usage Examples:

// Creating and using Map
const userPreferences = new Map();
 
// Any type can be a key
const user1 = { id: 1, name: "Alice" };
const user2 = { id: 2, name: "Bob" };
 
userPreferences.set(user1, { theme: "dark", language: "en" });
userPreferences.set(user2, { theme: "light", language: "es" });
userPreferences.set("defaultTheme", "light");
userPreferences.set(42, "answer to everything");
 
// Getting values
console.log(userPreferences.get(user1)); // { theme: "dark", language: "en" }
console.log(userPreferences.get("defaultTheme")); // "light"
 
// Map maintains insertion order
for (let [key, value] of userPreferences) {
  console.log(key, "=>", value);
}
 
// Useful Map methods
console.log(userPreferences.size); // 4
console.log(userPreferences.has(user1)); // true
userPreferences.delete(user2);
userPreferences.clear(); // removes all entries

1️⃣1️⃣ When, Why, and How to Use Map()

🕐 When to Use Map():

Need non-string keys:

const cache = new Map();
const functionKey = () => "hello";
const objectKey = { id: 123 };
 
cache.set(functionKey, "cached result");
cache.set(objectKey, "user data");

Frequent additions/deletions:

// Better performance than objects for this
const activeConnections = new Map();
 
function addConnection(socket) {
  activeConnections.set(socket.id, socket);
}
 
function removeConnection(socketId) {
  activeConnections.delete(socketId);
}

Need to know the size:

const inventory = new Map();
inventory.set("apples", 50);
inventory.set("oranges", 30);
 
console.log(inventory.size); // 2 - O(1) operation
// vs Object.keys(obj).length - O(n) operation

Need iteration in insertion order:

const processQueue = new Map();
processQueue.set("task1", { priority: 1 });
processQueue.set("task2", { priority: 3 });
processQueue.set("task3", { priority: 2 });
 
// Process in order of insertion
for (let [taskId, task] of processQueue) {
  console.log(`Processing ${taskId}`);
}

🤔 Why Use Map():

Performance: O(1) average for get/set/delete operations
Flexibility: Any type as key (objects, functions, primitives)
Size tracking: Built-in size property
Iteration: Guaranteed insertion order
No default keys: Unlike objects, no prototype pollution
Cleaner API: Clear methods for common operations

🛠️ How to Use Map():

Basic Operations:

const map = new Map();
 
// Setting values
map.set("key1", "value1");
map.set(42, "number key");
map.set(true, "boolean key");
 
// Getting values
const value = map.get("key1");
 
// Checking existence
if (map.has("key1")) {
  console.log("Key exists!");
}
 
// Deleting
map.delete("key1");
 
// Clearing all
map.clear();

Advanced Patterns:

1. Caching/Memoization:

const memoCache = new Map();
 
function expensiveFunction(n) {
  if (memoCache.has(n)) {
    return memoCache.get(n);
  }
  
  // Expensive computation
  const result = n * n * n;
  memoCache.set(n, result);
  return result;
}

2. Counting Frequencies:

function countFrequencies(arr) {
  const frequencies = new Map();
  
  for (let item of arr) {
    frequencies.set(item, (frequencies.get(item) || 0) + 1);
  }
  
  return frequencies;
}
 
const fruits = ["apple", "banana", "apple", "orange", "banana", "apple"];
console.log(countFrequencies(fruits));
// Map { "apple" => 3, "banana" => 2, "orange" => 1 }

3. Grouping Objects:

const users = [
  { name: "Alice", department: "Engineering" },
  { name: "Bob", department: "Marketing" },
  { name: "Charlie", department: "Engineering" },
  { name: "Diana", department: "Sales" }
];
 
function groupBy(array, key) {
  const groups = new Map();
  
  for (let item of array) {
    const group = item[key];
    if (!groups.has(group)) {
      groups.set(group, []);
    }
    groups.get(group).push(item);
  }
  
  return groups;
}
 
const usersByDept = groupBy(users, "department");
console.log(usersByDept);

4. LRU Cache Implementation:

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
  }
 
  get(key) {
    if (this.cache.has(key)) {
      // Move to end (most recently used)
      const value = this.cache.get(key);
      this.cache.delete(key);
      this.cache.set(key, value);
      return value;
    }
    return -1;
  }
 
  put(key, value) {
    if (this.cache.has(key)) {
      this.cache.delete(key);
    } else if (this.cache.size >= this.capacity) {
      // Remove least recently used (first item)
      const firstKey = this.cache.keys().next().value;
      this.cache.delete(firstKey);
    }
    
    this.cache.set(key, value);
  }
}

1️⃣2️⃣ Map() vs Object vs Custom Hash Table

Feature	Map	Object	Custom Hash Table
Key Types	Any	String/Symbol	Depends on implementation
Size	`map.size`	`Object.keys(obj).length`	Custom property
Iteration Order	Insertion order	Insertion order (ES2015+)	Depends on implementation
Performance (get/set)	O(1) average	O(1) average	O(1) average
Prototype	No default keys	Has prototype	No prototype
JSON Serialization	Not directly	Native support	Custom implementation
Memory Overhead	Higher	Lower	Varies
Browser Support	ES6+	All	All

When to Choose Each:

Use Map when:

Need non-string keys
Frequent additions/deletions
Need exact size count
Want guaranteed iteration order
Need to avoid prototype pollution

Use Object when:

Keys are always strings
Need JSON serialization
Working with records/dictionaries
Need property access syntax (obj.prop)

Use Custom Hash Table when:

Need specific hash function behavior
Want to understand internals
Have specific performance requirements
Need custom collision resolution

🎯 Practical Examples and Use Cases

Example 1: User Session Management

class SessionManager {
  constructor() {
    this.sessions = new Map();
  }
 
  createSession(userId, sessionData) {
    const sessionId = this.generateSessionId();
    this.sessions.set(sessionId, {
      userId,
      ...sessionData,
      createdAt: new Date(),
      lastAccessed: new Date()
    });
    return sessionId;
  }
 
  getSession(sessionId) {
    const session = this.sessions.get(sessionId);
    if (session) {
      session.lastAccessed = new Date();
    }
    return session;
  }
 
  cleanupExpiredSessions(maxAge = 24 * 60 * 60 * 1000) { // 24 hours
    const now = Date.now();
    for (let [sessionId, session] of this.sessions) {
      if (now - session.lastAccessed.getTime() > maxAge) {
        this.sessions.delete(sessionId);
      }
    }
  }
 
  generateSessionId() {
    return Math.random().toString(36).substr(2, 9);
  }
}

Example 2: Event System with Map

class EventEmitter {
  constructor() {
    this.events = new Map();
  }
 
  on(event, callback) {
    if (!this.events.has(event)) {
      this.events.set(event, []);
    }
    this.events.get(event).push(callback);
  }
 
  emit(event, ...args) {
    if (this.events.has(event)) {
      this.events.get(event).forEach(callback => callback(...args));
    }
  }
 
  off(event, callback) {
    if (this.events.has(event)) {
      const callbacks = this.events.get(event);
      const index = callbacks.indexOf(callback);
      if (index > -1) {
        callbacks.splice(index, 1);
      }
      if (callbacks.length === 0) {
        this.events.delete(event);
      }
    }
  }
 
  listEvents() {
    return Array.from(this.events.keys());
  }
}
 
// Usage
const emitter = new EventEmitter();
const handler = (data) => console.log("Received:", data);
 
emitter.on("data", handler);
emitter.emit("data", "Hello World"); // Received: Hello World

📊 Performance Comparison

// Performance test function
function performanceTest() {
  const iterations = 1000000;
  const keys = Array.from({ length: iterations }, (_, i) => `key${i}`);
  
  // Test Map
  console.time("Map Set");
  const map = new Map();
  keys.forEach((key, i) => map.set(key, i));
  console.timeEnd("Map Set");
  
  console.time("Map Get");
  keys.forEach(key => map.get(key));
  console.timeEnd("Map Get");
  
  // Test Object
  console.time("Object Set");
  const obj = {};
  keys.forEach((key, i) => obj[key] = i);
  console.timeEnd("Object Set");
  
  console.time("Object Get");
  keys.forEach(key => obj[key]);
  console.timeEnd("Object Get");
  
  // Test Custom Hash Table
  console.time("Custom Hash Table Set");
  const ht = new HashTable(1000);
  keys.forEach((key, i) => ht.set(key, i));
  console.timeEnd("Custom Hash Table Set");
  
  console.time("Custom Hash Table Get");
  keys.forEach(key => ht.get(key));
  console.timeEnd("Custom Hash Table Get");
}
 
// Run the test
// performanceTest();

🎉 Summary

Hash tables are fundamental data structures that provide:

Fast O(1) average-case performance for basic operations
Flexible key-value storage with any data types as keys
Efficient memory usage when implemented properly

JavaScript's Map is a sophisticated, optimized hash table implementation that:

Maintains insertion order
Supports any key type
Provides excellent performance
Offers a clean, intuitive API

Understanding both the theory behind hash tables and the practical usage of Map will make you a more effective JavaScript developer and help you choose the right data structure for each situation.

Remember: Use the right tool for the job - Map for complex key-value scenarios, Objects for simple records, and custom implementations when you need specific behavior or want to learn the internals!

Arrays Analysis of Algorithms