Pertanyaan “struktur mana yang lebih cepat?” menggoda untuk dijawab dengan mengukur detik — dan justru di situ jawabannya paling sering menyesatkan. Hasil System.nanoTime() pada program Java dipengaruhi pemanasan JIT compiler, pengumpulan objek yang belum terjadi, dan isi cache prosesor, sehingga dua eksekusi program yang sama bisa menghasilkan angka berbeda drastis. Chapter penutup ini mengambil jalan yang lebih kokoh: kita bandingkan kompleksitas operasi — seberapa cepat biaya tumbuh ketika jumlah data membengkak — lengkap dengan alasan struktural di balik setiap angka, lalu kita buktikan lewat penghitungan operasi yang deterministik, bukan lewat jam dinding. Alat pengukuran waktu yang benar (JMH) tetap kita kenal di akhir sebagai panduan menuju Section khusus performa.

Cara Membaca Notasi Big-O #

Notasi O(f(n)) mengukur bentuk pertumbuhan biaya terhadap jumlah elemen n, bukan jumlah detik. O(1) berarti biaya tidak bertambah ketika data membengkak; O(log n) berarti tiap penggandaan data hanya menambah sejumlah langkah tetap; O(n) berarti biaya naik sebanding jumlah data; O(n log n) adalah wilayah algoritma pengurutan. Notasi ini sengaja membuang faktor konstanta — dua operasi sama-sama O(1) bisa berbeda nyata hingga sepuluh kali — sehingga di data kecil, struktur bukan penentu utama; pengaruhnya baru menentukan ketika n mencapai puluhan ribu ke atas.

Notasi juga punya dua rasa yang perlu dibedakan: worst case dan rata-rata. Struktur berbasis hash menjanjikan O(1) rata-rata — asumsinya hash tersebar merata — namun berporak-porak menjadi O(n) bila seluruh elemen bertabrakan di bucket yang sama. Pohon merah-hitam pada TreeSet/TreeMap lebih lambat di kertas (O(log n)) tetapi janjinya berlaku untuk semua kasus.

Tabel Kompleksitas Operasi #

Tabel berikut merangkum empat operasi paling sering ditanyakan pada delapan implementasi inti:

Implementasiadd / offer / putget (indeks / key)containsremove / poll
ArrayListO(1) amortized (ujung)O(1)O(n)O(n)
LinkedListO(1) (ujung)O(n)O(n)O(1) di ujung, O(n) di tengah
ArrayDequeO(1) (ujung)—O(n)O(1) (ujung)
HashSetO(1) rata-rata—O(1) rata-rataO(1) rata-rata
TreeSetO(log n)—O(log n)O(log n)
HashMapO(1) rata-rataO(1) rata-rataO(1) rata-rata (containsKey)O(1) rata-rata
TreeMapO(log n)O(log n)O(log n)O(log n)
PriorityQueueO(log n) (offer)peek O(1)O(n)O(log n) (poll)

Beberapa sel memuat catatan penting. Tanda — berarti operasi bukan bagian desain struktur tersebut (misalnya ArrayDeque tidak menyediakan akses indeks). Baris LinkedList menunjukkan jebakan klasik: menghapus node memang O(1), tetapi menemukan node-nya menuntut penelusuran O(n) — maka remove di tengah tetap linear. Baris PriorityQueue menegaskan bahwa contains pada heap tidak lebih cepat daripada pada ArrayList — heap hanya mengatur kepala antrean, bukan pencarian.

Biaya Amortized pada ArrayList #

ArrayList menyisipkan O(1) amortized — istilah yang sering dibaca sepintas tanpa makna. Program berikut membangun kembali mekanismenya: list berbasis array yang kapasitasnya berganda dua kali lipat setiap kali penuh, sambil menghitung berapa kali penyalinan array terjadi:

java DemonstrasiAmortized.java 
import java.util.*;

public class DemonstrasiAmortized {
    // List int sederhana dengan array internal yang bertumbuh dua kali lipat.
    static class DaftarInt {
        int[] data;
        int ukuran = 0;
        long jumlahSalin = 0;
        long elemenTersalin = 0;

        DaftarInt(int kapasitasAwal) {
            data = new int[kapasitasAwal];
        }

        void tambah(int nilai) {
            if (ukuran == data.length) {
                jumlahSalin++;
                elemenTersalin += ukuran;
                data = Arrays.copyOf(data, data.length * 2);
            }
            data[ukuran++] = nilai;
        }
    }

