LinkedHashSet

HashSet memberi kita kecepatan hashing, tetapi meninggalkan urutan iterasi yang tidak bisa dijanjikan. LinkedHashSet mengambil jalan tengah yang cerdas: implementasi ini memakai mekanisme hash HashSet dan menjaga sebuah rantai tautan tambahan yang mencatat urutan penyisipan, sehingga iterasi selalu mengikuti urutan masuk. Biayanya jelas dan terukur — setiap elemen membawa dua referensi tautan ekstra (maju dan mundur) sehingga jejak memori lebih besar daripada HashSet. Pada Chapter ini kita bedah perilaku urutan penyisipannya, lalu kita rakit satu pola klasik yang memanfaatkan gabungan keunikan dan urutan: antrean FIFO yang otomatis membuang duplikat.

Dua Struktur dalam Satu Wadah #

Di balik layar, sebuah LinkedHashSet (yang di dalamnya mewarisi HashMap dengan linked hash map) menyimpan dua hal sekaligus: tabel bucket seperti HashSet untuk menempatkan elemen berdasarkan hash, dan daftar berantai ganda yang menghubungkan seluruh elemen sesuai urutan penyisipan. Operasi add, contains, dan remove tetap memakai jalur hash sehingga tetap O(1) rata-rata; sementara itu, iterasi cukup berjalan menyusuri daftar tautan dari kepala ke ekor — urutan penyisipan muncul alami tanpa penyortiran apa pun.

Ada satu aturan halus yang membedakan “urutan penyisipan” dari sekadar “urutan pertama kali dilihat”. Jika kita memasukkan elemen yang sudah ada, add mengembalikan false dan posisi lama elemen tersebut tidak berubah. Elemen hanya bergeser ke ekor jika elemen tersebut dihapus lebih dulu lalu dimasukkan lagi — karena saat itulah penyisipan benar-benar terjadi.

Perilaku Urutan dalam Praktik #

Program berikut membuktikan ketiga aturan tersebut lewat daftar hadir tiga peserta:

import java.util.*;

public class UrutanSisip {
    public static void main(String[] args) {
        LinkedHashSet<String> hadir = new LinkedHashSet<>();
        hadir.add("Budi");
        hadir.add("Siti");
        hadir.add("Dewi");
        System.out.println("Awal             : " + hadir);

        // Duplikat ditolak; posisi lama dipertahankan.
        hadir.add("Budi");
        System.out.println("add Budi lagi    : " + hadir);

        // Keluar lalu masuk lagi -> pindah ke ekor.
        hadir.remove("Siti");
        hadir.add("Siti");
        System.out.println("Siti keluar-masuk: " + hadir);

        // SequencedSet (Java 21+): ujung depan juga bisa diatur.
        hadir.addFirst("Siti");
        System.out.println("addFirst Siti    : " + hadir);
        System.out.println("getFirst()       : " + hadir.getFirst());
    }
}

Output yang Dihasilkan:

Awal             : [Budi, Siti, Dewi]
add Budi lagi    : [Budi, Siti, Dewi]
Siti keluar-masuk: [Budi, Dewi, Siti]
addFirst Siti    : [Siti, Budi, Dewi]
getFirst()       : Siti

Mari kita bedah baris-baris pentingnya:

1. Baris 6-9 (add pertama kali): urutan cetakan [Budi, Siti, Dewi] sama dengan urutan penyisipan — inilah janji utama LinkedHashSet.
2. Baris 13 (hadir.add("Budi") kedua kali): add mengembalikan false, Budi tetap di posisi depan; mencoba “menyisipkan ulang” tidak memindahkan elemen.
3. Baris 17-18 (remove lalu add): Siti keluar dari daftar, lalu masuk kembali sebagai penyisipan baru — posisinya bergeser ke ekor menjadi [Budi, Dewi, Siti].
4. Baris 21-23 (addFirst dan getFirst): sejak Java 21, LinkedHashSet memenuhi kontrak SequencedSet sehingga ujung depan bisa dibaca dan diatur langsung; addFirst("Siti") memindahkan Siti ke depan menjadi [Siti, Budi, Dewi].

Pola FIFO Dedup untuk Antrean Layanan #

Gabungan “keunikan + urutan penyisipan + akses ujung O(1)” menghasilkan pola yang sangat berguna: memproses aliran data dengan mengabaikan duplikat namun tetap menjaga urutan kedatangan pertama. Kasus nyatanya antrean layanan pelanggan — setiap orang mungkin menekan tombol panggilan berkali-kali, tetapi hanya kedatangan pertamanya yang berharga:

