HashMap: bilik rahsia, sihir dan perlanggaran

Mari bayangkan HashMap sebagai istana dengan bilik rahsia (baldi), di mana setiap bilik didahului oleh pintu ajaib - fungsi hash. Bagaimanakah mekanisme ajaib ini berfungsi dan apa yang berlaku apabila dua entiti ajaib bertembung di tempat yang sama? Mari selami dunia rahsia HashMap. Mula-mula, mari kita lihat kandungan HashMap.

Komponen Asas HashMap

tatasusunan jadual: Tatasusunan ini ialah storan data utama. Setiap sel tatasusunan (atau baldi) mengandungi indeks unik, di mana rantaian nilai atau pun pokok binari dalam kes sejumlah besar elemen boleh disimpan.

LoadFactor: LoadFactor menentukan jumlah HashMap boleh diisi sebelum mengembangkannya. Faktor beban lalai ialah 0.75, yang mencapai keseimbangan antara penjimatan memori dan kelajuan akses. Apabila HashMap 75% penuh, ia menggandakan saiz jadual dan mengagihkan semula elemen untuk mengekalkan kecekapan.

Ambang: Ambang ialah titik di mana HashMap memutuskan untuk mengembangkan jadual. Dikira sebagai(kapasiti * loadFactor). Sebagai contoh, jika kapasiti ialah 16 dan loadFactor ialah 0.75, maka ambang akan menjadi 12. Apabila HashMap mencapai 12 elemen, ia meningkatkan saiznya.

Saiz menjejaki bilangan semasa pasangan nilai kunci dalam HashMap.

Setiap pasangan nilai kunci dalam HashMap disimpan dalam struktur yang dipanggil Nod yang mengandungi:

kunci - kunci pasangan,
nilai—nilai pasangan,
hash - cincang dikira berdasarkan kunci hashCode(),
seterusnya - pautan ke elemen seterusnya dalam rantai sekiranya berlaku perlanggaran.

static class Node<K, V> implements Map.Entry<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;

    Node(int hash, K key, V value, Node<K, V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    ....
}

Setiap Nod disambungkan ke nod seterusnya dalam baldi yang sama apabila berlanggar, mencipta senarai terpaut. Senarai ini secara automatik bertukar menjadi pokok binari yang seimbang jika lebih daripada lapan elemen terkumpul dalam baldi.

Fungsi Hash: Cara Kunci Mencari Bilik Mereka

Bayangkan HashMap ialah sebuah istana yang besar dengan banyak bilik. Setiap bilik mempunyai nombor unik, tetapi bagaimanakah kunci menentukan bilik yang hendak dituju? Ini ialah tugas fungsi cincang, alat ajaib yang membantu menentukan baldi (bilik) kunci tertentu akan diletakkan.

Apabila kami menambah kunci, kaedah putVal memanggil kaedah hashCode() kunci untuk mencipta cincang, yang kemudiannya diperhalusi untuk diedarkan secara sama rata ke seluruh baldi.
Pengiraan Indeks: Menggunakan formula int index = hashCode & (panjang- 1) , HashMap mengira indeks yang menghala ke baldi dalam tatasusunan jadual.

Di sini kod cincang ialah kod unik yang diterima oleh kunci melalui fungsi cincang. Kami kemudian melakukan operasi AND bitwise pada panjang - 1. Ini bersamaan dengan mengira baki kod cincang dibahagikan dengan bilangan baldi, dan dengan itu kami menentukan indeks dalam tatasusunan baldi.

import java.util.HashMap;

public class MagicalHashMap {
    public static void main(String[] args) {
        // Создаем новый HashMap
        HashMap<String, String> rooms = new HashMap<>();

        // Добавляем элементы в HashMap
        rooms.put("apple", "A room full of apples");
        rooms.put("banana", "A room full of bananas");

        // Поиск по ключу
        System.out.println("Room for 'apple': " + rooms.get("apple"));
        System.out.println("Room for 'banana': " + rooms.get("banana"));
    }
}

Akibatnya, setiap kunci melalui fungsi cincang dan berakhir di bilik uniknya sendiri, yang indeksnya dikira menggunakan bitwise DAN.

Semakan perlanggaran: Jika baldi kosong, pasangan nilai kunci baharu ditambah. Jika tidak, putVal menyemak sama ada kunci sepadan:

