HashMap adalah implementasi Map yang paling banyak dipakai di seluruh ekosistem Java — dan untuk alasan yang kuat: operasi get, put, containsKey, dan remove rata-rata selesai dalam waktu konstan O(1), berapa pun jumlah pasangan yang disimpan. Kecepatan itu bukan hasil kebetulan melainkan konsekuensi teknik hashing: key diubah menjadi angka, angka itu menentukan laci penyimpanan, dan pencarian langsung membuka laci yang tepat. Pada Chapter ini kita bedah mesin di baliknya — bucket, tabrakan (collision), load factor, dan rehash — lalu kita kupas satu kontrak yang wajib dipenuhi agar mesin itu bekerja: equals dan hashCode pada key.

Bagaimana HashMap Menyimpan Data #

Di dalam HashMap terdapat array bernama table yang berisi sejumlah bucket. Saat put(k, v) dipanggil, HashMap menghitung k.hashCode(), meratakannya dengan operasi bit agar sebarannya lebih merata, lalu memilih indeks bucket dengan hash & (kapasitas - 1). Operasi bitwise ini setara dengan hash % kapasitas ketika kapasitas berupa pangkat dua — murah bagi prosesor dan menentukan satu-satunya bucket tempat pasangan itu boleh hidup.

Pencarian mengikuti jalur yang sama persis: get(k) menghitung hash dari k, melompat ke bucket yang ditunjuk, lalu membandingkan isi bucket dengan equals. Konsekuensi logisnya penting untuk dipahami: dua objek yang setara menurut equals wajib memiliki hashCode yang sama — kalau tidak, satu objek dicari di bucket A sedangkan kembaranya disimpan di bucket B, dan pasangan itu tidak akan pernah ditemukan.

Simulasi Bucket, Tabrakan, dan Rehash #

Karena bucket HashMap yang asli tersembunyi di internal JVM, kita bangun simulasi yang disederhanakan: array empat bucket, key bertipe Integer, dan indeks dihitung dengan n % kapasitas. Simulasi ini meniru tiga perilaku inti HashMap: tabrakan dua key di bucket yang sama, ambang load factor 0.75, dan rehash yang menggandakan kapasitas lalu menebarkan ulang seluruh isi:

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

Output yang Dihasilkan:

text 
Masukkan 10 -> bucket 2 [kapasitas 4]
Masukkan 22 -> bucket 2 (tabrakan dengan 10) [kapasitas 4]
Masukkan 31 -> bucket 3 [kapasitas 4]
  >> load factor 0.75 terlampaui: kapasitas 4 -> 8
Masukkan 4 -> bucket 4 [kapasitas 8]
Masukkan 17 -> bucket 1 [kapasitas 8]
Masukkan 28 -> bucket 4 (tabrakan dengan 4) [kapasitas 8]

Bucket 0 : []
Bucket 1 : [17]
Bucket 2 : [10]
Bucket 3 : []
Bucket 4 : [4, 28]
Bucket 5 : []
Bucket 6 : [22]
Bucket 7 : [31]

Urutan iterasi: 17 10 4 28 22 31

Mari kita bedah peristiwanya satu per satu:

  1. Baris 14-16 (10 dan 22): keduanya menghasilkan sisa 2 saat dibagi 4, sehingga menempati bucket yang sama — inilah collision. HashMap yang asli menangani tabrakan dengan menyimpan node berantai di dalam bucket (dan mengubah rantai menjadi red-black tree bila tabrakan di satu bucket sangat panjang).
  2. Baris 18-19 (rehash): sebelum memasukkan anggota keempat, beban 4 > 4 × 0.75 sudah terlampaui, sehingga kapasitas digandakan menjadi 8 dan seluruh isi ditebarkan ulang — perhatikan bahwa 22 pindah dari bucket 2 ke bucket 6. Operasi put yang memicu rehash menjadi lebih lambat dari biasanya; inilah makna istilah amortized: biaya penyebaran ulang ditanggung sedikit demi sedikit oleh seluruh operasi sebelumnya.
  3. Baris 21-23 (28): tabrakan tetap mungkin setelah rehash — 4 dan 28 sama-sama jatuh ke bucket 4 pada kapasitas 8. Tabrakan tidak salah; yang diperhatikan HashMap hanyalah agar tidak menggerombol di satu bucket.
  4. Baris 32-38 (urutan iterasi): iterasi menyusuri bucket demi bucket dari indeks kecil ke besar, menghasilkan 17 10 4 28 22 31 — bukan urutan penyisipan 10 22 31 4 17 28. Inilah penjelasan mesin di balik urutan aneh pada contoh-contoh HashMap sebelumnya.

