Java Academy · Pelajaran

Cara HashMap Berfungsi

Baldi, pencincangan dan perlanggaran

Pelajaran 1 daripada 413 langkah

Cara HashMap Berfungsi ialah pelajaran Java Academy percuma di CoddyKit. Ini ialah pelajaran 1 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Java Academy, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Java Academy merangkumi sejumlah 4 pelajaran.

Perkara yang Disimpan oleh HashMap

HashMap menyimpan pasangan kunci-nilai dan memberikan pencarian, penyisipan serta pengalihan pada purata O(1).

Secara dalaman, ia menyimpan tatasusunan yang dipanggil jadual. Setiap slot dalam tatasusunan ini dipanggil bakul.

Kunci menentukan bakul tempat sesuatu entri diletakkan.
Nilai ialah perkara yang anda dapat semula apabila mencari kunci.

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"));
    }
}

Mencincang Kunci

Apabila anda memanggil put(key, value), peta memanggil key.hashCode() untuk mendapatkan int.

HashMap kemudian menyebarkan bit tersebut dengan fungsi dalaman supaya kod cincangan yang lemah sekalipun tersebar merentasi bakul.

Nombor akhir dikurangkan dengan hash & (table.length - 1) untuk mendapatkan indeks bakul.
Panjang jadual sentiasa kuasa dua, jadi topeng ini 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);
    }
}

Bakul dalam Tindakan

Setiap bakul boleh menyimpan lebih daripada satu entri. Apabila dua kunci dipetakan ke bakul yang sama, keadaan itu dipanggil perlanggaran.

Perlanggaran adalah perkara biasa dan dijangka. HashMap mengendalikannya dengan merantaikan entri bersama-sama dalam bakul.

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");
    }
}

Perlanggaran dan Rantaian

Sebelum Java 8, semua entri yang berlanggar berada dalam senarai berantai tunggal di dalam bakul.

Pencarian menyusuri senarai sambil memanggil equals() sehingga menemui kunci yang sepadan.

Beberapa perlanggaran: masih pada asasnya O(1).
Banyak perlanggaran dalam satu bakul: prestasi merosot menghampiri O(n) untuk bakul itu.

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 Bertembung

Rentetan "FB" dan "Ea" mempunyai hashCode() yang sama dalam Java. Ini ialah contoh perlanggaran klasik.

Walaupun kod cincangan sama, peta masih menyimpannya secara berasingan kerana equals() membezakan kedua-duanya dalam bakul.

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 mengawal sejauh mana jadual boleh dipenuhi sebelum jadual itu berkembang. Nilai lalai ialah 0.75.

Kapasiti 16 dan faktor muatan 0.75 bermaksud saiz semula dicetuskan pada 12 entri.
Faktor muatan yang lebih rendah membazirkan memori tetapi mengurangkan perlanggaran.
Faktor muatan yang lebih tinggi menjimatkan memori tetapi meningkatkan perlanggaran.

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 Saiz Jadual

Apabila bilangan entri melebihi capacity * loadFactor, saiz jadual digandakan.

Setiap entri sedia ada dicincang semula ke dalam jadual baharu yang lebih besar. Ini ialah operasi yang mahal, jadi penetapan saiz awal penting untuk peta yang 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 Saiz Awal untuk Prestasi

Jika anda tahu lebih kurang berapa banyak entri yang akan disimpan, berikan kapasiti awal untuk mengelakkan saiz semula berulang.

Peraturan umum: kapasiti 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 membenarkan satu kunci kosong dan berbilang nilai kosong.

Kunci kosong sentiasa pergi ke bakul 0 (cincangannya dianggap 0).
Gunakan getOrDefault untuk mengelakkan kekeliruan antara kunci yang tiada dengan 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 Lelaran Tidak Dijamin

HashMap tidak memberikan sebarang jaminan tentang urutan lelaran. Urutan bergantung pada kod cincangan dan susun atur bakul.

Jika anda memerlukan urutan yang boleh dijangka, gunakan LinkedHashMap (urutan penyisipan) atau TreeMap (urutan terisih).

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 Laluan get()

Carian mengikuti langkah-langkah berikut:

Kira hashCode() dan sebarkan bitnya.
Gunakan topeng untuk mencari indeks baket.
Telusuri baket sambil membandingkan kunci dengan equals().
Pulangkan nilai yang sepadan atau null.

hashCode yang baik bersama equals yang betul memastikan setiap langkah berjalan pantas.

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);
    }
}

Semakan Pantas

Uji pemahaman Anda tentang cara HashMap mencari baket.

Jawab dalam pelajaran interaktif

Rumusan

Anda telah mempelajari cara HashMap berfungsi secara dalaman:

Kunci dicincang dan dipetakan kepada baket.
Perlanggaran dikendalikan dengan memautkan entri dalam baket.
Faktor muatan (0.75) mencetuskan penggandaan saiz dan pencincangan semula.
Menetapkan saiz awal mengelakkan perubahan saiz yang mahal, dan susunan lelaran tidak dijamin.

Seterusnya, kita akan melihat mengapa hashCode sahaja tidak mencukupi tanpa equals yang betul.

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"));
    }
}

Percuma untuk bermula

Pelajari Java dengan tutor kecerdasan buatan — percuma

Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.

Kursus: 104
Pelajaran: 374

Mula belajar secara percuma Lihat kursus penuh

Soalan Lazim

Adakah pelajaran “Cara HashMap Berfungsi” percuma?

Ya — teks penuh “Cara HashMap Berfungsi” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Java Academy, tingkat taraf kepada CoddyKit PRO. Kursus Java Academy merangkumi sejumlah 4 pelajaran.

Apakah yang akan saya pelajari dalam “Cara HashMap Berfungsi”?

Baldi, pencincangan dan perlanggaran Anda berlatih Java Academy menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.

Adakah saya memerlukan pengalaman untuk memulakan Java Academy?

Tiada pengalaman terdahulu diperlukan. Pembelajaran Java Academy di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 1 daripada 4.

Berapa lamakah pelajaran “Cara HashMap Berfungsi” diambil?

Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.

Bolehkah saya menulis dan menjalankan kod dalam pelajaran Java Academy ini?

Ya. Setiap pelajaran Java Academy menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.

Semua pelajaran dalam kursus ini

← Kembali ke Java Academy