―HashMapas
Keuntungan: Kecepatan kueri super cepat dan struktur data yang dapat mencapai O (1) kompleksitas waktu adalah hashmap. Data penyimpanan panjang variabel dinamis (relatif terhadap array).
Kerugian: Nilai hash perlu dihitung ekstra, dan jika tidak ditangani dengan benar, itu akan memakan ruang ekstra.
―Bagaimana menggunakan hashmap -
Biasanya kami menggunakan hashmap sebagai berikut
Peta <integer, string> peta = hashmap baru <integer, string> (); peta.put (1, "a"); peta.put (2, "b");
Kode di atas membuat hashmap baru dan memasukkan dua data. Jenis data dasar tidak diterima di sini untuk melakukan K dan V.
Jika Anda menulis ini, akan ada masalah:
Peta <int, double> peta = hashmap baru <int, double> ();
Mengapa kita menggunakan cara ini? Silakan lihat kode sumbernya:
HashMap kelas publik <K, V> memperluas abstrak abstrak <k, v> mengimplementasikan peta <k, v>, dapat dikloning, serializable
Ini adalah definisi kelas implementasi hashmap.
―HashMap adalah struktur data panjang yang dinamis-
Saat menggunakan hashmap, untuk meningkatkan efisiensi eksekusi, kami sering mengatur kapasitas inisialisasi hashmap:
Peta <String, String> RM = HashMap baru <String, String> (2)
Atau gunakan peta kelas alat Guava untuk dengan mudah membuat koleksi dan menginisialisasi nilai dengan ukuran yang sesuai.
Peta <String, Object> Map = Maps.NewHashMapWithExpectedSize (7);
Jadi mengapa menggunakannya seperti ini? Mari kita lihat konstruktor sumber mereka.
Konstruktor tanpa parameter:
hashmap publik () {this.loadFactor = default_load_factor; threshold = (int) (default_initial_capacity * default_load_factor); Table = entri baru [default_initial_capacity]; init (); } hashmap publik () {
this.loadFactor = default_load_factor;
threshold = (int) (default_initial_capacity * default_load_factor);
Table = entri baru [default_initial_capacity];
init ();
}
/** * Membangun <tt> hashMap </tt> kosong dengan kapasitas awal * yang ditentukan dan faktor beban default (0,75). * * @param inisial kapasitas kapasitas awal. * @Throws IllegalArgumentException Jika kapasitas awal negatif. */ hashmap publik (int initialcapacity) {this (initialcapacity, default_load_factor); }Penjelasan Kata benda:
Default_Load_factor // Faktor pemuatan default, 0,75 jika tidak ditentukan. Default_initial_capacity // Kapasitas inisialisasi default, default adalah 16 ambang batas // nilai ambang batas (YU) dihitung berdasarkan faktor beban dan kapasitas inisialisasi. <span style = "Color: RGB (54, 46, 43); font-family:" Microsoft Yahei ";"> ambang batas berarti bahwa ketika ukuran hashmap lebih besar dari ambang batas, operasi ubah ukuran akan dilakukan.
Jadi kita tahu bahwa jika kita memanggil konstruktor tanpa parameter, kita akan mendapatkan array 16 kapasitas.
Jadi pertanyaannya adalah: Bagaimana jika kapasitas awal tidak cukup?
Array adalah fixed-length, cara menggunakan data panjang tetap untuk mewakili data panjang yang tidak pasti? Jawabannya adalah menemukan yang lebih lama, tetapi mengurangi efisiensi saat mengubah ukuran. Jadi kami sarankan hashmap diberi kapasitas yang andal saat menginisialisasi.
―Hashmap Metode put -
public v put (key k, nilai v) {if (key == null) // Jika kunci kosong, perbedaan antara hashmap dan hashtable returns putfornullkey (value); int hash = hash (key.hashcode ()); // bingkai nilai hash berdasarkan kode hash dari kunci int i = indexfor (hash, tabel.length); // bingkai subskrip array untuk dimasukkan berdasarkan nilai hash untuk (entri <k, v> e = tabel [i]; e! = Null; e = e.next) {// Seluruh loop mengimplementasikan yang jika k ada, kemudian ganti objek k; if (e.hash == hash && ((k = e.key) == key || key.equals (k))) {v oldValue = E.Value; E.Value = nilai; E.RecordAccess (ini); Kembalikan OldValue; }} modcount ++; // counter addentry (hash, key, value, i); // Tambahkan ke array return null; }Jika data yang dimasukkan melebihi kapasitas yang ada, itu akan dijalankan
addentry (hash, kunci, nilai, i);
void addEntry (int hash, K key, nilai v, int bucketIndex) {entri <k, v> e = tabel [bucketIndex]; tabel [bucketIndex] = entri baru <k, v> (hash, kunci, nilai, e); if (size ++> = threshold) <span style = "color:#ff0000;"> <strong> ubah ukuran (2 * table.length);}Di sini, jika ukuran ++> ambang saat ini ditampilkan, maka ukuran saat ini akan diperluas dua kali dan mengubah ukuran (2*tabel.length) akan dieksekusi. Jadi bagaimana mereka berkembang?
void mengubah ukuran (int newcapacity) {entri [] oldtable = tabel; int oldcapacity = oldtable.length; if (oldcapacity == maximum_capacity) {threshold = integer.max_value; kembali; } Entri [] newtable = entri baru [newcapacity]; <span style = "warna: rgb (51, 51, 51); font-family: arial;"> baru array baru, </span> <strong> <span style = "color:#ff0000;"> transfer (newtable); </span> </strong> // transfer array ke tabel array baru = baru; threshold = (int) (newcapacity * loadFactor); // Hitung ulang kapasitas}Bagaimana transfer transfer transfer ditransfer?
void transfer (entri [] newtable) {entri [] src = tabel; int newcapacity = newtable.length; untuk (int j = 0; j <src.length; j ++) {entri <k, v> e = src [j]; if (e! = null) {src [j] = null; do {entri <k, v> next = e.next; int i = <strong> <span style = "color:#ff0000;"> indexfor (e.hash, newcapacity); // Hitung ulang indeks berdasarkan kapasitas nilai hash </span> </strong> e.next = newtable [i]; Newtable [i] = e; e = selanjutnya; } while (e! = null); }}}― Jumlah eksekusi tambahan ekspansi hashmap-
Jadi jika kita ingin menambahkan hashmap dari 1000 elemen, jika kita menggunakan nilai default, berapa banyak perhitungan tambahan yang perlu saya hitung?
Ketika lebih besar dari 16*0,75 = 12, itu perlu dihitung ulang 12 kali
Ketika lebih besar dari 16*2*0,75 = 24, diperlukan 24 perhitungan tambahan.
...
Ketika lebih besar dari 16*n*0,75 = 768, diperlukan 768 perhitungan tambahan.
Jadi kami menghitung 12+24+48+...+768 kali dalam proses ekspansi
Oleh karena itu, sangat disarankan agar kita secara manual menentukan ukuran awal jika kita tahu ruang lingkup dalam proyek seperti ini:
Peta <integer, string> peta = hashmap baru <integer, string> (1000);
Ringkasan: Inilah sebabnya mengapa efisiensi eksekusi hashmap sangat berkurang jika melebihi kapasitas awal selama penggunaan.
Di atas adalah semua tentang penggunaan hashmap dalam artikel ini tentang analisis kode sumber java, saya harap ini akan membantu semua orang. Teman yang tertarik dapat terus merujuk ke topik terkait lainnya di situs ini. Jika ada kekurangan, silakan tinggalkan pesan untuk menunjukkannya. Terima kasih teman atas dukungan Anda untuk situs ini!