// 第 11 周 – 用线性探测的开放定址法（整数键）
// 运行：java LinearProbing.java
public class LinearProbing {
    static final int EMPTY = Integer.MIN_VALUE;
    final int[] table;
    long probes; // 检查了多少个单元

    LinearProbing(int m) {
        table = new int[m];
        java.util.Arrays.fill(table, EMPTY);
    }

    int hash(int k) { return Math.floorMod(k, table.length); }

    // 插入：从 h(k) 开始，放入第一个空位
    void insert(int k) {
        int i = hash(k);
        for (int step = 0; step < table.length; step++) {
            probes++;
            int j = (i + step) % table.length;
            if (table[j] == EMPTY || table[j] == k) {
                table[j] = k;
                return;
            }
        }
        throw new IllegalStateException("the table is full");
    }

    // 查找：从 h(k) 开始逐个探测，直到找到或遇到空位
    boolean contains(int k) {
        int i = hash(k);
        for (int step = 0; step < table.length; step++) {
            probes++;
            int j = (i + step) % table.length;
            if (table[j] == EMPTY) return false;
            if (table[j] == k) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        LinearProbing t = new LinearProbing(10);
        for (int k : new int[] { 13, 7, 23, 33 }) t.insert(k);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < t.table.length; i++) sb.append(i).append(':').append(t.table[i] == EMPTY ? "-" : t.table[i]).append("  ");
        System.out.println(sb);
        t.probes = 0;
        System.out.println("contains(33) = " + t.contains(33) + " (" + t.probes + " probes)");
        t.probes = 0;
        System.out.println("contains(43) = " + t.contains(43) + " (" + t.probes + " probes)");
        System.out.println("Note: for deletion writing EMPTY is not enough – it would break the search chain (a \"deleted\" mark is needed).");

        // 装填因子的影响：查找成功时的平均探测次数
        System.out.println("\nLoad factor (α) and average number of probes for a successful search:");
        java.util.Random rnd = new java.util.Random(1);
        for (double alpha : new double[] { 0.25, 0.5, 0.75, 0.9, 0.99 }) {
            int m = 100_000, n = (int) (alpha * m);
            LinearProbing lp = new LinearProbing(m);
            int[] keys = new int[n];
            for (int i = 0; i < n; i++) {
                keys[i] = rnd.nextInt(Integer.MAX_VALUE);
                lp.insert(keys[i]);
            }
            lp.probes = 0;
            for (int k : keys) lp.contains(k);
            System.out.printf("  α = %.2f: %.2f%n", alpha, (double) lp.probes / n);
        }
    }
}