Java Academy · Pelajaran

Cara Kerja HashMap

Bucket, hashing, dan collision.

Cara Kerja HashMap adalah pelajaran Java Academy gratis di CoddyKit. Ini adalah pelajaran 1 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Java Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Java Academy mencakup 4 pelajaran total.

Isi yang Disimpan HashMap

HashMap menyimpan pasangan kunci-nilai dan menyediakan pencarian, penyisipan, serta penghapusan dengan kinerja rata-rata O(1).

Secara internal, HashMap menyimpan larik yang disebut tabel. Setiap slot dalam larik ini disebut keranjang.

Kunci menentukan keranjang tempat sebuah entri ditempatkan.
Nilai adalah hasil yang Anda dapatkan ketika mencari kunci tersebut.

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

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> ages = new HashMap<>();
        ages.put("Alice", 30);
        ages.put("Bob", 25);
        System.out.println(ages.get("Alice"));
    }
}

Membuat Hash dari Kunci

Saat Anda memanggil put(key, value), peta memanggil key.hashCode() untuk memperoleh nilai int.

HashMap kemudian menyebarkan bit tersebut dengan fungsi internal agar bahkan kode hash yang buruk pun tersebar di seluruh keranjang.

Bilangan akhirnya diperkecil menggunakan hash & (table.length - 1) untuk memperoleh indeks keranjang.
Panjang tabel selalu merupakan pangkat dua, sehingga masker tersebut berfungsi.

public class Main {
    public static void main(String[] args) {
        String key = "Alice";
        int h = key.hashCode();
        int spread = h ^ (h >>> 16);
        int index = spread & (16 - 1);
        System.out.println("hashCode: " + h);
        System.out.println("bucket index: " + index);
    }
}

Cara Kerja Keranjang

Setiap keranjang dapat menampung lebih dari satu entri. Ketika dua kunci dipetakan ke keranjang yang sama, terjadilah tabrakan.

Tabrakan merupakan hal yang normal dan memang diperkirakan. HashMap menanganinya dengan merangkai entri dalam keranjang.

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

public class Main {
    public static void main(String[] args) {
        Map<Integer, String> m = new HashMap<>();
        for (int i = 0; i < 5; i++) {
            m.put(i, "v" + i);
        }
        System.out.println(m.size() + " entries stored");
    }
}

Tabrakan dan Rantai

Sebelum Java 8, semua entri yang bertabrakan berada dalam daftar tertaut tunggal di dalam keranjang.

Pencarian menelusuri daftar tersebut sambil memanggil equals() sampai menemukan kunci yang cocok.

Sedikit tabrakan: tetap secara efektif O(1).
Banyak tabrakan dalam satu keranjang: kinerjanya menurun mendekati O(n) untuk keranjang tersebut.

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

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("FB", 1);
        m.put("Ea", 2);
        System.out.println("FB hash: " + "FB".hashCode());
        System.out.println("Ea hash: " + "Ea".hashCode());
        System.out.println(m.get("FB") + ", " + m.get("Ea"));
    }
}

Mengapa FB dan Ea Bertabrakan

Teks "FB" dan "Ea" memiliki hashCode() yang sama di Java. Ini adalah contoh klasik tabrakan.

Meskipun kode hash-nya identik, peta tetap memisahkan keduanya karena equals() membedakannya di dalam keranjang.

public class Main {
    public static void main(String[] args) {
        System.out.println("FB".hashCode() == "Ea".hashCode());
        System.out.println("FB".equals("Ea"));
    }
}

Faktor Muatan

Faktor muatan mengatur seberapa penuh tabel sebelum ukurannya bertambah. Nilai bawaannya adalah 0.75.

Kapasitas 16 dan faktor muatan 0.75 berarti pengubahan ukuran terpicu pada 12 entri.
Faktor muatan yang lebih rendah memboroskan memori, tetapi mengurangi tabrakan.
Faktor muatan yang lebih tinggi menghemat memori, tetapi meningkatkan tabrakan.

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

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>(16, 0.75f);
        for (int i = 0; i < 12; i++) m.put(i, i);
        System.out.println("Stored " + m.size() + " entries");
    }
}

Mengubah Ukuran Tabel

Ketika jumlah entri melebihi capacity * loadFactor, ukuran tabel menjadi dua kali lebih besar.

