Struktur data efisien: Set & Map

Optimasi Kode di Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Menerapkan kompleksitas ruang/waktu

Kita kini paham kompleksitas ruang dan waktu!

Bagaimana menerapkannya untuk menulis kode yang lebih efisien?

Dengan memilih struktur data yang tepat!

Sistem manajemen pengguna

Kita membangun sistem manajemen pengguna
Kita perlu mengecek, untuk sebuah username, apakah pengguna ada
Menggunakan list: kompleksitas $O(n)$

public boolean usernameExists(ArrayList<String> users, String newUsername) {
    for (String username : users) {
        if (username.equals(newUsername)) {
            return true;
        }
    }
    return false;
}

Set

Kumpulan elemen unik dengan pencarian cepat
Kompleksitas waktu rata-rata $O(1)$ untuk tambah, hapus, dan cek keberadaan elemen

Solusi sistem manajemen pengguna yang lebih baik:

public class UserRegistry {
    private HashSet<String> users = new HashSet<>();

    public boolean userExists(String username) {
        return users.contains(username); // O(1) waktu rata-rata
    }
}

Map

Seperti kamus, kata (key) -> definisi (value)
HashMap: kompleksitas waktu rata-rata $O(1)$ untuk operasi

public class UserCache {
    private HashMap<String, UserProfile> userProfiles = new HashMap<>();

    public UserProfile getUser(String username) {
        return userProfiles.get(username);  // O(1) waktu rata-rata
    }
}

Metode hashcode

Yang membuatnya cepat -> hashCode()
Pada contoh ArrayList, kita tidak tahu indeks username yang dicari
Dengan hashcode(), kita bisa mengubah objek menjadi indeks yang bisa dicari
Misal pavlos.2020 -> 35189

pavlos.2020 diproses lewat hashcode, menghasilkan 35189

Pengindeksan elemen

HashMap dan HashSet memakai array dasar
Saat menambah elemen:
- Java memanggil hashCode() pada elemen untuk mendapat integer
- Lalu ambil modulo untuk nomor bucket

Contoh:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

"optimizingCodeInJava" -> 1406313774 // Diimplementasikan oleh Java
1406313774 % 16 = 14 <- itu bucket kita!

Collision

Saat lebih dari satu item masuk ke bucket yang sama
- Disebut collision
LinkedList dipakai untuk bucket
Karena itu kita bilang $O(1)$ rata-rata

Catatan penting

Memilih struktur data seperti memilih alat yang tepat untuk pekerjaan—palu (ArrayList) cocok untuk paku, tapi buruk untuk sekrup (di mana Set lebih baik).

Peralatan

Ayo berlatih!

Optimasi Kode di Java