Hash Maps: When and Why

// Simplified hash function (real ones are more complex)
function hash(key, arraySize) {
  let hash = 0;
  for (let char of key) {
    hash = (hash + char.charCodeAt(0)) % arraySize;
  }
  return hash;
}

// Example
hash("apple", 10);  // Returns index 0-9
hash("banana", 10); // Returns different index
// Modulo (%) keeps result within array bounds

// Conceptual representation
const hashMap = [
  null,                    // Index 0: empty
  { key: "apple", value: 5 },  // Index 1
  null,
  [                        // Index 3: collision! (chaining)
    { key: "banana", value: 3 },
    { key: "cherry", value: 7 }
  ],
  // ...
];

// Usage
map.set("apple", 5);     // Hash "apple" → index 1
map.get("apple");        // Returns 5
map.set("banana", 3);    // Hash "banana" → index 3
map.set("cherry", 7);    // Hash collision! → also index 3

class HashMap {
  constructor() {
    this.buckets = new Array(10).fill(null).map(() => []);
    this.size = 0;
  }

  hash(key) {
    return key.length % this.buckets.length;
  }

  set(key, value) {
    const index = this.hash(key);
    const bucket = this.buckets[index];
    
    // Check if key exists, update
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        bucket[i][1] = value;
        return;
      }
    }
    
    // Add new entry
    bucket.push([key, value]);
    this.size++;
  }

  get(key) {
    const index = this.hash(key);
    const bucket = this.buckets[index];
    
    for (let [k, v] of bucket) {
      if (k === key) return v;
    }
    return undefined;
  }
}

// Usage
const map = new HashMap();
map.set("apple", 5);
map.set("banana", 3);  // Might collide with apple
map.get("apple");      // Still fast: scan short chain

class HashMapProbing {
  constructor() {
    this.buckets = new Array(10).fill(null);
    this.size = 0;
  }

  hash(key) {
    return key.length % this.buckets.length;
  }

  set(key, value) {
    let index = this.hash(key);
    
    // Find next empty slot
    while (this.buckets[index] !== null) {
      if (this.buckets[index][0] === key) {
        this.buckets[index][1] = value; // Update existing
        return;
      }
      index = (index + 1) % this.buckets.length; // Wrap around
    }
    
    this.buckets[index] = [key, value];
    this.size++;
  }

  get(key) {
    let index = this.hash(key);
    
    while (this.buckets[index] !== null) {
      if (this.buckets[index][0] === key) {
        return this.buckets[index][1];
      }
      index = (index + 1) % this.buckets.length;
    }
    return undefined;
  }
}

// Before resize: capacity 10, size 8 → load factor 0.8
// Triggers resize!

// After resize: capacity 20, size 8 → load factor 0.4
// All entries rehashed with new capacity

// Why? Keeps chains short → maintains O(1) performance

// ❌ Brute Force: O(n²)
function twoSumBrute(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
  return null;
}

// ✅ Hash Map: O(n)
function twoSum(nums, target) {
  const map = new Map(); // value → index
  
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    
    if (map.has(complement)) {
      return [map.get(complement), i];
    }
    
    map.set(nums[i], i);
  }
  
  return null;
}

// Example
twoSum([2, 7, 11, 15], 9); // Returns [0, 1] (2 + 7 = 9)

// How it works:
// i=0: looking for 7 (9-2), not found, store 2→0
// i=1: looking for 2 (9-7), FOUND at index 0! Return [0, 1]

function groupAnagrams(strs) {
  const map = new Map(); // sorted → [words]
  
  for (let str of strs) {
    // Key: sorted version (anagrams have same sorted form)
    const key = str.split('').sort().join('');
    
    if (!map.has(key)) {
      map.set(key, []);
    }
    map.get(key).push(str);
  }
  
  return Array.from(map.values());
}

// Example
groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]);
// Returns: [["eat","tea","ate"], ["tan","nat"], ["bat"]]

// How it works:
// "eat" → sorted "aet" → map["aet"] = ["eat"]
// "tea" → sorted "aet" → map["aet"] = ["eat", "tea"]
// "tan" → sorted "ant" → map["ant"] = ["tan"]
// etc.

function lengthOfLongestSubstring(s) {
  const map = new Map(); // char → last index
  let maxLen = 0;
  let start = 0;
  
  for (let end = 0; end < s.length; end++) {
    const char = s[end];
    
    // If seen and within current window, move start
    if (map.has(char) && map.get(char) >= start) {
      start = map.get(char) + 1;
    }
    
    map.set(char, end);
    maxLen = Math.max(maxLen, end - start + 1);
  }
  
  return maxLen;
}

// Example
lengthOfLongestSubstring("abcabcbb"); // Returns 3 ("abc")

// Trace "abcabcbb":
// a: map={a:0}, start=0, len=1
// b: map={a:0,b:1}, start=0, len=2
// c: map={a:0,b:1,c:2}, start=0, len=3
// a: duplicate at 0! start=1, map={a:3,b:1,c:2}, len=3
// b: duplicate at 1! start=2, map={a:3,b:4,c:2}, len=3
// c: duplicate at 2! start=3, map={a:3,b:4,c:5}, len=3
// ...

function firstUniqChar(s) {
  // Two passes: count frequencies, then find first with count 1
  const freq = new Map();
  
  for (let char of s) {
    freq.set(char, (freq.get(char) || 0) + 1);
  }
  
  for (let i = 0; i < s.length; i++) {
    if (freq.get(s[i]) === 1) {
      return i;
    }
  }
  
  return -1;
}

// Example
firstUniqChar("leetcode"); // Returns 0 ('l')
firstUniqChar("loveleetcode"); // Returns 2 ('v')

// Why two passes?
// First pass: count all frequencies O(n)
// Second pass: find first with count 1 O(n)
// Total: O(n) time, O(1) space (max 26 letters)