Hash Collisions — Bad hashCode() Killed Response Times

public class HashFunctionDemo {

    // A simple hash function: sum the ASCII values of all characters,
    // multiply by a prime to reduce clustering, then fit into tableSize slots.
    static int computeHash(String key, int tableSize) {
        int hashValue = 0;
        for (int i = 0; i < key.length(); i++) {
            // charAt gives the character's ASCII integer value
            hashValue = (hashValue * 31 + key.charAt(i)) % tableSize;
        }
        return hashValue;
    }

    public static void main(String[] args) {
        int tableSize = 7; // small table so collisions happen quickly

        String[] keys = {"cat", "dog", "act", "god", "tac"};

        System.out.println("Key    -> Hash Index (table size = " + tableSize + ")");
        System.out.println("-------------------------------");

        for (String key : keys) {
            int index = computeHash(key, tableSize);
            System.out.printf("%-6s -> slot %d%n", key, index);
        }
    }
}

import java.util.LinkedList;

public class ChainingHashMap {

    // Each entry in the table holds a linked list of KeyValuePair objects
    static class KeyValuePair {
        String key;
        String value;

        KeyValuePair(String key, String value) {
            this.key = key;
            this.value = value;
        }
    }

    private static final int TABLE_SIZE = 7;

    // The hash table: an array where each slot is a linked list (the "chain")
    @SuppressWarnings("unchecked")
    private LinkedList<KeyValuePair>[] table = new LinkedList[TABLE_SIZE];

    ChainingHashMap() {
        // Pre-fill every slot with an empty list so we never hit a null pointer
        for (int i = 0; i < TABLE_SIZE; i++) {
            table[i] = new LinkedList<>();
        }
    }

    private int getSlot(String key) {
        int hashValue = 0;
        for (int i = 0; i < key.length(); i++) {
            hashValue = (hashValue * 31 + key.charAt(i)) % TABLE_SIZE;
        }
        return hashValue;
    }

    // INSERT: compute the slot, then append to that slot's linked list
    public void put(String key, String value) {
        int slot = getSlot(key);
        LinkedList<KeyValuePair> chain = table[slot];

        // If the key already exists, update its value instead of duplicating it
        for (KeyValuePair pair : chain) {
            if (pair.key.equals(key)) {
                pair.value = value; // update in place
                System.out.println("Updated '" + key + "' at slot " + slot);
                return;
            }
        }

        // Key not found in the chain — add a new entry
        chain.add(new KeyValuePair(key, value));
        System.out.println("Inserted '" + key + "' at slot " + slot
                + (chain.size() > 1 ? " [COLLISION — chain length now " + chain.size() + "]" : ""));
    }

    // LOOKUP: go to the slot, walk the chain looking for a matching key
    public String get(String key) {
        int slot = getSlot(key);
        for (KeyValuePair pair : table[slot]) {
            if (pair.key.equals(key)) {
                return pair.value; // found it
            }
        }
        return null; // key doesn't exist in the map
    }

    // Print every slot and its chain so we can visualize the structure
    public void printTable() {
        System.out.println("\n--- Hash Table State ---");
        for (int i = 0; i < TABLE_SIZE; i++) {
            System.out.print("Slot " + i + ": ");
            if (table[i].isEmpty()) {
                System.out.println("[empty]");
            } else {
                StringBuilder sb = new StringBuilder();
                for (KeyValuePair pair : table[i]) {
                    sb.append("[").append(pair.key).append("=>").append(pair.value).append("] -> ");
                }
                System.out.println(sb.toString().replaceAll(" -> $", ""));
            }
        }
    }

    public static void main(String[] args) {
        ChainingHashMap map = new ChainingHashMap();

        map.put("cat",   "feline");
        map.put("dog",   "canine");
        map.put("act",   "perform");  // 'act' collides with 'cat' at slot 3
        map.put("god",   "deity");    // 'god' collides with 'dog' at slot 6
        map.put("tac",   "fastener");
        map.put("cat",   "kitty");    // updating an existing key

        map.printTable();

        System.out.println("\nLookup 'act' -> " + map.get("act"));
        System.out.println("Lookup 'god' -> " + map.get("god"));
        System.out.println("Lookup 'xyz' -> " + map.get("xyz"));
    }
}

public class LinearProbingHashMap {

    private static final int TABLE_SIZE = 11; // prime number reduces clustering
    private static final String TOMBSTONE = "__DELETED__"; // marker for deleted slots

    private String[] keys   = new String[TABLE_SIZE];
    private String[] values = new String[TABLE_SIZE];