Padanan *—nilai dikemas kini.
*Tidak sepadan - konflik timbul - lebih lanjut tentang mereka.

Perlanggaran: Bilik rahsia yang terbuka antara satu sama lain

Apakah yang berlaku jika dua kunci berakhir di dalam bilik yang sama (beberapa kunci membawa kepada satu baldi)? Dalam HashMap ini dipanggil perlanggaran. Ini adalah apabila dua kekunci mempunyai kod cincang yang sama dan cuba masuk ke baldi yang sama. Bilakah ini boleh dilakukan? Contohnya, kami tersilap mengganti kod cincang.

static class Node<K, V> implements Map.Entry<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;

    Node(int hash, K key, V value, Node<K, V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    ....
}

Dalam contoh ini, kelas KeyWithSameHash mempunyai kaedah hashCode() yang ditindih yang mengembalikan nilai yang sama untuk semua keadaan, menyebabkan semua kunci berakhir dalam sel yang sama tatasusunan jadual:

import java.util.HashMap;

public class MagicalHashMap {
    public static void main(String[] args) {
        // Создаем новый HashMap
        HashMap<String, String> rooms = new HashMap<>();

        // Добавляем элементы в HashMap
        rooms.put("apple", "A room full of apples");
        rooms.put("banana", "A room full of bananas");

        // Поиск по ключу
        System.out.println("Room for 'apple': " + rooms.get("apple"));
        System.out.println("Room for 'banana': " + rooms.get("banana"));
    }
}

Untuk semua kunci, nilai hashCode() ialah 42, jadi setiap kali kunci ditambahkan, indeks baldi dalam jadual akan sama.

Tetapi bukannya terhantuk kepala, kunci membuka pintu tambahan, menjadikan bilik itu koridor ajaib yang menuju ke bilik baharu. Bilik baharu ini pada asasnya ialah cara untuk menyelesaikan perlanggaran.

Senarai Terpaut: Apabila dua kekunci dengan kod cincang yang sama berakhir dalam baldi yang sama, HashMap mencipta senarai terpaut dalam baldi itu. Kekunci terus disimpan dalam senarai ini dan jika perlu, semakan dibuat menggunakan kaedah equals() untuk memastikan kekunci itu memang sama.

Pokok merah-hitam: Apabila bilangan perlanggaran dalam satu baldi menjadi terlalu tinggi (koridor menjadi terlalu panjang), HashMap menukarnya kepada pokok merah-hitam. Ini membantu mempercepatkan carian dan mengelakkan kelembapan di bawah beban berat.

Cara equals() dan hashCode() berfungsi

Untuk sihir HashMap berfungsi dengan betul, adalah penting bahawa dua kekunci yang sama dengan nilai yang sama mengembalikan kod cincang yang sama, dan juga dibandingkan dengan betul menggunakan kaedah equals(). Ia seperti ejaan yang memeriksa sama ada dua objek adalah sama, walaupun ia mungkin diwakili dalam cara yang berbeza.

hashCode(): Setiap objek mesti mempunyai kod cincang uniknya sendiri. Ini membolehkan HashMap mencari baldi tempat kunci perlu diletakkan dengan cekap.
equals(): Jika dua objek mempunyai kod cincang yang sama, kaedah equals() menyemak untuk melihat sama ada objek itu sebenarnya sama.
Jika semakan ini tidak ada, HashMap boleh mengelirukan dua kekunci berbeza, yang akan membawa kepada tingkah laku program yang salah.

Kesimpulan

Dunia HashMap ialah dunia keajaiban di mana fungsi cincang dan perlanggaran membantu kunci mencari bilik mereka dan memastikan istana itu teratur. Setiap kunci mempunyai laluan sendiri yang membawa kepada indeks yang unik, terima kasih kepada fungsi cincang. Dan apabila dua kekunci bertembung dalam baldi yang sama, keajaiban itu terus berfungsi, membuka pintu baharu dalam bentuk senarai terpaut atau pokok merah-hitam untuk mencari jalan yang betul.

Jadi, terima kasih kepada hashCode(), equals() dan koridor perlanggaran ajaib, HashMap terus menjadi salah satu alatan paling berkuasa dalam senjata pembangun Java, menjamin kecekapan dan ketepatan walaupun dalam situasi yang paling mengelirukan.

Atas ialah kandungan terperinci HashMap: bilik rahsia, sihir dan perlanggaran. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!