Hash Tables and Hash Maps Explained — How They Work, When to Use Them, and Why They're Fast

public class HashingMechanism {

    // Simulates what a hash table does internally:
    // takes a key, computes a bucket index, stores the value there.
    static final int BUCKET_COUNT = 16; // small number so we can see collisions easily

    public static int computeBucketIndex(String key) {
        // Step 1: get Java's built-in hash code for this string
        int hashCode = key.hashCode();

        // Step 2: hashCode can be negative, so we take absolute value
        int positiveHash = Math.abs(hashCode);

        // Step 3: use modulo to fit the hash into our bucket array
        // This is exactly what HashMap does internally (simplified)
        return positiveHash % BUCKET_COUNT;
    }

    public static void main(String[] args) {
        String[] keys = {"username", "email", "password", "sessionToken", "userId"};

        System.out.println("Key              | Hash Code       | Bucket Index");
        System.out.println("-".repeat(55));

        for (String key : keys) {
            int hashCode = key.hashCode();
            int bucketIndex = computeBucketIndex(key);
            // Each key lands in a different bucket — that's good distribution
            System.out.printf("%-16s | %-15d | %d%n", key, hashCode, bucketIndex);
        }

        // Demonstration: same key ALWAYS gives the same bucket (deterministic)
        System.out.println("\nRunning 'username' hash three times:");
        for (int i = 0; i < 3; i++) {
            System.out.println("  Bucket index: " + computeBucketIndex("username"));
        }
    }
}

import java.util.ArrayList;
import java.util.List;

// A hand-rolled hash table using separate chaining
// Building this yourself is the best way to truly understand HashMap internals
public class SeparateChainingHashTable<K, V> {

    // Each bucket holds a list of key-value pairs (the 'chain')
    private static class Entry<K, V> {
        K key;
        V value;

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

    private final int bucketCount;
    private final List<List<Entry<K, V>>> buckets;
    private int totalEntries;

    public SeparateChainingHashTable(int bucketCount) {
        this.bucketCount = bucketCount;
        this.buckets = new ArrayList<>(bucketCount);

        // Pre-fill with empty lists so we never get a NullPointerException
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<>());
        }
    }

    private int getBucketIndex(K key) {
        // Bitwise AND with max int to strip the sign bit — safer than Math.abs()
        return (key.hashCode() & Integer.MAX_VALUE) % bucketCount;
    }

    public void put(K key, V value) {
        int index = getBucketIndex(key);
        List<Entry<K, V>> chain = buckets.get(index);

        // Check if key already exists — if so, update the value (no duplicates)
        for (Entry<K, V> entry : chain) {
            if (entry.key.equals(key)) {
                entry.value = value; // overwrite existing value
                return;
            }
        }

        // Key not found in chain — append a new entry
        chain.add(new Entry<>(key, value));
        totalEntries++;
    }

    public V get(K key) {
        int index = getBucketIndex(key);
        List<Entry<K, V>> chain = buckets.get(index);

        // Walk the chain to find matching key
        for (Entry<K, V> entry : chain) {
            if (entry.key.equals(key)) {
                return entry.value;
            }
        }
        return null; // key doesn't exist
    }

    public double loadFactor() {
        // Load factor > 0.75 means it's time to resize (same threshold Java uses)
        return (double) totalEntries / bucketCount;
    }

    public void printBucketStats() {
        System.out.println("\nBucket distribution:");
        for (int i = 0; i < bucketCount; i++) {
            int chainLength = buckets.get(i).size();
            if (chainLength > 0) {
                System.out.printf("  Bucket %2d: %d item(s) %s%n",
                        i, chainLength, chainLength > 1 ? "<-- COLLISION" : "");
            }
        }
        System.out.printf("Load factor: %.2f%n", loadFactor());
    }

    public static void main(String[] args) {
        // Simulating a user session cache
        SeparateChainingHashTable<String, String> sessionCache =
                new SeparateChainingHashTable<>(8); // intentionally small to force collisions

        sessionCache.put("user:1001", "Alice");
        sessionCache.put("user:1002", "Bob");
        sessionCache.put("user:1003", "Carol");
        sessionCache.put("user:1004", "David");
        sessionCache.put("user:1005", "Eve");

        System.out.println("Looking up user:1003 -> " + sessionCache.get("user:1003"));
        System.out.println("Looking up user:9999 -> " + sessionCache.get("user:9999")); // not found

        // Update an existing key — should overwrite, not duplicate
        sessionCache.put("user:1001", "Alice Smith");
        System.out.println("After update, user:1001 -> " + sessionCache.get("user:1001"));

        sessionCache.printBucketStats();
    }
}

import java.util.*;

public class HashMapRealWorldUsage {

    // Use case 1: Word frequency counter — classic HashMap pattern
    public static Map<String, Integer> countWordFrequency(String[] words) {
        Map<String, Integer> frequencyMap = new HashMap<>();

        for (String word : words) {
            // getOrDefault avoids a null check on first encounter
            frequencyMap.put(word, frequencyMap.getOrDefault(word, 0) + 1);
        }
        return frequencyMap;
    }

