HashMap cepat, tetapi kita sudah melihat harganya: urutan iterasi mengikuti bucket dan tidak bisa dijanjikan. Banyak kasus nyata justru butuh kecepatan hashing dan urutan yang terprediksi — riwayat pencarian pengguna, urutan menu yang ditampilkan, atau cache yang tahu entri mana yang paling lama tidak disentuh. LinkedHashMap menjawab kebutuhan itu dengan satu tambahan elegan: setiap entry diberi dua rujukan — before dan after — yang merangkai seluruh entry menjadi daftar tautan ganda, sehingga iterasi berjalan menyusuri daftar tersebut, bukan menyusuri bucket. Pada Chapter ini kita bedah cara kerjanya, perilaku urutan penyisipannya, dan penerapan paling terkenalnya: cache berkebijakan LRU.

Daftar Tautan yang Mengingat Urutan #

Secara struktural, LinkedHashMap adalah HashMap yang setiap bucket-node-nya juga dirangkai ke daftar tautan tersendiri. Penyisipan tetap berjalan lewat mekanisme hash (kecepatan O(1) rata-rata tetap terjaga), lalu entry baru ditambahkan di ekor daftar tautan. Iterasi — lewat keySet(), values(), entrySet(), atau forEach — cukup berjalan dari kepala daftar ke ekornya tanpa menyentuh array bucket sama sekali.

Biayanya nyata namun kecil: dua rujukan ekstra pada setiap entry. LinkedHashMap juga mewarisi perilaku HashMap yang tidak disinkronkan antar thread, kontrak equals/hashCode pada key, dan ambang load factor 0.75 untuk rehash.

Urutan Penyisipan dalam Praktik #

Program berikut menyimpan harga buah pada LinkedHashMap dan HashMap dengan urutan penyisipan yang sama, lalu menguji tiga peristiwa yang menggerakkan urutan: put ulang pada key yang sama, remove, dan penyisipan kembali:

java UrutanSisipMap.java 
import java.util.*;

public class UrutanSisipMap {
    public static void main(String[] args) {
        Map<String, Integer> harga = new LinkedHashMap<>();
        harga.put("Apel", 3000);
        harga.put("Jeruk", 5000);
        harga.put("Pisang", 2000);
        harga.put("Mangga", 7000);
        System.out.println("LinkedHashMap : " + harga);

        Map<String, Integer> acak = new HashMap<>();
        acak.put("Apel", 3000);
        acak.put("Jeruk", 5000);
        acak.put("Pisang", 2000);
        acak.put("Mangga", 7000);
        System.out.println("HashMap       : " + acak);

        harga.put("Apel", 3500);
        System.out.println("put ulang     : " + harga);

        harga.remove("Jeruk");
        System.out.println("remove        : " + harga);

        harga.put("Jeruk", 5000);
        System.out.println("sisip ulang   : " + harga);

        harga.forEach((nama, nilai) ->
                System.out.println("  " + nama + " = Rp" + nilai));
    }
}

Output yang Dihasilkan:

text 
LinkedHashMap : {Apel=3000, Jeruk=5000, Pisang=2000, Mangga=7000}
HashMap       : {Pisang=2000, Mangga=7000, Apel=3000, Jeruk=5000}
put ulang     : {Apel=3500, Jeruk=5000, Pisang=2000, Mangga=7000}
remove        : {Apel=3500, Pisang=2000, Mangga=7000}
sisip ulang   : {Apel=3500, Pisang=2000, Mangga=7000, Jeruk=5000}
  Apel = Rp3500
  Pisang = Rp2000
  Mangga = Rp7000
  Jeruk = Rp5000

Mari kita bedah baris-baris pentingnya:

  1. Baris 7-9 vs baris 12-15 (dua put berurutan): isi kedua map identik, tetapi LinkedHashMap tercetak [Apel, Jeruk, Pisang, Mangga] — persis urutan masuk — sedangkan HashMap tercetak mengikuti bucket. Inilah satu-satunya perbedaan yang terlihat dari luar.
  2. Baris 17-18 (put ulang): nilai Apel berganti menjadi 3500 tetapi posisinya tidak berpindah — penggantian nilai memperbarui isi node yang sudah ada, bukan memindahkannya di daftar tautan.
  3. Baris 20-23 (remove lalu sisip ulang): remove melepaskan Jeruk dari daftar; penyisipan kembali selalu menempel di ekor, sehingga Jeruk muncul setelah Mangga. Urutan mencerminkan urutan penyisipan terakhir, bukan urutan pertama kali key terlihat.

Mode accessOrder #

Konstruktor LinkedHashMap punya bentuk tiga argumen: LinkedHashMap(kapasitasAwal, loadFactor, accessOrder). Argumen ketiga mengubah makna daftar tautan dari urutan penyisipan menjadi urutan akses: setiap get, put, dan putAll memindahkan entry yang disentuh ke ekor daftar. Dengan mode ini, kepala daftar selalu menampung entry yang paling lama tidak diakses — tepat yang dibutuhkan kebijakan Least Recently Used (LRU). Perlu dicatat bahwa mode bawaan (accessOrder bernilai false) lebih hemat: get tidak menyentuh daftar sama sekali.

Cache LRU dengan removeEldestEntry #

LinkedHashMap menyediakan hook khusus untuk cache: method protected removeEldestEntry(Map.Entry) yang dipanggil otomatis setelah setiap put. Implementasi bawaannya selalu mengembalikan false (tidak menghapus apa pun); dengan meng-override method tersebut, kita menentukan kapan entry tertua dibuang. Program berikut merakit cache stok berkapasitas tiga:

