HashSet

Setelah memahami kontrak keunikan pada Set, kita berkenalan dengan implementasi yang paling cepat dan paling banyak dipakai: HashSet. Struktur ini menjawab satu pertanyaan dengan kecepatan hampir konstan — “apakah elemen ini sudah ada?” — berkat teknik hashing: setiap elemen diubah menjadi angka oleh hashCode, lalu dikelompokkan ke dalam wadah bernama bucket sehingga pencarian tidak perlu menyisir seluruh isi. Dalam praktik sehari-hari, HashSet menjadi pilihan default untuk daftar kata terlarang, nomor kupon undian, daftar hadir, dan pengecekan duplikat apa pun yang tidak butuh urutan. Pada Chapter ini kita bedah mekanisme bucket-nya, lalu kita bongkar satu kejutan yang sering menjegal pemula: urutan iterasi HashSet yang tidak bisa diprediksi.

Bagaimana Hashing Membagi Penyimpanan #

Bayangkan lemari dengan 16 laci bernomor. Setiap barang baru dimasukkan ke laci yang ditentukan sisa baginya — misalnya nomor 19 masuk laci 3 (karena 19 % 16 = 3), nomor 30 masuk laci 14. Ketika kita menanyakan “apakah 19 ada?”, HashSet tidak membuka ke-16 laci; struktur ini langsung membuka laci 3 dan memeriksa isinya. Inilah alasan operasi add, contains, dan remove rata-rata O(1): jumlah laci yang dibuka tetap satu, berapa pun jumlah barang.

Alur keputusan saat add berlangsung dapat digambarkan begini:

Dua objek yang setara lewat equals selalu mendapat hash yang sama sehingga jatuh ke bucket yang sama — di sanalah equals dipanggil untuk memastikan. Jika banyak objek berbeda menggerombol di bucket yang sama (misalnya karena hashCode yang buruk), keunggulan O(1) menurun menjadi perilaku mirip List. HashSet juga menjaga rasio isi-kapasitas — load factor default 0.75: ketika 75% bucket terisi, jumlah bucket digandakan dan elemen disebar ulang.

HashSet dalam Praktik #

Program berikut menyimpan nomor kupon undian pada HashSet, menguji keanggotaan, menghapus satu elemen, lalu mengiterasi sisanya:

import java.util.*;

public class KuponUndian {
    public static void main(String[] args) {
        HashSet<Integer> kupon = new HashSet<>();
        int[] masukan = {30, 7, 19, 3, 11};
        for (int n : masukan) {
            kupon.add(n);
        }
        System.out.println("Isi kupon : " + kupon);
        System.out.println("Ukuran    : " + kupon.size());

        System.out.println("contains(7)  : " + kupon.contains(7));
        System.out.println("contains(99) : " + kupon.contains(99));

        kupon.remove(7);
        System.out.println("Setelah remove(7): " + kupon);

        System.out.print("Iterasi   : ");
        for (int n : kupon) {
            System.out.print(n + " ");
        }
        System.out.println();
    }
}

Output yang Dihasilkan:

Isi kupon : [19, 3, 7, 11, 30]
Ukuran    : 5
contains(7)  : true
contains(99) : false
Setelah remove(7): [19, 3, 11, 30]
Iterasi   : 19 3 11 30 

Mari kita bedah baris-baris pentingnya:

1. Baris 6-10 (kupon.add(n)): lima nomor masuk, semuanya unik sehingga setiap add menyimpan elemen. Urutan keluaran [19, 3, 7, 11, 30] bukan urutan penyisipan dan bukan urutan terurut — urutan tersebut adalah urutan bucket.
2. Baris 13-14 (contains(7) dan contains(99)): keanggotaan diperiksa dengan melompat langsung ke bucket masing-masing — dua pertanyaan ini menuntut waktu yang hampir sama meski jawabannya berbeda.
3. Baris 16 (kupon.remove(7)): penghapusan juga berbasis hash: lari ke bucket milik 7, temukan elemennya, cabut dari rantai bucket.
4. Baris 19-22 (enhanced for-loop): iterasi menjelajahi bucket demi bucket dari awal array bucket hingga akhir, itulah mengapa hasilnya mengikuti urutan bucket, bukan urutan masuk.

