HashDemo.java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Set;

/**
 * 07_hashing 示範程式：手刻雜湊表、線性探測、HashMap/HashSet、equals/hashCode 契約、可變鍵的災難。
 *
 * 編譯與執行：
 *   javac *.java
 *   java -ea HashDemo
 */
public class HashDemo {

    /** 一個「值型」的類別：兩個座標相同就該視為同一個鍵。 */
    @SuppressWarnings("overrides")   // 故意示範錯誤：javac 其實會警告「覆寫了 equals 卻沒覆寫 hashCode」
    static class PointNoHash {
        final int x, y;
        PointNoHash(int x, int y) { this.x = x; this.y = y; }

        @Override
        public boolean equals(Object o) {          // 只覆寫 equals、忘了 hashCode → 契約被破壞
            return o instanceof PointNoHash p && p.x == x && p.y == y;
        }
    }

    /** 正確版：equals 與 hashCode 一起覆寫，且用同一組欄位。 */
    static class Point {
        final int x, y;
        Point(int x, int y) { this.x = x; this.y = y; }

        @Override
        public boolean equals(Object o) {
            return o instanceof Point p && p.x == x && p.y == y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);             // 標準寫法：把所有參與 equals 的欄位丟進去
        }

        @Override
        public String toString() { return "(" + x + "," + y + ")"; }
    }

    /** record：自動產生「一致」的 equals 與 hashCode，是最安全的鍵。 */
    record Coord(int x, int y) {}

    /** 用手刻雜湊表找出出現最多次的單字。 */
    static String mostCommonWord(String[] words) {
        ChainingHashMap<String, Integer> counts = new ChainingHashMap<>();
        for (String w : words) {
            Integer c = counts.get(w);
            counts.put(w, c == null ? 1 : c + 1);
        }
        String best = null;
        int bestCount = -1;
        for (String w : words) {
            int c = counts.get(w);
            if (c > bestCount) {
                best = w;
                bestCount = c;
            }
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println("=== 1. 手刻的鏈結雜湊表 ===");
        ChainingHashMap<String, Integer> ages = new ChainingHashMap<>(4);
        ages.put("Liam", 30);
        ages.put("Thomas", 25);
        ages.put("Alice", 28);
        System.out.println("  容量 " + ages.capacity() + "，size " + ages.size() + "：");
        ages.dump();
        ages.put("Bob", 41);                                  // 負載 4/4 > 0.75 → 觸發倍增
        System.out.println("  put(Bob) 後容量 " + ages.capacity() + "（倍增＋重新雜湊）：");
        ages.dump();
        assert ages.get("Liam") == 30 && ages.get("Nobody") == null;
        assert ages.put("Liam", 31) == 30 && ages.get("Liam") == 31;   // 覆蓋回傳舊值
        assert ages.remove("Thomas") == 25 && !ages.containsKey("Thomas");
        assert ages.size() == 3;

        System.out.println("=== 2. 大量資料：鏈保持很短 ===");
        ChainingHashMap<String, Integer> big = new ChainingHashMap<>();
        for (int i = 0; i < 100_000; i++) {
            big.put("key" + i, i);                            // 十萬個字串鍵
        }
        for (int i = 0; i < 100_000; i++) {
            assert big.get("key" + i) == i;
        }
        System.out.println("  100000 個鍵，容量 " + big.capacity() + "，最長的鏈 = " + big.longestChain());

        String[] words = "the cat and the dog and the bird".split(" ");
        System.out.println("  最常見的單字 = " + mostCommonWord(words));
        assert mostCommonWord(words).equals("the");

        System.out.println("=== 3. 線性探測 ===");
        LinearProbingIntSet set = new LinearProbingIntSet(8);
        for (int x : new int[]{5, 13, 21, 7, 29}) {
            set.add(x);
        }
        set.dump();
        assert set.contains(13) && !set.contains(99) && set.size() == 5;
        set.probes = 0;
        for (int i = 0; i < 1000; i++) {
            set.add(i * 37);
        }
        System.out.println("  加入 1000 個元素共探測 " + set.probes + " 次（平均每次 "
                + String.format("%.2f", set.probes / 1000.0) + " 次額外探測）");

        System.out.println("=== 4. 標準函式庫：HashMap 與 HashSet ===");
        Map<String, Integer> wordCount = new HashMap<>();
        for (String w : words) {
            wordCount.merge(w, 1, Integer::sum);              // 有就 +1，沒有就放 1
        }
        System.out.println("  wordCount = " + wordCount);
        Set<Integer> seen = new HashSet<>();
        int[] data = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
        List<Integer> dups = new ArrayList<>();
        for (int d : data) {
            if (!seen.add(d)) {                               // add 回傳 false 表示已存在
                dups.add(d);
            }
        }
        System.out.println("  重複出現的數字 = " + dups);

        System.out.println("=== 5. equals/hashCode 契約 ===");
        Set<PointNoHash> broken = new HashSet<>();
        broken.add(new PointNoHash(1, 2));
        System.out.println("  只覆寫 equals：contains(new PointNoHash(1,2)) = "
                + broken.contains(new PointNoHash(1, 2)) + "  ← 找不到！");
        Set<Point> good = new HashSet<>();
        good.add(new Point(1, 2));
        System.out.println("  equals+hashCode：contains(new Point(1,2)) = " + good.contains(new Point(1, 2)));
        Set<Coord> rec = new HashSet<>();
        rec.add(new Coord(1, 2));
        System.out.println("  record：contains(new Coord(1,2)) = " + rec.contains(new Coord(1, 2)));
        assert !broken.contains(new PointNoHash(1, 2)) && good.contains(new Point(1, 2)) && rec.contains(new Coord(1, 2));

        System.out.println("=== 6. 可變的鍵是災難 ===");
        List<String> key = new ArrayList<>(List.of("a"));
        Map<List<String>, Integer> map = new HashMap<>();
        map.put(key, 42);
        System.out.println("  put 之後 get(key) = " + map.get(key));
        key.add("b");                                          // 改變了鍵 → hashCode 變了
        System.out.println("  key.add(\"b\") 之後 get(key) = " + map.get(key)
                + "，size = " + map.size() + "  ← 值還在表裡，卻永遠找不到");
        assert map.get(key) == null && map.size() == 1;
        System.out.println("全部通過。");
    }
}