ChainingHashMap.java

/**
 * 手刻的雜湊表（hash table）：用「鏈結」（chaining，也叫 separate chaining）解決碰撞。
 *
 * 結構：一個桶陣列（buckets），每個桶是一條「鏈結串列」，串著所有雜湊到該桶的 (key, value)。
 *
 * 操作平均 O(1) 的前提：
 *   1. 雜湊函數分布均勻；
 *   2. 負載因子 size / buckets.length 不要太大——超過 0.75 就把桶陣列倍增並「重新雜湊」（rehash）。
 *
 * 資料不變量：
 *   - 每個鍵最多出現在一條鏈上、且出現一次；
 *   - 鍵 k 一定位於 buckets[indexFor(k)] 這條鏈上；
 *   - size 等於所有鏈的節點總數。
 */
public class ChainingHashMap<K, V> {

    /** 鏈結串列的節點：一個 (key, value) 對，加上指向同桶下一個節點的參照。 */
    private static class Node<K, V> {
        final K key;
        V value;
        Node<K, V> next;

        Node(K key, V value, Node<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    private static final double MAX_LOAD_FACTOR = 0.75;

    private Node<K, V>[] buckets;
    private int size = 0;

    @SuppressWarnings({"unchecked", "rawtypes"})   // 泛型陣列不能直接 new，只能 new Node[..] 再轉型
    public ChainingHashMap(int initialCapacity) {
        this.buckets = (Node<K, V>[]) new Node[Math.max(1, initialCapacity)];
    }

    public ChainingHashMap() {
        this(8);
    }

    /** 鍵 → 桶索引：用 floorMod 確保結果在 0..length-1（hashCode 可能是負數）。 */
    private int indexFor(K key, int length) {
        return Math.floorMod(key.hashCode(), length);
    }

    /** 在鍵所屬的鏈上找節點；找不到回傳 null。 */
    private Node<K, V> findNode(K key) {
        Node<K, V> n = this.buckets[indexFor(key, this.buckets.length)];
        while (n != null) {
            if (n.key.equals(key)) {      // 先用 hashCode 找桶，再用 equals 確認：兩者必須一致！
                return n;
            }
            n = n.next;
        }
        return null;
    }

    /** 新增或覆蓋。@return 舊值，若原本沒有則回傳 null */
    public V put(K key, V value) {
        if (key == null) {
            throw new IllegalArgumentException("鍵不可為 null");
        }
        Node<K, V> existing = findNode(key);
        if (existing != null) {
            V old = existing.value;
            existing.value = value;
            return old;
        }
        int idx = indexFor(key, this.buckets.length);
        this.buckets[idx] = new Node<>(key, value, this.buckets[idx]);   // 插在鏈的最前面：O(1)
        this.size = this.size + 1;
        if ((double) this.size / this.buckets.length > MAX_LOAD_FACTOR) {
            resize();
        }
        return null;
    }

    public V get(K key) {
        Node<K, V> n = findNode(key);
        return n == null ? null : n.value;
    }

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

    /** 移除鍵。@return 被移除的值，若不存在則回傳 null */
    public V remove(K key) {
        int idx = indexFor(key, this.buckets.length);
        Node<K, V> prev = null;
        Node<K, V> n = this.buckets[idx];
        while (n != null) {
            if (n.key.equals(key)) {
                if (prev == null) {
                    this.buckets[idx] = n.next;   // 移除的是鏈的第一個節點
                } else {
                    prev.next = n.next;           // 跳過 n
                }
                this.size = this.size - 1;
                return n.value;
            }
            prev = n;
            n = n.next;
        }
        return null;
    }

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

    public int capacity() {
        return this.buckets.length;
    }

    /** 桶陣列倍增，並把每個節點「重新雜湊」到新位置（索引會變，因為 length 變了）。 */
    @SuppressWarnings({"unchecked", "rawtypes"})
    private void resize() {
        Node<K, V>[] old = this.buckets;
        this.buckets = (Node<K, V>[]) new Node[old.length * 2];
        for (Node<K, V> n : old) {
            while (n != null) {
                Node<K, V> next = n.next;
                int idx = indexFor(n.key, this.buckets.length);
                n.next = this.buckets[idx];
                this.buckets[idx] = n;
                n = next;
            }
        }
    }

    /** 最長的鏈有幾個節點（用來觀察碰撞情況）。 */
    public int longestChain() {
        int best = 0;
        for (Node<K, V> n : this.buckets) {
            int len = 0;
            while (n != null) {
                len = len + 1;
                n = n.next;
            }
            best = Math.max(best, len);
        }
        return best;
    }

    /** 每個桶依序印出：方便看見「桶」與「鏈」長什麼樣子。 */
    public void dump() {
        for (int i = 0; i < this.buckets.length; i++) {
            StringBuilder sb = new StringBuilder("    [" + i + "]");
            Node<K, V> n = this.buckets[i];
            while (n != null) {
                sb.append(" → (").append(n.key).append(", ").append(n.value).append(")");
                n = n.next;
            }
            System.out.println(sb);
        }
    }
}