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

Time Complexity

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