java CacheKecil.java 
import java.util.*;

public class CacheKecil {
    // Cache kecil berbasis LinkedHashMap dengan kebijakan LRU.
    static class CacheStok extends LinkedHashMap<String, Integer> {
        private final int kapasitas;

        CacheStok(int kapasitas) {
            super(16, 0.75f, true); // argumen ketiga: accessOrder = true
            this.kapasitas = kapasitas;
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
            return size() > kapasitas;
        }
    }

    public static void main(String[] args) {
        CacheStok cache = new CacheStok(3);
        System.out.println("Kapasitas cache: 3, mode accessOrder aktif");

        cache.put("pensil", 6000);
        cache.put("buku", 4000);
        cache.put("spidol", 7000);
        System.out.println("isi awal          : " + cache);

        cache.get("pensil");
        System.out.println("setelah get(pensil): " + cache);

        cache.put("tas", 3000);
        System.out.println("setelah put(tas)   : " + cache);

        cache.put("buku", 4500);
        System.out.println("setelah put(buku)  : " + cache);
    }
}

Output yang Dihasilkan:

text 
Kapasitas cache: 3, mode accessOrder aktif
isi awal          : {pensil=6000, buku=4000, spidol=7000}
setelah get(pensil): {buku=4000, spidol=7000, pensil=6000}
setelah put(tas)   : {spidol=7000, pensil=6000, tas=3000}
setelah put(buku)  : {pensil=6000, tas=3000, buku=4500}

Poin bedahnya:

  1. Baris 11 (super(16, 0.75f, true)): konstruktor induk dipanggil dengan accessOrder = true; tanpa argumen ini, urutan tetap berbasis penyisipan dan cache tidak akan bereaksi terhadap get.
  2. Baris 16-18 (removeEldestEntry): dipanggil LinkedHashMap setelah penyisipan baru; mengembalikan true ketika size() melampaui kapasitas membuat entry di kepala daftar — yang paling lama tidak disentuh — terbuang otomatis. Entry yang dihapus tetap dilewatkan lewat parameter eldest seandainya kita ingin memindahkannya ke penyimpanan lain.
  3. Baris 27-28 (get("pensil")): sekadar membaca pensil memindahkannya dari kepala ke ekor — urutan menjadi [buku, spidol, pensil] tanpa satu operasi penyisipan pun.
  4. Baris 30-33 (dua put terakhir): tas masuk saat cache penuh sehingga buku (kepala daftar) terbuang; buku dimasukkan kembali saat spidol kini menjadi yang tertua. Himpunan isi akhir [pensil, tas, buku] adalah tiga entri yang paling baru disentuh.

LinkedHashMap memberi urutan berdasarkan waktu kejadian: kapan entry masuk atau disentuh. Ada satu bentuk urutan yang belum kita miliki: urutan berdasarkan nilai key itu sendiri — harga dari termurah ke termahal, tanggal dari terlama ke terbaru. Untuk itu kita beralih ke TreeMap, implementasi Map yang menyusun key-nya di dalam pohon merah-hitam dan membuka seluruh navigasi rentang dari NavigableMap.

Referensi #

Berkas Sumber

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

CacheKecil.java

Unduh berkas
java 
import java.util.*;

public class CacheKecil {
    // Cache kecil berbasis LinkedHashMap dengan kebijakan LRU.
    static class CacheStok extends LinkedHashMap<String, Integer> {
        private final int kapasitas;

        CacheStok(int kapasitas) {
            super(16, 0.75f, true); // argumen ketiga: accessOrder = true
            this.kapasitas = kapasitas;
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
            return size() > kapasitas;
        }
    }

    public static void main(String[] args) {
        CacheStok cache = new CacheStok(3);
        System.out.println("Kapasitas cache: 3, mode accessOrder aktif");

        cache.put("pensil", 6000);
        cache.put("buku", 4000);
        cache.put("spidol", 7000);
        System.out.println("isi awal          : " + cache);

        cache.get("pensil");
        System.out.println("setelah get(pensil): " + cache);

        cache.put("tas", 3000);
        System.out.println("setelah put(tas)   : " + cache);

        cache.put("buku", 4500);
        System.out.println("setelah put(buku)  : " + cache);
    }
}

UrutanSisipMap.java

Unduh berkas
java 
import java.util.*;

public class UrutanSisipMap {
    public static void main(String[] args) {
        Map<String, Integer> harga = new LinkedHashMap<>();
        harga.put("Apel", 3000);
        harga.put("Jeruk", 5000);
        harga.put("Pisang", 2000);
        harga.put("Mangga", 7000);
        System.out.println("LinkedHashMap : " + harga);

        Map<String, Integer> acak = new HashMap<>();
        acak.put("Apel", 3000);
        acak.put("Jeruk", 5000);
        acak.put("Pisang", 2000);
        acak.put("Mangga", 7000);
        System.out.println("HashMap       : " + acak);

        harga.put("Apel", 3500);
        System.out.println("put ulang     : " + harga);

        harga.remove("Jeruk");
        System.out.println("remove        : " + harga);

        harga.put("Jeruk", 5000);
        System.out.println("sisip ulang   : " + harga);

        harga.forEach((nama, nilai) ->
                System.out.println("  " + nama + " = Rp" + nilai));
    }
}