Map

Map menampung data sebagai pasangan kunci-nilai (key-value), sehingga sebuah nilai dicari lewat kuncinya, bukan lewat posisi. Bentuk ini pas untuk kamus data, misalnya stok barang per nama barang atau skor per nomor peserta. Topik ini mempraktikkan HashMap sebagai pilihan utamanya, membongkar cara kerja tabel hash di baliknya, lalu menutup dengan TreeMap dan LinkedHashMap untuk kebutuhan urutan.

Operasi harian pada HashMap#

Tiga metode membentuk hampir seluruh pekerjaan harian Map, yaitu put(K, V) untuk menyimpan, get(K) untuk membaca, dan remove(K) untuk menghapus. Menyimpan dengan kunci yang sudah ada menggantikan nilai lamanya, sedangkan membaca kunci yang belum pernah disimpan mengembalikan null, bukan error. Program berikut memainkan ketiganya pada kasus stok gudang sederhana.

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

public class DemoHashMap {

    public static void main(String[] args) {
        Map<String, Integer> stokGudang = new HashMap<>();
        stokGudang.put("pensil", 120);
        stokGudang.put("buku tulis", 80);
        stokGudang.put("penghapus", 45);

        System.out.println("stok buku tulis : " + stokGudang.get("buku tulis"));
        System.out.println("stok penggaris  : " + stokGudang.get("penggaris"));
        System.out.println("dengan default  : " + stokGudang.getOrDefault("penggaris", 0));

        stokGudang.put("pensil", 130);          // kunci sama, nilai diganti
        stokGudang.remove("penghapus");
        System.out.println("isi map         : " + stokGudang);
        System.out.println("jumlah pasangan : " + stokGudang.size());
        System.out.println("ada buku tulis? : " + stokGudang.containsKey("buku tulis"));

        for (Map.Entry<String, Integer> pasangan : stokGudang.entrySet()) {
            System.out.println(pasangan.getKey() + " => " + pasangan.getValue());
        }
    }
}

stok buku tulis : 80
stok penggaris  : null
dengan default  : 0
isi map         : {pensil=130, buku tulis=80}
jumlah pasangan : 2
ada buku tulis? : true
pensil => 130
buku tulis => 80

Baris keluaran yang paling penting justru yang membaca kunci yang tidak ada, yaitu stok penggaris : null. Nilai null semacam ini mudah berubah menjadi NullPointerException ketika langsung dipakai dalam perhitungan, sehingga getOrDefault disediakan sebagai versi yang aman. Perhatikan pula put("pensil", 130), yang tidak menambah pasangan baru melainkan menimpa nilai lama, sehingga ukuran map tetap dua setelahnya. Perulangan for-each di atas memakai entrySet(), yaitu tampilan kumpulan pasangan lengkap beserta kunci dan nilainya.

Pemilihan tampilan map yang disusuri juga berdampak pada biaya. containsKey menikuti jalur tabel hash sehingga hampir konstan, sedangkan containsValue tidak punya jalan pintas, karena metode ini menyusuri seluruh keranjang satu per satu untuk mencari satu nilai. Bila kunci dan nilai dibutuhkan bersamaan, entrySet lebih hemat daripada menyusuri keySet lalu memanggil get untuk tiap kuncinya, karena pasangan lengkapnya sudah ada di tangan.

Cara HashMap menempatkan kunci#

Kecepatan HashMap berasal dari tabel hash, yaitu array berisi sejumlah keranjang (bucket) tempat pasangan disimpan. Ketika kunci disimpan, Java memanggil hashCode() kunci tersebut, lalu mengubah kode hash itu menjadi indeks keranjang. Pencarian tidak lagi menyusuri seluruh isi, melainkan langsung melompat ke keranjang hasil perhitungan, sehingga biaya get dan put rata-rata $O(1)$ berapa pun ukurannya.

Sebagai gambaran, kunci “Budi” menghasilkan kode hash 2081848, dan 2081848 % 16 jatuh ke indeks 8, persis seperti diagram di atas. Implementasi yang sesungguhnya mencampur bit kode hash lebih dahulu sebelum mengambil sisanya, sehingga indeks kenyataannya bisa berbeda dari sisa bagi murni ini. Campuran bit itu hanya memperbaiki persebaran kunci, sedangkan idenya tetap sama, yaitu menurunkan satu indeks dari satu kode hash.

Dua kunci berbeda bisa saja jatuh di keranjang yang sama, keadaan yang disebut tabrakan (collision). Dalam satu keranjang, pasangan-pasangan yang bertabrakan disusun berurutan, dan equals dipanggil untuk membedakan kunci mana yang dimaksud. Mekanisme inilah yang mengikat HashMap pada kontrak equals dan hashCode, karena perhitungan keranjang memakai hashCode sedangkan pembedaan akhir memakai equals.