Kontrak equals dan hashCode #

HashMap memakai hashCode untuk menentukan bucket dan equals untuk memastikan kesetaraan di dalam bucket. Kontrak yang mengikat keduanya: jika a.equals(b) mengembalikan true, maka a.hashCode() == b.hashCode() wajib benar. Arah sebaliknya tidak wajib — dua objek dengan hash sama boleh saja tidak setara; keduanya hanya bertetangga di bucket yang sama, dan equals yang memutuskan.

Jika kontrak dilanggar, gejalanya senyap: put berhasil, size bertambah, entry terlihat saat iterasi, tetapi get mengembalikan null untuk key yang seharusnya ditemukan. Jenis pelanggaran paling umum bukanlah hash yang salah, melainkan key yang berubah setelah dimasukkan — dibuktikan pada bagian terakhir chapter ini.

Record sebagai Key Ideal #

Key yang baik bersifat immutable (tidak bisa berubah), memiliki equals dan hashCode yang konsisten, dan murah dihitung. Sebelum Java 16, tiga syarat itu harus ditulis manual lewat method yang dioverride; sejak Java 16, record menyediakan semuanya otomatis karena seluruh komponen record bersifat final dan kedua method itu dihasilkan dari komponen-komponennya:

java KunciRecord.java 
import java.util.*;

public class KunciRecord {
    // Record otomatis membuat equals dan hashCode dari seluruh komponennya.
    record KodeBarang(String kategori, int nomor) {}

    public static void main(String[] args) {
        Map<KodeBarang, String> gudang = new HashMap<>();
        gudang.put(new KodeBarang("ATK", 101), "Pensil 2B");
        gudang.put(new KodeBarang("ATK", 102), "Buku Tulis");
        gudang.put(new KodeBarang("ELE", 201), "Kalkulator");

        System.out.println("cari (ATK, 101)  : " + gudang.get(new KodeBarang("ATK", 101)));
        System.out.println("cari (ATK, 999)  : " + gudang.get(new KodeBarang("ATK", 999)));
        System.out.println("ukuran awal      : " + gudang.size());

        gudang.put(new KodeBarang("ATK", 101), "Pensil 2B isi 12");
        System.out.println("setelah put ulang: " + gudang.get(new KodeBarang("ATK", 101)));
        System.out.println("ukuran akhir     : " + gudang.size());

        System.out.println("Daftar entry:");
        gudang.forEach((kode, nama) -> System.out.println("  " + kode + " -> " + nama));
    }
}

Output yang Dihasilkan:

text 
cari (ATK, 101)  : Pensil 2B
cari (ATK, 999)  : null
ukuran awal      : 3
setelah put ulang: Pensil 2B isi 12
ukuran akhir     : 3
Daftar entry:
  KodeBarang[kategori=ATK, nomor=102] -> Buku Tulis
  KodeBarang[kategori=ATK, nomor=101] -> Pensil 2B isi 12
  KodeBarang[kategori=ELE, nomor=201] -> Kalkulator

Poin bedahnya:

  1. Baris 6 (record KodeBarang): satu baris deklarasi menghasilkan constructor, accessor, equals, hashCode, dan toString — dua method tengah itulah yang dibaca HashMap.
  2. Baris 14 (get(new KodeBarang("ATK", 101))): objek pencarian dibuat baru, berbeda dari objek yang dipakai saat put — namun ditemukan, karena equals membandingkan isi (ATK, 101), bukan alamat objek. Inilah perilaku yang diharapkan dari kontrak yang benar.
  3. Baris 21-23 (put ulang): key setara menimpa value lama; ukuran tetap 3 karena HashMap menghitung keunikan berdasarkan equals, bukan jumlah objek.

Jebakan Key yang Berubah #

Sekarang kita lihat akibat key yang mutable. Class Pelanggan menghitung hashCode dari field nama — field yang masih terbuka untuk diubah. Entry dimasukkan dengan nama Budi, lalu nama objek key diganti menjadi Siti setelah entry tersimpan:

java KunciBerubah.java 
import java.util.*;

public class KunciBerubah {
    // equals dan hashCode mengikuti field nama, yang masih bisa diubah.
    static class Pelanggan {
        String nama;

        Pelanggan(String nama) {
            this.nama = nama;
        }

        @Override
        public boolean equals(Object o) {
            return o instanceof Pelanggan p && p.nama.equals(nama);
        }

        @Override
        public int hashCode() {
            return nama.hashCode();
        }

        @Override
        public String toString() {
            return nama;
        }
    }

