StringHashing.java

/**
 * 雜湊函數（hash function）實驗：字串的多項式滾動雜湊 vs 壞的雜湊。
 *
 * 編譯與執行：javac StringHashing.java && java -ea StringHashing
 */
public class StringHashing {

    /**
     * 多項式滾動雜湊（polynomial rolling hash）：
     *   h = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
     * 每一步把累積值乘 31 再加下一個字元，所以「位置」也會影響結果（"ab" != "ba"）。
     * 這基本上就是 java.lang.String.hashCode() 的演算法。
     * 注意：int 會溢位（overflow），這沒關係——溢位後的值一樣是確定性的。
     */
    static int goodHash(String s) {
        int h = 0;
        int i = 0;
        while (i < s.length()) {
            h = 31 * h + s.charAt(i);
            i = i + 1;
        }
        return h;
    }

    /** 只把字元加總：位置資訊丟了，"ab" 與 "ba" 必撞（分布差）。 */
    static int mediocreHash(String s) {
        int h = 0;
        for (char c : s.toCharArray()) {
            h = h + c;
        }
        return h;
    }

    /** 「正確」但完全沒用的雜湊：滿足等價一致性與確定性，卻讓所有鍵撞在同一桶。 */
    static int badHash(String s) {
        return 0;
    }

    /** 把雜湊值變成合法的桶索引：先取絕對值再取餘數（注意 Integer.MIN_VALUE 的陷阱）。 */
    static int bucketOf(int hash, int capacity) {
        return Math.floorMod(hash, capacity);   // floorMod 永遠回傳 0..capacity-1，比 Math.abs(h) % c 安全
    }

    interface Hasher {
        int hash(String s);
    }

    /** 統計 words 被 hasher 分到 capacity 個桶時，最擠的桶有幾個鍵、有幾個空桶。 */
    static void report(String name, Hasher hasher, String[] words, int capacity) {
        int[] counts = new int[capacity];
        for (String w : words) {
            counts[bucketOf(hasher.hash(w), capacity)]++;
        }
        int maxBucket = 0, empty = 0;
        for (int c : counts) {
            if (c > maxBucket) {
                maxBucket = c;
            }
            if (c == 0) {
                empty++;
            }
        }
        System.out.printf("  %-13s 最擠的桶 = %3d 個鍵，空桶 = %3d / %d%n", name, maxBucket, empty, capacity);
    }

    public static void main(String[] args) {
        System.out.println("=== 1. 雜湊函數必須「尊重等價」：equals 的兩個字串雜湊值相同 ===");
        String a = "hello";
        String b = new String("hello");             // 不同物件、相同內容
        assert a != b && a.equals(b);
        assert goodHash(a) == goodHash(b);
        assert a.hashCode() == b.hashCode();
        System.out.println("  goodHash(\"hello\") = " + goodHash(a) + "，String.hashCode() = " + a.hashCode());
        assert goodHash(a) == a.hashCode() : "我們的實作應與 String.hashCode 一致";

        System.out.println("=== 2. 位置很重要 ===");
        System.out.println("  goodHash(ab) = " + goodHash("ab") + "，goodHash(ba) = " + goodHash("ba"));
        System.out.println("  mediocreHash(ab) = " + mediocreHash("ab") + "，mediocreHash(ba) = " + mediocreHash("ba") + "（碰撞！）");

        System.out.println("=== 3. 溢位是正常現象：值仍然是確定性的 ===");
        String longStr = "The quick brown fox jumps over the lazy dog";
        System.out.println("  goodHash(長句) = " + goodHash(longStr) + "（可能是負數）");
        System.out.println("  桶索引（容量 16）= " + bucketOf(goodHash(longStr), 16));

        System.out.println("=== 4. 分布品質：1000 個鍵放進 128 個桶 ===");
        String[] words = new String[1000];
        for (int i = 0; i < words.length; i++) {
            words[i] = "user" + i;                   // 很規律的鍵：對雜湊函數是嚴苛的考驗
        }
        report("goodHash", StringHashing::goodHash, words, 128);
        report("mediocreHash", StringHashing::mediocreHash, words, 128);
        report("badHash", StringHashing::badHash, words, 128);
        System.out.println("  （理想狀況：1000/128 ≈ 8 個鍵一桶）");
        System.out.println("全部通過。");
    }
}