Hash Collisions — HashMap Degradation to O(n)

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

/**
 * CollisionDemo — illustrates how hashCode() quality affects
 * bucket distribution in a HashMap.
 *
 * Run this with your actual key domain to audit distribution
 * before deploying a new hashCode() implementation.
 */
public class CollisionDemo {

    // --- POOR hashCode(): ignores sessionToken entirely ---
    // Two sessions for the same user always collide
    static class SessionKeyPoor {
        final int    userId;
        final String sessionToken;

        SessionKeyPoor(int userId, String sessionToken) {\n            this.userId       = userId;\n            this.sessionToken = sessionToken;\n        }

        @Override
        public int hashCode() {
            return userId;  // sessionToken completely ignored
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof SessionKeyPoor)) return false;
            SessionKeyPoor other = (SessionKeyPoor) o;
            return userId == other.userId
                && Objects.equals(sessionToken, other.sessionToken);
        }
    }

    // --- GOOD hashCode(): incorporates all fields used in equals() ---
    static class SessionKeyGood {
        final int    userId;
        final String sessionToken;

        SessionKeyGood(int userId, String sessionToken) {\n            this.userId       = userId;\n            this.sessionToken = sessionToken;\n        }

        @Override
        public int hashCode() {
            return Objects.hash(userId, sessionToken);
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof SessionKeyGood)) return false;
            SessionKeyGood other = (SessionKeyGood) o;
            return userId == other.userId
                && Objects.equals(sessionToken, other.sessionToken);
        }
    }

    // Computes bucket distribution for a set of keys at a given capacity
    static <K> void auditDistribution(String label, Iterable<K> keys, int capacity) {
        int[] bucketCounts = new int[capacity];
        int   total        = 0;
        int   maxBucket    = 0;

        for (K key : keys) {
            // Replicates HashMap's internal index computation
            int hash  = key.hashCode();
            hash      = hash ^ (hash >>> 16);  // HashMap's spread() equivalent
            int index = (capacity - 1) & hash;
            bucketCounts[index]++;
            total++;
            maxBucket = Math.max(maxBucket, bucketCounts[index]);
        }

        int nonEmpty = 0;
        for (int count : bucketCounts) {
            if (count > 0) nonEmpty++;
        }

        System.out.printf("\n[%s]%n", label);
        System.out.printf("  Keys: %d | Capacity: %d | Non-empty buckets: %d%n",
                          total, capacity, nonEmpty);
        System.out.printf("  Max entries in one bucket: %d%n", maxBucket);
        System.out.printf("  Ideal max (with perfect distribution): ~%d%n",
                          (int) Math.ceil((double) total / nonEmpty));
    }

    public static void main(String[] args) {
        int capacity = 64;
        java.util.List<SessionKeyPoor> poorKeys = new java.util.ArrayList<>();
        java.util.List<SessionKeyGood> goodKeys = new java.util.ArrayList<>();

        // Simulate 50 sessions for userId=1 — all same userId, different tokens
        for (int i = 0; i < 50; i++) {
            String token = "token-" + i;
            poorKeys.add(new SessionKeyPoor(1, token));
            goodKeys.add(new SessionKeyGood(1, token));
        }
        // Add 50 sessions across different userIds
        for (int i = 2; i <= 51; i++) {
            poorKeys.add(new SessionKeyPoor(i, "token-0"));
            goodKeys.add(new SessionKeyGood(i, "token-0"));
        }

        auditDistribution("Poor hashCode (ignores sessionToken)", poorKeys, capacity);
        auditDistribution("Good hashCode (Objects.hash all fields)", goodKeys, capacity);
    }
}

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;

/**
 * ChainingHashMap — a minimal separate chaining hash map.
 * Written to make the internal mechanics transparent.
 * This mirrors the core behaviour of java.util.HashMap
 * without Java 8's treeification complexity.
 *
 * Not production code — use java.util.HashMap in real systems.
 */