    public static void main(String[] args) {
        Map<Pelanggan, Integer> poin = new HashMap<>();
        Pelanggan kunci = new Pelanggan("Budi");
        poin.put(kunci, 120);

        System.out.println("get(Budi) sebelum ubah : " + poin.get(new Pelanggan("Budi")));

        kunci.nama = "Siti"; // field milik key diubah setelah key dimasukkan
        System.out.println("get(Budi) setelah ubah : " + poin.get(new Pelanggan("Budi")));
        System.out.println("get(Siti)              : " + poin.get(new Pelanggan("Siti")));
        System.out.println("ukuran map             : " + poin.size());
        System.out.println("isi map                : " + poin);
    }
}

Output yang Dihasilkan:

text 
get(Budi) sebelum ubah : 120
get(Budi) setelah ubah : null
get(Siti)              : null
ukuran map             : 1
isi map                : {Siti=120}

Mari kita urai kejadiannya:

  1. Baris 30 (sebelum ubah): get menemukan 120 — kontrak bekerja normal selama field key tidak disentuh.
  2. Baris 33-34 (setelah kunci.nama = "Siti"): entry tersimpan di bucket milik hash Budi, tetapi objek key di dalam entry kini bernama Siti. Pencarian dengan Budi sampai ke bucket yang benar lalu gagal di equals; pencarian dengan Siti diarahkan ke bucket milik hash Siti yang kosong. Kedua jalur menghasilkan null.
  3. Baris 35-37: size() masih 1 dan isi map masih tercetak — entry-nya tidak hilang, hanya tidak lagi bisa dijumpai lewat get. Hanya iterasi penuh yang masih menemukannya, dan penghapusan lewat remove(Budi) juga gagal, sehingga entry seperti ini berpotensi membocorkan memori secara perlahan.

HashMap memberi kecepatan, tetapi kontraknya menuntut kedisiplinan key, dan urutan iterasinya tidak bisa dijanjikan. Untuk kasus yang butuh kecepatan hashing sekaligus urutan yang terprediksi, Java menyediakan LinkedHashMap — implementasi yang menambah satu daftar tautan untuk mengingat urutan penyisipan. Chapter berikutnya membedahnya sampai ke penerapannya sebagai cache LRU.

Referensi #

Berkas Sumber

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

KunciBerubah.java

Unduh berkas
java 
import java.util.*;

public class KunciBerubah {
    // equals dan hashCode mengikuti field nama, yang masih bisa diubah.
    static class Pelanggan {
        String nama;

        Pelanggan(String nama) {
            this.nama = nama;
        }

        @Override
        public boolean equals(Object o) {
            return o instanceof Pelanggan p && p.nama.equals(nama);
        }

        @Override
        public int hashCode() {
            return nama.hashCode();
        }

        @Override
        public String toString() {
            return nama;
        }
    }

    public static void main(String[] args) {
        Map<Pelanggan, Integer> poin = new HashMap<>();
        Pelanggan kunci = new Pelanggan("Budi");
        poin.put(kunci, 120);

        System.out.println("get(Budi) sebelum ubah : " + poin.get(new Pelanggan("Budi")));

        kunci.nama = "Siti"; // field milik key diubah setelah key dimasukkan
        System.out.println("get(Budi) setelah ubah : " + poin.get(new Pelanggan("Budi")));
        System.out.println("get(Siti)              : " + poin.get(new Pelanggan("Siti")));
        System.out.println("ukuran map             : " + poin.size());
        System.out.println("isi map                : " + poin);
    }
}

KunciRecord.java

Unduh berkas
java 
import java.util.*;

public class KunciRecord {
    // Record otomatis membuat equals dan hashCode dari seluruh komponennya.
    record KodeBarang(String kategori, int nomor) {}

    public static void main(String[] args) {
        Map<KodeBarang, String> gudang = new HashMap<>();
        gudang.put(new KodeBarang("ATK", 101), "Pensil 2B");
        gudang.put(new KodeBarang("ATK", 102), "Buku Tulis");
        gudang.put(new KodeBarang("ELE", 201), "Kalkulator");

        System.out.println("cari (ATK, 101)  : " + gudang.get(new KodeBarang("ATK", 101)));
        System.out.println("cari (ATK, 999)  : " + gudang.get(new KodeBarang("ATK", 999)));
        System.out.println("ukuran awal      : " + gudang.size());

        gudang.put(new KodeBarang("ATK", 101), "Pensil 2B isi 12");
        System.out.println("setelah put ulang: " + gudang.get(new KodeBarang("ATK", 101)));
        System.out.println("ukuran akhir     : " + gudang.size());

        System.out.println("Daftar entry:");
        gudang.forEach((kode, nama) -> System.out.println("  " + kode + " -> " + nama));
    }
}

TabelHashSederhana.java

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