LinearProbingIntSet.java

/**
 * 用「線性探測」（linear probing，一種開放定址法 open addressing）實作的整數集合。
 *
 * 不用鏈結串列：所有元素直接放在桶陣列裡。
 * 碰撞時就往下一格找（到尾端繞回開頭），直到找到空格為止。
 *
 * 優點：記憶體連續、快取友善。缺點：容易形成「群聚」（clustering）——
 * 一長串被占用的格子會讓插入與查詢都變慢；因此負載因子要壓得更低（這裡 0.5）。
 *
 * 為了簡化，本類別只支援 add / contains（刪除需要「墓碑」標記，見教材說明）。
 *
 * 資料不變量：若 x 在集合中，則從 indexFor(x) 開始往後（繞回）掃到 x 之前，不會遇到空格。
 */
public class LinearProbingIntSet {

    private static final int EMPTY = Integer.MIN_VALUE;   // 哨兵值：代表「這格是空的」
    private int[] table;
    private int size = 0;
    public int probes = 0;                                // 統計探測次數（教學用）

    public LinearProbingIntSet(int capacity) {
        this.table = new int[Math.max(2, capacity)];
        java.util.Arrays.fill(this.table, EMPTY);
    }

    private int indexFor(int x, int length) {
        return Math.floorMod(Integer.hashCode(x) * 0x9E3779B1, length);   // 乘一個大奇數「攪亂」一下
    }

    public boolean add(int x) {
        if (x == EMPTY) {
            throw new IllegalArgumentException("此實作不能存放 Integer.MIN_VALUE（被當成哨兵值）");
        }
        if (contains(x)) {
            return false;
        }
        if ((this.size + 1) * 2 > this.table.length) {   // 負載因子超過 0.5：倍增並重新插入
            resize();
        }
        int i = indexFor(x, this.table.length);
        while (this.table[i] != EMPTY) {                 // 線性探測：往下一格找
            this.probes = this.probes + 1;
            i = (i + 1) % this.table.length;             // 到尾端就繞回開頭
        }
        this.table[i] = x;
        this.size = this.size + 1;
        return true;
    }

    public boolean contains(int x) {
        int i = indexFor(x, this.table.length);
        while (this.table[i] != EMPTY) {                 // 遇到空格就可以確定不存在
            this.probes = this.probes + 1;
            if (this.table[i] == x) {
                return true;
            }
            i = (i + 1) % this.table.length;
        }
        return false;
    }

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

    private void resize() {
        int[] old = this.table;
        this.table = new int[old.length * 2];
        java.util.Arrays.fill(this.table, EMPTY);
        this.size = 0;
        for (int x : old) {
            if (x != EMPTY) {
                add(x);                                  // 重新插入（索引會變）
            }
        }
    }

    /** 印出桶陣列：'.' 代表空格。 */
    public void dump() {
        StringBuilder sb = new StringBuilder("    ");
        for (int x : this.table) {
            sb.append(x == EMPTY ? "." : String.valueOf(x)).append(' ');
        }
        System.out.println(sb);
    }
}