Hashing

What is a Hash Table?

A hash table is a data structure that maps keys to values using a hash function. It provides O(1) average-time lookup, insertion, and deletion.

How It Works

Key: "apple" → Hash Function → Index: 3

Table:
Index 0: []
Index 1: []
Index 2: []
Index 3: ["apple" → 5.00]  ← stored here
Index 4: []
Index 5: []

The Hash Function

A hash function converts a key into an array index.

// Simple hash function for strings
int hash(String key) {
    int hash = 0;
    for (char c : key.toCharArray()) {
        hash = (hash * 31 + c) % capacity;
    }
    return hash;
}

Why O(1) Average?

1. Hash function distributes keys evenly
2. Each bucket has ~1 element on average
3. Direct access to bucket: O(1)

Java Collections

// HashMap: Key-Value pairs
Map<String, Integer> map = new HashMap<>();
map.put("apple", 5);
int price = map.get("apple");  // 5

// HashSet: Unique elements only
Set<String> set = new HashSet<>();
set.add("apple");
boolean exists = set.contains("apple");  // true

// LinkedHashMap: Maintains insertion order
Map<String, Integer> linked = new LinkedHashMap<>();

// TreeMap: Sorted by key
Map<String, Integer> tree = new TreeMap<>();

Common Operations

Map<String, Integer> map = new HashMap<>();

// Insert
map.put("key", 100);

// Access
int val = map.get("key");           // 100
int val2 = map.getOrDefault("missing", 0); // 0

// Check existence
boolean hasKey = map.containsKey("key");    // true
boolean hasVal = map.containsValue(100);     // true

// Remove
map.remove("key");

// Size
int size = map.size();

// Iterate
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

// Get all keys
Set<String> keys = map.keySet();

// Get all values
Collection<Integer> values = map.values();

What is a Collision?

When two different keys hash to the same index.

"apple" → hash → 3
"grape" → hash → 3  ← Collision!

Collision Resolution

1. Chaining (Java's approach)

Each bucket contains a linked list:

Index 3: [("apple", 5) → ("grape", 4)]

2. Open Addressing

Find another empty slot:

Index 3: ("apple", 5)
Index 4: ("grape", 4)  ← probe next slot

When Collisions Happen

• Many keys hash to same index
• Load factor too high
• Poor hash function

Load Factor

Load Factor = (number of elements) / (number of buckets)

Java's HashMap resizes when load factor > 0.75.

Impact on Performance

Load Factor	Avg Chain Length	Performance
0.1	0.1	O(1)
0.5	0.5	O(1)
0.75	0.75	O(1)
1.0	1.0	O(1)-O(n)
2.0	2.0	O(n) worst

Time Complexity

Operation	Average	Worst Case
Insert	O(1)	O(n)
Lookup	O(1)	O(n)
Delete	O(1)	O(n)

Worst case happens when all keys hash to same bucket (degrades to linked list).

The Pattern

Count occurrences of each element.

// Count character frequencies
String s = "hello";
Map<Character, Integer> freq = new HashMap<>();
for (char c : s.toCharArray()) {
    freq.put(c, freq.getOrDefault(c, 0) + 1);
}
// freq = {h:1, e:1, l:2, o:1}

Using for Arrays

// Count element frequencies
int[] arr = {1, 2, 2, 3, 3, 3};
Map<Integer, Integer> freq = new HashMap<>();
for (int num : arr) {
    freq.put(num, freq.getOrDefault(num, 0) + 1);
}
// freq = {1:1, 2:2, 3:3}

Common Problems

1. Find Most Frequent Element

int maxCount = 0;
int mostFrequent = 0;
for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
    if (entry.getValue() > maxCount) {
        maxCount = entry.getValue();
        mostFrequent = entry.getKey();
    }
}

2. Check if All Characters Are Unique

boolean allUnique(String s) {
    Set<Character> seen = new HashSet<>();
    for (char c : s.toCharArray()) {
        if (!seen.add(c)) return false;
    }
    return true;
}

3. Find First Non-Repeating Character

int firstNonRepeating(String s) {
    Map<Character, Integer> freq = new HashMap<>();
    for (char c : s.toCharArray()) {
        freq.put(c, freq.getOrDefault(c, 0) + 1);
    }
    for (int i = 0; i < s.length(); i++) {
        if (freq.get(s.charAt(i)) == 1) return i;
    }
    return -1;
}

Frequency Counting Template

Map<T, Integer> freq = new HashMap<>();
for (T element : collection) {
    freq.put(element, freq.getOrDefault(element, 0) + 1);
}

When to Use

• Counting occurrences
• Finding duplicates
• Grouping elements
• Checking permutations/anagrams
• Two Sum pattern

Pattern 1: Two Sum

Find two numbers that add to target.

int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] {map.get(complement), i};
        }
        map.put(nums[i], i);
    }
    return new int[] {};
}
// Time: O(n), Space: O(n)

Pattern 2: Grouping

Group elements by some property.

// Group by remainder when divided by k
Map<Integer, List<Integer>> groups = new HashMap<>();
for (int num : nums) {
    int key = ((num % k) + k) % k;  // handle negatives
    groups.computeIfAbsent(key, k -> new ArrayList<>()).add(num);
}

Pattern 3: Subarray Sum

Find subarrays with given sum.

int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> prefixSums = new HashMap<>();
    prefixSums.put(0, 1);
    int sum = 0, count = 0;
    
    for (int num : nums) {
        sum += num;
        if (prefixSums.containsKey(sum - k)) {
            count += prefixSums.get(sum - k);
        }
        prefixSums.put(sum, prefixSums.getOrDefault(sum, 0) + 1);
    }
    return count;
}
// Time: O(n), Space: O(n)

Pattern 4: Anagram Detection

Check if strings are anagrams.

boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    
    int[] count = new int[26];
    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i) - 'a']++;
        count[t.charAt(i) - 'a']--;
    }
    
    for (int c : count) {
        if (c != 0) return false;
    }
    return true;
}

Pattern 5: LRU Cache

class LRUCache extends LinkedHashMap<Integer, Integer> {
    private int capacity;
    
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }
    
    public int get(int key) {
        return super.getOrDefault(key, -1);
    }
    
    public void put(int key, int value) {
        super.put(key, value);
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > capacity;
    }
}

When to Use Hashing

Problem Type	Pattern
Two Sum	Complement lookup
Grouping	Key-based grouping
Frequency	Count occurrences
Anagram	Character count
Subarray sum	Prefix sum
Caching	LRU/LFU