public class HashTableManual {

    // Entri rantai: satu pasangan kunci-nilai plus tautan ke entri berikutnya.
    static class Entri {
        final String kunci;
        String nilai;
        Entri berikutnya;

        Entri(String kunci, String nilai) {
            this.kunci = kunci;
            this.nilai = nilai;
        }
    }

    private Entri[] bucket = new Entri[5];
    private int jumlah;

    // Penghitung node yang diperiksa ketika mengambil satu nilai.
    static long pemeriksaan;

    public static void main(String[] args) {
        HashTableManual tabel = new HashTableManual();
        tabel.taruh("Budi", "Jakarta");
        tabel.taruh("Siti", "Bandung");
        tabel.taruh("Dewi", "Semarang");
        tabel.taruh("Andi", "Yogyakarta");
        tabel.taruh("Rina", "Surabaya");
        tabel.taruh("Dodi", "Medan");
        tabel.taruh("Ani", "Denpasar");
        tabel.taruh("Bella", "Palembang");

        System.out.println("=== Penempatan kunci (hashCode mod 5) ===");
        for (String kunci : new String[] {"Budi", "Siti", "Dewi", "Andi",
                "Rina", "Dodi", "Ani", "Bella"}) {
            System.out.printf("  %-6s hash=%-11d -> bucket %d%n",
                    kunci, kunci.hashCode(), tabel.hash(kunci));
        }

        System.out.println();
        System.out.printf("=== Kapasitas 5, entri %d, load factor %.2f ===%n",
                tabel.jumlah, (double) tabel.jumlah / tabel.bucket.length);
        tabel.cetakDistribusi();

        pemeriksaan = 0;
        String nilai = tabel.ambil("Siti");
        System.out.println("ambil(\"Siti\") = " + nilai
                + ", node diperiksa: " + pemeriksaan);

        System.out.println();
        tabel.perbesar();
        System.out.printf("=== Setelah perbesar: kapasitas %d, load factor %.2f ===%n",
                tabel.bucket.length, (double) tabel.jumlah / tabel.bucket.length);
        tabel.cetakDistribusi();

        pemeriksaan = 0;
        nilai = tabel.ambil("Siti");
        System.out.println("ambil(\"Siti\") = " + nilai
                + ", node diperiksa: " + pemeriksaan);
    }

    int hash(String kunci) {
        return Math.floorMod(kunci.hashCode(), bucket.length);
    }

    void taruh(String kunci, String nilai) {
        int indeks = hash(kunci);
        for (Entri e = bucket[indeks]; e != null; e = e.berikutnya) {
            if (e.kunci.equals(kunci)) {
                e.nilai = nilai;    // kunci lama: perbarui nilainya
                return;
            }
        }
        Entri baru = new Entri(kunci, nilai);
        baru.berikutnya = bucket[indeks];   // sisip di kepala rantai: O(1)
        bucket[indeks] = baru;
        jumlah++;
    }

    String ambil(String kunci) {
        int indeks = hash(kunci);
        for (Entri e = bucket[indeks]; e != null; e = e.berikutnya) {
            pemeriksaan++;
            if (e.kunci.equals(kunci)) {
                return e.nilai;
            }
        }
        return null;
    }

    void perbesar() {
        Entri[] bucketLama = bucket;
        bucket = new Entri[bucketLama.length * 2];
        for (Entri kepala : bucketLama) {
            for (Entri e = kepala; e != null; ) {
                Entri berikutnya = e.berikutnya;
                int indeks = hash(e.kunci);       // hash dihitung ulang
                e.berikutnya = bucket[indeks];
                bucket[indeks] = e;
                e = berikutnya;
            }
        }
    }

    void cetakDistribusi() {
        int terpanjang = 0;
        for (int i = 0; i < bucket.length; i++) {
            StringBuilder sb = new StringBuilder();
            int panjang = 0;
            for (Entri e = bucket[i]; e != null; e = e.berikutnya) {
                sb.append(e.kunci).append("=").append(e.nilai);
                if (e.berikutnya != null) {
                    sb.append(" -> ");
                }
                panjang++;
            }
            terpanjang = Math.max(terpanjang, panjang);
            System.out.printf("  bucket[%d]: %s%n", i,
                    sb.isEmpty() ? "(kosong)" : sb);
        }
        System.out.printf("  rantai terpanjang: %d, rata-rata panjang rantai: %.2f%n",
                terpanjang, (double) jumlah / bucket.length);
    }
}