    public static void main(String[] args) {
        int total = 100_000;

        DaftarInt tumbuh = new DaftarInt(4);
        for (int i = 0; i < total; i++) {
            tumbuh.tambah(i);
        }
        System.out.println("Kapasitas awal 4 (bertumbuh sendiri):");
        System.out.println("  elemen ditambahkan : " + total);
        System.out.println("  operasi salin array: " + tumbuh.jumlahSalin);
        System.out.println("  elemen tersalin     : " + tumbuh.elemenTersalin);
        System.out.printf("  rata-rata salin per tambah: %.2f%n",
                (double) tumbuh.elemenTersalin / total);

        DaftarInt siap = new DaftarInt(131_072);
        for (int i = 0; i < total; i++) {
            siap.tambah(i);
        }
        System.out.println("Kapasitas awal 131072 (dihitung di muka):");
        System.out.println("  operasi salin array: " + siap.jumlahSalin);
        System.out.println("  elemen tersalin     : " + siap.elemenTersalin);
    }
}

Output yang Dihasilkan:

text 
Kapasitas awal 4 (bertumbuh sendiri):
  elemen ditambahkan : 100000
  operasi salin array: 15
  elemen tersalin     : 131068
  rata-rata salin per tambah: 1.31
Kapasitas awal 131072 (dihitung di muka):
  operasi salin array: 0
  elemen tersalin     : 0

Poin bedahnya:

  1. Baris 33-40 (kapasitas 4): dari 100.000 penyisipan hanya terjadi 15 penyalinan array (kapasitas melompat 4 → 8 → … → 131.072), dengan total 131.068 elemen tersalin — rata-rata 1,31 elemen per penyisipan. Inilah makna amortized: biaya penyalinan besar tersebar rata sehingga tiap add praktis konstan, meski sebagian kecil add (15 dari 100.000) membayar lebih mahal.
  2. Baris 42-48 (kapasitas 131.072): menetapkan kapasitas di muka menghapus seluruh penyalinan. ArrayList menyediakan new ArrayList<>(kapasitas) dan ensureCapacity, sedangkan untuk HashMap, aturan praktisnya kapasitas ≈ perkiraanUkuran / 0.75 agar ambang rehash tidak terlampaui di tengah pengisian.
  3. Rumus pertumbuhan dua kali lipat adalah alasan matematisnya: jumlah elemen yang pernah tersalin tidak pernah melampaui sekitar dua kali jumlah elemen akhir — deret geometrik 4+8+16+… ≈ 2 × suku terakhir.

Menghitung Operasi, Bukan Detik #

Cara kedua membuktikan kompleksitas tanpa jam dinding adalah menghitung perbandingan yang dilakukan algoritma. Program berikut mencari elemen terakhir dari 1.000 bilangan terurut dengan dua strategi — pemindaian linear (perilaku indexOf) dan pencarian biner (perilaku Collections.binarySearch pada list terurut):

java BiayaPencarian.java 
import java.util.*;