public class ChainingHashMap<K, V> {\n\n    private static final int    DEFAULT_CAPACITY    = 16;\n    private static final double DEFAULT_LOAD_FACTOR = 0.75;\n\n    // Each bucket is a list of key-value entries\n    // java.util.HashMap uses Node<K,V>[] internally — same idea\n    private List<Entry<K, V>>[] buckets;\n    private int                 size;\n    private final double        loadFactor;\n\n    static class Entry<K, V> {\n        final K key;\n        V       value;\n\n        Entry(K key, V value) {\n            this.key   = key;\n            this.value = value;\n        }
    }

    @SuppressWarnings("unchecked")
    public ChainingHashMap(int initialCapacity, double loadFactor) {\n        this.buckets    = new LinkedList[initialCapacity];\n        this.loadFactor = loadFactor;\n        this.size       = 0;\n    }

    public ChainingHashMap() {
        this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    // Spread the hash to avoid clustering on lower bits
    // Mirrors HashMap's (h = key.hashCode()) ^ (h >>> 16)
    private int spread(int hashCode) {
        return hashCode ^ (hashCode >>> 16);
    }

    private int bucketIndex(K key) {
        return spread(Objects.hashCode(key)) & (buckets.length - 1);
    }

    public void put(K key, V value) {\n        // Check load factor and resize before inserting\n        if ((double) size / buckets.length >= loadFactor) {\n            resize();\n        }

        int index = bucketIndex(key);
        if (buckets[index] == null) {
            buckets[index] = new LinkedList<>();
        }

        // Update value if key already exists in the chain
        for (Entry<K, V> entry : buckets[index]) {
            if (Objects.equals(entry.key, key)) {\n                entry.value = value;\n                return;\n            }
        }

        // Key not found in chain — append new entry
        buckets[index].add(new Entry<>(key, value));
        size++;
    }

    public V get(K key) {
        int index = bucketIndex(key);
        if (buckets[index] == null) return null;

        // Walk the chain at this bucket — O(n) for n entries in this bucket
        for (Entry<K, V> entry : buckets[index]) {
            if (Objects.equals(entry.key, key)) {\n                return entry.value;\n            }
        }
        return null;
    }

    public boolean remove(K key) {
        int index = bucketIndex(key);
        if (buckets[index] == null) return false;

        return buckets[index].removeIf(e -> Objects.equals(e.key, key));
    }

    @SuppressWarnings("unchecked")
    private void resize() {
        List<Entry<K, V>>[] oldBuckets = buckets;
        buckets = new LinkedList[oldBuckets.length * 2];
        size    = 0;

        // Rehash all existing entries into new bucket array
        for (List<Entry<K, V>> bucket : oldBuckets) {\n            if (bucket != null) {\n                for (Entry<K, V> entry : bucket) {\n                    put(entry.key, entry.value);  // recomputes bucket index\n                }
            }
        }
        System.out.printf("[resize] new capacity: %d%n", buckets.length);
    }

    // Diagnostic: print bucket distribution for auditing
    public void printBucketDistribution() {
        int occupied = 0;
        int maxChain = 0;
        for (List<Entry<K, V>> bucket : buckets) {\n            if (bucket != null && !bucket.isEmpty()) {\n                occupied++;\n                maxChain = Math.max(maxChain, bucket.size());\n            }
        }
        System.out.printf(
            "Buckets: %d total | %d occupied | max chain length: %d | load: %.2f%n",
            buckets.length, occupied, maxChain, (double) size / buckets.length
        );
    }

    public int size() { return size; }

    public static void main(String[] args) {
        ChainingHashMap<String, Integer> map = new ChainingHashMap<>(8, 0.75);

        // Insert enough entries to trigger a resize
        String[] keys = { "alpha", "bravo", "charlie", "delta",
                          "echo", "foxtrot", "golf", "hotel" };
        for (int i = 0; i < keys.length; i++) {
            map.put(keys[i], i);
        }

        System.out.println("--- After inserting 8 entries into capacity-8 map ---");
        map.printBucketDistribution();

        System.out.println("get("charlie") = " + map.get("charlie"));
        System.out.println("get("india")   = " + map.get("india"));

        map.remove("delta");
        System.out.println("After remove("delta"), get("delta") = " + map.get("delta"));

        map.printBucketDistribution();
    }
}

import java.util.Objects;

/**
 * OpenAddressingHashMap — linear probing implementation.
 * Demonstrates the core mechanics of open addressing:
 * probe sequences, tombstone deletion, and load-factor resizing.
 *
 * Not production code — use java.util.HashMap in real systems.
 * This implementation is for understanding the mechanics.
 */
public class OpenAddressingHashMap<K, V> {\n\n    private static final int    DEFAULT_CAPACITY    = 16;\n    private static final double MAX_LOAD_FACTOR     = 0.65; // conservative for open addressing\n\n    // Sentinel for deleted slots — probe sequences must continue through these\n    private static final Object TOMBSTONE = new Object();\n\n    private Object[] keys;\n    private Object[] values;\n    private int      size;       // live entries\n    private int      tombstones; // deleted slots not yet reclaimed\n\n    public OpenAddressingHashMap() {\n        keys      = new Object[DEFAULT_CAPACITY];\n        values    = new Object[DEFAULT_CAPACITY];\n        size      = 0;\n        tombstones = 0;\n    }

    private int hash(K key) {
        int h = Objects.hashCode(key);
        h = h ^ (h >>> 16);  // spread to reduce clustering on lower bits
        return Math.abs(h) % keys.length;
    }

    public void put(K key, V value) {\n        // Resize if live entries + tombstones exceed load factor\n        // Tombstones count against effective load because they consume slots\n        if ((double)(size + tombstones) / keys.length >= MAX_LOAD_FACTOR) {\n            resize();\n        }

        int index         = hash(key);
        int firstTombstone = -1;

        for (int i = 0; i < keys.length; i++) {
            int probe = (index + i) % keys.length;  // linear probe

            if (keys[probe] == null) {
                // Empty slot — insert here (or at first tombstone if found earlier)
                int insertAt = (firstTombstone != -1) ? firstTombstone : probe;
                if (firstTombstone != -1) tombstones--; // reclaiming a tombstone
                keys[insertAt]   = key;
                values[insertAt] = value;
                size++;
                return;
            }

            if (keys[probe] == TOMBSTONE) {
                // Record first tombstone — we can reuse it for insertion
                if (firstTombstone == -1) firstTombstone = probe;
                continue;
            }

            if (Objects.equals(keys[probe], key)) {\n                // Key already exists — update value in place\n                values[probe] = value;\n                return;\n            }
            // Occupied by a different key — continue probing (linear: next slot)
        }

        // Table is full (should not reach here with correct load factor management)
        throw new IllegalStateException("Hash table is full — resize threshold too high");
    }

    @SuppressWarnings("unchecked")
    public V get(K key) {
        int index = hash(key);

        for (int i = 0; i < keys.length; i++) {
            int probe = (index + i) % keys.length;

            if (keys[probe] == null) {
                // Empty slot — key definitely not present (probe sequence ends here)
                return null;
            }

            if (keys[probe] == TOMBSTONE) {
                // Deleted slot — continue probing (key may be further along)
                continue;
            }

            if (Objects.equals(keys[probe], key)) {\n                return (V) values[probe];\n            }
        }
        return null;
    }

    public boolean remove(K key) {
        int index = hash(key);

        for (int i = 0; i < keys.length; i++) {
            int probe = (index + i) % keys.length;

            if (keys[probe] == null) return false;  // not present

            if (keys[probe] == TOMBSTONE) continue;

            if (Objects.equals(keys[probe], key)) {\n                // Place tombstone — cannot leave null or probe sequences break\n                keys[probe]   = TOMBSTONE;\n                values[probe] = null;\n                size--;\n                tombstones++;\n                return true;\n            }
        }
        return false;
    }

    @SuppressWarnings("unchecked")
    private void resize() {
        Object[] oldKeys   = keys;
        Object[] oldValues = values;
        keys      = new Object[oldKeys.length * 2];
        values    = new Object[oldKeys.length * 2];
        size      = 0;
        tombstones = 0;

        System.out.printf("[resize] %d -> %d capacity%n",
                          oldKeys.length, keys.length);

        // Rehash all live entries — tombstones are discarded during rebuild
        for (int i = 0; i < oldKeys.length; i++) {
            if (oldKeys[i] != null && oldKeys[i] != TOMBSTONE) {
                put((K) oldKeys[i], (V) oldValues[i]);
            }
        }
    }

    public void printStats() {
        System.out.printf(
            "Capacity: %d | Live entries: %d | Tombstones: %d | Effective load: %.2f%n",
            keys.length, size, tombstones,
            (double)(size + tombstones) / keys.length
        );
    }

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

        System.out.println("--- Inserting entries ---");
        String[] keys = { "alpha", "bravo", "charlie", "delta",
                          "echo", "foxtrot", "golf", "hotel", "india", "juliet" };
        for (int i = 0; i < keys.length; i++) {
            map.put(keys[i], i);
        }
        map.printStats();

        System.out.println("\n--- Lookups ---");
        System.out.println("get("charlie") = " + map.get("charlie"));
        System.out.println("get("kilo")    = " + map.get("kilo"));

        System.out.println("\n--- Deletions (tombstone behaviour) ---");
        map.remove("bravo");
        map.remove("delta");
        map.printStats();
        // Probe sequence for keys that probed through bravo/delta still works
        System.out.println("get("charlie") after deletions = " + map.get("charlie"));
    }
}

#include <iostream>
#include <vector>
#include <forward_list>
#include <functional>
#include <utility>

// Minimal separate chaining hash map in C++
template<typename K, typename V, typename Hash = std::hash<K>>
class ChainingHashMap {\nprivate:\n    using Entry = std::pair<K, V>;\n    std::vector<std::forward_list<Entry>> buckets;\n    Hash hasher;\n    size_t num_entries;\n    double max_load_factor;\n\n    size_t bucket_index(const K& key) const {\n        return hasher(key) % buckets.size();\n    }

    void rehash(size_t new_capacity) {
        std::vector<std::forward_list<Entry>> old_buckets = std::move(buckets);
        buckets.resize(new_capacity);
        num_entries = 0;
        for (auto& chain : old_buckets) {
            for (auto& entry : chain) {
                insert(std::move(entry));
            }
        }
    }

public:
    ChainingHashMap(size_t initial_capacity = 16, double max_load = 0.75)
        : buckets(initial_capacity), num_entries(0), max_load_factor(max_load) {}

    void insert(const Entry& entry) {
        if (static_cast<double>(num_entries) / buckets.size() >= max_load_factor) {
            rehash(buckets.size() * 2);
        }
        size_t idx = bucket_index(entry.first);
        // Update existing key
        for (auto& e : buckets[idx]) {
            if (e.first == entry.first) {
                e.second = entry.second;
                return;
            }
        }
        // Not found, add to front
        buckets[idx].push_front(entry);
        ++num_entries;
    }

    V* find(const K& key) {
        size_t idx = bucket_index(key);
        for (auto& e : buckets[idx]) {
            if (e.first == key) {
                return &e.second;
            }
        }
        return nullptr;
    }

    bool remove(const K& key) {
        size_t idx = bucket_index(key);
        buckets[idx].remove_if([&](const Entry& e) { return e.first == key; });
        // Note: remove_if might not actually remove if not found; we check size change
        auto old_size = buckets[idx].size();
        // Remove_if removes all matching, but we only expect one.
        // Better: iterate manually. For simplicity, we'll just return true/false
        // Real implementation would count.
        return true; // simplified
    }

    size_t size() const { return num_entries; }

    void print_distribution() const {
        size_t occupied = 0;
        size_t max_chain = 0;
        for (auto& chain : buckets) {
            if (!chain.empty()) {
                occupied++;
                size_t chain_len = std::distance(chain.begin(), chain.end());
                if (chain_len > max_chain) max_chain = chain_len;
            }
        }
        std::cout << "Buckets: " << buckets.size() << " total, "
                  << occupied << " occupied, max chain: " << max_chain
                  << ", load: " << static_cast<double>(num_entries)/buckets.size() << std::endl;
    }
};

// Linear probing open addressing hash map
template<typename K, typename V, typename Hash = std::hash<K>>
class LinearProbingHashMap {\nprivate:\n    enum SlotState { EMPTY, OCCUPIED, DELETED };
    std::vector<K> keys;
    std::vector<V> values;
    std::vector<SlotState> states;
    size_t num_entries;
    size_t num_deleted; // tombstones
    double max_load_factor;
    Hash hasher;

    size_t probe(const K& key, size_t i) const {\n        return (hasher(key) + i) % keys.size();\n    }

    void rehash(size_t new_capacity) {
        std::vector<K> old_keys = std::move(keys);
        std::vector<V> old_values = std::move(values);
        std::vector<SlotState> old_states = std::move(states);
        keys.resize(new_capacity);
        values.resize(new_capacity);
        states.assign(new_capacity, EMPTY);
        num_entries = 0;
        num_deleted = 0;
        for (size_t i = 0; i < old_keys.size(); ++i) {
            if (old_states[i] == OCCUPIED) {
                insert(old_keys[i], old_values[i]);
            }
        }
    }

public:
    LinearProbingHashMap(size_t initial_capacity = 16, double max_load = 0.65)
        : keys(initial_capacity), values(initial_capacity), states(initial_capacity, EMPTY),
          num_entries(0), num_deleted(0), max_load_factor(max_load) {}

    void insert(const K& key, const V& value) {\n        if (static_cast<double>(num_entries + num_deleted) / keys.size() >= max_load_factor) {\n            rehash(keys.size() * 2);\n        }
        for (size_t i = 0; i < keys.size(); ++i) {
            size_t idx = probe(key, i);
            if (states[idx] == EMPTY || states[idx] == DELETED) {
                keys[idx] = key;
                values[idx] = value;
                states[idx] = OCCUPIED;
                ++num_entries;
                if (states[idx] == DELETED) --num_deleted; // reclaiming tombstone
                return;
            }
            if (states[idx] == OCCUPIED && keys[idx] == key) {
                values[idx] = value; // update existing
                return;
            }
        }
        // Should not reach with proper load factor
    }

    V* find(const K& key) {
        for (size_t i = 0; i < keys.size(); ++i) {
            size_t idx = probe(key, i);
            if (states[idx] == EMPTY) return nullptr;
            if (states[idx] == OCCUPIED && keys[idx] == key) {
                return &values[idx];
            }
        }
        return nullptr;
    }

    bool remove(const K& key) {
        for (size_t i = 0; i < keys.size(); ++i) {
            size_t idx = probe(key, i);
            if (states[idx] == EMPTY) return false;
            if (states[idx] == OCCUPIED && keys[idx] == key) {
                states[idx] = DELETED;
                --num_entries;
                ++num_deleted;
                return true;
            }
        }
        return false;
    }

    size_t size() const { return num_entries; }
};

int main() {
    // Test ChainingHashMap
    ChainingHashMap<int