Operasi hash map

Hash map adalah tabel hash siap pakai yang tersedia di hampir semua bahasa pemrograman, dan topik ini melatih pemakaian sehari-harinya pada dict Python serta HashMap Java. Tiga operasi dasarnya, yaitu put, get, dan delete, dibedah dari sisi kompleksitas rata-rata maupun terburuknya. Bagian akhir menyandingkan kedua bahasa dalam satu tabel perbandingan, lalu topik ditutup dengan daftar jebakan yang paling sering muncul.

Tiga operasi dan biayanya#

Operasi put menyimpan pasangan kunci-nilai, get membaca nilai dari sebuah kunci, dan delete menghapus pasangannya. Ketiganya mengikuti mekanisme tabel hash yang sama, hitung indeks dari kunci, lalu bekerja pada bucket tempat kunci itu mendarat. Selama fungsi hash merata dan load factor terjaga, langkah-langkah tersebut tidak bergantung pada banyaknya data, sehingga biaya rata-ratanya $O(1)$. Kasus terburuknya adalah $O(n)$, terjadi ketika semua kunci bertumpuk pada satu bucket sehingga pencarian kembali menjadi penelusuran list penuh.

Kasus terburuk itu jarang muncul dalam praktik karena implementasi nyata memakai fungsi hash yang tersebar dan melakukan resize sebelum load factor membahayakan. Tetap saja, pemahaman tentang terburuknya menjelaskan mengapa kualitas fungsi hash bukan perkara sampingan. Soal kompetitif bahkan pernah diserang lewat masukan yang sengaja dirancang membuat tabrakan beruntun, sehingga sejumlah bahasa menambahkan pengacakan pada fungsi hash stringnya untuk menangkal serangan semacam itu. Selama load factor dijaga lewat resize, beban tiap bucket tetap kecil dan janji rata-rata itu bertahan.

Dict Python dalam praktik#

Dict Python menyediakan cara membaca, menulis, memeriksa, dan menghapus pasangan dengan sintaks yang ringkas, dan hampir semuanya berbentuk operator alih-alih pemanggilan metode. Stok barang dipakai sebagai bahan latihan karena operasinya menggambarkan pemakaian dict yang paling lazim, menyimpan jumlah lalu membacanya kembali. Program berikut mencoba semuanya sekaligus, termasuk perilaku ketika kunci yang dicari tidak ada.

"""Operasi inti dict Python: menulis, membaca, memeriksa, dan menghapus."""

stok = {}                      # dict kosong
stok["pulpen"] = 24            # menulis pasangan kunci-nilai (put)
stok["buku"] = 10
stok["penghapus"] = 7
print("isi awal       :", stok)

stok["buku"] = 12              # kunci yang sudah ada, nilai lamanya diganti
print("get buku       :", stok.get("buku"))
print("get penggaris  :", stok.get("penggaris"))      # kunci tak ada: None
print("get + bawaan   :", stok.get("penggaris", 0))   # None diganti nilai bawaan

print("setdefault     :", stok.setdefault("penggaris", 0))  # belum ada: disisipkan
print("setdefault     :", stok.setdefault("buku", 99))      # sudah ada: nilai lama

print("kunci pulpen?  :", "pulpen" in stok)           # pemeriksaan keanggotaan
print("pop pulpen     :", stok.pop("pulpen"))         # ambil nilai, lalu hapus
print("pop penggaris  :", stok.pop("penggaris", 0))   # kunci sudah tiada: bawaan
print("isi akhir      :", stok)

isi awal       : {'pulpen': 24, 'buku': 10, 'penghapus': 7}
get buku       : 12
get penggaris  : None
get + bawaan   : 0
setdefault     : 0
setdefault     : 12
kunci pulpen?  : True
pop pulpen     : 24
pop penggaris  : 0
isi akhir      : {'buku': 12, 'penghapus': 7}

Perbedaan paling penting ada pada pembacaan kunci yang tidak ada. Kurung siku stok["penggaris"] melempar KeyError dan menghentikan program, sedangkan get() mengembalikan None atau nilai bawaan yang disediakan. Metode setdefault menyisipkan nilai bawaan hanya ketika kuncinya belum ada, berguna untuk menyiapkan list kosong sebelum diisi pada pola pengelompokan. Operator in memeriksa keberadaan kunci tanpa mengambil nilainya, dan pop mengambil nilai sekaligus menghapus pasangannya dalam satu langkah. Perhatikan pula urutan cetak yang mengikuti urutan penyisipan, sifat dict yang segera dibandingkan dengan HashMap.

HashMap pada Java#

HashMap adalah pilihan standar Java untuk hash map, tersedia pada paket java.util dan dipanggil lewat metode eksplisit alih-alih kurung siku. Deklarasinya menuliskan antarmuka Map di sisi kiri, sehingga pergantian implementasi cukup mengubah sisi kanannya tanpa menyentuh kode pemakainya. Program berikut mengulang skenario stok yang sama untuk memperlihatkan padanannya satu per satu.

import java.util.HashMap;
import java.util.Map;