    private int computeHash(String key) {
        int hashValue = 0;
        for (int i = 0; i < key.length(); i++) {
            hashValue = (hashValue * 31 + key.charAt(i)) % TABLE_SIZE;
        }
        return hashValue;
    }

    // INSERT: find the target slot; if it's taken, probe forward one step at a time
    public void put(String key, String value) {
        int startSlot = computeHash(key);
        int currentSlot = startSlot;
        int probeCount = 0;

        while (probeCount < TABLE_SIZE) {
            // A null slot or a tombstone (deleted) slot is available for writing
            if (keys[currentSlot] == null || keys[currentSlot].equals(TOMBSTONE)) {
                keys[currentSlot]   = key;
                values[currentSlot] = value;
                System.out.printf("Inserted '%s' at slot %d (probed %d time(s))%n",
                        key, currentSlot, probeCount);
                return;
            }

            // If the same key already exists, overwrite its value
            if (keys[currentSlot].equals(key)) {
                values[currentSlot] = value;
                System.out.printf("Updated '%s' at slot %d%n", key, currentSlot);
                return;
            }

            // Slot is occupied by a different key — move to the next slot (linear probe)
            currentSlot = (currentSlot + 1) % TABLE_SIZE; // wrap around with modulo
            probeCount++;
        }

        System.out.println("Table is full! Could not insert '" + key + "'");
    }

    // LOOKUP: start at the hash slot and probe forward until we find the key or an empty slot
    public String get(String key) {
        int startSlot = computeHash(key);
        int currentSlot = startSlot;
        int probeCount = 0;

        while (probeCount < TABLE_SIZE) {
            if (keys[currentSlot] == null) {
                return null; // genuinely empty — key was never inserted
            }
            if (keys[currentSlot].equals(key)) {
                return values[currentSlot]; // found the key
            }
            // Keep probing past tombstones and other occupied slots
            currentSlot = (currentSlot + 1) % TABLE_SIZE;
            probeCount++;
        }
        return null;
    }

    // DELETE: we can't just set to null (would break probe chains), so place a tombstone
    public void delete(String key) {
        int startSlot = computeHash(key);
        int currentSlot = startSlot;
        int probeCount = 0;

        while (probeCount < TABLE_SIZE) {
            if (keys[currentSlot] == null) return; // key doesn't exist
            if (keys[currentSlot].equals(key)) {
                keys[currentSlot]   = TOMBSTONE; // mark as deleted, don't break the chain
                values[currentSlot] = null;
                System.out.println("Deleted '" + key + "' at slot " + currentSlot);
                return;
            }
            currentSlot = (currentSlot + 1) % TABLE_SIZE;
            probeCount++;
        }
    }

    public void printTable() {
        System.out.println("\n--- Hash Table State ---");
        for (int i = 0; i < TABLE_SIZE; i++) {
            if (keys[i] == null) {
                System.out.printf("Slot %2d: [empty]%n", i);
            } else if (keys[i].equals(TOMBSTONE)) {
                System.out.printf("Slot %2d: [tombstone]%n", i);
            } else {
                System.out.printf("Slot %2d: %s => %s%n", i, keys[i], values[i]);
            }
        }
    }

    public static void main(String[] args) {
        LinearProbingHashMap map = new LinearProbingHashMap();

        map.put("apple",  "fruit");
        map.put("grape",  "vine fruit");  // may collide depending on hash
        map.put("mango",  "tropical");
        map.put("lemon",  "citrus");
        map.put("apple",  "red fruit");   // updating existing key

        map.printTable();

        System.out.println("\nLookup 'mango' -> " + map.get("mango"));
        System.out.println("Lookup 'kiwi'  -> " + map.get("kiwi"));

        map.delete("grape");
        System.out.println("After deleting 'grape':");
        System.out.println("Lookup 'mango' -> " + map.get("mango")); // still works!
    }
}

public class LoadFactorDemo {

    // This demo shows WHY we care about the load factor:
    // as it rises, the average probe count in a linear-probing table climbs fast.

    static int simulateInserts(int tableSize, int itemsToInsert) {
        String[] table = new String[tableSize];
        int totalProbes = 0;

        for (int item = 0; item < itemsToInsert; item++) {
            // Simulate a key with a spread-out hash using item * prime
            int slot = (item * 37) % tableSize;
            int probes = 0;

            // Linear probe until we find an empty slot
            while (table[slot] != null) {
                slot = (slot + 1) % tableSize;
                probes++;
            }
            table[slot] = "item" + item;
            totalProbes += probes;
        }

        return totalProbes;
    }