public class BiayaPencarian {
    public static void main(String[] args) {
        int[] data = new int[1000];
        for (int i = 0; i < data.length; i++) {
            data[i] = i * 2; // bilangan genap terurut
        }
        int target = 1998; // elemen terakhir

        int langkahLinear = 0;
        for (int n : data) {
            langkahLinear++;
            if (n == target) {
                break;
            }
        }

        int langkahBiner = 0;
        int lo = 0;
        int hi = data.length - 1;
        while (lo <= hi) {
            langkahBiner++;
            int mid = (lo + hi) >>> 1;
            if (data[mid] == target) {
                break;
            }
            if (data[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }

        System.out.println("ukuran data         : " + data.length);
        System.out.println("target              : " + target);
        System.out.println("perbandingan linear : " + langkahLinear);
        System.out.println("perbandingan biner  : " + langkahBiner);
    }
}

Output yang Dihasilkan:

text 
ukuran data         : 1000
target              : 1998
perbandingan linear : 1000
perbandingan biner  : 10

Poin bedahnya:

  1. Hasil 1000 vs 10: pemindaian linear menyentuh seluruh elemen karena targetnya kebetulan di ujung; pencarian biner membelah wilayah pencarian menjadi dua pada setiap langkah sehingga 1.000 elemen habis dalam 10 langkah — sesuai logaritma basis dua dari 1.000.
  2. Struktur menentukan kelayakan biner: pencarian biner menuntut data terurut dan akses acak O(1) — persis syarat yang dipenuhi ArrayList hasil Collections.sort, dan alasan Collections.binarySearch dijalankan pada List terurut. Struktur hash mencapai hal serupa lewat jalur berbeda: HashSet.contains O(1) rata-rata tanpa syarat terurut, tetapi dengan syarat kontrak hash yang baik.
  3. Skala yang perlu diantisipasi: pada satu juta elemen, linear butuh hingga 1.000.000 perbandingan sementara biner tetap sekitar 20 — selisih yang tidak bisa dikecilkan oleh faktor konstanta mana pun.

Biaya di Luar Notasi #

Big-O membuang faktor konstanta, namun dua faktor konstanta ini kerap mengubah keputusan praktis. Pertama, autoboxing: ArrayList<Integer> menyimpan objek Integer — tiap elemen menuntut header objek dan rujukan di samping nilainya, sehingga jejak memorinya beberapa kali lipat int[], dan setiap list.add(5) pada variabel Integer menciptakan objek baru di luar jangkauan cache Integer (-128 sampai 127). Untuk jutaan bilangan, int[] atau pustaka khusus primitive collection jauh lebih ramping. Kedua, lokalitas memori: array ArrayList menempati blok memori berurutan yang ramah cache prosesor, sedangkan LinkedList menyimpan node yang tersebar di heap — prosesor melompat-lompat mengikuti rujukan, dan lompatan itu berbiaya nyata meski notasi Big-O sama-sama O(n) untuk penelusuran.

Kerangka terakhir ini menutup Section: kita mengenal struktur, mengelola urutan dan keunikan, memetakan key ke value, lalu memilih dan menimbang biayanya. Satu perhatian mengikuti kita sepanjang Section ini tanpa pernah dibedah tuntas — penulisan List<String>, Map<String, Integer>, TreeSet<Integer> yang selalu disertai tipe dalam kurung siku. Mekanisme di balik kurung siku itu bernama generics, sistem tipe parameter yang menjadi fondasi seluruh Collections Framework dan topik pembuka Section berikutnya.

Referensi #

Berkas Sumber

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

BiayaPencarian.java

Unduh berkas
java 
import java.util.*;

public class BiayaPencarian {
    public static void main(String[] args) {
        int[] data = new int[1000];
        for (int i = 0; i < data.length; i++) {
            data[i] = i * 2; // bilangan genap terurut
        }
        int target = 1998; // elemen terakhir

        int langkahLinear = 0;
        for (int n : data) {
            langkahLinear++;
            if (n == target) {
                break;
            }
        }

        int langkahBiner = 0;
        int lo = 0;
        int hi = data.length - 1;
        while (lo <= hi) {
            langkahBiner++;
            int mid = (lo + hi) >>> 1;
            if (data[mid] == target) {
                break;
            }
            if (data[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }

        System.out.println("ukuran data         : " + data.length);
        System.out.println("target              : " + target);
        System.out.println("perbandingan linear : " + langkahLinear);
        System.out.println("perbandingan biner  : " + langkahBiner);
    }
}

DemonstrasiAmortized.java

Unduh berkas
java 
import java.util.*;

public class DemonstrasiAmortized {
    // List int sederhana dengan array internal yang bertumbuh dua kali lipat.
    static class DaftarInt {
        int[] data;
        int ukuran = 0;
        long jumlahSalin = 0;
        long elemenTersalin = 0;

        DaftarInt(int kapasitasAwal) {
            data = new int[kapasitasAwal];
        }

        void tambah(int nilai) {
            if (ukuran == data.length) {
                jumlahSalin++;
                elemenTersalin += ukuran;
                data = Arrays.copyOf(data, data.length * 2);
            }
            data[ukuran++] = nilai;
        }
    }

    public static void main(String[] args) {
        int total = 100_000;

        DaftarInt tumbuh = new DaftarInt(4);
        for (int i = 0; i < total; i++) {
            tumbuh.tambah(i);
        }
        System.out.println("Kapasitas awal 4 (bertumbuh sendiri):");
        System.out.println("  elemen ditambahkan : " + total);
        System.out.println("  operasi salin array: " + tumbuh.jumlahSalin);
        System.out.println("  elemen tersalin     : " + tumbuh.elemenTersalin);
        System.out.printf("  rata-rata salin per tambah: %.2f%n",
                (double) tumbuh.elemenTersalin / total);

        DaftarInt siap = new DaftarInt(131_072);
        for (int i = 0; i < total; i++) {
            siap.tambah(i);
        }
        System.out.println("Kapasitas awal 131072 (dihitung di muka):");
        System.out.println("  operasi salin array: " + siap.jumlahSalin);
        System.out.println("  elemen tersalin     : " + siap.elemenTersalin);
    }
}