Hash set

Hash set adalah tabel hash yang hanya menyimpan kunci tanpa nilai, sehingga kegunaannya terkonsentrasi pada satu pertanyaan, apakah sebuah nilai pernah muncul. Topik ini mengukur selisih kecepatan antara pemeriksaan keanggotaan pada hash set dan pemindaian list pada masukan yang sama, lalu memakai keunggulan itu untuk deduplikasi. Versi Javanya, HashSet, diuji dalam program terpisah, dan jebakan urutan iterasi set ditutup dengan peringatan yang konkret.

Keanggotaan berbiaya konstan#

Pemeriksaan keanggotaan pada hash set memakai mesin yang sama dengan hash map, hitung indeks dari nilai yang dicari, lalu periksa bucket yang dituju. Karena tidak ada pemindaian elemen satu per satu, biayanya $O(1)$ rata-rata, sedangkan operator in pada list harus memeriksa elemen dari depan sampai target ditemukan, berbiaya $O(n)$. Selisihnya terasa kecil pada data sepuluh elemen, tetapi membengkak cepat ketika pemeriksaan dilakukan berkali-kali pada data besar. Demo berikut menghitung perbandingannya pada masukan yang sama, lengkap dengan penghitung operasi.

"""Menghitung biaya pemeriksaan keanggotaan pada list dan hash set."""

angka = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9]
kueri = [7, 10]                # 7 ada di data, 10 tidak ada

# list: setiap kueri memindai elemen satu per satu dari depan
pemindaian = 0
for t in kueri:
    for nilai in angka:
        pemindaian += 1
        if nilai == t:
            break

# hash set: dibangun sekali, lalu setiap kueri satu langkah
himpunan = set(angka)
pemeriksaan = len(kueri)       # setiap kueri hanya satu pemeriksaan keanggotaan

print("ukuran data :", len(angka))
print("list        :", pemindaian, "perbandingan untuk", len(kueri), "kueri")
print("hash set    :", pemeriksaan, "pemeriksaan untuk", len(kueri), "kueri")
print("7 ada       :", 7 in himpunan)
print("10 ada      :", 10 in himpunan)

ukuran data : 15
list        : 29 perbandingan untuk 2 kueri
hash set    : 2 pemeriksaan untuk 2 kueri
7 ada       : True
10 ada      : False

List memerlukan 29 perbandingan untuk dua kueri, 14 untuk mencari angka 7 yang berada menjelang akhir data dan 15 untuk memastikan angka 10 memang tidak ada. Hash set menjawab dua kueri itu dengan dua pemeriksaan, satu langkah per kueri, setelah membayar pembangunan himpunan sebanyak $O(n)$ di awal. Polanya jelas, pembangunan hash set sepadan ketika kuerinya banyak, dan pemborosan ketika kuerinya hanya satu kali. Hitunglah berapa kali pemeriksaan dilakukan sebelum memilih struktur datanya.

Struktur ini muncul alami dalam pekerjaan sehari-hari, misalnya memeriksa apakah nomor peserta sudah terdaftar sebelum pencatatan dilanjutkan, atau menyaring alamat email ganda pada satu daftar undangan. Polanya selalu sama, simpan sekali pada hash set, lalu setiap pemeriksaan berikutnya bertanya pada hash set alih-alih menyapu daftar dari awal. Soal pemrograman meminjam bentuk yang sama, kumpulan angka diperiksa keberadaan duplikatnya dengan satu hash set, dan jawaban tercapai tanpa perbandingan berpasangan.

Deduplikasi yang menjaga urutan#

Deduplikasi adalah pembuangan duplikat dari sebuah koleksi, dan hash set membuatnya sederhana karena nilai yang sudah ada tidak tersimpan dua kali. Cara tercepat, membungkus koleksi dengan set(), punya cacat berupa urutan hasil yang tidak dijamin, karena urutan iterasi set bukan urutan penyisipan. Banyak laporan justru membutuhkan urutan kemunculan pertama tetap terpelihara, misalnya daftar kata unik sesuai urutan kemunculannya. Dua cara berikut membuang duplikat tanpa mengacaukan urutannya.

"""Membuang duplikat tanpa mengacaukan urutan kemunculan pertama."""

kata = ["daun", "akar", "daun", "batang", "akar", "bunga", "daun"]

# cara 1: dict.fromkeys, kunci dict unik dan urutan penyisipannya terjaga
unik1 = list(dict.fromkeys(kata))

# cara 2: set penanda + satu lintasan manual
terlihat = set()
unik2 = []
for k in kata:
    if k not in terlihat:
        terlihat.add(k)
        unik2.append(k)

print("asli     :", kata)
print("fromkeys :", unik1)
print("penanda  :", unik2)
print("set()    :", len(set(kata)), "kata unik, urutannya tidak dijamin")

