LinkedHashMap mengingat urutan berdasarkan waktu — kapan entry masuk atau disentuh. Ada kebutuhan lain yang lebih menuntut: urutan berdasarkan nilai key itu sendiri. Daftar produk yang selalu tampil dari harga termurah, buku besar yang rentang tanggalnya bisa dipotong, atau pencarian “harga terdekat di bawah anggaran” semuanya menuntut key yang tersusun terus-menerus, bukan sekadar terurut saat ditampilkan. TreeMap memenuhinya dengan menyimpan entry di dalam red-black tree — pohon pencarian biner yang selalu seimbang — sehingga isinya terurut sejak penyisipan dan siap menjawab pertanyaan rentang kapan pun. Pada Chapter ini kita pelajari navigasi tetangga, pemotongan rentang, dan Comparator kustom sebagai penentu urutan.

Pohon Merah-Hitam sebagai Mesin Urutan #

Setiap put pada TreeMap menuruni pohon dari akar: key yang lebih kecil berbelok ke kiri, key yang lebih besar berbelok ke kanan, sampai menemukan posisi daun. Pohon merah-hitam menjaga keseimbangan dengan rotasi dan pewarnaan saat penyisipan, sehingga tinggi pohon dijamin O(log n) — konsekuensinya, put, get, containsKey, dan remove masing-masing berbiaya O(log n), sedikit lebih lambat daripada O(1) rata-rata HashMap namun tetap cepat untuk jutaan entry. Iterasi berjalan in-order — kiri, akar, kanan — dan itulah alasan isi TreeMap selalu keluar terurut tanpa pemanggilan sort di mana pun.

Konsekuensi struktural yang penting: setiap key harus bisa dibandingkan. Tanpa Comparator pada konstruktor, TreeMap memanggil compareTo dari interface Comparable milik key — perwujudan TreeMap<Object, ...> yang diisi objek yang tidak membandingkan dirinya akan gagal saat runtime dengan ClassCastException, sebagaimana dibuktikan pada Chapter TreeSet.

Key Terurut dan Navigasi Tetangga #

Program berikut menyimpan daftar produk toko dengan harga sebagai key dan nama produk sebagai value, lalu menjajal method navigasi milik NavigableMap — interface yang diimplementasi TreeMap:

java HargaTerurut.java 
import java.util.*;

public class HargaTerurut {
    public static void main(String[] args) {
        TreeMap<Integer, String> produk = new TreeMap<>();
        produk.put(15000, "Kipas Angin");
        produk.put(5000, "Sapu");
        produk.put(25000, "Rice Cooker");
        produk.put(10000, "Ember");
        produk.put(40000, "Setrika");
        System.out.println("isi terurut         : " + produk);

        System.out.println("firstKey()          : " + produk.firstKey());
        System.out.println("lastKey()           : " + produk.lastKey());
        System.out.println("firstEntry()        : " + produk.firstEntry());
        System.out.println("lastEntry()         : " + produk.lastEntry());

        System.out.println("floorKey(12000)     : " + produk.floorKey(12000));
        System.out.println("ceilingKey(12000)   : " + produk.ceilingKey(12000));
        System.out.println("lowerKey(15000)     : " + produk.lowerKey(15000));
        System.out.println("higherKey(15000)    : " + produk.higherKey(15000));
    }
}

Output yang Dihasilkan:

text 
isi terurut         : {5000=Sapu, 10000=Ember, 15000=Kipas Angin, 25000=Rice Cooker, 40000=Setrika}
firstKey()          : 5000
lastKey()           : 40000
firstEntry()        : 5000=Sapu
lastEntry()         : 40000=Setrika
floorKey(12000)     : 10000
ceilingKey(12000)   : 15000
lowerKey(15000)     : 10000
higherKey(15000)    : 25000

Mari kita bedah baris-baris pentingnya:

  1. Baris 6-11 (lima put): harga dipasang dalam urutan acak (15000 lebih dulu), tetapi keluaran langsung terurut {5000=Sapu, 10000=Ember, ...} — pohon menyusun sejak entry pertama, tanpa penyortiran ulang.
  2. Baris 13-16 (firstKey/lastKey/firstEntry/lastEntry): membaca ujung terkecil dan terbesar; varian Entry mengembalikan pasangan lengkap, varian Key hanya key-nya.
  3. Baris 18-21 (empat method tetangga): perbedaan maknanya ringkas namun sering tertukar — tabel berikut merangkumnya terhadap argumen:
MethodMengembalikanContoh pada data
floorKey(x)key terbesar yang ≤ xfloorKey(12000) → 10000
ceilingKey(x)key terkecil yang ≥ xceilingKey(12000) → 15000
lowerKey(x)key terbesar yang < xlowerKey(15000) → 10000
higherKey(x)key terkecil yang > xhigherKey(15000) → 25000

Pasangan floor/ceiling memakai batas inklusif — cocok untuk “harga tidak melebihi anggaran” — sedangkan lower/higher memakai batas ketat. Keempat method mengembalikan null bila tidak ada kandidat; floorKey(4000) pada data ini menghasilkan null karena seluruh key lebih besar dari 4000.