Setiap entri yang sudah ada akan dihitung ulang nilai hash-nya ke dalam tabel baru yang lebih besar. Ini merupakan operasi yang mahal, sehingga penetapan ukuran awal penting untuk peta berukuran besar.

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

public class Main {
    public static void main(String[] args) {
        // Pre-size to avoid repeated resizes
        Map<Integer, Integer> m = new HashMap<>(1024);
        for (int i = 0; i < 800; i++) m.put(i, i * 2);
        System.out.println("size = " + m.size());
    }
}

Menetapkan Ukuran Awal demi Kinerja

Jika Anda mengetahui kira-kira berapa banyak entri yang akan disimpan, berikan kapasitas awal untuk menghindari perubahan ukuran berulang.

Aturan praktis: kapasitas awal = expectedSize / 0.75 + 1.

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

public class Main {
    public static void main(String[] args) {
        int expected = 1000;
        int capacity = (int) (expected / 0.75) + 1;
        Map<Integer, String> m = new HashMap<>(capacity);
        System.out.println("Initial capacity hint: " + capacity);
        m.put(1, "ok");
        System.out.println(m.get(1));
    }
}

Kunci dan Nilai Kosong

HashMap memungkinkan satu kunci kosong dan beberapa nilai kosong.

Kunci kosong selalu masuk ke keranjang 0 karena hash-nya dianggap 0.
Gunakan getOrDefault untuk menghindari kerancuan antara kunci yang tidak ada dan nilai kosong.

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

public class Main {
    public static void main(String[] args) {
        Map<String, String> m = new HashMap<>();
        m.put(null, "nullKeyValue");
        m.put("a", null);
        System.out.println(m.get(null));
        System.out.println(m.getOrDefault("missing", "default"));
    }
}

Urutan Iterasi Tidak Dijamin

HashMap tidak menjamin urutan iterasi. Urutannya bergantung pada kode hash dan susunan keranjang.

Jika Anda memerlukan urutan yang dapat diprediksi, gunakan LinkedHashMap (urutan penyisipan) atau TreeMap (urutan terurut).

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

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("one", 1);
        m.put("two", 2);
        m.put("three", 3);
        for (Map.Entry<String, Integer> e : m.entrySet()) {
            System.out.println(e.getKey() + "=" + e.getValue());
        }
    }
}

Ringkasan Jalur get()

Pencarian mengikuti langkah-langkah berikut:

Hitung hashCode() dan sebarkan bitnya.
Terapkan masker untuk menemukan indeks keranjang.
Telusuri keranjang sambil membandingkan kunci dengan equals().
Kembalikan nilai yang cocok atau nilai kosong.

hashCode yang baik dan equals yang benar membuat setiap langkah tetap cepat.

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

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> stock = new HashMap<>();
        stock.put("apple", 50);
        stock.put("pear", 20);
        String key = "apple";
        Integer qty = stock.get(key);
        System.out.println(key + " -> " + qty);
    }
}

Pemeriksaan Singkat

Uji pemahaman Anda tentang cara HashMap menemukan keranjang.

Rangkuman

Anda telah mempelajari cara kerja HashMap secara internal:

Kunci di-hash dan dipetakan ke keranjang.
Tabrakan ditangani dengan merangkai entri dalam sebuah keranjang.
Faktor muatan (0.75) memicu penggandaan ukuran dan penghashan ulang.
Penentuan ukuran awal mencegah perubahan ukuran yang mahal, dan urutan iterasi tidak dijamin.

Berikutnya, Anda akan melihat mengapa hashCode saja tidak cukup tanpa equals yang benar.

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

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>(64);
        m.put("recap", 1);
        System.out.println("HashMap basics complete: " + m.get("recap"));
    }
}

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Cara Kerja HashMap” gratis?

Ya — teks lengkap “Cara Kerja HashMap” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Java Academy, upgrade ke CoddyKit PRO. Kursus Java Academy mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Cara Kerja HashMap”?

Bucket, hashing, dan collision. Kamu berlatih Java Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai Java Academy?

Tidak diperlukan pengalaman sebelumnya. Java Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 1 dari 4.

Berapa lama pelajaran “Cara Kerja HashMap” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran Java Academy ini?

Ya. Setiap pelajaran Java Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

← Kembali ke Java Academy