HashMap adalah implementasi antarmuka peta berdasarkan tabel hash, menyediakan semua operasi pemetaan opsional, dan memungkinkan nilai nol dan konstruksi nol, dari sinkronisasi dan tidak ada jaminan pesanan pemetaan. Mari kita catat prinsip implementasi hashmap.
Penyimpanan internal hashmap
Dalam HashMap, semua hubungan pasangan-nilai kunci disimpan dengan mempertahankan array tabel variabel instan (juga dikenal sebagai ember). Bucket adalah array objek masuk. Ukuran ember dapat diubah ukurannya sesuai kebutuhan, dan panjangnya harus menjadi kekuatan 2. Kode berikut:
/ *** Array entri kosong, nilai default dari entri akhir ember*/ statis <?,?> [] Kosong_table = {}; / *** bucket, mengubah ukuran sesuai kebutuhan, tetapi harus berupa kekuatan 2*/ entri transien <k, v> [] tabel = (entri <k, v> []) kosong_table;Kapasitas awal dan faktor beban
HashMap memiliki dua parameter yang mempengaruhi kinerja, kapasitas awal dan faktor beban. Kapasitas adalah jumlah ember dalam tabel hash, kapasitas awal hanya kapasitas tabel hash saat dibuat, dan faktor beban adalah skala di mana tabel hash dapat mencapai seberapa penuh sebelum kapasitasnya secara otomatis meningkat. Ketika jumlah entri dalam tabel hash melebihi produk dari faktor beban dan kapasitas saat ini, tabel hash harus diulangi (mis., Membangun kembali struktur data internal), dan rekonstruksi dibuat pada dua kali jumlah kapasitas saat ini. Kapasitas awal dan faktor beban dapat diatur melalui konstruktor. Kapasitas awal default adalah 16 entri, kapasitas maksimum adalah 2^30 entri, dan faktor beban default adalah 0,75
Bucket seperti ember yang menyimpan air. Kapasitas penyimpanan awal defaultnya adalah 16 unit air. Ketika air dituangkan ke 16*0,75, kapasitas akan diperluas terlebih dahulu menjadi 32 unit ketika data ditambahkan di waktu berikutnya. 0.75 adalah faktor beban, dan kapasitas awal dan faktor beban dapat diatur saat membuat ember. Kapasitas maksimum ember adalah 2 unit air dengan daya 30. Ketika jumlah pengaturan kapasitas awal lebih besar dari kapasitas maksimum, kapasitas maksimum akan berlaku. Saat berkembang, itu akan dikembalikan secara langsung jika lebih besar dari atau sama dengan kapasitas maksimum.
Berikut ini adalah bagian dari kode sumber HashMap, yang mendefinisikan kapasitas awal default, faktor beban dan beberapa konstanta lainnya:
/ ** * Kapasitas awal default harus menjadi kekuatan 2. */ static final int default_initial_capacity = 1 << 4; // alias 16/ *** Kapasitas maksimum, jika kapasitas awal lebih besar dari kapasitas maksimum melalui parameter konstruktor, kapasitas juga akan digunakan sebagai kapasitas awal* harus menjadi kekuatan 2 dan kurang dari atau sama dengan daya ke -30 dari 2*/ statis int int maksimum_capacity = 1 << 30; / *** Faktor beban default dapat ditentukan oleh konstruktor*/ statis float float default_load_factor = 0.75f; / *** Tabel array kosong, ketika ember tidak diinisialisasi*/ entri akhir statis <?,?> [] Empleme_table = {}; / *** bucket, menyimpan semua entri pasangan nilai kunci, dan dapat diubah ukurannya sesuai kebutuhan, dan panjangnya harus menjadi kekuatan 2*/ entri transien <k, v> [] tabel = (entri <k, v> []) kosong_table; /*** Jumlah pasangan nilai kunci di peta, ukurannya akan +1 atau -1 operasi setiap kali ditambahkan atau dihapus. */ ukuran int transien; /** * Nilai kritis nilai beban, yang perlu diubah ukurannya adalah: (kapasitas * faktor beban). Setelah masing -masing mengubah ukuran, kapasitas baru akan dihitung menggunakan kapasitas baru. * @serial */ // Jika tabel == kosong_table maka ini adalah kapasitas awal di mana tabel // akan dibuat saat meningkat. ambang batas int; / ** * Faktor beban, jika tidak ditentukan dalam konstruktor, faktor beban default digunakan, * * @serial */ final float loadfactor; /** * Jumlah kali modifikasi struktur hashmap, ubah jumlah peta dalam hashmap atau memodifikasi struktur internalnya ketika struktur dimodifikasi (misalnya, metode * rehash, membangun kembali struktur data internal). Bidang ini digunakan dalam * iterator yang dihasilkan pada tampilan koleksi hashmap diproses menjadi cepat */transient int modcount;Kapasitas Awal dan Penyesuaian Kinerja Faktor Beban
Biasanya, faktor beban default (0,75) mencari kompromi dalam biaya waktu dan ruang. Meskipun faktor beban terlalu tinggi, ia juga meningkatkan biaya kueri (ini tercermin di sebagian besar operasi hashmap, termasuk operasi GET dan pasang). Saat mengatur kapasitas awal, jumlah entri yang diperlukan dalam peta dan faktor bebannya harus diperhitungkan untuk meminimalkan jumlah operasi pengulangan. Jika kapasitas awal lebih besar dari jumlah maksimum entri yang dibagi dengan faktor beban, operasi pengulangan tidak akan terjadi.
Jika banyak hubungan pemetaan harus disimpan dalam instance hashmap, membuatnya dengan kapasitas awal yang cukup besar akan membuat hubungan pemetaan lebih efisien disimpan relatif untuk melakukan operasi pengulangan otomatis atas permintaan untuk meningkatkan kapasitas tabel.
Berikut ini adalah kode untuk membangun kembali struktur data hashmap:
void mengubah ukuran (int newcapacity) {entri [] oldtable = tabel; int oldcapacity = oldtable.length; if (oldcapacity == maximum_capacity) {// Jika kapasitas telah mencapai batas maksimum, lalu atur nilai beban dan kembali langsung ke threshold = integer.max_value; kembali; } // Buat tabel baru untuk menyimpan entri data [] newtable = entri baru [newcapacity]; // Transfer data dari tabel lama ke tabel baru, langkah ini akan membutuhkan banyak waktu untuk mentransfer (newtable, inithashseedasneed (newcapacity)); tabel = newtable; // Akhirnya atur nilai beban threshold = (int) math.min (newcapacity * loadFactor, maksimum_capacity + 1);}Metode Konstruksi Hashmap
Metode konstruksi keempat adalah membuat hashmap baru dengan peta yang ada. Mari kita bicarakan nanti. Bahkan, tiga metode konstruksi pertama disebut dalam metode ketiga akhir dengan dua parameter. Jika tidak ada parameter yang dilewati, nilai default digunakan. Kodenya adalah sebagai berikut:
/** * Membangun <tt> hashmap </tt> kosong dengan kapasitas awal default * (16) dan faktor beban default (0,75). */ public hashMap () {this (default_initial_capacity, default_load_factor); } /** * 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); } /** * Membangun <tt> hashmap </tt> kosong dengan kapasitas awal * yang ditentukan dan faktor beban. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */ public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity); if (initialcapacity> maximum_capacity) initialcapacity = maximum_capacity; if (loadfactor <= 0 || float.isnan (loadfactor)) melempar baru ilegalargumentException ("faktor beban ilegal:" +loadfactor); this.loadFactor = loadFactor; threshold = InitialCapacity; init (); }Seperti dapat dilihat dari yang di atas, dalam konstruktor, jika kapasitas awal lebih besar dari kapasitas maksimum, kapasitas maksimum akan diganti secara langsung.
Letakkan metode
Selanjutnya, mari kita lihat bagian hashmap yang lebih penting
/*** Dalam peta ini, nilai yang ditentukan dan build yang ditentukan terkait. Jika peta sebelumnya berisi hubungan pemetaan kunci, nilai lama diganti** @param menentukan kunci yang akan dikaitkan* @param menentukan nilai yang akan dikaitkan* @return nilai lama yang terkait dengan kunci, jika kunci tidak memiliki hubungan pemetaan, public null (returning null mungkin berarti bahwa pemetaan dikaitkan dengan kunci sebelumnya)*/ public null (returning null mungkin berarti bahwa pemetaan dikaitkan dengan kunci sebelumnya)*/ public null (return null mungkin berarti bahwa pemetaan dikaitkan dengan kunci sebelumnya)*/ public null (return null mungkin berarti bahwa pemetaan dikaitkan dengan kunci sebelumnya)*/ public null (return null mungkin berarti bahwa pemetaan dikaitkan dengan kunci sebelumnya)*/ public null (return null mungkin berarti bahwa pemetaan dikaitkan dengan kunci sebelum)* inflatetable (ambang); } if (key == null) return putfornullKey (value); int hash = hash (kunci); int i = indexfor (hash, table.length); untuk (entri <k, v> e = tabel [i]; e! = null; e = e.next) {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 ++; addentry (hash, kunci, nilai, i); kembali nol; }1. Pertama, dalam metode put, pertama -tama tentukan apakah ember dalam keadaan tidak diinisialisasi default. Jika tidak diinisialisasi, hubungi metode inflatetable untuk menginisialisasi, dan kemudian tentukan apakah tombol parameter adalah nol. Jika nol, hubungi Putfornullkey khusus untuk menempatkan data dengan kunci sebagai nol. Metode Putfornullkey sebenarnya sama dengan langkah 3 berikut, kecuali bahwa lokasi penyimpanan default data dengan kunci sebagai nol adalah yang pertama, yaitu, subskrip default adalah 0.
2. Jika kunci tidak nol, panggil metode hash () untuk mendapatkan nilai hash kunci. Anda dapat menghitung posisi di mana kunci dapat ditempatkan di ember berdasarkan nilai hash dan panjang ember.
3. Ada atribut berikutnya di objek entri, yang dapat membentuk daftar tertaut satu arah untuk menyimpan elemen dengan nilai hash yang sama. Oleh karena itu, ketika nilai hash dari kunci dihitung, lokasi penyimpanan juga akan diulang. Cukup menilai apakah elemen lokasi penyimpanan dan daftar atribut elemen berikutnya persis sama dengan nilai hash dari kunci dan kunci yang diberikan. Jika ada yang sepenuhnya konsisten, itu berarti sudah ada, ganti nilai lama dan mengembalikan nilai lama secara langsung sebagai nilai pengembalian.
4. Tingkatkan jumlah modifikasi struktural dengan 1
5. Panggil metode AddEntry untuk menambahkan pasangan nilai kunci baru ke hashmap. Metode addentitas pertama -tama menentukan apakah data masuk saat ini lebih besar dari atau sama dengan nilai beban (kapasitas faktor beban ember *) dan posisi yang ditentukan dari ember tidak nol. Jika sudah lebih besar dari dan posisi yang ditentukan bukan nol, kapasitas ember penyesuaian adalah dua kali kapasitas saat ini. Kapasitas ember penyesuaian dirujuk ke Direktori Penyesuaian Kinerja Kapasitas dan Faktor Beban di atas. Hitung ulang nilai hash dan hitung lokasi penyimpanan. Hubungi metode CreateEntry untuk menyimpannya di ember
void addEntry (int hash, K key, nilai v, int bucketIndex) {if ((size> = threshold) && (null! = Table [bucketIndex])) {ubah ukuran (2 * table.length); hash = (null! = key)? hash (kunci): 0; bucketIndex = indexfor (hash, table.length); } createEntry (hash, kunci, nilai, bucketindex); } void createEntry (int hash, K key, v nilai, int bucketIndex) {entri <k, v> e = tabel [bucketIndex]; tabel [bucketIndex] = entri baru <> (hash, kunci, nilai, e); ukuran ++; } /*** Metode konstruktor entri untuk membuat entri baru. */ Entri (int h, k k, v v, entri <k, v> n) {value = v; Berikutnya = n; kunci = k; hash = h; }6. Dalam metode CreateEntry, pertama -tama dapatkan entri di lokasi yang ditentukan, dan kemudian hasilkan entri baru. Saat menghasilkan entri, simpan entri asli di properti berikutnya dari entri yang baru dihasilkan (lihat metode konstruksi entri), dan ganti entri di lokasi yang ditentukan dengan yang baru dihasilkan.
Karena ketika menambahkan entri baru, nilai hash perlu dihitung, dan ketika panjangnya tidak cukup, panjangnya perlu disesuaikan. Ketika ada elemen di lokasi penyimpanan yang dihitung, daftar yang ditautkan perlu disimpan, sehingga efisiensi menggunakan hashmap untuk menambahkan operasi baru tidak terlalu tinggi.
Dapatkan metode
Pertama, mari kita lihat kode sumber metode GET:
/*** Mengembalikan nilai yang dipetakan oleh kunci yang ditentukan; Jika peta ini tidak mengandung hubungan pemetaan apa pun untuk kunci ini, ia mengembalikan nol * mengembalikan nilai nol tidak selalu berarti bahwa peta tidak berisi pemetaan kunci, dan juga dapat mengubah pemetaan menjadi nol. Anda dapat menggunakan operasi ContainsKey untuk membedakan antara dua situasi ini * @See #put (objek, objek) */ public v get (tombol objek) {if (key == null) return getFornullKey (); Entri <k, v> entri = getEntry (key); return null == entri? null: entry.getValue (); } entri akhir <k, v> getEntry (tombol objek) {if (size == 0) {return null; } int hash = (key == null)? 0: hash (kunci); untuk (entri <k, v> e = tabel [indexfor (hash, table.length)]; e! = null; e = e.next) {objek k; if (e.hash == hash && ((k = e.key) == key || (key! = null && key.equals (k)))) return e; } return null;}Metode GET mudah diimplementasikan, dan berikut ini adalah beberapa langkah:
Dengan melihat kode sumber GET, kita dapat menemukan bahwa metode GET menghitung lokasi penyimpanan melalui nilai hash kunci dan panjang ember. Pada dasarnya, Anda dapat menemukan elemen yang Anda cari. Bahkan jika Anda melintasi beberapa kunci dengan nilai hash berulang, itu sangat cepat. Karena nilai hash relatif unik, hashmap sangat cepat untuk mencari.
Objek khusus sebagai kunci untuk hashmap
Pengguna kelas {// ID nomor terlindungi int iDnumber; pengguna publik (int id) {idNumber = id; }} public class testuser {public static void main (string [] args) {peta <user, string> peta = new HashMap <user, string> (); untuk (int i = 0; i <5; i ++) {map.put (pengguna baru (i), "Nama:"+i); } System.out.println ("Nama User3:" + Map.get (pengguna baru (3))); }} Output: User3 Nama: NULLSeperti disebutkan di atas, saat menggunakan instance kelas pengguna khusus sebagai objek hashmap, nama User3 tidak dapat ditemukan saat mencetak, karena kelas pengguna secara otomatis mewarisi objek kelas dasar, sehingga metode kode hashcode akan secara otomatis digunakan untuk menghasilkan nilai hash, dan menggunakan alamat objek untuk menghitung nilai hash secara default. Oleh karena itu, nilai hash dari instance pertama yang dihasilkan oleh pengguna baru (3) berbeda dari nilai hash dari instance kedua yang dihasilkan. Namun, jika Anda hanya hanya perlu mengganti metode kode hash, itu tidak akan berfungsi dengan baik, kecuali jika Anda mengganti metode yang sama pada saat yang sama, itu juga merupakan bagian dari objek. HashMap menggunakan Equals () untuk menentukan apakah kunci saat ini sama dengan kunci yang ada dalam tabel. Anda dapat merujuk pada metode GET atau Letakkan di atas.
Metode Equals () yang benar harus memenuhi 5 Ketentuan berikut: --- Lihat "Pikiran Pemrograman Java" -Halaman 489
Sekali lagi : objek default.Equals () hanyalah alamat objek perbandingan, jadi satu pengguna baru (3) tidak sama dengan pengguna baru lainnya (3). Oleh karena itu, jika Anda ingin menggunakan kelas Anda sendiri sebagai kunci untuk hashmap, Anda harus kelebihan beban kedua hashcode () dan equals ().
Kode berikut berfungsi secara normal:
Pengguna kelas {// ID nomor terlindungi int iDnumber; pengguna publik (int id) {idNumber = id; } @Override public int hashCode () {return IDNumber; } @Override public boolean sama (objek obj) {return obj instance dari pengguna && (idNumber == ((pengguna) obj) .idnumber); }} public class testuser {public static void main (string [] args) {peta <user, string> peta = new HashMap <user, string> (); untuk (int i = 0; i <5; i ++) {map.put (pengguna baru (i), "Nama:"+i); } System.out.println ("Nama User3:" + Map.get (pengguna baru (3))); }} Output: nama user3: Nama: 3Di atas hanya mengembalikan iDnumber sebagai satu -satunya diskriminasi dalam kode hashc, dan pengguna juga dapat mengimplementasikan metode mereka sendiri sesuai dengan bisnis mereka sendiri. Dalam metode Equals, instanceof akan diam -diam memeriksa apakah objeknya nol. Jika parameter di sebelah kiri instanceof adalah nol, false akan dikembalikan. Jika parameter Equals () tidak nol dan jenisnya benar, perbandingan akan didasarkan pada nomor iDnumber aktual di setiap objek. Seperti yang dapat dilihat dari output, metode saat ini benar.
Lihat:
"Pikiran Pemrograman Java"
JDK 1.6 Manual Bantuan Cina
Di atas adalah semua konten artikel ini. Saya berharap konten artikel ini akan membantu untuk belajar atau bekerja semua orang. Saya juga berharap untuk mendukung wulin.com lebih lanjut!