Semua struktur sejauh ini menemukan data dengan menelusurinya: linear search memeriksa elemen satu per satu, BST berjalan menyusuri cabang. Hash table menembak lebih langsung: dari kunci, hitung satu indeks array, dan data sudah menunggu di sana — rata-rata O(1) untuk sisip, pencarian, dan penghapusan. Struktur inilah yang berdiri di balik HashMap dan HashSet di pustaka Java, struktur data yang paling sering dipakai di aplikasi nyata. Kekuatan tersebut menuntut dua syarat yang harus dipahami: fungsi hash yang menyebar kunci secara merata, dan strategi menangani collision ketika dua kunci mendarat di bucket yang sama.

Dari Kunci ke Indeks Bucket #

Mekanismenya tiga langkah. Pertama, method hashCode() mengubah kunci menjadi bilangan bulat. Kedua, bilangan itu di-modulo-kan dengan jumlah bucket untuk mendapat indeks array yang sah; Java memakai Math.floorMod agar hasil selalu positif. Ketiga, entri disimpan di bucket tersebut. Idealnya setiap bucket hanya berisi satu entri sehingga pencarian berhenti setelah satu perbandingan. Kenyataannya, jumlah kunci tak terbatas sementara jumlah bucket terbatas — dua kunci berbeda pasti bisa mendarat di bucket sama; kejadian inilah yang disebut collision.

Kita bangun versi manualnya dengan bucket array berkapasitas 5 dan chaining: setiap bucket adalah linked list kecil dari entri yang berbagi alamat yang sama:

java HashTableManual.java 
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);
    }
}

Output yang Dihasilkan:

text 
=== Penempatan kunci (hashCode mod 5) ===
  Budi   hash=2081848     -> bucket 3
  Siti   hash=2577259     -> bucket 4
  Dewi   hash=2126643     -> bucket 3
  Andi   hash=2045330     -> bucket 0
  Rina   hash=2547274     -> bucket 4
  Dodi   hash=2135664     -> bucket 4
  Ani    hash=65980       -> bucket 0
  Bella  hash=64068510    -> bucket 0

=== Kapasitas 5, entri 8, load factor 1.60 ===
  bucket[0]: Bella=Palembang -> Ani=Denpasar -> Andi=Yogyakarta
  bucket[1]: (kosong)
  bucket[2]: (kosong)
  bucket[3]: Dewi=Semarang -> Budi=Jakarta
  bucket[4]: Dodi=Medan -> Rina=Surabaya -> Siti=Bandung
  rantai terpanjang: 3, rata-rata panjang rantai: 1.60
ambil("Siti") = Bandung, node diperiksa: 3

=== Setelah perbesar: kapasitas 10, load factor 0.80 ===
  bucket[0]: Andi=Yogyakarta -> Ani=Denpasar -> Bella=Palembang
  bucket[1]: (kosong)
  bucket[2]: (kosong)
  bucket[3]: Dewi=Semarang
  bucket[4]: Rina=Surabaya -> Dodi=Medan
  bucket[5]: (kosong)
  bucket[6]: (kosong)
  bucket[7]: (kosong)
  bucket[8]: Budi=Jakarta
  bucket[9]: Siti=Bandung
  rantai terpanjang: 3, rata-rata panjang rantai: 0.80
ambil("Siti") = Bandung, node diperiksa: 1

Output tersebut menampilkan seluruh mekanisme hash table secara terbuka. Mari kita bedah bagian-bagian pentingnya:

  1. Baris 60-62 (hash): Math.floorMod(kunci.hashCode(), bucket.length) mengubah hash besar seperti 2081848 menjadi indeks 0 sampai 4. Tanpa floorMod, hash negatif akan menghasilkan indeks negatif yang melempar ArrayIndexOutOfBoundsException.
  2. Baris 64-77 (taruh): loop kecil memeriksa apakah kunci sudah ada di rantai — kalau ada, nilai saja yang diganti. Kalau tidak ditemukan, entri baru disisipkan di kepala rantai dengan dua penugasan tautan, sehingga sisip tetap O(1) berapa pun panjang rantainya.
  3. Baris 79-89 (ambil): pencarian hanya menyusuri rantai di satu bucket. Inilah sumber O(1): ruang pencarian tidak tumbuh mengikuti jumlah data, melainkan mengikuti panjang rantai.
  4. Baris 91-103 (perbesar): kapasitas digandakan lalu setiap entri di-rehash — indeks dihitung ulang terhadap kapasitas baru. Node lama dipindahkan, bukan dibuat ulang, cukup dengan menyambung ulang tautan.

Collision dan Load Factor #

Perhatikan penempatan kunci pada output: Budi dan Dewi sama-sama mendarat di bucket 3; Siti, Rina, dan Dodi berbagi bucket 4. Pada kapasitas 5 dengan 8 entri, rata-rata panjang rantai adalah 8/5 = 1,60 — persis nilai load factor (jumlah entri dibagi jumlah bucket). ambil("Siti") kembali mengunjungi 3 node karena Siti duduk di ujung rantai bucket 4.

Setelah perbesar() menggandakan kapasitas menjadi 10, load factor turun ke 0,80 dan Siti kini sendirian di bucket 9 — pencariannya memeriksa 1 node. Inilah logika di balik HashMap yang otomatis memperbesar diri ketika load factor melewati 0,75: rantai rata-rata dipendekan sehingga operasi kembali mendekati O(1). Menariknya, bucket 0 tetap menampung 3 entri (Andi, Ani, Bella) karena ketiga kunci tersebut kebetulan bernilai sama saat di-modulo 10 — resize memperbaiki rata-rata, bukan menjamin setiap kunci terpisah.