    public static void main(String[] args) {
        int tableSize = 100;

        System.out.println("Load Factor | Items | Total Extra Probes | Avg Probes/Insert");
        System.out.println("------------------------------------------------------------");

        int[] itemCounts = {10, 30, 50, 70, 80, 90, 95};

        for (int items : itemCounts) {
            double loadFactor = (double) items / tableSize;
            int totalProbes = simulateInserts(tableSize, items);
            double avgProbes = (double) totalProbes / items;

            System.out.printf("   %.2f     |  %3d  |        %5d       |      %.2f%n",
                    loadFactor, items, totalProbes, avgProbes);
        }
    }
}

public class HashMapInternalsDemo {
    // Simulate Java's treeification threshold logic
    // In real HashMap, when TREEIFY_THRESHOLD = 8 and chain length >= 8,
    // the chain is converted to a TreeNode (Red-Black tree).

    public static void main(String[] args) {
        java.util.HashMap<String, String> map = new java.util.HashMap<>();

        // Insert 10 keys all with same hash (simulate bad hashCode)
        String base = "badHash";
        for (int i = 0; i < 10; i++) {
            map.put(base + i, "value" + i);
        }

        // Lookup time stays fast because Java's treeification handles the long chain
        long start = System.nanoTime();
        String val = map.get("badHash9");
        long end = System.nanoTime();
        System.out.println("Lookup took " + (end - start) + " ns — still fast due to treeification");

        // Show table size after resizing
        try {
            java.lang.reflect.Field tableField = java.util.HashMap.class.getDeclaredField("table");
            tableField.setAccessible(true);
            Object[] table = (Object[]) tableField.get(map);
            System.out.println("Table length: " + table.length);
        } catch (Exception e) {
            System.out.println("Cannot reflect table size");
        }
    }
}

import java.util.HashMap;

public class MutableKeyTrap {
    static class MutableKey {
        int id;
        String name;

        MutableKey(int id, String name) {
            this.id = id;
            this.name = name;
        }

        @Override
        public int hashCode() { return id * 31 + name.hashCode(); }

        @Override
        public boolean equals(Object o) {
            if (!(o instanceof MutableKey)) return false;
            MutableKey other = (MutableKey) o;
            return this.id == other.id && this.name.equals(other.name);
        }
    }

    public static void main(String[] args) {
        HashMap<MutableKey, String> map = new HashMap<>();

        MutableKey key = new MutableKey(1, "Alice");
        map.put(key, "value1");

        System.out.println("Before mutation: " + map.get(key)); // "value1"

        key.id = 2;  // mutate! hashCode changes but bucket remains old

        System.out.println("After mutation: " + map.get(key)); // null — key lost!

        // The old key is still in the map but in the wrong bucket
        // Create a new key with original state to find it:
        MutableKey originalKey = new MutableKey(1, "Alice");
        System.out.println("With original state: " + map.get(originalKey)); // still "value1"
    }
}

// io.thecodeforge.hash.DoubleHashTable
public class DoubleHashTable<K, V> {
    private Entry<K, V>[] table;
    private int capacity;

    public DoubleHashTable(int capacity) {
        this.capacity = capacity;
        this.table = new Entry[capacity];
    }

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

    // Must be odd, less than capacity, and never 0
    private int hash2(K key) {
        return 1 + (Math.abs(key.hashCode() % (capacity - 1)));
    }

    public void put(K key, V value) {
        int idx = hash1(key);
        int step = hash2(key);
        while (table[idx] != null && !table[idx].deleted) {
            if (table[idx].key.equals(key)) {
                table[idx].value = value;
                return;
            }
            idx = (idx + step) % capacity;
        }
        table[idx] = new Entry<>(key, value);
    }
}

// io.thecodeforge.hash.RobinHoodHash
public class RobinHoodHash<K, V> {
    private static class Entry<K, V> {
        K key; V value; int dist; // distance from ideal slot
    }

    private Entry<K, V>[] table;
    private int capacity;

    public RobinHoodHash(int capacity) {
        this.capacity = capacity;
        this.table = new Entry[capacity];
    }

    public void put(K key, V value) {
        int idx = Math.abs(key.hashCode() % capacity);
        int dist = 0;
        Entry<K, V> newEntry = new Entry<>(key, value, dist);
        while (true) {
            Entry<K, V> cur = table[idx];
            if (cur == null) {
                table[idx] = newEntry;
                return;
            }
            if (cur.key.equals(key)) {
                cur.value = value;
                return;
            }
            // Swap if new entry has drifted further
            if (newEntry.dist > cur.dist) {
                table[idx] = newEntry;
                newEntry = cur;
            }
            idx = (idx + 1) % capacity;
            newEntry.dist++;
        }
    }
}