Memotong Rentang dengan headMap, tailMap, subMap #

NavigableMap juga memotong isi menjadi view rentang: headMap(batas) berisi key sebelum batas, tailMap(batas) berisi key mulai batas ke atas, dan subMap(min, max) memotong keduanya. Program berikut mempraktikkan ketiganya sekaligus membuktikan bahwa view tersebut hidup:

java PotonganRentang.java 
import java.util.*;

public class PotonganRentang {
    public static void main(String[] args) {
        TreeMap<Integer, String> produk = new TreeMap<>();
        produk.put(15000, "Kipas Angin");
        produk.put(5000, "Sapu");
        produk.put(25000, "Rice Cooker");
        produk.put(10000, "Ember");
        produk.put(40000, "Setrika");

        System.out.println("Semua produk   : " + produk);
        System.out.println("headMap(15000) : " + produk.headMap(15000));
        System.out.println("tailMap(15000) : " + produk.tailMap(15000));
        System.out.println("subMap(10000, 25000) : " + produk.subMap(10000, 25000));

        // View adalah jendela hidup: menulis lewat view mengubah map aslinya.
        SortedMap<Integer, String> murah = produk.headMap(15000);
        murah.put(7000, "Gayung");
        System.out.println("Setelah isi via view : " + produk);

        System.out.println("pollFirstEntry()     : " + produk.pollFirstEntry());
        System.out.println("Setelah poll         : " + produk);
    }
}

Output yang Dihasilkan:

text 
Semua produk   : {5000=Sapu, 10000=Ember, 15000=Kipas Angin, 25000=Rice Cooker, 40000=Setrika}
headMap(15000) : {5000=Sapu, 10000=Ember}
tailMap(15000) : {15000=Kipas Angin, 25000=Rice Cooker, 40000=Setrika}
subMap(10000, 25000) : {10000=Ember, 15000=Kipas Angin}
Setelah isi via view : {5000=Sapu, 7000=Gayung, 10000=Ember, 15000=Kipas Angin, 25000=Rice Cooker, 40000=Setrika}
pollFirstEntry()     : 5000=Sapu
Setelah poll         : {7000=Gayung, 10000=Ember, 15000=Kipas Angin, 25000=Rice Cooker, 40000=Setrika}

Poin bedahnya:

  1. Baris 12-14 (tiga potongan): headMap(15000) memuat key < 15000 (batas atas eksklusif), tailMap(15000) memuat key ≥ 15000 (batas bawah inklusif), dan subMap(10000, 25000) mengambil rentang [10000, 25000) — bawah masuk, atas tidak.
  2. Baris 17-18 (put lewat view): menambahkan 7000=Gayung lewat headMap langsung menambah entry pada map asli — view adalah jendela ke data yang sama, bukan salinan. Menulis key di luar rentang view (murah.put(20000, ...)) akan melempar IllegalArgumentException.
  3. Baris 20-21 (pollFirstEntry): membaca sekaligus menghapus entry terkecil — pasangan method pollLastEntry() melakukan hal yang sama di ujung besar. Pola ini cocok untuk antrean berbasis prioritas nilai key.

Comparator Kustom untuk Urutan Sendiri #

Urutan alami key tidak selalu sesuai kebutuhan. Konstruktor TreeMap(Comparator) mengganti seluruh definisi urutan — dan bersamanya, definisi keunikan: TreeMap membandingkan key lewat compare() atau compareTo(), bukan lewat equals(). Dua key yang hasil compare()-nya 0 dianggap key yang sama sehingga yang terakhir menimpa nilai yang pertama. Program berikut memakai dua comparator berbeda pada dua map:

java UrutanKustomMap.java 
import java.util.*;

public class UrutanKustomMap {
    public static void main(String[] args) {
        // Urutan menurun: key terbesar tampil lebih dulu.
        TreeMap<String, Integer> nilaiTurun = new TreeMap<>(Comparator.reverseOrder());
        nilaiTurun.put("Budi", 78);
        nilaiTurun.put("Siti", 92);
        nilaiTurun.put("Dewi", 88);
        System.out.println("reverseOrder()     : " + nilaiTurun);
        System.out.println("firstKey()         : " + nilaiTurun.firstKey());

        // Urutan komposit: panjang nama dulu, lalu alfabetis.
        Comparator<String> panjangLaluAbjad =
                Comparator.comparingInt(String::length)
                          .thenComparing(Comparator.naturalOrder());
        TreeMap<String, Integer> peserta = new TreeMap<>(panjangLaluAbjad);
        peserta.put("Anton", 3);
        peserta.put("Budi", 1);
        peserta.put("Dewi", 2);
        peserta.put("Rani", 4);
        System.out.println("panjang lalu abjad : " + peserta);
        System.out.println("firstKey()         : " + peserta.firstKey());
        System.out.println("lastKey()          : " + peserta.lastKey());
    }
}

