Struktur penyimpanan
Pertama, hashmap disimpan berdasarkan tabel hash. Ada array di dalamnya. Ketika suatu elemen harus disimpan, pertama -tama hitung nilai hash dari kuncinya dan temukan subskrip yang sesuai dari elemen dalam array berdasarkan nilai hash. Jika tidak ada elemen pada posisi ini, masukkan elemen saat ini secara langsung. Jika ada elemen (diingat sebagai di sini), tautkan elemen saat ini ke bagian depan elemen A dan kemudian masukkan elemen saat ini ke dalam array. Jadi di HashMap, array sebenarnya menyimpan simpul pertama dari daftar tertaut. Di bawah ini adalah gambar dari Baidu Encyclopedia:
Seperti yang ditunjukkan pada gambar di atas, setiap elemen adalah objek entri, di mana kunci dan nilai elemen disimpan, dan ada pointer yang dapat digunakan untuk menunjuk ke objek berikutnya. Semua kunci dengan nilai hash yang sama (yaitu, konflik) merangkai mereka bersama -sama menggunakan daftar tertaut, yang merupakan metode ritsleting.
Variabel internal
//Default initial capacity static final int DEFAULT_INITIAL_CAPACITY = 16;//Maximum capacity static final int MAXIMUM_CAPACITY = 1 << 30;//Default load factor static final float DEFAULT_LOAD_FACTOR = 0.75f;//Hast table transient Entry<K,V>[] table;//Number of key-value pairs transient int size;//The threshold of expansion int ambang; // faktor beban hash array hash float loadfactor;
Dalam variabel di atas, kapasitas mengacu pada panjang tabel hash, yaitu, ukuran tabel, dan standarnya adalah 16. Load Factor Loadfactor adalah "derajat penuh" dari tabel hash, dan dokumentasi JDK mengatakan ini:
Faktor beban adalah ukuran seberapa penuh tabel hash diperbolehkan untuk mendapatkan sebelum kapasitasnya meningkat secara otomatis. Ketika jumlah entri dalam tabel hash melebihi produk dari faktor beban dan kapasitas saat ini, tabel hash dinyalakan kembali (yaitu, struktur data internal dibangun kembali) sehingga tabel hash memiliki sekitar dua kali jumlah ember.
Makna umum adalah: faktor pemuatan adalah ukuran seberapa penuh tabel hash dapat dipasang sebelum ekspansi. Ketika jumlah "pasangan nilai kunci" di tabel hash melebihi produk dari kapasitas saat ini dan faktor pemuatan, tabel hash hash (yaitu, struktur data internal dibangun kembali), dan kapasitas tabel hash menjadi sekitar dua kali yang asli.
Seperti yang dapat dilihat dari definisi variabel di atas, faktor pemuatan default Default_load_factor adalah 0,75. Semakin besar nilai ini, semakin tinggi tingkat pemanfaatan ruang, tetapi kecepatan kueri (termasuk GET dan put) akan melambat. Setelah memahami faktor pemuatan, ambang batas juga dapat memahaminya. Ini sebenarnya sama dengan faktor pemuatan kapasitas*.
Konstruktor
hashmap publik (int initialcapacity, float loadfactor) {if (initialcapacity <0) melempar IllegalArgumentException baru ("Kapasitas Awal Ilegal:" + InitialCapacity); if (initialcapacity> maximum_capacity) initialcapacity = maximum_capacity; if (loadfactor <= 0 || float.isnan (loadfactor)) melempar baru ilegalargumentException ("faktor beban ilegal:" + loadfactor); // Temukan kekuatan 2> = Kapasitas Inisial Kapasitas = 1; sementara (kapasitas <initialcapacity) // Hitung daya terkecil 2 yang lebih besar dari kapasitas kapasitas yang ditentukan << = 1; this.loadFactor = loadFactor; threshold = (int) math.min (kapasitas * loadfactor, maksimum_capacity + 1); Tabel = entri baru [kapasitas]; // Alokasikan ruang ke tabel hash usealthashashashing = sun.misc.vm.isbooted () && (kapasitas> = holder.alternative_hashing_threshold); init ();}Ada beberapa konstruktor, dan mereka pada akhirnya akan memanggil yang di atas. Ia menerima dua parameter, satu adalah kapasitas awal dan yang lainnya adalah faktor pemuatan. Pada awalnya, pertama -tama kami menentukan apakah kombinasi nilai itu legal, dan jika ada masalah, pengecualian akan dilemparkan. Yang penting adalah perhitungan kapasitas di bawah ini, logikanya adalah untuk menghitung kekuatan terkecil 2 lebih besar dari kapasitas awal. Faktanya, tujuannya adalah untuk membuat kapasitas lebih dari atau sama dengan kapasitas awal yang ditentukan, tetapi nilai ini harus merupakan kelipatan eksponensial dari 2, yang merupakan masalah utama. Alasan untuk ini terutama untuk memetakan nilai hash. Pertama -tama mari kita lihat metode hash di hashmap:
final int hash (objek k) {int h = 0; if (usealthashing) {if (k instance dari string) {return sun.misc.hashing.stringhash32 ((string) k); } h = hashseed; } h ^= k.hashcode (); // Fungsi ini memastikan bahwa hashcode yang hanya berbeda dengan // kelipatan konstan pada setiap posisi bit memiliki // jumlah tabrakan (sekitar 8 pada faktor beban default). h ^ = (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4);} static int indexfor (int h, int length) {return h & (length-1);}Metode hash () menghitung ulang nilai hash kunci dan menggunakan operasi bit yang relatif kompleks. Saya tidak tahu logika spesifiknya. Bagaimanapun, itu jelas merupakan metode yang lebih baik, yang dapat mengurangi konflik atau sesuatu.
Indexfor () di bawah ini adalah subskrip elemen dalam tabel hash berdasarkan nilai hash. Secara umum, dalam tabel hash, Anda menggunakan nilai hash untuk memodulasi panjang tabel. Ketika panjang (yaitu, kapasitas) adalah kekuatan 2, h & (panjang-1) adalah efek yang sama. Selain itu, kekuatan 2 harus menjadi angka genap, maka setelah mengurangi 1, itu adalah angka ganjil, dan bit terakhir dari biner harus 1. Kemudian bit terakhir h & (panjang-1) mungkin 1 atau 0, yang dapat hashed secara merata. Jika panjang adalah angka ganjil, maka panjang-1 adalah angka genap dan bit terakhir adalah 0. Pada saat ini, bit terakhir H & (panjang-1) mungkin hanya 0, dan semua subskrip yang dihasilkan bahkan, jadi setengah dari ruang terbuang. Oleh karena itu, kapasitas dalam hashmap harus menjadi kekuatan 2. Anda dapat melihat bahwa default default_initial_capacity = 16 dan maximum_capacity = 1 << 30 sama -sama seperti ini.
Objek Masuk
Pasangan nilai kunci dalam hashmap dienkapsulasi ke dalam objek masuk, yang merupakan kelas internal dalam hashmap. Mari kita lihat implementasinya:
entri kelas statis <k, v> mengimplementasikan peta.entry <k, v> {final k key; Nilai v; Entri <k, v> berikutnya; int hash; Entri (int h, k k, v v, entri <k, v> n) {value = v; Berikutnya = n; kunci = k; hash = h; } public final k getKey () {return key; } public final v getValue () {nilai pengembalian; } public final v setValue (v newValue) {v oldValue = value; value = newValue; Kembalikan OldValue; } public final boolean sama (objek o) {if (! (o instanceof map.entry)) return false; Peta.entry e = (map.entry) o; Objek k1 = getKey (); Objek k2 = e.getKey (); if (k1 == k2 || (k1! = null && k1.equals (k2))) {objek v1 = getValue (); Objek v2 = e.getValue (); if (v1 == v2 || (v1! = null && v1.equals (v2))) mengembalikan true; } return false; } public final int hashCode () {return (key == null? 0: key.hashCode ()) ^ (value == null? 0: value.hashcode ()); } public final string toString () {return getKey () + "=" + getValue (); } void recordAccess (hashMap <k, v> m) {}}Implementasi kelas ini sederhana dan mudah dimengerti. Metode seperti getKey (), getValue () disediakan untuk panggilan. Untuk menentukan kesetaraan, perlu bahwa kunci dan nilainya sama.
menempatkan operasi
Put pertama sebelum Anda mendapatkannya, jadi lihat metode put () terlebih dahulu:
public v put (key k, nilai v) {if (key == null) return putfornullKey (nilai); 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); return null;}Dalam metode ini, pertama -tama tentukan apakah kunci itu nol. Jika ya, hubungi metode putfornullkey (), yang berarti bahwa hashmap memungkinkan kunci menjadi nol (pada kenyataannya, nilai bisa). Jika tidak nol, hitung nilai hash dan dapatkan subskrip dalam tabel. Kemudian buka daftar tertaut yang sesuai untuk menanyakan apakah kunci yang sama sudah ada. Jika sudah ada, nilainya akan diperbarui secara langsung. Kalau tidak, hubungi ADDENTRY () Metode untuk dimasukkan.
Lihatlah metode putfornullkey ():
private v putfornullKey (nilai v) {untuk (entri <k, v> e = tabel [0]; e! = null; e = e.next) {if (e.key == null) {v oldValue = e.value; E.Value = nilai; E.RecordAccess (ini); Kembalikan OldValue; }} modcount ++; addentry (0, null, value, 0); return null;}Dapat dilihat bahwa ketika kunci adalah nol, nilainya akan diperbarui jika ada, jika tidak addEntry () akan dipanggil untuk dimasukkan.
Berikut ini adalah implementasi metode addEntry ():
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 kunci, nilai v, int bucketIndex) {entri <k, v> e = tabel [bucketIndex]; tabel [bucketIndex] = entri baru <> (hash, kunci, nilai, e); ukuran ++;}Pertama, tentukan apakah akan memperluas kapasitas (peningkatan kapasitas akan menghitung ulang nilai subskrip dan menyalin elemen), kemudian menghitung subskrip array, dan akhirnya memasukkan elemen menggunakan metode penyisipan header di createEntry ().
dapatkan operasi
public v get (kunci objek) {if (key == null) return getFornullKey (); Entri <k, v> entri = getEntry (key); return null == entri? null: entry.getValue ();} private v getFornullKey () {for (entri <k, v> e = tabel [0]; e! = null; e = e.next) {if (e.key == null) mengembalikan e.value; } return null;} entri akhir <k, v> getEntrry (kunci objek) {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;}Ini lebih sederhana dari put (). Anda juga perlu menentukan apakah kuncinya adalah nol, dan kemudian permintaan traversal dari daftar yang ditautkan.
Optimalisasi Kinerja
HashMap adalah struktur data yang efisien dan universal yang dapat dilihat di mana -mana di setiap program Java. Mari kita perkenalkan beberapa pengetahuan dasar terlebih dahulu. Seperti yang mungkin Anda ketahui, HashMap menggunakan metode hashcode () dan equals () kunci untuk membagi nilai menjadi ember yang berbeda. Jumlah ember biasanya sedikit lebih besar dari jumlah catatan di peta, sehingga setiap ember akan mencakup lebih sedikit nilai (lebih disukai satu). Saat mencari melalui tombol, kita dapat dengan cepat menemukan ember (menggunakan hashcode () untuk memodulo jumlah ember) dan objek yang kita cari dalam waktu yang konstan.
Anda seharusnya sudah mengetahui semua hal ini. Anda mungkin juga tahu bahwa tabrakan hash dapat memiliki dampak bencana pada kinerja hashmap. Jika beberapa nilai hashcode () masuk ke dalam ember yang sama, nilai -nilai ini disimpan dalam daftar yang ditautkan. Dalam kasus terburuk, semua kunci dipetakan ke dalam ember yang sama, sehingga hashmap merosot menjadi daftar yang ditautkan - waktu pencarian adalah dari O (1) hingga O (n). Mari kita menguji kinerja hashmap di Java 7 dan Java 8 dalam keadaan normal. Untuk mengontrol perilaku metode hashcode (), kami mendefinisikan kelas kunci sebagai berikut:
Kunci kelas mengimplementasikan yang sebanding <Yey> {private final int value; key (value int) {this.value = value;}@overridepublic int compareto (key o) {return integer.compare (this.value, o.value);}@overDidepublic boolean equals (objek o) {o.value); o.getClass ()) return false; tombol kunci = (key) o; value return == key.value;}@overridepublic int hashCode () {value return;}}Implementasi kelas kunci cukup standar: ia menulis ulang metode Equals () dan menyediakan metode hashcode () yang cukup layak. Untuk menghindari GC yang berlebihan, saya menyimpan objek kunci yang tidak dapat diubah alih -alih mulai membuatnya lagi setiap saat:
Kunci kelas mengimplementasikan yang sebanding <Y key> {kunci kelas publik {public static final int max_key = 10_000_000; Kunci akhir statis privat [] keys_cache = Kunci baru [max_key]; static {for (int i = 0; i <max_key; ++ i) {keys_cache [i] = Key i = i);}} public {public) {keys_cache [i] = Kunci baru (i);}} public {public) {keys_cache [i] = Kunci baru (i);}}} {public i) {keys_cache [i] = new Key (i);};Sekarang kita bisa mulai menguji. Benchmark kami menggunakan nilai -nilai kunci kontinu untuk membuat hashmap dari berbagai ukuran (pengganda untuk 10, dari 1 hingga 1 juta). Dalam tes, kami juga akan menggunakan kunci untuk mencari dan mengukur waktu yang dibutuhkan untuk hashmap dari berbagai ukuran:
impor com.google.caliper.param; import com.google.caliper.runner; import com.google.caliper.simpleBenchmark; Public Class MapBenchmark Memperluas SimpleBenchmark {private HashMap <Key, Integer> peta; @paramprivate int papsizeS; @OverRIDEPROPRIPREPROCED / INTEGROPER; @paramprivate; @Overrotected {eVPROPRITE {OMERROPRIVATE {@exprivate {@everrotected; HashMap <> (mapsize); for (int i = 0; i <mapsize; ++ i) {map.put (keys.of (i), i);}} public void timeMapget (int reps) {for (int i = 0; i <reps; i ++) {map.get (keys.of (i % mapssize;Menariknya, dalam hashmap.get () sederhana ini, Java 8 lebih cepat 20% dari Java 7. Kinerja keseluruhan juga cukup baik: meskipun ada sejuta catatan dalam hashmap, satu kueri hanya membutuhkan waktu kurang dari 10 nanoseconds, yaitu sekitar 20 siklus CPU pada mesin saya. Sangat mengejutkan! Tapi ini bukan yang ingin kita ukur.
Misalkan ada kunci yang buruk, selalu mengembalikan nilai yang sama. Ini adalah skenario terburuk, dan Anda tidak boleh menggunakan hashmap sama sekali:
Kunci kelas mengimplementasikan yang sebanding <Yey> {//...@overridepublic int hashCode () {return 0;}}Hasil Java 7 diharapkan. Saat ukuran hashmap tumbuh, metode overhead dari get () semakin besar dan lebih besar. Karena semua catatan ada dalam daftar tertaut ultra-panjang dalam ember yang sama, mencari rata-rata satu catatan memerlukan melintasi setengah dari daftar. Oleh karena itu, dapat dilihat dari gambar bahwa kompleksitas waktunya adalah O (n).
Namun, Java 8 tampil jauh lebih baik! Ini adalah kurva log, jadi kinerjanya lebih baik. Terlepas dari skenario terburuk dari tabrakan hash parah, tolok ukur yang sama ini memiliki kompleksitas waktu di JDK8 dari O (LOGN). Jika Anda melihat kurva JDK 8 saja, itu akan lebih jelas. Ini adalah distribusi linier logaritmik:
Mengapa ada peningkatan kinerja yang hebat, meskipun simbol O besar digunakan di sini (Big O menggambarkan batas atas asimptotik)? Bahkan, optimasi ini telah disebutkan dalam JEP-180. Jika catatan dalam ember terlalu besar (saat ini Treeify_Threshold = 8), HashMap secara dinamis akan menggantinya dengan implementasi TREEMAP khusus. Ini akan menghasilkan hasil yang lebih baik, O (LOGN), tidak buruk O (n). Bagaimana cara kerjanya? Catatan yang sesuai dengan kunci yang memiliki konflik di depan hanya ditambahkan ke daftar yang ditautkan, dan catatan -catatan ini hanya dapat ditemukan melalui traversal. Namun, setelah melebihi ambang batas ini, HashMap mulai meningkatkan daftar ke pohon biner, menggunakan nilai hash sebagai variabel cabang pohon. Jika kedua nilai hash tidak sama tetapi menunjuk ke ember yang sama, yang lebih besar akan dimasukkan ke dalam subtree kanan. Jika nilai hash sama, hashmap berharap bahwa nilai kunci paling baik diimplementasikan oleh antarmuka yang sebanding sehingga dapat dimasukkan secara berurutan. Ini tidak diperlukan untuk kunci Hashmap, tetapi tentu saja yang terbaik jika diimplementasikan. Jika antarmuka ini tidak diterapkan, Anda seharusnya tidak berharap untuk mencapai peningkatan kinerja jika terjadi tabrakan hash yang parah.
Apa gunanya peningkatan kinerja ini? Misalnya, program jahat, jika ia tahu bahwa kami menggunakan algoritma hashing, ia dapat mengirim sejumlah besar permintaan, menghasilkan tabrakan hash yang serius. Kemudian terus -menerus mengakses tombol -tombol ini dapat secara signifikan mempengaruhi kinerja server, yang mengarah ke penolakan serangan layanan (DOS). Lompatan dari O (N) ke O (LOGN) di JDK 8 dapat secara efektif mencegah serangan yang serupa, sementara juga sedikit meningkatkan prediktabilitas kinerja hashmap. Saya harap peningkatan ini pada akhirnya akan meyakinkan bos Anda untuk setuju untuk meningkatkan ke JDK 8.
Lingkungan yang digunakan untuk tes adalah: Intel Core i7-3635qm @ 2.4 GHz, memori 8GB, hard disk SSD, menggunakan parameter JVM default, berjalan pada sistem Windows 8.1 64-bit.
Meringkaskan
Implementasi dasar hashmap adalah sebagaimana dianalisis di atas, dan akhirnya ringkasan dibuat: