Hashmap dan Hashset adalah dua anggota penting dari Kerangka Koleksi Java. HashMap adalah kelas implementasi umum untuk antarmuka peta, dan hashset adalah kelas implementasi umum untuk antarmuka yang ditetapkan. Meskipun spesifikasi antarmuka yang diimplementasikan oleh hashmap dan hashset berbeda, mekanisme penyimpanan hash yang mendasarinya persis sama, dan bahkan hashset itu sendiri menggunakan hashmap untuk mengimplementasikannya.
Bahkan, ada banyak kesamaan antara hashset dan hashmap. Untuk hashset, sistem menggunakan algoritma hash untuk menentukan lokasi penyimpanan elemen pengumpulan, sehingga dapat memastikan bahwa elemen pengumpulan dapat disimpan dan diambil dengan cepat; Untuk HashMap, sistem kunci sistem diproses secara keseluruhan, dan sistem selalu menghitung lokasi penyimpanan nilai kunci berdasarkan algoritma hash, sehingga pasangan nilai kunci dari peta dapat disimpan dan diambil dengan cepat.
Sebelum memperkenalkan penyimpanan koleksi, harus ditunjukkan bahwa meskipun koleksi mengklaim untuk menyimpan objek Java, itu sebenarnya tidak memasukkan objek Java ke dalam koleksi yang ditetapkan, tetapi hanya menyimpan referensi ke objek -objek ini dalam koleksi yang ditetapkan. Dengan kata lain, koleksi Java sebenarnya adalah koleksi beberapa variabel referensi yang menunjuk pada objek Java yang sebenarnya.
1. Fitur dasar hashmap
Setelah membaca komentar dalam kode sumber JDK hashmap.class, Anda dapat meringkas banyak fitur hashmap.
HashMap memungkinkan kunci dan nilai menjadi nol, sedangkan hashtable tidak.
Hashmap adalah benang-utas, sedangkan hashtable aman-utas
Urutan elemen dalam hashmap tidak selalu sama, dan posisi elemen yang sama juga dapat berubah dari waktu ke waktu (kasus mengubah ukuran)
Kompleksitas waktu melintasi hashmap sebanding dengan kapasitasnya dan jumlah elemen yang ada. Jika Anda ingin memastikan efisiensi traversal, kapasitas awal tidak dapat diatur terlalu tinggi atau faktor keseimbangan tidak dapat ditetapkan terlalu rendah.
Mirip dengan daftar terkait sebelumnya, karena HashMap adalah utas-tidak aman, gagal-cepat akan dihasilkan ketika iterator mencoba mengubah struktur kontainer selama proses iterasi. Hashmap yang disinkronkan dapat diperoleh melalui koleksi.
2. Analisis Struktur Data Tabel Hash
Tabel hash (tabel hash, tabel hash) adalah struktur data yang secara langsung mengakses lokasi penyimpanan memori berdasarkan kata kunci. Dengan kata lain, tabel hash menetapkan pemetaan langsung antara kata kunci dan alamat penyimpanan
Seperti yang ditunjukkan pada gambar di bawah ini, kunci memperoleh posisi indeks ember melalui fungsi hash.
Memperoleh indeks melalui fungsi hash pasti akan terjadi situasi yang sama, yaitu konflik. Berikut adalah beberapa cara untuk menyelesaikan konflik:
Open Addressing: Ide dasar dari metode ini adalah memindai posisi di bawah tabel secara berurutan saat menghadapi konflik, dan mengisi jika ada yang gratis. Algoritma spesifik tidak akan dijelaskan lagi, berikut ini adalah diagram skematik:
PERBAIKAN PERBEDAKAN: Ide dasar dari metode ini adalah untuk merangkai entri dengan nilai indeks yang sama dalam daftar tertaut saat menghadapi konflik. Algoritma spesifik tidak akan dijelaskan lagi, berikut ini adalah diagram skematik:
Metode untuk menyelesaikan konflik dalam hashmap di JDK adalah dengan menggunakan metode rantai terpisah.
3. Analisis Kode Sumber Hashmap (JDK1.7)
1. Elemen baca dan tulis hashmap
Pintu masuk
Elemen yang disimpan dalam hashmap adalah jenis masuk. Kode Sumber Entri dalam Kode Sumber diberikan di bawah ini:
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; } // Metode Get and Set Kunci, Nilai Dihilangkan, Dapatkan dan Tetapkan Operasi akan digunakan dalam iterator berikutnya ... Publik Boolean Equals (Object 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; } // Di sini, lakukan atau mengoperasikan kode hashcode dan kode hashcode nilai untuk mendapatkan kode hashcode entri hashcode int final publik () {return objects.hashcode (getKey ()) ^ objects.hashcode (getValue ()); } public final string toString () {return getKey () + "=" + getValue (); } /** * Metode ini dipanggil setiap kali nilai dalam entri * ditimpa dengan doa put (k, v) untuk kunci k yang sudah * di hashmap. * / void RecordAccess (HashMap <K, V> M) {} / ** * Metode ini dipanggil setiap kali entri * dihapus dari tabel. */ void recordremoval (hashmap <k, v> m) {}}Entri termasuk kunci, nilai, hash dan referensi ke entri berikutnya. Jelas bahwa ini adalah daftar tunggal yang ditautkan, yang mengimplementasikan antarmuka MAP.Entry.
Recordacess (HashMap <K, V> dan RecordRemoval (HashMap <K, V>) tidak diimplementasikan dalam HashMap. Namun, dua metode LinkedHashMap digunakan untuk mengimplementasikan algoritma LRU.
Dapatkan: Baca elemen untuk mendapatkan entri yang sesuai dari HashMap. Berikut ini adalah kode sumber GET:
public v get (tombol objek) {// Situasi di mana kunci adalah null if (key == null) return getFornullKey (); // Temukan entri berdasarkan entri entri kunci <k, v> entri = getEntry (key); return null == entri? null: entry.getValue (); }Kode Sumber GetFornullkey
private v getFornullKey () {if (size == 0) {return null; } // transtraighten rantai konflik untuk (entri <k, v> e = tabel [0]; e! = Null; e = e.next) {if (e.key == null) mengembalikan nilai e. } return null; }Masuk dengan nol kunci disimpan dalam tabel [0], tetapi rantai konflik pada tabel [0] tidak selalu memiliki kunci sebagai nol, sehingga perlu dilalui.
Dapatkan entri sesuai dengan kunci:
entri akhir <k, v> getEntry (tombol objek) {if (size == 0) {return null; } int hash = (key == null)? 0: hash (kunci); // Dapatkan posisi indeks dalam tabel melalui hash, dan kemudian melintasi daftar tertaut yang bertentangan untuk menemukan kunci (entri <k, v> e = tabel [indexfor (hash, tabel.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; }Di atas adalah proses hashmap membaca entri dan kode sumbernya. Kompleksitas waktu o (1)
Put: Tulis elemen
Operasi put di hashmap relatif rumit karena akan ada operasi ekspansi hashmap selama operasi put.
Ketika elemen baru ditulis, jika ada kunci untuk menulis elemen dalam hashmap, operasi penggantian nilai dilakukan, yang setara dengan pembaruan. Ini kode sumber put:
public v put (Key k, nilai v) {// Jika tabel kosong, isi if (tabel == kosong_table) sesuai dengan ambang batas ukuran {inflatetable (ambang); } // Isi entri dengan kunci sebagai null if (key == null) return putfornullkey (value); // menghasilkan hash untuk mendapatkan pemetaan indeks indeks int hash = hash (kunci); int i = indexfor (hash, table.length); // Transulasi rantai konflik indeks saat ini untuk menemukan apakah ada kunci yang sesuai untuk (entri <k, v> e = Tabel [i]; e! = Null; e = e.next) {objek k; // Jika ada kunci yang sesuai, ganti oldValue dan kembalikan oldValue if (e.hash == hash && ((k = e.key) == key || key.equals (k))) {v oldValue = e.value; E.Value = nilai; E.RecordAccess (ini); Kembalikan OldValue; }} // Kunci entri yang baru ditulis tidak ada di rantai konflik MODCount ++; // Masukkan tambahan entri baru (hash, kunci, nilai, i); kembali nol; }Kode Sumber Addentry dan CreateEntry:
void addEntry (int hash, k kunci, nilai v, int bucketIndex) {// Sebelum memasukkan entri baru, pertama menilai ukuran hashmap saat ini dan ukuran ambang batasnya, dan pilih apakah akan memperluas if ((size> = threshold) && (null! = Tabel [bucketIndex]))) {ukuran ulang (2 * tabel); 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]; // Metode penyisipan kepala, entri yang baru ditulis dimasukkan ke depan entri pertama dalam rantai konflik pada posisi indeks saat ini. tabel [bucketIndex] = entri baru <> (hash, kunci, nilai, e); ukuran ++; }Di atas adalah proses penulisan entri ke hashmap dan kode sumbernya. Kompleksitas waktu o (1)
Hapus Hapus Elemen:
Entri akhir <k, v> remeVETRYFORKEY (kunci objek) {if (size == 0) {return null; } // Hitung nilai hash sesuai dengan kunci dan dapatkan indeks int hash = (key == null)? 0: hash (kunci); int i = indexfor (hash, table.length); // Hapus daftar tertaut, tentukan dua pointer, pra mewakili entri pendahulu <k, v> prev = tabel [i]; Entri <k, v> e = prev; // transtraight rantai konflik dan hapus semua kunci sementara (e! = Null) {entri <k, v> next = e.next; Objek k; // jika ditemukan (e.hash == hash && ((k = e.key) == key || (key! = Null && key.equals (k)))) {modcount ++; ukuran--; // Menemukan simpul pertama adalah simpul yang akan dihapus jika (prev == e) tabel [i] = selanjutnya; else prev.next = next; E.Recordremoval (ini); mengembalikan e; } prev = e; e = selanjutnya; } return e; }Di atas adalah proses hashmap menghapus entri dan kode sumbernya. Kompleksitas waktu o (1)
2. Prinsip hashing hashmap (fungsi hash)
Implementasi fungsi hash dalam hashmap dilakukan melalui hash (objek k) dan indexfor (int h, int length). Mari kita lihat kode sumber di bawah ini:
final int hash (objek k) {int h = hashseed; if (0! = h && k String dari string) {return sun.misc.hashing.stringhash32 ((string) k); } 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). // untuk mengurangi kemungkinan konflik h ^ = (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }Dapatkan kode sumber indeks indeks:
statis int indexfor (int h, int length) {// tegas integer.bitcount (panjang) == 1: "Panjang harus menjadi kekuatan tidak nol 2"; return h & (length-1); }HashMap memetakan tombol ke indeks dalam interval [0, tabel.length] melalui fungsi hash. Umumnya ada dua jenis metode pengindeksan:
hash (kunci) % tabel.length, di mana panjang harus menjadi bilangan prima. Hashtable menggunakan implementasi ini di JDK.
Untuk alasan khusus untuk menggunakan bilangan prima, Anda dapat menemukan bukti data algoritma yang relevan, yang tidak akan dinyatakan di sini.
hash (kunci) & (tabel.length - 1) di mana panjang harus ke 2 daya eksponensial. HashMap di JDK menggunakan metode implementasi ini.
Karena ukuran panjang adalah 2 kali eksponensial, hash (kunci) & (tabel.length - 1) akan selalu antara [0, panjang - 1]. Namun, jika Anda melakukan ini sendirian, akan ada masalah besar dengan konflik, karena nilai kode hash di Java adalah 32 bit. Ketika kapasitas hashmap kecil, misalnya, ketika 16, ketika melakukan operasi XOR, bit tinggi selalu dibuang, tetapi setelah operasi bit rendah, probabilitas konflik terjadi meningkat.
Oleh karena itu, untuk mengurangi probabilitas kejadian konflik, banyak operasi bit dan operasi eksklusif atau dilakukan dalam kode.
3. Strategi Alokasi Memori Hashmap
Kapasitas Variabel Anggota dan Loadfactor
Kapasitas kapasitas yang diperlukan adalah kelipatan eksponensial 2 dalam hashmap, dan kapasitas default adalah 1 << 4 = 16. Ada juga faktor keseimbangan (LoadFactor) dalam hashmap. Faktor -faktor yang sangat tinggi akan mengurangi ruang penyimpanan, tetapi waktu untuk mencari (pencarian, termasuk metode put dan dapatkan dalam hashmap) akan meningkat. Nilai default LoadFactor adalah 0,75, yang merupakan nilai optimal yang diberikan dengan menimbang kompleksitas waktu dan kompleksitas ruang.
static final int default_initial_capacity = 1 << 4; // alias 16 statis final int maximum_capacity = 1 << 30; statis final float default_load_factor = 0.75f;
Hashmap Constructor
Konstruksi hashmap adalah untuk menetapkan kapasitas dan nilai awal loadfactor
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); this.loadFactor = loadFactor; threshold = InitialCapacity; init (); } Saya telah mengatakan sebelumnya bahwa kapasitas dalam hashmap harus berupa waktu eksponensial 2, dan tidak ada batasan dalam konstruktor. Jadi bagaimana memastikan bahwa nilai kapasitas adalah waktu eksponensial 2?
Selama operasi put, kode sumber akan menentukan apakah tabel hash saat ini adalah tabel kosong. Jika demikian, hubungi inflatetable (int tosize)
private void inflatetable (int tosize) {// Temukan kekuatan 2> = tosize int kapasitas = rounduptopowerof2 (tosize); threshold = (int) math.min (kapasitas * loadfactor, maksimum_capacity + 1); Tabel = entri baru [kapasitas]; inithashseedasneed (kapasitas); }di mana Rounduptopowerof2 adalah untuk mendapatkan kekuatan N 2 lebih besar dari atau sama dengan parameter yang diberikan
private static int rounduptopowerof2 (nomor int) {// asert number> = 0: "Nomor harus non-negatif"; Return Number> = Maximum_capacity? Maximum_capacity: (nomor> 1)? Integer.highestonebit ((angka - 1) << 1): 1; }Integer.HightestOneBit (int) adalah operasi yang mempertahankan bit tertinggi dari parameter yang diberikan dan mengubah 0. Sederhananya, itu adalah mengubah parameter int ke n kekuatan kurang dari atau sama dengan maksimum 2.
Jika angka adalah N daya 2, bit tertinggi adalah pada bit tinggi kedua asli setelah penurunan 1, dan kemudian bergeser 1 bit kiri untuk tetap diposisikan ke posisi bit tertinggi. Jika angka bukan N daya 2, bit tertinggi masih bit tertinggi asli setelah penurunan 1 bit kiri untuk bergeser 1 bit kiri menjadi
Kapasitas Perluas:
HashMap akan memiliki perilaku mengubah ukuran saat operasi. Kode sumber spesifik adalah sebagai berikut:
void mengubah ukuran (int newcapacity) {entri [] oldtable = tabel; int oldcapacity = oldtable.length; // Tabel hash telah mencapai kapasitas maksimumnya, 1 << 30 if (oldcapacity == maximum_capacity) {threshold = integer.max_value; kembali; } Entri [] newtable = entri baru [newcapacity]; // Transfer entri di OldTable ke Newtable // Nilai Pengembalian Inithashseedasneed menentukan apakah akan menghitung ulang transfer nilai hash (Newtable, Inithashseedasneed (Newcapacity)); tabel = newtable; // Hitung ulang ambang batas ambang = (int) math.min (newcapacity * loadfactor, maximum_capacity + 1); } void transfer (entri [] newtable, boolean rehash) {int newCapacity = newtable.length; // Transweep oldtable untuk (entri <k, v> e: tabel) {// rantai konflik transweep while (null! = E) {entri <k, v> next = e.next; if (rehash) {// menghitung ulang nilai hash e.hash = null == E.Key? 0: hash (e.key); } int i = indexfor (e.hash, newcapacity); // Masukkan elemen ke kepala, metode penyisipan header e.next = newtable [i]; Newtable [i] = e; e = selanjutnya; }}}Di atas adalah seluruh proses alokasi memori hashmap. Singkatnya, ketika HashMap melakukan entri, ia akan memeriksa kapasitas saat ini dan ukuran ambang batas untuk memilih apakah akan memperluas kapasitas. Ukuran masing -masing ekspansi adalah 2 * tabel.length. Selama periode ekspansi, itu akan menentukan apakah nilai hash perlu dihitung ulang berdasarkan inithashseedasneed.
4. Hashmap iterator
Iterator seperti ValueTerator, KeyIterator, EntryIterator dan lainnya di HashMap semuanya didasarkan pada Hashiterator. Mari kita lihat kode sumbernya:
Hashiterator kelas abstrak privat <e> mengimplementasikan iterator <E> {entri <k, v> next; // Entri berikutnya untuk mengembalikan int diharapkan MODCount; // untuk indeks int cepat-cepat; // slot saat ini, entri indeks tabel <k, v> arus; // Hashiterator entri saat ini () {diharapkanmodcount = modcount; // Temukan entri pertama di tabel hash if (size> 0) {entri [] t = tabel; while (index <t.length && (next = t [index ++]) == null); }} public final boolean hasnext () {return next! = null; } Entri akhir <k, v> nextEntry () {// hashmap tidak aman, dan ketika melintasi, masih menentukan apakah ada modifikasi struktur tabel jika (modcount! = diharapkan modcount) melempar concurrentModificationException (); Entri <k, v> e = selanjutnya; if (e == null) melempar nosuchelementException baru (); if ((next = e.next) == null) {// Temukan entri entri berikutnya [] t = tabel; while (index <t.length && (next = t [index ++]) == null); } current = e; mengembalikan e; } public void remeF () {if (current == null) melempar IllegalStateException baru (); if (modcount! = diharapkan modcount) lempar concurrentmodificationException baru (); Objek k = current.key; saat ini = null; Hashmap.this.removeentryforkey (k); diharapkan modcount = modcount; }}Tiga iterator, kunci, nilai, dan entri, dienkapsulasi dan menjadi tiga perspektif koleksi: kunci, nilai, dan entri. Ketiga perspektif koleksi ini mendukung operasi hashmap hapus, pelepasan, dan jelas, dan tidak mendukung operasi Tambah dan Addall.