Output yang Dihasilkan:

text 
reverseOrder()     : {Siti=92, Dewi=88, Budi=78}
firstKey()         : Siti
panjang lalu abjad : {Budi=1, Dewi=2, Rani=4, Anton=3}
firstKey()         : Budi
lastKey()          : Anton

Poin bedahnya:

  1. Baris 6-10 (Comparator.reverseOrder()): urutan alami String dibalik menjadi menurun — firstKey() kini mengembalikan Siti, nama terakhir secara alfabetis. Seluruh navigasi (floorKey, tailMap, dan lainnya) otomatis mengikuti comparator ini.
  2. Baris 13-15 (comparingInt(...).thenComparing(...)): comparator komposit membandingkan panjang nama lebih dulu; bila sama panjang, urutan alfabetis menyelesaikannya. Nama empat huruf (Budi, Dewi, Rani) mendahului Anton yang lima huruf, dan firstKey()/lastKey() mengikuti urutan tersebut.

Dengan TreeMap, kita menuntaskan tiga implementasi Map utama: HashMap untuk kecepatan, LinkedHashMap untuk urutan kejadian, dan TreeMap untuk urutan nilai beserta navigasi rentangnya. Masih tersisa satu anggota tua dari generasi pertama Java yang sering muncul di kode lawas — Hashtable, implementasi synchronized yang kini digantikan ConcurrentHashMap. Chapter berikutnya menelusuri sejarahnya, perbedaannya dari HashMap, dan alasan migrasinya.

Referensi #

Berkas Sumber

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

HargaTerurut.java

Unduh berkas
java 
import java.util.*;

public class HargaTerurut {
    public static void main(String[] args) {
        TreeMap<Integer, String> produk = new TreeMap<>();
        produk.put(15000, "Kipas Angin");
        produk.put(5000, "Sapu");
        produk.put(25000, "Rice Cooker");
        produk.put(10000, "Ember");
        produk.put(40000, "Setrika");
        System.out.println("isi terurut         : " + produk);

        System.out.println("firstKey()          : " + produk.firstKey());
        System.out.println("lastKey()           : " + produk.lastKey());
        System.out.println("firstEntry()        : " + produk.firstEntry());
        System.out.println("lastEntry()         : " + produk.lastEntry());

        System.out.println("floorKey(12000)     : " + produk.floorKey(12000));
        System.out.println("ceilingKey(12000)   : " + produk.ceilingKey(12000));
        System.out.println("lowerKey(15000)     : " + produk.lowerKey(15000));
        System.out.println("higherKey(15000)    : " + produk.higherKey(15000));
    }
}

PotonganRentang.java

Unduh berkas
java 
import java.util.*;

public class PotonganRentang {
    public static void main(String[] args) {
        TreeMap<Integer, String> produk = new TreeMap<>();
        produk.put(15000, "Kipas Angin");
        produk.put(5000, "Sapu");
        produk.put(25000, "Rice Cooker");
        produk.put(10000, "Ember");
        produk.put(40000, "Setrika");

        System.out.println("Semua produk   : " + produk);
        System.out.println("headMap(15000) : " + produk.headMap(15000));
        System.out.println("tailMap(15000) : " + produk.tailMap(15000));
        System.out.println("subMap(10000, 25000) : " + produk.subMap(10000, 25000));

        // View adalah jendela hidup: menulis lewat view mengubah map aslinya.
        SortedMap<Integer, String> murah = produk.headMap(15000);
        murah.put(7000, "Gayung");
        System.out.println("Setelah isi via view : " + produk);

        System.out.println("pollFirstEntry()     : " + produk.pollFirstEntry());
        System.out.println("Setelah poll         : " + produk);
    }
}

UrutanKustomMap.java

Unduh berkas
java 
import java.util.*;

public class UrutanKustomMap {
    public static void main(String[] args) {
        // Urutan menurun: key terbesar tampil lebih dulu.
        TreeMap<String, Integer> nilaiTurun = new TreeMap<>(Comparator.reverseOrder());
        nilaiTurun.put("Budi", 78);
        nilaiTurun.put("Siti", 92);
        nilaiTurun.put("Dewi", 88);
        System.out.println("reverseOrder()     : " + nilaiTurun);
        System.out.println("firstKey()         : " + nilaiTurun.firstKey());

        // Urutan komposit: panjang nama dulu, lalu alfabetis.
        Comparator<String> panjangLaluAbjad =
                Comparator.comparingInt(String::length)
                          .thenComparing(Comparator.naturalOrder());
        TreeMap<String, Integer> peserta = new TreeMap<>(panjangLaluAbjad);
        peserta.put("Anton", 3);
        peserta.put("Budi", 1);
        peserta.put("Dewi", 2);
        peserta.put("Rani", 4);
        System.out.println("panjang lalu abjad : " + peserta);
        System.out.println("firstKey()         : " + peserta.firstKey());
        System.out.println("lastKey()          : " + peserta.lastKey());
    }
}