Kontrak equals dan hashCode #

Hash table hanya bekerja bila dua method bekerja sama: hashCode() menentukan bucket, equals() memastikan kunci di dalam rantai benar-benar sama. Program berikut menunjukkan apa yang terjadi pada class yang melanggar kontrak tersebut:

java EqualsHashCode.java 
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

public class EqualsHashCode {

    // Versi tanpa equals dan hashCode: identitas objek yang dipakai.
    static class TitikPlain {
        final int x;
        final int y;

        TitikPlain(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    // Versi dengan equals dan hashCode: isi field yang dipakai.
    static class Titik {
        final int x;
        final int y;

        Titik(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (!(o instanceof Titik)) {
                return false;
            }
            Titik lain = (Titik) o;
            return x == lain.x && y == lain.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }

    // record: equals, hashCode, dan toString dibuat otomatis.
    record TitikRecord(int x, int y) { }

    public static void main(String[] args) {
        Map<TitikPlain, String> mapPlain = new HashMap<>();
        mapPlain.put(new TitikPlain(3, 4), "Budi");
        mapPlain.put(new TitikPlain(3, 4), "Siti");
        System.out.println("Tanpa equals/hashCode : ukuran map = " + mapPlain.size());
        System.out.println("  ambil (3,4)        : " + mapPlain.get(new TitikPlain(3, 4)));

        Map<Titik, String> map = new HashMap<>();
        map.put(new Titik(3, 4), "Budi");
        map.put(new Titik(3, 4), "Siti");
        System.out.println("Dengan equals/hashCode: ukuran map = " + map.size());
        System.out.println("  ambil (3,4)        : " + map.get(new Titik(3, 4)));

        Map<TitikRecord, String> mapRecord = new HashMap<>();
        mapRecord.put(new TitikRecord(3, 4), "Budi");
        mapRecord.put(new TitikRecord(3, 4), "Siti");
        System.out.println("Dengan record         : ukuran map = " + mapRecord.size());
        System.out.println("  ambil (3,4)        : " + mapRecord.get(new TitikRecord(3, 4)));
    }
}

Output yang Dihasilkan:

text 
Tanpa equals/hashCode : ukuran map = 2
  ambil (3,4)        : null
Dengan equals/hashCode: ukuran map = 1
  ambil (3,4)        : Siti
Dengan record         : ukuran map = 1
  ambil (3,4)        : Siti

Tanpa equals dan hashCode, dua objek TitikPlain(3, 4) dianggap dua kunci berbeda: map menyimpan dua entri dan get mengembalikan null karena objek ketiga yang dibuat untuk mengambil tidak identik dengan keduanya. Class Titik yang mengimplementasikan kedua method menghasilkan perilaku yang benar — satu entri, nilai terbaru. Kontraknya ketat: objek yang equals wajib punya hashCode sama; pelanggaran membuat objek “hilang” di dalam map. record TitikRecord memecahkan masalah ini secara deklaratif karena compiler yang menyusun kedua method dari komponen record.

Hash table memberi pencarian rata-rata O(1) tanpa syarat urutan. Namun banyak persoalan justru butuh data terurut: rentang harga, ranking, batas bawah. Struktur berikutnya, binary search tree, menjanjikan urutan sekaligus pencarian yang cepat.

Referensi #

Berkas Sumber

Berkas pendukung halaman ini dapat diunduh dan dijalankan langsung sesuai penjelasan di atas.

EqualsHashCode.java

Unduh berkas
java 
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

public class EqualsHashCode {

    // Versi tanpa equals dan hashCode: identitas objek yang dipakai.
    static class TitikPlain {
        final int x;
        final int y;

        TitikPlain(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    // Versi dengan equals dan hashCode: isi field yang dipakai.
    static class Titik {
        final int x;
        final int y;

        Titik(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (!(o instanceof Titik)) {
                return false;
            }
            Titik lain = (Titik) o;
            return x == lain.x && y == lain.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }

    // record: equals, hashCode, dan toString dibuat otomatis.
    record TitikRecord(int x, int y) { }

    public static void main(String[] args) {
        Map<TitikPlain, String> mapPlain = new HashMap<>();
        mapPlain.put(new TitikPlain(3, 4), "Budi");
        mapPlain.put(new TitikPlain(3, 4), "Siti");
        System.out.println("Tanpa equals/hashCode : ukuran map = " + mapPlain.size());
        System.out.println("  ambil (3,4)        : " + mapPlain.get(new TitikPlain(3, 4)));

        Map<Titik, String> map = new HashMap<>();
        map.put(new Titik(3, 4), "Budi");
        map.put(new Titik(3, 4), "Siti");
        System.out.println("Dengan equals/hashCode: ukuran map = " + map.size());
        System.out.println("  ambil (3,4)        : " + map.get(new Titik(3, 4)));

        Map<TitikRecord, String> mapRecord = new HashMap<>();
        mapRecord.put(new TitikRecord(3, 4), "Budi");
        mapRecord.put(new TitikRecord(3, 4), "Siti");
        System.out.println("Dengan record         : ukuran map = " + mapRecord.size());
        System.out.println("  ambil (3,4)        : " + mapRecord.get(new TitikRecord(3, 4)));
    }
}

HashTableManual.java

Unduh berkas
java 
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);
    }
}