Hash Tables

Definition

---

Big O Complexity

---

When to Use

---

Pros and Cons

---

Collision Resolution

---

Implementation

HashMap Implementation (Chaining)

public class MyHashMap<K, V> {
    private class Entry {
        K key;
        V value;
        Entry next;

        Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    private Entry[] buckets;
    private int size;
    private int capacity;
    private static final int DEFAULT_CAPACITY = 16;
    private static final double LOAD_FACTOR = 0.75;

    public MyHashMap() {
        this.capacity = DEFAULT_CAPACITY;
        this.buckets = new Entry[capacity];
        this.size = 0;
    }

    private int hash(K key) {
        return Math.abs(key.hashCode() % capacity);
    }

    public void put(K key, V value) {
        if ((double) size / capacity >= LOAD_FACTOR) {
            resize();
        }

        int index = hash(key);
        Entry entry = buckets[index];

        // Check if key exists
        while (entry != null) {
            if (entry.key.equals(key)) {
                entry.value = value;  // Update
                return;
            }
            entry = entry.next;
        }

        // Insert at head of chain
        Entry newEntry = new Entry(key, value);
        newEntry.next = buckets[index];
        buckets[index] = newEntry;
        size++;
    }

    public V get(K key) {
        int index = hash(key);
        Entry entry = buckets[index];

        while (entry != null) {
            if (entry.key.equals(key)) {
                return entry.value;
            }
            entry = entry.next;
        }
        return null;
    }

    public boolean containsKey(K key) {
        return get(key) != null;
    }

    public V remove(K key) {
        int index = hash(key);
        Entry entry = buckets[index];
        Entry prev = null;

        while (entry != null) {
            if (entry.key.equals(key)) {
                if (prev == null) {
                    buckets[index] = entry.next;
                } else {
                    prev.next = entry.next;
                }
                size--;
                return entry.value;
            }
            prev = entry;
            entry = entry.next;
        }
        return null;
    }

    private void resize() {
        Entry[] oldBuckets = buckets;
        capacity *= 2;
        buckets = new Entry[capacity];
        size = 0;

        for (Entry entry : oldBuckets) {
            while (entry != null) {
                put(entry.key, entry.value);
                entry = entry.next;
            }
        }
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }
}

HashSet Implementation

public class MyHashSet<E> {
    private MyHashMap<E, Object> map;
    private static final Object PRESENT = new Object();

    public MyHashSet() {
        map = new MyHashMap<>();
    }

    public void add(E e) {
        map.put(e, PRESENT);
    }

    public boolean contains(E e) {
        return map.containsKey(e);
    }

    public void remove(E e) {
        map.remove(e);
    }

    public int size() {
        return map.size();
    }
}

---

Java Collections Usage

// HashMap
Map<String, Integer> map = new HashMap<>();
map.put("apple", 5);                    // Add
map.get("apple");                        // Get - returns 5
map.getOrDefault("banana", 0);          // Get with default
map.containsKey("apple");               // Check key
map.containsValue(5);                   // Check value
map.remove("apple");                    // Remove
map.size();                             // Size
map.isEmpty();                          // Is empty
map.clear();                            // Clear all

// Iteration
for (String key : map.keySet()) { }
for (Integer value : map.values()) { }
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    String key = entry.getKey();
    Integer value = entry.getValue();
}

// Common operations
map.putIfAbsent("key", 1);              // Add if not present
map.merge("key", 1, Integer::sum);      // Add or merge
map.compute("key", (k, v) -> v == null ? 1 : v + 1);
map.computeIfAbsent("key", k -> new ArrayList<>());

// HashSet
Set<String> set = new HashSet<>();
set.add("apple");
set.contains("apple");
set.remove("apple");

// LinkedHashMap - maintains insertion order
Map<String, Integer> linkedMap = new LinkedHashMap<>();

// TreeMap - sorted by key
Map<String, Integer> treeMap = new TreeMap<>();

// ConcurrentHashMap - thread-safe
Map<String, Integer> concurrentMap = new ConcurrentHashMap<>();

---

Common Patterns & Problems

Two Sum

public 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[] {};
}

Group Anagrams

public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();

    for (String s : strs) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);

        map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }

    return new ArrayList<>(map.values());
}

First Non-Repeating Character

public int firstUniqChar(String s) {
    Map<Character, Integer> count = new HashMap<>();

    for (char c : s.toCharArray()) {
        count.merge(c, 1, Integer::sum);
    }

    for (int i = 0; i < s.length(); i++) {
        if (count.get(s.charAt(i)) == 1) {
            return i;
        }
    }
    return -1;
}

Longest Substring Without Repeating Characters

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> map = new HashMap<>();
    int maxLen = 0, left = 0;

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (map.containsKey(c)) {
            left = Math.max(left, map.get(c) + 1);
        }
        map.put(c, right);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

Subarray Sum Equals K

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> prefixCount = new HashMap<>();
    prefixCount.put(0, 1);  // Empty prefix

    int count = 0, prefixSum = 0;

    for (int num : nums) {
        prefixSum += num;
        count += prefixCount.getOrDefault(prefixSum - k, 0);
        prefixCount.merge(prefixSum, 1, Integer::sum);
    }

    return count;
}

LRU Cache

class LRUCache extends LinkedHashMap<Integer, Integer> {
    private int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);  // accessOrder = 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<Integer, Integer> eldest) {
        return size() > capacity;
    }
}

Frequency Count Pattern

// Count character frequencies
public Map<Character, Integer> countFrequencies(String s) {
    Map<Character, Integer> freq = new HashMap<>();
    for (char c : s.toCharArray()) {
        freq.merge(c, 1, Integer::sum);
    }
    return freq;
}

// Find top K frequent elements
public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int num : nums) {
        count.merge(num, 1, Integer::sum);
    }

    return count.entrySet().stream()
        .sorted((a, b) -> b.getValue() - a.getValue())
        .limit(k)
        .mapToInt(Map.Entry::getKey)
        .toArray();
}

---

Hash Function Guidelines

---

Tips & Tricks

---