Hash Map Hash-Flooding Attack — 2ms to 30s Latency

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);
    }
}

#include <iostream>
#include <unordered_map>
#include <string>
#include <vector>

// Custom hash for a pair (like for adjacency lists)
struct PairHash {
    std::size_t operator()(const std::pair<int, int>& p) const {
        // Simple combination: use two different primes
        return std::hash<int>()(p.first) ^ (std::hash<int>()(p.second) << 1);
    }
};

int main() {
    // Word frequency counter — same logic as Java example
    std::vector<std::string> words = {"hash", "table", "hash", "map", "hash", "table", "bucket"};
    std::unordered_map<std::string, int> freq;

    for (const auto& word : words) {
        freq[word]++; // default-initializes to 0 on first access
    }

    std::cout << "Word frequencies (C++ unordered_map):\n";
    for (const auto& [word, count] : freq) {
        std::cout << "  " << word << ": " << count << "\n";
    }

    // Inspect bucket distribution
    std::cout << "\nBucket distribution (bucket count = " << freq.bucket_count() << "):\n";
    for (std::size_t i = 0; i < freq.bucket_count(); ++i) {
        std::size_t bucket_size = freq.bucket_size(i);
        if (bucket_size > 0) {
            std::cout << "  Bucket " << i << ": " << bucket_size << " item(s)";
            if (bucket_size > 1) std::cout << " <-- COLLISION";
            std::cout << "\n";
        }
    }

    // Using custom hash for pair key
    std::unordered_map<std::pair<int, int>, std::string, PairHash> edgeLabel;
    edgeLabel[{1, 2}] = "direct";
    edgeLabel[{2, 3}] = "indirect";
    std::cout << "\nEdge label for (1,2): " << edgeLabel[{1, 2}] << "\n";

    return 0;
}

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

public class HashMapResizeDemo {

    public static void main(String[] args) {
        // Without pre-sizing — runs through resizes
        long startNoSize = System.nanoTime();
        Map<Integer, String> noSizeMap = new HashMap<>();
        for (int i = 0; i < 100_000; i++) {
            noSizeMap.put(i, "value-" + i);
        }
        long timeNoSize = System.nanoTime() - startNoSize;

        // With pre-sizing — capacity = expectedSize / 0.75
        int expectedSize = 100_000;
        int initialCapacity = (int) (expectedSize / 0.75);
        long startSized = System.nanoTime();
        Map<Integer, String> sizedMap = new HashMap<>(initialCapacity);
        for (int i = 0; i < expectedSize; i++) {
            sizedMap.put(i, "value-" + i);
        }
        long timeSized = System.nanoTime() - startSized;

        System.out.printf("Time without pre-sizing: %,d ns%n", timeNoSize);
        System.out.printf("Time with pre-sizing:    %,d ns%n", timeSized);
        System.out.printf("Speedup: ~%.0f%%%n", (double)(timeNoSize - timeSized)/timeNoSize * 100);
    }
}

// io.thecodeforge — dsa tutorial

public class HashTableSimple {
    private final String[] keys;
    private final String[] values;
    private final int capacity;

    public HashTableSimple(int capacity) {
        this.capacity = capacity;
        this.keys = new String[capacity];
        this.values = new String[capacity];
    }

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

    public void put(String key, String value) {
        int index = hash(key);
        while (keys[index] != null && !keys[index].equals(key)) {
            index = (index + 1) % capacity; // linear probing
        }
        keys[index] = key;
        values[index] = value;
    }

    public String get(String key) {
        int index = hash(key);
        while (keys[index] != null) {
            if (keys[index].equals(key)) return values[index];
            index = (index + 1) % capacity;
        }
        return null;
    }

    public static void main(String[] args) {
        HashTableSimple table = new HashTableSimple(10);
        table.put("username", "sherlock");
        table.put("password", "221b_baker");
        System.out.println(table.get("username"));
        System.out.println(table.get("missing"));
    }
}

// io.thecodeforge — dsa tutorial

import java.util.HashMap;

public class LoadFactorDemo {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>(16, 0.5f);
        
        long start = System.nanoTime();
        for (int i = 0; i < 1_000_000; i++) {
            map.put("key-" + i, i);
        }
        long end = System.nanoTime();
        System.out.println("Load factor 0.5: " + (end - start) / 1_000_000 + "ms");

        HashMap<String, Integer> map2 = new HashMap<>(16, 0.9f);
        
        start = System.nanoTime();
        for (int i = 0; i < 1_000_000; i++) {
            map2.put("key-" + i, i);
        }
        end = System.nanoTime();
        System.out.println("Load factor 0.9: " + (end - start) / 1_000_000 + "ms");
    }
}

// io.thecodeforge — dsa tutorial

import java.util.HashMap;

public class ResizeImpact {
    public static void main(String[] args) {
        HashMap<String, Integer> poorlySized = new HashMap<>();
        HashMap<String, Integer> wellSized = new HashMap<>(16384, 0.75f);

        long start = System.nanoTime();
        for (int i = 0; i < 10_000; i++) {
            poorlySized.put("key-" + i, i);
        }
        long end = System.nanoTime();
        System.out.println("Poorly sized: " + (end - start) / 1_000_000 + "ms");

        start = System.nanoTime();
        for (int i = 0; i < 10_000; i++) {
            wellSized.put("key-" + i, i);
        }
        end = System.nanoTime();
        System.out.println("Well sized: " + (end - start) / 1_000_000 + "ms");
    }
}