asli     : ['daun', 'akar', 'daun', 'batang', 'akar', 'bunga', 'daun']
fromkeys : ['daun', 'akar', 'batang', 'bunga']
penanda  : ['daun', 'akar', 'batang', 'bunga']
set()    : 4 kata unik, urutannya tidak dijamin

Kedua cara menghasilkan urutan yang sama persis, daun, akar, batang, bunga, sesuai kemunculan pertamanya. Cara dict.fromkeys memanfaatkan dua sifat dict sekaligus, kuncinya unik dan urutan penyisipannya terjaga, sehingga satu baris cukup. Cara set penanda lebih panjang, tetapi idiom yang sama dapat dipindahkan ke bahasa apa pun, termasuk ketika penyaringan perlu digabung dengan pengolahan pada kemunculan pertama setiap butir. Ukuran hasil sengaja dicetak dari len(set(kata)) saja, karena mencetak set-nya langsung justru memunculkan urutan yang tidak terjamin.

HashSet pada Java#

HashSet adalah hash set bawaan Java dengan operasi add, contains, remove, dan size, semuanya $O(1)$ rata-rata. Konstruktor HashSet juga menerima kapasitas awal, berguna ketika banyaknya elemen sudah dapat diperkirakan sehingga resize dapat dikurangi. Program berikut menguji perilakunya pada kumpulan kata yang sengaja diberi duplikat.

import java.util.HashSet;
import java.util.Set;

public class DemoHashSet {
    public static void main(String[] args) {
        Set<String> kata = new HashSet<>();
        kata.add("daun");            // add: menyisipkan bila belum ada
        kata.add("akar");
        kata.add("daun");            // sudah ada: tidak berefek apa pun
        System.out.println("ukuran           : " + kata.size());
        System.out.println("berisi akar?     : " + kata.contains("akar"));
        System.out.println("berisi batang?   : " + kata.contains("batang"));
        kata.remove("akar");
        System.out.println("ukuran baru      : " + kata.size());
        System.out.println("berisi akar?     : " + kata.contains("akar"));
        System.out.println("kosong?          : " + kata.isEmpty());
    }
}

ukuran           : 2
berisi akar?     : true
berisi batang?   : false
ukuran baru      : 1
berisi akar?     : false
kosong?          : false

Panggilan add ketiga terhadap “daun” tidak menambah apa pun, terlihat dari ukuran yang tetap 2 meskipun add dipanggil tiga kali. Metode add mengembalikan true ketika nilai benar-benar baru disisipkan dan false ketika sudah ada, sehingga panggilannya bisa sekaligus dipakai sebagai pemeriksaan. Sama seperti HashMap, HashSet tidak menjamin urutan iterasi, maka program di atas sengaja hanya mencetak size, contains, dan isEmpty yang semuanya deterministik. Semua metode itu bekerja pada mesin bucket yang sama dengan HashMap, hanya tanpa nilai yang menyertainya.

Kesalahan umum#

1. Mengandalkan urutan iterasi set. Urutan iterasi hash set tidak dijamin di Java dan bisa berubah antar eksekusi di Python, karena letak setiap nilai mengikuti hash string yang diacak ulang setiap kali program dijalankan. Simpan urutan pada list terpisah atau dict, atau urutkan secara eksplisit sebelum dicetak.
2. Membangun hash set untuk satu kueri. Pembangunan memakan $O(n)$, sehingga satu pemeriksaan tunggal lebih murah dilakukan langsung pada list. Hash set terbayar ketika pemeriksaannya berulang, misalnya di dalam perulangan.
3. Mengambil elemen lewat indeks. Set tidak mendukung s[0] karena tidak menyimpan posisi, dan kebutuhan seperti itu biasanya tanda bahwa list atau hasil sorted lebih tepat. Gunakan min, max, atau urutkan dahulu bila butuh elemen tertentu.

Ringkasan#

• Pemeriksaan keanggotaan hash set berbiaya $O(1)$ rata-rata, sedangkan pemindaian list berbiaya $O(n)$, dan selisihnya terukur pada masukan yang sama.
• Deduplikasi yang menjaga urutan memakai dict.fromkeys atau set penanda dalam satu lintasan.
• HashSet Java menyediakan add, contains, remove, dan size dengan semantik yang sama, tanpa jaminan urutan iterasi.
• Hash set terbayar ketika kuerinya banyak, bukan untuk satu pemeriksaan tunggal.

Referensi#

• Data Structures — Python Software Foundation — dokumentasi set bawaan Python dan operasi keanggotaannya.
• HashSet — Oracle — dokumentasi add, contains, remove, dan size pada HashSet.
• Hash table — Wikipedia — mekanisme bucket yang berdiri di belakang hash set.