Tiga implementasi, tiga urutan#

Sebagaimana keluarga Set, implementasi Map berbeda pada urutan yang dijanjikan. Program berikut memasukkan pasangan yang sama ke tiga implementasi, lalu mencetak hasilnya.

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.TreeMap;

public class DemoUrutanMap {

    public static void main(String[] args) {
        Map<String, Integer> hashMap = new HashMap<>();
        Map<String, Integer> linkedMap = new LinkedHashMap<>();
        TreeMap<String, Integer> treeMap = new TreeMap<>();

        String[] masukan = {"mangga", "apel", "jeruk", "durian"};
        for (int i = 0; i < masukan.length; i++) {
            hashMap.put(masukan[i], i + 1);
            linkedMap.put(masukan[i], i + 1);
            treeMap.put(masukan[i], i + 1);
        }

        System.out.println("HashMap     : " + hashMap);
        System.out.println("LinkedHashMap: " + linkedMap);
        System.out.println("TreeMap     : " + treeMap);
        System.out.println("kunci pertama TreeMap: " + treeMap.firstKey());
    }
}

HashMap     : {jeruk=3, apel=2, mangga=1, durian=4}
LinkedHashMap: {mangga=1, apel=2, jeruk=3, durian=4}
TreeMap     : {apel=2, durian=4, jeruk=3, mangga=1}
kunci pertama TreeMap: apel

HashMap mencetak urutan internal tabel hash yang tidak bisa diprediksi. LinkedHashMap menyimpan rantai tambahan antar-pasangan, sehingga urutannya persis mengikuti urutan put, dan rantai itulah yang menambah sedikit konsumsi memorinya. Konstruktor LinkedHashMap bahkan menerima penanda urutan-akses (access order), yang menyusun pasangan berdasarkan kapan terakhir dibaca, dasar dari cache sederhana yang membuang entri paling lama tak disentuh. TreeMap menyusun pasangan di dalam pohon merah-hitam berdasarkan urutan alami kunci, sehingga cetakannya alfabetis dan metode pemandu seperti firstKey() tersedia. Biaya operasinya pun berbeda, $O(1)$ rata-rata untuk HashMap dan LinkedHashMap, sedangkan $O(\log n)$ untuk TreeMap karena setiap penyimpanan harus menjaga keterurutan.

Kesalahan umum#

• Memakai hasil get tanpa memeriksa null. Kunci yang belum disimpan mengembalikan null, dan pemakaiannya langsung dalam perhitungan memicu NullPointerException. Gunakan getOrDefault, atau periksa dengan containsKey bila keberadaan kuncinya belum pasti.
• Mengandalkan urutan HashMap. Urutan cetaknya adalah jejak tabel hash dan bisa berubah. Pilih LinkedHashMap bila urutan penyimpanan penting, atau TreeMap bila isinya perlu terurut berdasarkan kunci.
• Menyimpan kunci yang isinya berubah setelah dimasukkan. Indeks keranjang dihitung dari keadaan kunci saat itu, sehingga objek yang berubah bisa “hilang” meski masih ada di dalam map. Jadikan kunci imutabel.
• Mengira kunci boleh lebih dari satu nilai. Menyimpan put(kunci, nilaiA) lalu put(kunci, nilaiB) menyisakan satu pasangan berisi nilaiB. Susun Map<String, List<Integer>> bila satu kunci memang harus menampung banyak nilai.

Ringkasan#

• Map menyimpan pasangan kunci-nilai, dengan put, get, remove, dan containsKey sebagai operasi intinya.
• HashMap mencari lewat tabel hash, yaitu hashCode() kunci dihitung menjadi indeks keranjang, lalu equals membedakan kandidat di dalam keranjang yang sama.
• Kapasitas tabel tumbuh otomatis lewat faktor beban, sehingga biaya get dan put rata-rata tetap konstan.
• LinkedHashMap menjaga urutan penyimpanan, TreeMap menjaga urutan kunci, dan keduanya adalah pilihan ketika urutan lebih berharga daripada sedikit kecepatan.

Referensi#

• Interface Map (The Java Tutorials) — Oracle — kontrak Map, operasi dasarnya, dan perbandingan implementasinya.
• Class HashMap — Oracle Java SE 21 — dokumentasi HashMap, termasuk faktor beban default dan catatan urutan iterasi.
• Class TreeMap — Oracle Java SE 21 — dokumentasi TreeMap beserta metode pemandu urutan kuncinya.