Ketika Urutan Penyisipan Membuktikan Beda #

Perbedaan urutan paling mudah dilihat jika kita memasukkan data yang sama ke HashSet dan LinkedHashSet. Program berikut memasukkan empat nama buah dengan urutan yang sama ke kedua struktur:

import java.util.*;

public class BandingUrutan {
    public static void main(String[] args) {
        Set<String> hash = new HashSet<>();
        Set<String> linked = new LinkedHashSet<>();
        for (String nama : List.of("Apel", "Jeruk", "Pisang", "Mangga")) {
            hash.add(nama);
            linked.add(nama);
        }
        System.out.println("Penyisipan    : [Apel, Jeruk, Pisang, Mangga]");
        System.out.println("HashSet       : " + hash);
        System.out.println("LinkedHashSet : " + linked);
    }
}

Output yang Dihasilkan:

Penyisipan    : [Apel, Jeruk, Pisang, Mangga]
HashSet       : [Pisang, Mangga, Apel, Jeruk]
LinkedHashSet : [Apel, Jeruk, Pisang, Mangga]

Pembacaan hasilnya:

1. Baris HashSet: urutan [Pisang, Mangga, Apel, Jeruk] tidak mengikuti urutan masuk [Apel, Jeruk, Pisang, Mangga] maupun urutan alfabetis — sekali lagi, urutan bucket yang berbicara.
2. Baris LinkedHashSet: urutan keluar sama persis dengan urutan masuk, karena implementasi ini menjaga daftar tautan penyisipan sebagai tambahan (perilaku ini dibahas tuntas pada Chapter LinkedHashSet).

Kapan Memakai HashSet #

Sebagai data tambahan, HashSet mengizinkan satu elemen null (karena hanya ada satu kemungkinan “nilai null”) dan kapasitas awalnya bisa diatur lewat konstruktor new HashSet<>(kapasitasAwal) ketika perkiraan jumlah elemen sudah diketahui. Untuk kebutuhan thread-safe, pustaka menyediakan ConcurrentHashMap.newKeySet() — topik konkurensi yang membahasnya berada di Section lanjutan.

Kecepatan HashSet terbeli dengan satu pengorbanan: urutan iterasi yang liar dan tak bisa dijanjikan. Bagaimana jika kita ingin kecepatan hashing dan urutan yang terprediksi? Chapter berikutnya membahas LinkedHashSet, implementasi yang menyimpan keduanya sekaligus.

Referensi #

• Java API Specification: java.util.HashSet
• Java API Specification: java.util.Set
• Dev.java: The Java Collections Framework

import java.util.*;

public class BandingUrutan {
    public static void main(String[] args) {
        Set<String> hash = new HashSet<>();
        Set<String> linked = new LinkedHashSet<>();
        for (String nama : List.of("Apel", "Jeruk", "Pisang", "Mangga")) {
            hash.add(nama);
            linked.add(nama);
        }
        System.out.println("Penyisipan    : [Apel, Jeruk, Pisang, Mangga]");
        System.out.println("HashSet       : " + hash);
        System.out.println("LinkedHashSet : " + linked);
    }
}

import java.util.*;

public class KuponUndian {
    public static void main(String[] args) {
        HashSet<Integer> kupon = new HashSet<>();
        int[] masukan = {30, 7, 19, 3, 11};
        for (int n : masukan) {
            kupon.add(n);
        }
        System.out.println("Isi kupon : " + kupon);
        System.out.println("Ukuran    : " + kupon.size());

        System.out.println("contains(7)  : " + kupon.contains(7));
        System.out.println("contains(99) : " + kupon.contains(99));

        kupon.remove(7);
        System.out.println("Setelah remove(7): " + kupon);

        System.out.print("Iterasi   : ");
        for (int n : kupon) {
            System.out.print(n + " ");
        }
        System.out.println();
    }
}