    // Use case 2: Grouping items — one key maps to a collection of values
    public static Map<String, List<String>> groupStudentsByCourse(String[][] enrollments) {
        Map<String, List<String>> courseRoster = new HashMap<>();

        for (String[] enrollment : enrollments) {
            String course = enrollment[0];
            String student = enrollment[1];

            // computeIfAbsent creates the list only if the key is missing — cleaner than a null check
            courseRoster.computeIfAbsent(course, k -> new ArrayList<>()).add(student);
        }
        return courseRoster;
    }

    // Use case 3: Two-sum problem — shows how HashMap eliminates a nested loop
    public static int[] findTwoSum(int[] prices, int targetBudget) {
        // key = price we've seen, value = its index in the array
        Map<Integer, Integer> seenPrices = new HashMap<>();

        for (int i = 0; i < prices.length; i++) {
            int complement = targetBudget - prices[i];

            if (seenPrices.containsKey(complement)) {
                // Found the pair — O(1) lookup instead of scanning the array again
                return new int[]{seenPrices.get(complement), i};
            }
            seenPrices.put(prices[i], i);
        }
        return new int[]{}; // no valid pair found
    }

    public static void main(String[] args) {
        // --- Word Frequency ---
        String[] articleWords = {"hash", "table", "hash", "map", "hash", "table", "bucket"};
        Map<String, Integer> frequency = countWordFrequency(articleWords);
        System.out.println("Word frequencies:");
        // Sort by frequency descending for readable output
        frequency.entrySet().stream()
                .sorted(Map.Entry.<String, Integer>comparingByValue().reversed())
                .forEach(e -> System.out.printf("  %-10s: %d%n", e.getKey(), e.getValue()));

        // --- Course Grouping ---
        String[][] enrollments = {
                {"DSA", "Alice"}, {"DSA", "Bob"}, {"OS", "Alice"},
                {"Networking", "Carol"}, {"DSA", "Carol"}, {"OS", "Bob"}
        };
        Map<String, List<String>> roster = groupStudentsByCourse(enrollments);
        System.out.println("\nCourse rosters:");
        roster.forEach((course, students) ->
                System.out.printf("  %-12s: %s%n", course, students));

        // --- Two Sum ---
        int[] itemPrices = {15, 7, 30, 18, 3};
        int budget = 33;
        int[] result = findTwoSum(itemPrices, budget);
        System.out.printf("%nItems at indices %d and %d sum to budget of %d (prices: %d + %d)%n",
                result[0], result[1], budget, itemPrices[result[0]], itemPrices[result[1]]);
    }
}

import java.util.HashMap;
import java.util.Map;

public class HashMapPerformanceDemo {

    // A deliberately broken hashCode — returns the same value for everything
    // This is the worst-case scenario: all entries pile into one bucket
    static class BrokenProductId {
        private final String id;

        BrokenProductId(String id) { this.id = id; }

        @Override
        public int hashCode() {
            return 42; // every instance hashes to the same bucket — catastrophic
        }

        @Override
        public boolean equals(Object other) {
            if (this == other) return true;
            if (!(other instanceof BrokenProductId)) return false;
            return this.id.equals(((BrokenProductId) other).id);
        }
    }

    // A correct hashCode — delegates to the well-tested String implementation
    static class FixedProductId {
        private final String id;

        FixedProductId(String id) { this.id = id; }

        @Override
        public int hashCode() {
            return id.hashCode(); // distribute based on actual content
        }

        @Override
        public boolean equals(Object other) {
            if (this == other) return true;
            if (!(other instanceof FixedProductId)) return false;
            return this.id.equals(((FixedProductId) other).id);
        }
    }

    public static void main(String[] args) {
        int itemCount = 50_000;

        // --- Broken hash: O(n) per lookup ---
        Map<BrokenProductId, String> brokenMap = new HashMap<>();
        for (int i = 0; i < itemCount; i++) {
            brokenMap.put(new BrokenProductId("prod-" + i), "Product " + i);
        }

        long startBroken = System.nanoTime();
        String brokenResult = brokenMap.get(new BrokenProductId("prod-49999"));
        long brokenTime = System.nanoTime() - startBroken;

        // --- Fixed hash: O(1) per lookup ---
        Map<FixedProductId, String> fixedMap = new HashMap<>();
        for (int i = 0; i < itemCount; i++) {
            fixedMap.put(new FixedProductId("prod-" + i), "Product " + i);
        }

        long startFixed = System.nanoTime();
        String fixedResult = fixedMap.get(new FixedProductId("prod-49999"));
        long fixedTime = System.nanoTime() - startFixed;

        System.out.println("Broken hashCode lookup result : " + brokenResult);
        System.out.printf("Broken hashCode lookup time   : %,d ns%n", brokenTime);
        System.out.println("\nFixed hashCode lookup result  : " + fixedResult);
        System.out.printf("Fixed hashCode lookup time    : %,d ns%n", fixedTime);
        System.out.printf("%nSpeedup with correct hashCode : ~%.0fx faster%n",
                (double) brokenTime / fixedTime);
    }
}