import java.util.*;

public class TabelHashSederhana {
    @SuppressWarnings("unchecked")
    public static void main(String[] args) {
        List<Integer>[] bucket = new List[4];
        for (int i = 0; i < bucket.length; i++) {
            bucket[i] = new ArrayList<>();
        }
        int ukuran = 0;

        int[] data = {10, 22, 31, 4, 17, 28};
        for (int n : data) {
            if (ukuran + 1 > bucket.length * 3 / 4) {
                bucket = rehash(bucket);
            }
            int indeks = n % bucket.length;
            String keterangan = bucket[indeks].isEmpty()
                    ? "" : " (tabrakan dengan " + bucket[indeks].get(0) + ")";
            bucket[indeks].add(n);
            ukuran++;
            System.out.println("Masukkan " + n + " -> bucket " + indeks + keterangan
                    + " [kapasitas " + bucket.length + "]");
        }

        System.out.println();
        for (int i = 0; i < bucket.length; i++) {
            System.out.println("Bucket " + i + " : " + bucket[i]);
        }

        System.out.println();
        System.out.print("Urutan iterasi: ");
        for (List<Integer> daftar : bucket) {
            for (int n : daftar) {
                System.out.print(n + " ");
            }
        }
        System.out.println();
    }

    @SuppressWarnings("unchecked")
    private static List<Integer>[] rehash(List<Integer>[] lama) {
        List<Integer>[] baru = new List[lama.length * 2];
        for (int i = 0; i < baru.length; i++) {
            baru[i] = new ArrayList<>();
        }
        for (List<Integer> daftar : lama) {
            for (int n : daftar) {
                baru[n % baru.length].add(n);
            }
        }
        System.out.println("  >> load factor 0.75 terlampaui: kapasitas "
                + lama.length + " -> " + baru.length);
        return baru;
    }
}