public class OperasiHashMap {
    public static void main(String[] args) {
        Map<String, Integer> stok = new HashMap<>();
        stok.put("pulpen", 24);          // put: menyisipkan pasangan kunci-nilai
        stok.put("buku", 10);
        stok.put("penghapus", 7);
        stok.put("buku", 12);            // kunci yang sudah ada, nilai diganti
        System.out.println("get buku         : " + stok.get("buku"));
        System.out.println("get penggaris    : " + stok.get("penggaris"));
        System.out.println("getOrDefault     : " + stok.getOrDefault("penggaris", 0));
        System.out.println("containsKey      : " + stok.containsKey("pulpen"));
        System.out.println("remove pulpen    : " + stok.remove("pulpen"));
        System.out.println("remove penggaris : " + stok.remove("penggaris"));
        System.out.println("getOrDefault     : " + stok.getOrDefault("pulpen", 0));
    }
}

get buku         : 12
get penggaris    : null
getOrDefault     : 0
containsKey      : true
remove pulpen    : 24
remove penggaris : null
getOrDefault     : 0

Perbedaan perilaku terbesar ada pada get terhadap kunci yang tidak ada, yang mengembalikan null tanpa melempar pengecualian. Kenyamanan itu berbalik membingungkan ketika nilai null memang boleh tersimpan, karena null hasil get tidak dapat dibedakan dari null yang sebenarnya, dan di sanalah containsKey diperlukan. Metode getOrDefault merangkum kedua kebutuhan itu dalam satu panggilan, sedangkan remove mengembalikan nilai lama dari kunci yang dihapusnya. Perhatikan juga bahwa put terhadap kunci yang sudah ada mengganti nilai lamanya, sama seperti pada dict. Tiga baris terakhir keluaran menunjukkan remove mengembalikan nilai yang dihapusnya, lalu getOrDefault menyatakan kekosongan pulpen dengan nilai bawaan nol.

Perbandingan dict dan HashMap#

Tabel berikut menyandingkan operasi yang sama pada kedua bahasa, sehingga pola pikirnya tinggal dipindahkan. Kedua struktur memetakan kunci ke nilai dengan mekanisme hash yang sama, sehingga tabel ini layak dibaca sebagai penerjemahan sintaks, bukan sebagai perbandingan dua hal yang asing. Perbedaannya terkonsentrasi pada nama metode dan perlakuan terhadap kunci yang tidak ada, sedangkan janji kompleksitasnya identik.

Baris terakhir layak digarisbawahi. Dict Python menjamin urutan iterasi mengikuti urutan penyisipan sejak Python 3.7, sedangkan HashMap tidak memberi jaminan urutan apa pun, sehingga kode yang mengandalkan urutan iterasi HashMap akan bersifat nondeterministik. Untuk kebutuhan urutan penyisipan di Java, pilihannya adalah LinkedHashMap, sementara dict Python sudah aman secara bawaan. Di luar perbedaan itu, keduanya sama-sama berjanji $O(1)$ rata-rata untuk put, get, dan delete.

Kesalahan umum#

1. Memakai list sebagai kunci dict. Penulisan data[[1, 2]] = "x" langsung melempar TypeError: unhashable type: 'list' karena list bisa berubah sehingga tidak punya hash yang stabil. Untuk kunci yang tersusun dari beberapa nilai, gunakan tuple, misalnya stok[("buku", 2024)], karena tuple tidak berubah dan dapat di-hash.
2. Memakai hasil get tanpa pemeriksaan. get() mengembalikan None untuk kunci yang tidak ada, dan aritmetika terhadap None melempar error di baris lain yang jauh dari sumber masalahnya. Periksa kunci dengan in terlebih dahulu, atau sediakan nilai bawaan pada get dan getOrDefault.
3. Mengharapkan HashMap Java terurut. Iterasi HashMap tidak mengikuti urutan penyisipan maupun urutan nilai kuncinya, sehingga keluaran yang tampak terurut hanyalah kebetulan. Gunakan LinkedHashMap bila urutan penyisipan diperlukan, atau TreeMap bila isinya perlu terurut menurut kunci.

Ringkasan#

• Put, get, dan delete pada hash map berbiaya $O(1)$ rata-rata dan $O(n)$ terburuk ketika tabrakan menumpuk di satu bucket.
• Dict Python menawarkan get, setdefault, in, dan pop, dengan None sebagai jawaban untuk kunci yang tidak ada.
• HashMap Java menawarkan put, get, containsKey, remove, dan getOrDefault, dengan null tanpa pengecualian.
• Perbedaan paling menentukan adalah urutan iterasi, dijamin pada dict dan tidak dijamin pada HashMap.

Referensi#

• Built-in Types — Python Software Foundation — dokumentasi tipe mapping dan perilaku dict pada kunci yang tidak ada.
• HashMap — Oracle — dokumentasi resmi put, get, containsKey, remove, dan getOrDefault.
• Algorithms, 4th Edition — Princeton University — materi tabel hash yang menghubungkan teori tabrakan dengan implementasinya.