Bagaimana untuk menyelesaikan masalah konflik hash dengan HashMap di Java

1. Algoritma Hash dan jadual Hash

Untuk memahami konflik Hash, fahami dahulu algoritma Hash dan jadual Hash

• Algoritma cincang ialah Tukar input daripada sebarang panjang kepada output panjang tetap melalui algoritma cincang Hasil output ialah nilai cincang

• Jadual cincang juga dipanggil "jadual cincang". dijana secara langsung oleh kunci Untuk mengakses struktur data lokasi storan memori, dalam pelaksanaan khusus, kami menggunakan fungsi Hash untuk memetakan kunci ke lokasi tertentu dalam jadual untuk mendapatkan data di lokasi ini, dengan itu mempercepatkan. carian data

2. Konflik cincang

Konflik cincang disebabkan oleh algoritma cincangan adalah tidak terhingga dan julat hasil pengiraan adalah terhad akan sentiasa berbeza data. Selepas pengiraan, nilai yang diperoleh adalah sama, maka dalam kes ini akan berlaku konflik hash

3. Terdapat empat kaedah untuk menyelesaikan konflik Hash

Kaedah pengalamatan terbuka juga dipanggil kaedah pengesanan linear Ia bermula dari kedudukan di mana konflik berlaku, mencari kedudukan bebas daripada jadual Hash dalam susunan tertentu, dan kemudian menyimpan elemen bercanggah ke dalam kedudukan ini , ThreadLocal menggunakan kaedah pengesanan linear untuk menyelesaikan konflik Hash

Seperti yang ditunjukkan dalam rajah, key=name disimpan pada indeks 1 jadual Hash, dan apabila key=hobby adalah ditambah padanya, dengan mengandaikan bahawa indeks yang dikira juga adalah 1, maka ini berlaku konflik Hash, dan kaedah pengalamatan terbuka terbuka adalah untuk mencari lokasi percuma untuk menyimpan kunci bercanggah

kaedah pengalamatan rantai kaedah biasa. Pemahaman mudah ialah meletakkan Kunci dengan konflik Hash disimpan dalam senarai terpaut sehala, seperti HashMap

Seperti yang ditunjukkan dalam rajah, kunci bercanggah adalah disimpan terus dalam senarai terpaut sehala

Kaedah Hash adalah untuk mengira kunci melalui fungsi Hash tertentu Apabila terdapat konflik, fungsi Hash lain boleh digunakan untuk mencincang kunci, dan operasi akan menjadi diteruskan sehingga tiada lagi konflik berlaku. Kaedah ini akan meningkatkan masa pengiraan, akan ada sedikit kesan ke atas prestasi

Untuk mewujudkan kawasan penyingkiran awam adalah untuk membahagikan jadual Hash kepada dua bahagian: jadual asas dan. jadual manfaat. Semua elemen yang bercanggah akan diletakkan dalam jadual manfaat

4 Pengoptimuman HashMap dalam versi JDK1.8

HashMap dalam versi JDK1.8 menyelesaikan masalah konflik Hash melalui rantaian. kaedah pengalamatan dan pokok merah-hitam Antaranya, merah-hitam Pokok ini adalah untuk mengoptimumkan masalah peningkatan kerumitan masa yang disebabkan oleh senarai terpaut panjang jadual Hash Apabila panjang senarai terpaut lebih besar daripada atau sama dengan 8 dan kapasiti jadual Hash adalah lebih besar daripada 64, menambahkan elemen pada senarai terpaut akan mencetuskan senarai terpaut kepada pokok merah-hitam

Atas ialah kandungan terperinci Bagaimana untuk menyelesaikan masalah konflik hash dengan HashMap di Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!