Kami telah menganalisis dua set ArrayList dan LinkedList. Kami tahu bahwa ArrayList diimplementasikan berdasarkan array, dan LinkedList diimplementasikan berdasarkan daftar tertaut. Masing -masing memiliki kelebihan dan kekurangannya sendiri. Misalnya, ArrayList akan lebih baik daripada LinkedList saat memposisikan dan mencari elemen, sementara LinkedList akan lebih baik daripada ArrayList saat menambahkan dan menghapus elemen. Hashmap yang diperkenalkan dalam artikel ini menggabungkan keunggulan keduanya. Lapisan yang mendasarinya diimplementasikan berdasarkan tabel hash. Jika konflik hash tidak dipertimbangkan, kompleksitas waktu hashmap Selain itu, penghapusan, modifikasi, dan operasi pencarian dapat mencapai O (1) yang menakjubkan. Pertama -tama mari kita lihat struktur tabel hash yang menjadi dasarnya.
Seperti yang dapat dilihat dari gambar di atas, tabel hash adalah struktur yang terdiri dari array dan daftar yang ditautkan. Tentu saja, angka di atas adalah contoh yang buruk. Fungsi hash yang baik harus mencoba untuk rata -rata distribusi elemen dalam array, mengurangi konflik hash dan mengurangi panjang daftar yang ditautkan. Semakin lama panjang daftar yang ditautkan berarti bahwa semakin banyak node yang perlu dilalui selama pencarian, semakin buruk kinerja tabel hash. Selanjutnya, mari kita lihat beberapa variabel anggota hashmap.
//Default initial capacity static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;//Default maximum capacity static final int MAXIMUM_CAPACITY = 1 << 30;//Default loading factor refers to how much the hash table can reach static final float DEFAULT_LOAD_FACTOR = 0.75f;//Empty hash table static final Entry<?,?>[] EMPTY_TABLE = {};//The actual hash Entri transien tabel <k, v> [] tabel = (entri <k, v> []) kosong_table; // ukuran hashmap, yaitu, jumlah pasangan nilai kunci yang disimpan dalam hashmap ukuran int transien; // ambang batasan yang digunakan; untuk mekanisme gagal-cepat int int modcount; // gunakan ambang default hash alternatif alternatif final alternatif_hashing_threshold_default = integer.max_value; // biji hash acak membantu mengurangi jumlah tabrakan hash int transient hashed = 0;Seperti yang dapat dilihat dari variabel anggota, kapasitas awal hashmap default adalah 16, dan faktor pemuatan default adalah 0,75. Threshold adalah ambang dari pasangan nilai kunci yang dapat disimpan dalam set. Standarnya adalah kapasitas awal*faktor pemuatan, yaitu, 16*0,75 = 12. Ketika pasangan nilai kunci perlu melebihi ambang batas, itu berarti bahwa tabel hash sudah jenuh saat ini. Jika elemen terus ditambahkan, konflik hash akan ditambahkan, yang akan menurunkan kinerja hashmap. Pada saat ini, mekanisme ekspansi kapasitas otomatis akan dipicu untuk memastikan kinerja hashmap. Kita juga dapat melihat bahwa tabel hash sebenarnya adalah array entri, dan setiap entri yang disimpan dalam array adalah simpul header dari daftar tertaut satu arah. Entri ini adalah kelas hash yang statis, mari kita lihat variabel masuk anggota.
entri kelas statis <k, v> mengimplementasikan peta.entry <k, v> {final k key; // nilai kunci v; // Nilai entri <k, v> selanjutnya; // Referensi ke hash ent entri berikutnya; // histocode ... // hilangkan kode berikut}Contoh entri adalah pasangan nilai kunci yang berisi kunci dan nilai. Setiap instance entri memiliki referensi ke instance entri berikutnya. Untuk menghindari perhitungan berulang, setiap instance entri juga menyimpan kode hash yang sesuai. Dapat dikatakan bahwa array masuk adalah inti dari hashmap, dan semua operasi dilakukan untuk array ini. Karena kode sumber hashmap relatif panjang, tidak mungkin untuk memperkenalkan semua metodenya secara komprehensif, jadi kami hanya fokus pada poin -poin penting untuk memperkenalkannya. Selanjutnya, kita akan berorientasi pada masalah dan mengeksplorasi mekanisme internal hashmap secara mendalam untuk masalah-masalah berikut.
1. Operasi apa yang dilakukan hashmap selama konstruksi?
// konstruktor, lulus dalam kapasitas inisialisasi dan faktor beban hashmap publik (int initialcapacity, float loadfactor) {if (initialcapacity <0) {lempar baru ilegalArgumentException ("kapasitas awal ilegal:" + kapasitas awal); } // Jika kapasitas inisialisasi lebih besar dari kapasitas maksimum, atur ke kapasitas maksimum jika (InitialCapacity> maximum_capacity) {initialCapacity = maximum_capacity; } // Jika faktor beban kurang dari 0 atau faktor beban bukan angka titik mengambang, pengecualian dilemparkan jika (loadfactor <= 0 || float.isnan (loadfactor)) {lempar IllegalArgumentException baru ("Faktor Beban Ilegal:" + LoadFactor); } // atur faktor beban this.loadFactor = loadFactor; // ambang batas adalah ambang kapasitas inisialisasi = kapasitas awal; init ();} void init () {}Semua konstruktor akan memanggil konstruktor ini. Dalam konstruktor ini, kami melihat bahwa selain melakukan beberapa verifikasi parameter, ia melakukan dua hal: atur faktor beban ke faktor beban yang masuk dan atur ambang batas ke ukuran inisialisasi yang masuk. Metode init kosong dan tidak melakukan apa -apa. Perhatikan bahwa saat ini, tidak ada array entri baru yang dibuat berdasarkan ukuran inisialisasi yang masuk. Jadi kapan kita akan membuat array baru? Terus membaca.
2. Operasi apa yang akan dilakukan saat HashMap menambahkan pasangan nilai kunci?
// Masukkan pasangan nilai-kunci ke dalam hashmap public v put (K key, value v) {// inisialisasi if (table == kosong_table) {// inisialisasi inflatetable tabel hash (ambang batas); } if (key == null) {return putfornullKey (value); } // Hitung kode hash dari kunci int hash = hash (kunci); // Posisikan posisi tabel hash sesuai dengan kode hash int i = indexfor (hash, tabel.length); untuk (entri <k, v> e = tabel [i]; e! = null; e = e.next) {objek k; // Jika kunci yang sesuai sudah ada, ganti nilai nilainya dan kembalikan nilai asli jika (e.hash == hash && ((k = e.key) == key || key.equals (k))) {v oldValue = e.value; E.Value = nilai; E.RecordAccess (ini); Kembalikan OldValue; }} modcount ++; // Jika tidak ada kunci yang sesuai, tambahkan entri ke addentry hashmap (hash, kunci, nilai, i); // return null return null;}Anda dapat melihat bahwa saat menambahkan pasangan nilai kunci, Anda akan terlebih dahulu memeriksa apakah tabel hash adalah tabel kosong, dan jika itu adalah tabel kosong, itu akan diinisialisasi. Kemudian lakukan operasi selanjutnya dan hubungi fungsi hash untuk menghitung kode hash dari kunci yang dilewati. Posisikan slot yang ditentukan dari array entri sesuai dengan kode hash, dan kemudian melintasi daftar slot yang ditautkan satu arah. Jika yang sudah ada sudah ada, lakukan operasi penggantian, jika tidak, entri baru akan dibuat dan ditambahkan ke tabel hash.
3. Bagaimana tabel hash diinisialisasi?
// Inisialisasi tabel hash dan kapasitas tabel hash akan mengembang, karena ada kemungkinan bahwa kapasitas yang masuk bukanlah kekuatan 2 inflatetable void swasta (int tosize) {// kapasitas tabel hash harus berupa kekuatan 2 int kapasitas = Rounduptopowerof2 (tosize); // Atur ambang batas, di sini umumnya kapasitas * loadfactor threshold = (int) math.min (kapasitas * loadfactor, maximum_capacity + 1); // Buat tabel hash baru dengan tabel kapasitas tertentu = entri baru [kapasitas]; // inisialisasi benih hash inithashseedasneed (kapasitas);}Seperti yang kita ketahui di atas, saat membangun hashmap, kita tidak akan membuat array entri baru, tetapi periksa apakah tabel hash saat ini adalah tabel kosong selama operasi put. Jika itu adalah tabel kosong, hubungi metode inflatetable untuk inisialisasi. Kode untuk metode ini diposting di atas. Anda dapat melihat bahwa kapasitas array masuk akan dihitung ulang di dalam metode, karena ukuran inisialisasi dilewati saat membangun hashmap mungkin bukan kekuatan 2, jadi Anda perlu mengubah nomor ini menjadi kekuatan 2 dan kemudian membuat array masuk baru berdasarkan kapasitas baru. Saat menginisialisasi tabel hash, atur ulang ambang batas lagi, dan ambang batas umumnya kapasitas*loadfactor. Selain itu, benih hash (hashseed) akan diinisialisasi saat menginisialisasi tabel hash. Hashseed ini digunakan untuk mengoptimalkan fungsi hash. Standarnya adalah 0, dan tidak ada algoritma hash alternatif yang digunakan, tetapi Anda juga dapat menetapkan nilai hashshseed sendiri untuk mencapai efek optimasi. Ini akan dibahas secara rinci di bawah ini.
4. Kapan HashMap menentukan apakah perlu memperluas kapasitas dan bagaimana ia memperluas kapasitas?
// Tambahkan metode entri dan pertama -tama tentukan apakah Anda ingin memperluas addentry kapasitas void (int hash, k kunci, nilai v, int bucketIndex) {// Jika ukuran hashmap lebih besar dari ambang batas dan nilai slot yang lebih besar dari tabel hash (ukuran (ukuran> = threshold) && (null! = Tabel haven) karena tabel haven) karena (ukuran> = ambang batas) && (null! = Tabel haven (null! = ambang batas, ini menunjukkan bahwa konflik hash akan terjadi, jadi perluas ukuran kapasitas (2 * tabel.length); hash = (null! = key)? hash (kunci): 0; bucketIndex = indexfor (hash, table.length); } // Di sini ditunjukkan di sini bahwa ukuran hashmap tidak melebihi ambang batas, sehingga tidak perlu memperluas kapasitas createEntry (hash, kunci, nilai, bucketindex);} // memperluas ubah ukuran tabel hash (int newcapacity) {entri [] oldtable = tabel; int oldcapacity = oldtable.length; // Jika kapasitas maksimum saat ini sudah digunakan, Anda hanya dapat meningkatkan ambang batas jika (oldcapacity == maximum_capacity) {threshold = integer.max_value; kembali; } // Sebaliknya, perluas entri kapasitas [] newtable = entri baru [newcapacity]; // Metode untuk memigrasikan transfer tabel hash (Newtable, inithashseedasneed (newcapacity)); // Atur tabel hash saat ini ke tabel tabel hash baru = newtable; // perbarui hash tabel threshold = (int) math.min (newcapacity * loadFactor, maximum_capacity + 1);}Saat memanggil metode put untuk menambahkan pasangan nilai kunci, jika tidak ada kunci dalam koleksi, hubungi metode AddEntry dan buat entri baru. Ketika Anda melihat kode addEntry yang diposting di atas, sebelum membuat entri baru, Anda akan menentukan apakah ukuran elemen koleksi saat ini melebihi ambang batas. Jika ambang batas melebihi ambang batas, hubungi ukuran untuk ekspansi. Kapasitas baru yang dilewati adalah dua kali tabel hash asli. Dalam metode mengubah ukuran, array masuk baru dengan kapasitas dua kali tabel hash asli akan dibuat. Kemudian semua elemen dalam tabel hash lama dimigrasi ke tabel hash baru, di mana rehash dapat dilakukan, dan apakah akan melakukan rehash dilakukan sesuai dengan nilai yang dihitung dengan metode inithashseedasneed. Setelah migrasi tabel hash selesai, tabel hash saat ini diganti dengan yang baru, dan akhirnya nilai ambang batas hashmap dihitung ulang berdasarkan kapasitas tabel hash baru.
5. Mengapa ukuran array masuk menjadi kekuatan 2?
// Kembalikan indeks array yang sesuai dengan kode hash static int indexfor (int h, int length) {return h & (length-1); }Metode IndexFor menghitung subskrip yang sesuai dalam array berdasarkan kode hash. Kita dapat melihat bahwa operator (&) digunakan di dalam metode ini. Operasi ini untuk melakukan operasi bit pada dua operan. Jika dua bit yang sesuai adalah 1, hasilnya adalah 1, jika tidak 0. Operasi sering digunakan untuk menghapus nilai operan bit tinggi, seperti: 01011010 & 00001111 = 00001010. Mari kita kembali ke kode dan lihat apa yang dilakukan H & (panjang-1).
Diketahui bahwa panjang yang dilewati adalah panjang array masuk. Kita tahu bahwa subskrip array dihitung dari 0, sehingga subskrip maksimum array adalah panjang-1. Jika panjang adalah kekuatan 2, maka bit biner panjang-1 diikuti oleh 1. Pada saat ini, fungsi h & (panjang-1) adalah untuk menghilangkan nilai h-bit tinggi dan hanya menyisakan nilai h bit rendah sebagai subskrip array. Dari sini kita dapat melihat bahwa ukuran array masuk didefinisikan sebagai kekuatan 2 untuk menggunakan algoritma ini untuk menentukan subskrip array.
6. Bagaimana fungsi hash menghitung kode hash?
// fungsi yang menghasilkan kode hash final int hash (objek k) {int h = hashseed; // Jika kunci adalah tipe string, gunakan algoritma hash lain jika (0! = H && k instance dari string) {return sun.misc.hashing.stringhash32 ((string) k); } h ^= k.hashcode (); // fungsi gangguan h ^ = (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4);}Dua baris terakhir dari metode hash adalah algoritma yang benar -benar menghitung nilai hash. Algoritma yang menghitung kode hash disebut fungsi gangguan. Fungsi gangguan yang disebut adalah mencampur semuanya bersama-sama. Anda dapat melihat bahwa empat operasi shift hak-kanan digunakan di sini. Tujuannya adalah untuk mencampur nilai tinggi H dan nilai rendah untuk meningkatkan keacakan nilai rendah. Seperti di atas, kita tahu bahwa subskrip dari array penentuan posisi ditentukan berdasarkan nilai bit rendah dari kode hash. Kode hash dari kunci dihasilkan oleh metode kode hash, dan nilai rendah kode hash yang dihasilkan oleh metode kode hash yang buruk mungkin memiliki banyak pengulangan. Untuk membuat kode hash dipetakan relatif seragam pada array, fungsi gangguan berguna, menggabungkan karakteristik nilai bit tinggi ke dalam nilai rendah-bit, meningkatkan keacakan nilai bit rendah, sehingga membuat distribusi hash lebih longgar, sehingga meningkatkan kinerja. Gambar berikut memberikan contoh untuk membantu memahami.
7. Apa yang terjadi dengan hash pengganti?
Kami melihat bahwa dalam metode hash, hashseed pertama -tama akan ditugaskan ke h. Hashshseed ini adalah biji hash, yang merupakan nilai acak, dan digunakan untuk membantu mengoptimalkan fungsi hash. Hashshseed default adalah 0, yang berarti bahwa algoritma hash alternatif tidak digunakan secara default. Jadi kapan harus menggunakan hashseed? Pertama, Anda perlu mengatur hash alternatif untuk mengaktifkan, dan menetapkan nilai jdk.map.althashing.threshold di properti sistem. Nilai ini -1 secara default di properti sistem. Ketika itu -1, nilai ambang penggunaan hash alternatif adalah integer.max_value. Ini juga berarti bahwa Anda mungkin tidak pernah menggunakan hash pengganti. Tentu saja Anda dapat mengatur ambang ini sedikit lebih kecil, sehingga hashseed acak akan dihasilkan ketika elemen yang ditetapkan mencapai ambang batas. Ini meningkatkan keacakan fungsi hash. Mengapa menggunakan hash alternatif? Ketika elemen yang ditetapkan mencapai ambang batas yang Anda tetapkan, itu berarti bahwa tabel hash relatif jenuh, dan kemungkinan konflik hash akan sangat meningkat. Pada saat ini, menggunakan fungsi hash yang lebih acak untuk elemen yang ditambahkan dapat membuat elemen tambahan didistribusikan secara lebih acak dalam tabel hash.
Catatan: Semua analisis di atas didasarkan pada JDK1.7, dan akan ada perubahan besar antara versi yang berbeda, pembaca perlu memperhatikan.