import java.util.*;

public class LogPengunjung {
    public static void main(String[] args) {
        // Aliran kedatangan pelanggan: ada yang datang dua kali.
        String[] kedatangan = {"Budi", "Siti", "Budi", "Dewi", "Siti", "Ani", "Dewi"};

        LinkedHashSet<String> antreanUnik = new LinkedHashSet<>();
        for (String nama : kedatangan) {
            antreanUnik.add(nama); // duplikat ditolak, urutan pertama tetap
        }
        System.out.println("Urutan layanan unik: " + antreanUnik);

        // Pola FIFO-dedup: layani satu per satu dari yang paling dulu datang.
        while (!antreanUnik.isEmpty()) {
            String dilayani = antreanUnik.removeFirst();
            System.out.println("Melayani: " + dilayani);
        }
        System.out.println("Sisa antrean: " + antreanUnik);
    }
}

Output yang Dihasilkan:

Urutan layanan unik: [Budi, Siti, Dewi, Ani]
Melayani: Budi
Melayani: Siti
Melayani: Dewi
Melayani: Ani
Sisa antrean: []

Poin bedahnya:

1. Baris 6-10 (loop add): tujuh kedatangan berisi hanya empat nama unik. Setiap add duplikat ditolak diam-diam, dan urutan yang tersimpan adalah urutan kedatangan pertama masing-masing: Budi, Siti, Dewi, lalu Ani.
2. Baris 14-17 (removeFirst dalam loop while): removeFirst() mengambil dan menghapus elemen terdepan sekaligus — kombinasi khas SequencedSet yang membuat pola FIFO enak dibaca tanpa Iterator eksplisit.
3. Hasil akhir: keempat pelanggan terlayani tepat sesuai urutan kedatangan pertama mereka, dan antrean berakhir kosong.

Jika dibandingkan dengan pendekatan ArrayList + contains sebelum menambah (O(n) per kedatangan), pola LinkedHashSet ini mempertahankan O(1) rata-rata per kedatangan. Kombinasi yang sama juga populer untuk deduplikasi log dengan urutan kejadian terjaga.

Biaya Tambahan dan Pemilihan #

Kejelasan urutan tidak gratis. Tabel berikut merangkum posisi ketiga implementasi Set:

Kecepatan hashing dan urutan penyisipan kini sudah kita kuasai. Masih ada satu janji urutan yang lebih kuat lagi: isi yang selalu terurut dengan kemampuan navigasi rentang. Chapter berikutnya membahas TreeSet dan interface NavigableSet di baliknya.

Referensi #

• Java API Specification: java.util.LinkedHashSet
• Java API Specification: java.util.SequencedSet
• Dev.java: The Java Collections Framework

import java.util.*;

public class LogPengunjung {
    public static void main(String[] args) {
        // Aliran kedatangan pelanggan: ada yang datang dua kali.
        String[] kedatangan = {"Budi", "Siti", "Budi", "Dewi", "Siti", "Ani", "Dewi"};

        LinkedHashSet<String> antreanUnik = new LinkedHashSet<>();
        for (String nama : kedatangan) {
            antreanUnik.add(nama); // duplikat ditolak, urutan pertama tetap
        }
        System.out.println("Urutan layanan unik: " + antreanUnik);

        // Pola FIFO-dedup: layani satu per satu dari yang paling dulu datang.
        while (!antreanUnik.isEmpty()) {
            String dilayani = antreanUnik.removeFirst();
            System.out.println("Melayani: " + dilayani);
        }
        System.out.println("Sisa antrean: " + antreanUnik);
    }
}

import java.util.*;

public class UrutanSisip {
    public static void main(String[] args) {
        LinkedHashSet<String> hadir = new LinkedHashSet<>();
        hadir.add("Budi");
        hadir.add("Siti");
        hadir.add("Dewi");
        System.out.println("Awal             : " + hadir);

        // Duplikat ditolak; posisi lama dipertahankan.
        hadir.add("Budi");
        System.out.println("add Budi lagi    : " + hadir);

        // Keluar lalu masuk lagi -> pindah ke ekor.
        hadir.remove("Siti");
        hadir.add("Siti");
        System.out.println("Siti keluar-masuk: " + hadir);

        // SequencedSet (Java 21+): ujung depan juga bisa diatur.
        hadir.addFirst("Siti");
        System.out.println("addFirst Siti    : " + hadir);
        System.out.println("getFirst()       : " + hadir.getFirst());
    }
}