Hashmap juga koleksi yang banyak kami gunakan. Ini adalah implementasi antarmuka peta berdasarkan tabel hash dan ada dalam bentuk nilai kunci. Dalam hashmap, nilai kunci selalu diproses secara keseluruhan. Sistem akan menghitung lokasi penyimpanan nilai kunci berdasarkan algoritma hash. Kami selalu dapat dengan cepat menyimpan dan mengambil nilai melalui kunci. Mari kita analisis akses ke hashmap.
1. Definisi
HashMap mengimplementasikan antarmuka peta dan mewarisi AbstractMap. Antarmuka peta mendefinisikan aturan untuk pemetaan kunci ke nilai, dan kelas AbstractMap menyediakan implementasi backbone dari antarmuka peta untuk meminimalkan pekerjaan yang diperlukan untuk mengimplementasikan antarmuka ini. Bahkan, kelas AbstractMap telah menerapkan peta. Saya pikir harus lebih jelas untuk menandai peta lz di sini!
HashMap kelas publik <K, V> memperluas abstrak abstrak <k, v> mengimplementasikan peta <k, v>, dapat dikloning, serializable
2. Fungsi Konstruktor
HashMap menyediakan tiga konstruktor:
HashMap (): Membangun hashmap kosong dengan kapasitas awal default (16) dan faktor pemuatan default (0,75).
HashMap (int initialcapacity): Membangun hashmap kosong dengan kapasitas awal yang ditentukan dan faktor pemuatan default (0,75).
HashMap (int initialcapacity, float loadfactor): Membangun hashmap kosong dengan kapasitas awal dan faktor beban yang ditentukan.
Dua parameter disebutkan di sini: kapasitas awal, faktor pemuatan. Dua parameter ini adalah parameter penting yang mempengaruhi kinerja hashmap. Kapasitas mewakili jumlah ember di tabel hash. Kapasitas awal adalah kapasitas saat membuat tabel hash. Faktor pemuatan adalah skala yang dapat dicapai tabel hash sebelum kapasitasnya meningkat secara otomatis. Ini mengukur tingkat penggunaan ruang tabel hash. Semakin besar faktor beban menunjukkan semakin tinggi tingkat pemuatan tabel hash, dan sebaliknya. Untuk tabel hash menggunakan metode daftar tertaut, waktu rata -rata untuk menemukan elemen adalah O (1+A). Oleh karena itu, jika faktor beban lebih besar, ruang akan lebih sepenuhnya digunakan, tetapi konsekuensinya adalah penurunan efisiensi pencarian; Jika faktor beban terlalu kecil, data tabel hash akan terlalu jarang, menyebabkan limbah serius ke ruang. Faktor beban default sistem adalah 0,75, dan kami umumnya tidak perlu memodifikasinya.
HashMap adalah struktur data yang mendukung akses cepat. Untuk memahami kinerjanya, Anda harus memahami struktur datanya.
AKU AKU AKU. Struktur data
Kita tahu bahwa dua struktur yang paling umum digunakan di Java adalah array dan pointer simulasi (referensi). Hampir semua struktur data dapat diimplementasikan dalam kombinasi dengan keduanya, dan hal yang sama berlaku untuk hashmap. Faktanya, HashMap adalah "Hash Daftar Tertaut", sebagai berikut Struktur Datanya:
Dari gambar di atas, kita dapat melihat apakah implementasi hashmap yang mendasari adalah atau array, tetapi setiap item dalam array adalah rantai. Parameter inisial kapasitas mewakili panjang array. Berikut ini adalah kode sumber konstruktor hashmap:
hashmap publik (int initialcapacity, float loadfactor) {// kapasitas awal tidak boleh <0 if (InitialCapacity <0) melempar IllegalArgumentException baru ("Kapasitas Awal Ilegal:" + InitialCapacity); // Kapasitas awal tidak dapat> nilai kapasitas maksimum, kapasitas maksimum hashmap adalah 2^30 jika (inisial kapasitas> maksimum_capacity) initialcapacity = maximum_capacity; // faktor beban tidak boleh <0 if (loadfactor <= 0 || float.isnan (loadfactor)) melempar baru ilegalargumentException ("faktor beban ilegal:" + loadfactor); // Hitung nilai n-power dari 2 terkecil lebih besar dari kapasitas awal. Kapasitas int = 1; while (kapasitas <initialcapacity) kapasitas << = 1; this.loadFactor = loadFactor; // Tetapkan batas kapasitas hashmap. Ketika kapasitas hashmap mencapai batas ini, operasi ekspansi kapasitas akan dilakukan threshold = (int) (kapasitas * loadfactor); // inisialisasi tabel tabel tabel = entri baru [kapasitas]; init (); } Seperti yang dapat dilihat dari kode sumber, array tabel akan diinisialisasi setiap kali hashmap baru dibuat. Elemen array tabel adalah simpul entri.
entri kelas statis <k, v> mengimplementasikan peta.entry <k, v> {final k key; Nilai v; Entri <k, v> berikutnya; hash int akhir; /*** Membuat entri baru. */ Entri (int h, k k, v v, entri <k, v> n) {value = v; Berikutnya = n; kunci = k; hash = h; } .....}Di antara mereka, entri adalah kelas dalam hashmap, yang berisi kunci kunci, nilai nilai, node berikutnya, dan nilai hash. Ini sangat penting. Justru karena entri membentuk item dari array tabel sebagai daftar tertaut.
Di atas secara singkat menganalisis struktur data hashmap, dan di bawah ini akan mengeksplorasi bagaimana hashmap mengimplementasikan akses cepat.
4. Implementasi Penyimpanan: Put (Key, Vlaue)
Pertama, mari kita lihat kode sumbernya
public v put (K key, nilai v) {// Ketika kunci adalah null, hubungi metode putfornullkey untuk menyimpan posisi pertama nol dan tabel. Inilah sebabnya mengapa hashmap memungkinkan null if (key == null) mengembalikan putfornullkey (nilai); // Hitung nilai hash dari kunci int hash = hash (key.hashcode ()); ----- (1) // Hitung posisi nilai hash kunci dalam tabel array int i = indexfor (hash, tabel.length); ----- (2) // iterate dari i dan temukan lokasi di mana kunci disimpan untuk (entri <k, v> e = tabel [i]; e! = Null; e = e.next) {objek k; // menilai apakah ada nilai hash yang sama pada rantai (kunci adalah sama) // jika ada yang sama, secara langsung menimpa nilai dan mengembalikan nilai lama jika (e.hash == hash && ((k = e.key) == Key || key.Equals (k))) {v oldValue = e.value; // nilai lama = nilai baru e.value = nilai; E.RecordAccess (ini); Kembalikan OldValue; // mengembalikan nilai lama}} // Tingkatkan jumlah modifikasi dengan 1 modcount ++; // Tambahkan kunci dan nilai ke AddEntry Posisi I (hash, kunci, nilai, i); kembali nol; }Melalui kode sumber, kita dapat dengan jelas melihat bahwa proses data menyimpan hashmap adalah: pertama -tama tentukan apakah kunci itu nol. Jika nol, hubungi langsung metode putfornulley. Jika tidak kosong, pertama -tama hitung nilai hash dari kunci, dan kemudian cari posisi indeks di tabel array sesuai dengan nilai hash. Jika ada elemen pada posisi ini, bandingkan apakah kunci yang sama ada. Jika ada, timpa nilai kunci asli, jika tidak simpan elemen di kepala rantai (elemen pertama yang disimpan ditempatkan di ujung rantai). Jika tabel tidak memiliki elemen di sana, itu akan disimpan secara langsung. Proses ini tampaknya sederhana, tetapi sebenarnya memiliki informasi di dalam. Ada beberapa poin sebagai berikut:
1. Mari kita lihat iterasi terlebih dahulu. Alasan iterasi di sini adalah untuk mencegah keberadaan nilai kunci yang sama. Jika dua nilai hash (kunci) ditemukan sama, metode pemrosesan hashmap adalah untuk mengganti nilai lama dengan nilai baru. Kuncinya tidak diproses di sini, yang menjelaskan bahwa tidak ada dua kunci yang identik dalam hashmap.
2. Dalam tampilan (1) dan (2). Ini adalah inti dari hashmap. Pertama -tama, ada metode hash, yang merupakan perhitungan matematika murni, yaitu untuk menghitung nilai hash h.
static int hash (int h) {h ^ = (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }Kita tahu bahwa untuk tabel hashmap, distribusi data harus merata (yang terbaik adalah memiliki hanya satu elemen untuk setiap item, sehingga dapat ditemukan secara langsung). Itu tidak bisa terlalu ketat atau terlalu longgar. Terlalu ketat akan menyebabkan kecepatan kueri yang lambat, dan terlalu longgar akan membuang ruang. Setelah menghitung nilai hash, bagaimana kita dapat memastikan bahwa elemen tabel didistribusikan secara merata? Kami akan memikirkan akuisisi cetakan, tetapi karena akuisisi cetakan banyak mengkonsumsi, hashmap menanganinya seperti ini: panggil metode indexfor.
indeks int statis untuk (int h, panjang int) {return h & (length-1); }Panjang array hashmap yang mendasari selalu pada n-power 2, dan ada di konstruktor: kapasitas << = 1; Melakukan hal itu selalu dapat memastikan bahwa panjang array hashmap yang mendasarinya berada di N -Power 2. Ketika panjangnya adalah N daya dari 2, H & (panjang - 1) setara dengan mengambil modulus panjang, dan kecepatannya jauh lebih cepat daripada mengambil modulus secara langsung. Ini adalah optimalisasi hashmap dalam hal kecepatan. Adapun mengapa ini adalah 2 untuk kekuatan ke -n, penjelasan berikut adalah.
Mari kita kembali ke metode IndexFor, yang hanya memiliki satu pernyataan: h & (panjang - 1). Selain operasi modulus di atas, kalimat ini juga memiliki tanggung jawab yang sangat penting: mendistribusikan data tabel secara merata dan memanfaatkan ruang penuh.
Di sini kita berasumsi bahwa panjangnya adalah 16 (2^n) dan 15, dan h adalah 5, 6, dan 7.
Ketika n = 15, hasil 6 dan 7 adalah sama, yang berarti bahwa lokasi mereka yang disimpan dalam tabel adalah sama, yaitu, tabrakan terjadi, dan 6 dan 7 akan membentuk daftar terkait di satu lokasi, yang akan menyebabkan penurunan kecepatan kueri. Memang benar bahwa hanya tiga angka yang dianalisis di sini, tetapi tidak banyak, jadi mari kita lihat 0-15.
Dari bagan di atas, kita melihat total 8 tabrakan, dan pada saat yang sama, kami menemukan bahwa ruang yang terbuang sangat besar, tanpa catatan dalam 1, 3, 5, 7, 9, 11, 13, dan 15 tempat, yaitu, tidak ada data yang disimpan. Ini karena ketika mereka melakukan & operasi dengan 14, bit terakhir dari hasil yang mereka dapatkan akan selalu 0, yaitu, tidak mungkin untuk menyimpan data di lokasi 0001, 0011, 0101, 0111, 1001, 1011, 1101, 1111, dan 1111. Ruang berkurang dan peluang tumbukan akan meningkat lebih lanjut, yang akan mengarah dengan lambat. Ketika panjang = 16, panjang 1 = 15 adalah 1111. Kemudian ketika melakukan operasi rendah & operasi, nilainya selalu sama dengan nilai hash asli, dan ketika melakukan operasi bit tinggi, nilainya sama dengan nilai rendah-bit. Oleh karena itu, ketika panjang = 2^n, probabilitas tabrakan antara nilai hash yang berbeda relatif kecil, yang akan membuat data didistribusikan secara merata di array tabel dan kecepatan kueri lebih cepat.
Di sini kami meninjau proses put: Ketika kami ingin menambahkan sepasang nilai kunci ke hashmap, sistem pertama-tama akan menghitung nilai hash kunci, dan kemudian mengkonfirmasi lokasi yang disimpan dalam tabel berdasarkan nilai hash. Jika tidak ada elemen pada posisi ini, masukkan langsung. Kalau tidak, perolehan di atas daftar elemen pada saat itu dan bandingkan nilai hash dari kuncinya sesuai. Jika dua nilai hash sama dan nilai kunci sama (e.hash == hash && ((k = e.key) == key || key.equals (k))), nilai simpul asli ditimpa dengan nilai entri baru. Jika dua nilai hash sama tetapi nilai kunci tidak sama, masukkan simpul ke header daftar yang ditautkan. Untuk proses implementasi spesifik, lihat metode AddEntry, sebagai berikut:
void addEntry (int hash, k kunci, nilai v, int bucketIndex) {// Dapatkan entri entri <k, v> e = tabel [bucketIndex]; // Masukkan entri yang baru dibuat ke dalam indeks BucketIndex dan biarkan titik masuk baru ke tabel entri asli [bucketIndex] = entri baru <k, v> (hash, kunci, nilai, e); // Jika jumlah elemen dalam hashmap melebihi batas, kapasitas akan dua kali lebih besar jika (ukuran ++> = ambang batas) ukuran (2 * table.length); }Ada dua poin yang perlu diperhatikan dalam metode ini:
Salah satunya adalah generasi rantai. Ini adalah desain yang sangat elegan. Sistem selalu menambahkan objek entri baru ke bucketindex. Jika ada objek di BucketIndex, objek entri yang baru ditambahkan akan menunjuk ke objek entri asli, membentuk rantai entri. Namun, jika tidak ada objek entri di BucketIndex, yaitu E == NULL, maka objek entri yang baru ditambahkan menunjuk ke nol, dan tidak akan ada rantai entri yang dihasilkan.
2. Perluasan kapasitas.
Ketika jumlah elemen dalam hashmap meningkat, probabilitas tabrakan menjadi lebih besar dan lebih besar, dan panjang daftar tautan yang dihasilkan akan menjadi lebih lama dan lebih lama. Ini pasti akan mempengaruhi kecepatan hashmap. Untuk memastikan efisiensi hashmap, sistem harus memperluas kapasitas pada titik kritis tertentu. Titik kritis ini adalah ketika jumlah elemen dalam hashmap sama dengan panjang array tabel* faktor beban. Tetapi penskalaan adalah proses yang sangat memakan waktu karena membutuhkan penghitungan ulang lokasi data ini dalam array tabel baru dan menyalinnya. Jadi jika kita telah meramalkan jumlah elemen dalam hashmap, maka jumlah elemen yang telah ditetapkan dapat secara efektif meningkatkan kinerja hashmap.
5. Implementasi Membaca: Dapatkan (Kunci)
Dibandingkan dengan penyimpanan hashmap, penarikan relatif sederhana. Temukan entri pada indeks di array tabel melalui nilai hash kunci, dan kemudian mengembalikan nilai yang sesuai dengan kunci.
public v get (tombol objek) {// if null, hubungi metode getFornullKey untuk mengembalikan nilai yang sesuai jika (key == null) return getFornullKey (); // Hitung kode hash -nya berdasarkan nilai kode hashcode dari hash hash = hash (key.hashcode ()); // ambil nilai pada indeks yang ditentukan dalam array tabel untuk (entri <k, v> e = tabel [indexfor (hash, tabel.length)]; e! = Null; e = e.next) {objek k; // Jika tombol yang dicari sama dengan kunci yang dicari, kembalikan nilai yang sesuai IF (e.hash == hash && ((k = e.key) == Key || key.equals (k))) mengembalikan E.Value; } return null; } Di sini, nilai yang dapat dengan cepat diambil berdasarkan kunci tidak hanya tidak dapat dipisahkan dari struktur data hashmap, tetapi juga banyak hubungannya dengan masuk. Seperti disebutkan sebelumnya, HashMap tidak menyimpan kunci dan nilai secara terpisah dalam prosedur tersimpan, tetapi diproses secara keseluruhan nilai kunci, yang merupakan objek entri. Pada saat yang sama, nilainya hanya setara dengan lampiran kunci. Selama proses penyimpanan, sistem menentukan lokasi penyimpanan entri di array tabel berdasarkan kode hash dari kunci, dan dalam proses pengambilan, objek entri yang sesuai juga diambil sesuai dengan kode hash dari kunci.
Tautan asli: http://www.cnblogs.com/chenssy/p/3521565.html
Di atas adalah semua konten artikel ini. Saya berharap ini akan membantu untuk pembelajaran semua orang dan saya harap semua orang akan lebih mendukung wulin.com.