Sebagian besar pengembang Java menggunakan peta, terutama hashmap. HashMap adalah cara sederhana namun kuat untuk menyimpan dan mendapatkan data. Tetapi berapa banyak pengembang yang tahu bagaimana hashmap bekerja secara internal? Beberapa hari yang lalu, saya membaca banyak kode sumber java.util.hashmap (termasuk Java 7 dan Java 8) untuk mendapatkan pemahaman yang mendalam tentang struktur data dasar ini. Dalam posting ini, saya akan menjelaskan implementasi java.util.hashmap, menjelaskan fitur -fitur baru yang ditambahkan dalam implementasi Java 8, dan membahas kinerja, memori, dan beberapa masalah yang diketahui saat menggunakan HashMap.
Penyimpanan internal
Kelas Java Hashmap mengimplementasikan antarmuka peta <k, v>. Metode utama dalam antarmuka ini meliputi:
V put (key k, nilai v) v get (kunci objek) v lepaskan (tombol objek) boolean containskey (tombol objek)
HashMap menggunakan entri kelas internal <K, V> untuk menyimpan data. Kelas dalam ini adalah pasangan nilai kunci sederhana dengan dua data tambahan:
Referensi ke entri lain, sehingga hashmap dapat menyimpan objek seperti daftar tautan.
Nilai hash yang digunakan untuk mewakili kunci. Menyimpan nilai ini dapat mencegah hashmap regenerasi nilai hash yang sesuai dengan kunci setiap kali diperlukan.
Berikut adalah bagian dari kode untuk entri <k, v> di bawah java 7:
Entri kelas statis <k, v> mengimplementasikan peta.entry <k, v> {final k key; v nilai; entri <k, v> next; int hash;…}HashMap menyimpan data ke dalam beberapa daftar searah (kadang -kadang disebut ember atau wadah orbin). Semua daftar didaftarkan dalam array entri (entri <k, v> [] array), dan panjang default dari array internal ini adalah 16.
Gambar berikut menjelaskan penyimpanan internal instance hashmap, yang berisi array objek yang dapat dibatalkan. Setiap objek terhubung ke objek lain, sehingga membentuk daftar tertaut.
Semua kunci dengan nilai hash yang sama akan ditempatkan dalam daftar tertaut yang sama (bucket). Kunci dengan hash yang berbeda mungkin berakhir di ember yang sama.
Ketika Pengguna Panggilan Letakkan (Key K, Value V) atau Dapatkan (Kunci Objek), program menghitung indeks bucket, objek harus masuk. Program kemudian akan mengulangi daftar yang sesuai untuk menemukan objek entri dengan kunci yang sama (menggunakan metode Equals () dari kunci).
Dalam kasus panggilan get (), program akan mengembalikan objek entri yang sesuai dengan nilai (jika ada objek entri).
Untuk panggilan untuk menempatkan (Key k, nilai V), jika objek entri sudah ada, program akan menggantikan nilai dengan nilai baru, jika tidak program akan membuat entri baru (kunci dan nilai dalam parameter) di header daftar tertaut satu arah.
Indeks bucket (daftar tertaut) dihasilkan melalui 3 langkah peta:
Pertama dapatkan kode hash dari kunci.
Program ini mengulangi kode hash untuk memblokir fungsi hash yang buruk untuk kunci, karena ini memiliki potensi untuk menempatkan semua data pada indeks yang sama (bucket) dari array internal.
Program ini mengambil kode hash duplikat dan menggunakan bitmask panjang array (minimum 1) untuk itu. Operasi ini memastikan bahwa indeks tidak akan lebih besar dari ukuran array. Anda dapat menganggapnya sebagai fungsi modulus yang dioptimalkan yang dihitung.
Berikut adalah kode sumber untuk menghasilkan indeks:
// Fungsi "Rehash" di Java 7 yang mengambil kode hash dari hash keystatic int (int h) {h ^ = (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >> 4);} // Fungsi "Rehash" di java 8 yang secara langsung mengambil KEYSTIC THE KEYSTIC THE KEYSTIC? 0: (h = key.hashCode ()) ^ (h >>> 16);} // Fungsi yang mengembalikan indeks dari indeks int hashstatic yang diulang untuk (int h, panjang int) {return h & (length-1);}Untuk bekerja lebih efisien, ukuran array dalam harus menjadi kekuatan 2. Mari kita lihat mengapa:
Dengan asumsi bahwa panjang array adalah 17, nilai topeng adalah 16 (array panjang-1). Representasi biner 16 adalah 0 ... 010000, sehingga untuk nilai apa pun h, hasil "H&6" adalah 16 atau 0. Ini berarti bahwa array panjang 17 hanya dapat diterapkan pada dua ember: satu adalah 0 dan yang lainnya adalah 16, yang tidak terlalu efisien. Tetapi jika Anda mengatur panjang array ke kekuatan 2, misalnya 16, maka pengindeksan bitwise berfungsi untuk "H & 15". Representasi biner dari 15 adalah 0 ... 001111, dan output nilai dengan rumus indeks dapat berkisar dari 0 hingga 15, sehingga array dengan panjang 16 dapat sepenuhnya digunakan. Misalnya:
Jika h = 952, representasi binernya adalah 0..01110111000, dan indeks yang sesuai adalah 0 ... 01000 = 8
Jika h = 1576, representasi binernya adalah 0..011000101000, dan indeks yang sesuai adalah 0 ... 01000 = 8
Jika h = 12356146, representasi binernya adalah 0..010111001000101010010, indeks yang sesuai adalah 0 ... 00010 = 2
Jika h = 59843, representasi binernya adalah 0..01110100111001111, indeks yang sesuai adalah 0 ... 00011 = 3
Mekanisme ini transparan untuk pengembang: jika ia memilih hashmap dengan panjang 37, peta akan secara otomatis memilih nilai daya berikutnya lebih besar dari 37 (64) sebagai panjang array internal.
Ubah Ulang Secara Otomatis
Setelah mendapatkan indeks, metode get (), put () atau lepaskan () akan mengakses daftar tertaut yang sesuai untuk melihat apakah objek entri untuk kunci yang ditentukan sudah ada. Tanpa modifikasi, mekanisme ini dapat menyebabkan masalah kinerja, karena metode ini memerlukan iterasi pada seluruh daftar untuk melihat apakah objek entri ada. Asumsikan bahwa panjang array internal mengambil nilai default 16, dan Anda perlu menyimpan 2.000.000 catatan. Dalam kasus terbaik, akan ada 125.000 objek masuk per daftar tertaut (2.000.000/16). Metode get (), lepas () dan put () memerlukan 125.000 iterasi setiap kali mereka dieksekusi. Untuk menghindari hal ini, HashMap dapat meningkatkan panjang array internal, sehingga memastikan bahwa hanya beberapa objek entri yang dipertahankan dalam daftar yang ditautkan.
Saat Anda membuat hashmap, Anda dapat menentukan panjang awal dan loadfactor melalui konstruktor berikut:
</pe> hashmap publik (int initialcapacity, float loadfactor) <Per>
Jika Anda tidak menentukan parameter, nilai kapasitas inisial default adalah 16, dan nilai loadfactor default adalah 0,75. Kapasitas awal mewakili panjang daftar tertaut dari array internal.
Saat Anda menggunakan metode put (...) untuk menambahkan pasangan nilai kunci baru ke peta, metode ini memeriksa apakah panjang array dalam perlu ditingkatkan. Untuk mencapai ini, peta menyimpan 2 data:
Ukuran peta: Ini mewakili jumlah catatan dalam hashmap. Kami memperbarui nilai saat kami memasukkan atau menghapusnya ke dalam hashmap.
Threshold: Ini sama dengan panjang array internal*Loadfactor, dan ambang ini juga akan diperbarui pada waktu yang sama setiap kali panjang array internal disesuaikan.
Sebelum menambahkan objek entri baru, metode put (...) memeriksa apakah ukuran peta saat ini lebih besar dari ambang batas. Jika lebih besar dari ambang batas, ia menciptakan array baru dengan dua kali lipat dari array internal saat ini. Karena ukuran array baru telah berubah, fungsi indeks (yaitu, hasil operasi bit yang mengembalikan "nilai hash dari kunci & (panjang array -1)") juga berubah. Mengubah ukuran array membuat dua ember baru (daftar tertaut) dan menugaskan kembali semua objek entri yang ada ke ember. Tujuan menyesuaikan ukuran array adalah untuk mengurangi ukuran daftar yang ditautkan, sehingga mengurangi waktu eksekusi put (), lepas () dan get () metode. Untuk semua objek entri yang sesuai dengan kunci dengan nilai hash yang sama, mereka dialokasikan untuk ember yang sama setelah mengubah ukuran. Namun, jika nilai hash dari dua objek entri berbeda, tetapi mereka berada pada ember yang sama sebelumnya, maka setelah penyesuaian, tidak ada jaminan bahwa mereka masih berada pada ember yang sama.
Gambar ini menggambarkan situasi array internal pra-adjust dan setelah penyesalan. Sebelum menyesuaikan panjang array, untuk mendapatkan objek entri E, peta perlu mengulangi daftar tertaut yang berisi 5 elemen. Setelah menyesuaikan panjang array, metode get () yang sama hanya perlu melintasi daftar tertaut yang berisi 2 elemen, sehingga kecepatan lari metode get () setelah menyesuaikan panjang array meningkat 2 kali.
Keamanan utas
Jika Anda sudah sangat akrab dengan HashMap, Anda pasti tahu bahwa itu bukan utas yang aman, tetapi mengapa? Misalnya misalkan Anda memiliki utas penulis yang hanya akan memasukkan data yang ada ke dalam peta, utas pembaca yang akan membaca data dari peta, jadi mengapa tidak berhasil?
Karena di bawah mekanisme ubah ukuran otomatis, jika utas mencoba menambah atau mendapatkan objek, peta dapat menggunakan nilai indeks lama, sehingga ember baru di mana objek entri berada tidak akan ditemukan.
Dalam kasus terburuk, ketika 2 utas memasukkan data secara bersamaan, 2 panggilan () panggilan akan dimulai pada saat yang sama dan array akan secara otomatis mengubah ukuran. Karena dua utas memodifikasi daftar tertaut secara bersamaan, ada kemungkinan bahwa peta keluar dalam loop internal dari daftar tertaut. Jika Anda mencoba mendapatkan data dari daftar dengan loop dalam, metode GET () tidak akan pernah berakhir.
Hashtable menyediakan implementasi yang aman-utas yang mencegah hal di atas terjadi. Namun, karena semua operasi CRUD yang sinkron sangat lambat. Misalnya, jika panggilan utas 1 dapatkan (key1), maka panggilan utas 2 dapatkan (key2), dan panggilan utas 2 dapatkan (key3), lalu pada waktu yang ditentukan, hanya 1 utas yang dapat memperoleh nilainya, tetapi semua 3 utas dapat mengakses data ini secara bersamaan.
Sejak Java 5, kami memiliki implementasi hashmap yang lebih baik dan aman: ConcurrenthashMap. Untuk ConcurrentMap, hanya ember yang disinkronkan, sehingga jika beberapa utas tidak menggunakan ember yang sama atau mengubah ukuran array internal, mereka dapat memanggil metode GET (), lepaskan () atau put () pada saat yang sama. Dalam aplikasi multithreaded, pendekatan ini adalah pilihan yang lebih baik.
Invariance of Bonds
Mengapa implementasi yang baik untuk menggunakan string dan bilangan bulat sebagai kunci untuk hashmap? Terutama karena mereka tidak berubah! Jika Anda memilih untuk membuat kelas sendiri sebagai kunci, tetapi Anda tidak dapat menjamin bahwa kelas tidak dapat diubah, Anda mungkin kehilangan data di dalam HashMap.
Mari kita lihat kasus penggunaan berikut:
Anda memiliki kunci yang nilai internalnya adalah "1".
Jika Anda memasukkan objek ke dalam hashmap, kuncinya adalah "1".
HashMap menghasilkan nilai hash dari kode hash kunci (mis. "1").
Peta menyimpan nilai hash ini dalam catatan yang baru dibuat.
Anda mengubah nilai internal kunci dan mengubahnya menjadi "2".
Nilai hash dari kunci berubah, tetapi hashmap tidak tahu ini (karena nilai hash lama disimpan).
Anda mencoba mendapatkan objek yang sesuai dengan kunci yang dimodifikasi.
Peta menghitung nilai hash dari kunci baru (mis. "2") untuk menemukan daftar tertaut (bucket) di mana objek entri berada.
Kasus 1: Karena Anda telah memodifikasi kunci, peta akan mencoba mencari objek entri dalam ember yang salah, tetapi tidak ditemukan.
Kasus 2: Anda beruntung bahwa ember yang dihasilkan oleh kunci yang dimodifikasi dan ember yang dihasilkan oleh kunci lama adalah sama. Peta kemudian akan melintasi daftar yang ditautkan dan objek entri dengan kunci yang sama telah ditemukan. Tetapi untuk menemukan kunci, peta pertama -tama akan membandingkan nilai hash kunci dengan memanggil metode Equals (). Karena kunci yang dimodifikasi akan menghasilkan nilai hash yang berbeda (nilai hash lama disimpan dalam catatan), maka MAP tidak memiliki cara untuk menemukan objek entri yang sesuai dalam daftar yang ditautkan.
Berikut adalah contoh Java di mana kami memasukkan dua pasangan nilai kunci ke dalam peta, dan kemudian saya memodifikasi kunci pertama dan mencoba untuk mendapatkan dua objek. Anda akan menemukan bahwa hanya objek kedua yang dikembalikan dari peta, objek pertama telah "hilang" di hashmap:
kelas publik mutableKeyTest {public static void main (string [] args) {class mykey {integer i; public void seti (integer i) {this.i = i;} public mykey (integer i) {this.i = i;}@overridepublic int hashcode () {return i; oBJ {oBJyOof@overridepublic int hashcode () {return i; MyKey) {return i.equals(((MyKey) obj).i);} elsereturn false;}}Map<MyKey, String> myMap = new HashMap<>();MyKey key1 = new MyKey(1);MyKey key2 = new MyKey(2);myMap.put(key1, "test " + 1);myMap.put(key2, "test " + 2);// modifying key1key1.seti (3); string test1 = mymap.get (key1); string test2 = mymap.get (key2); system.out.println ("test1 =" + test1 + "test2 =" + test2);}}Output dari kode di atas adalah "test1 = null test2 = test 2". Seperti yang kami harapkan, MAP tidak memiliki kemampuan untuk mendapatkan string 1 yang sesuai dengan kunci yang dimodifikasi 1.
Perbaikan Java 8
Di Java 8, implementasi internal dalam hashmap telah banyak dimodifikasi. Memang, Java 7 menggunakan 1000 baris kode untuk mengimplementasikannya, sedangkan Java 8 menggunakan 2000 baris kode. Sebagian besar dari apa yang saya jelaskan sebelumnya masih benar di Java 8, kecuali menggunakan daftar tertaut untuk menyimpan objek entri. Di Java 8, kami masih menggunakan array, tetapi akan disimpan di Node, yang berisi informasi yang sama dengan objek entri sebelumnya dan juga menggunakan daftar tertaut:
Berikut adalah bagian dari kode yang mengimplementasikan simpul di Java 8:
Node kelas statis <k, v> mengimplementasikan peta.entry <k, v> {final int hash; kunci k final; value; node <k, v> next;Jadi apa perbedaan besar dibandingkan dengan Java 7? Nah, node dapat diperluas ke treenode. Treeenode adalah struktur data dari pohon merah dan hitam yang dapat menyimpan lebih banyak informasi, sehingga kami dapat menambahkan, menghapus atau mendapatkan elemen di bawah kompleksitas O (log (n)). Contoh berikut menjelaskan semua informasi yang disimpan oleh Treenode:
kelas akhir statis treenode <k, v> meluas linkedhashmap.entry <k, v> {hash final int; // Diwarisi dari Node <K, V> Key K Final; // diwarisi dari node <k, v> v nilai; // diwarisi dari simpul <k, v> node <k, v> selanjutnya; // diwarisi dari simpul <k, v> entri <k, v> sebelum, setelah; // diwarisi dari linkedhashmap.entry <k, v> induk; treenode <k, v> kiri; treenode <k, v> kanan; treenode <k, v> prev; boolean merah;Pohon merah dan hitam adalah pohon-pohon pencarian biner yang menyeimbangkan diri. Mekanisme internalnya memastikan bahwa panjangnya selalu log (n), apakah kita menambahkan atau menghapus node. Manfaat paling penting dari menggunakan jenis pohon ini adalah bahwa banyak data dalam tabel internal memiliki indeks yang sama (bucket). Pada saat ini, kompleksitas pencarian pohon adalah O (log (n)), dan untuk daftar yang ditautkan, kompleksitasnya adalah O (n) untuk melakukan operasi yang sama.
Seperti yang Anda lihat, kami menyimpan lebih banyak data di pohon daripada daftar tertaut. Menurut prinsip warisan, tabel internal dapat berisi simpul (daftar tertaut) atau treenode (pohon merah dan hitam). Oracle memutuskan untuk menggunakan dua struktur data ini sesuai dengan aturan berikut:
- Untuk indeks yang ditentukan (bucket) dalam tabel internal, jika jumlah node lebih dari 8, daftar yang ditautkan akan dikonversi menjadi pohon merah dan hitam.
- Untuk indeks yang ditentukan (bucket) dalam tabel internal, jika jumlah node kurang dari 6, pohon merah dan hitam akan dikonversi menjadi daftar yang ditautkan.
Gambar ini menggambarkan array internal dalam hashmap Java 8, yang berisi kedua pohon (bucket 0) dan daftar tertaut (bucket 1, 2 dan 3). Bucket 0 adalah struktur pohon karena mengandung lebih dari 8 node.
Overhead memori
Java 7
Menggunakan hashmap mengkonsumsi beberapa memori. Di Java 7, HashMap merangkum pasangan nilai kunci menjadi objek entri, objek entri berisi informasi berikut:
Referensi ke catatan berikutnya nilai hash yang telah dihitung sebelumnya (integer)
Referensi ke kunci dan referensi ke nilai
Selain itu, HashMap di Java 7 menggunakan array internal objek masuk. Misalkan hashmap Java 7 berisi elemen N dan array internalnya memiliki kapasitas, maka konsumsi memori tambahan adalah tentang:
sizeof (integer)* n + sizeof (referensi)* (3* n + c)
di dalam:
Ukuran bilangan bulat adalah 4 byte
Ukuran referensi tergantung pada JVM, sistem operasi, dan prosesor, tetapi biasanya 4 byte.
Ini berarti bahwa overhead memori total biasanya 16 * n + 4 * byte kapasitas.
Catatan: Setelah peta secara otomatis diubah ukurannya, nilai kapasitas adalah daya terkecil berikutnya dari 2 lebih besar dari N.
Catatan: Mulai dari Java 7, HashMap mengadopsi mekanisme pemuatan malas. Ini berarti bahwa bahkan jika Anda menentukan ukuran untuk hashmap, array internal yang digunakan (mengonsumsi byte kapasitas 4*) yang tidak dialokasikan dalam memori sebelum kami pertama kali menggunakan metode put ().
Java 8
Dalam implementasi Java 8, hitung penggunaan memori menjadi lebih rumit karena node dapat menyimpan data yang sama dengan entri, atau tambahkan 6 referensi dan properti boolean (menentukan apakah itu treenode).
Jika semua node hanyalah node, maka memori yang dikonsumsi oleh Java 8 Hashmap sama dengan yang dikonsumsi oleh HashMap Java 7.
Jika semua node adalah Treeenode, maka memori yang dikonsumsi oleh Java 8 Hashmap menjadi:
N * sizeof (integer) + n * sizeof (boolean) + sizeof (referensi) * (9 * n + kapasitas)
Dalam sebagian besar JVM standar, hasil dari rumus di atas adalah 44 * n + 4 * byte kapasitas.
Masalah kinerja
Hashmap asimetris vs hashmap seimbang
Dalam kasus terbaik, baik metode get () dan put () hanya memiliki kompleksitas O (1). Namun, jika Anda tidak peduli dengan fungsi hash dari kunci, metode put () dan get () Anda dapat dijalankan dengan sangat lambat. Eksekusi yang efisien dari metode PUT () dan GET () tergantung pada data yang dialokasikan untuk indeks yang berbeda dari array internal (bucket). Jika fungsi hash dari kunci tidak dirancang dengan benar, Anda akan mendapatkan partisi asimetris (terlepas dari ukuran data internal). Semua metode put () dan get () akan menggunakan daftar tertaut terbesar, yang akan lambat dieksekusi karena membutuhkan iterasi pada semua catatan dalam daftar tertaut. Dalam kasus terburuk (jika sebagian besar data ada pada ember yang sama), kompleksitas waktu Anda menjadi O (n).
Ini adalah contoh visual. Grafik pertama menggambarkan hashmap asimetris dan grafik kedua menggambarkan hashmap yang disamakan.
Skewedhashmap
Dalam hashmap asimetris ini, akan membutuhkan waktu untuk menjalankan metode get () dan meletakkan () pada bucket 0. Mendapatkan catatan k mengambil 6 iterasi.
Dalam hashmap yang seimbang ini, hanya perlu 3 iterasi untuk mendapatkan catatan K. Kedua hashmap ini menyimpan jumlah data yang sama dan array internal memiliki ukuran yang sama. Satu -satunya perbedaan adalah fungsi hash dari kunci, yang digunakan untuk mendistribusikan catatan ke ember yang berbeda.
Berikut adalah contoh ekstrem yang ditulis dalam Java, di mana saya menggunakan fungsi hash untuk memasukkan semua data ke dalam daftar tertaut yang sama (bucket) dan kemudian saya menambahkan 2.000.000 lembar data.
public class Test {public static void main(String[] args) {class MyKey {Integer i;public MyKey(Integer i){this.i =i;}@Overridepublic int hashCode() {return 1;}@Overridepublic boolean equals(Object obj) {…}}Date begin = new Date();Map <MyKey,String> myMap= new HashMap <> (2_500_000,1); untuk (int i = 0; i <2_000_000; i ++) {myMap.put (mykey baru (i), "test"+i);} tanggal = tanggal baru (); batang System.out.println ("durasi (ms)"++(end.gettime.Konfigurasi mesin saya adalah Core i5-2500K @ 3.6G, dan dibutuhkan lebih dari 45 menit untuk berjalan di bawah Java 8U40 (saya menghentikan proses setelah 45 menit). Jika saya menjalankan kode yang sama, tetapi saya menggunakan fungsi hash seperti ini:
@OverridEpublic int hashCode () {int key = 2097152-1; Kembali Kunci+2097152*i;}Dibutuhkan 46 detik untuk menjalankannya, yang jauh lebih baik dari sebelumnya! Fungsi hash baru lebih masuk akal daripada fungsi hash lama saat memproses partisi hash, jadi memanggil metode put () lebih cepat. Jika Anda menjalankan kode yang sama sekarang, tetapi gunakan fungsi hash di bawah ini, ia memberikan partisi hash yang lebih baik:
@Overridepublic int hashCode () {return i;}Sekarang hanya butuh 2 detik!
Saya harap Anda dapat menyadari betapa pentingnya fungsi hash. Jika Anda menjalankan tes yang sama pada Java 7, yang pertama dan kedua akan lebih buruk (karena metode put () dalam Java 7 memiliki kompleksitas O (n), sedangkan kompleksitas dalam Java 8 memiliki O (log (n)).
Saat menggunakan hashmap, Anda perlu menemukan fungsi hash untuk kunci yang dapat menyebarkan kunci ke ember yang paling mungkin. Untuk melakukan ini, Anda perlu menghindari konflik hash. Objek string adalah kunci yang sangat baik karena memiliki fungsi hash yang bagus. Integer juga baik karena hashnya adalah nilainya sendiri.
Mengubah ukuran overhead
Jika Anda perlu menyimpan sejumlah besar data, Anda harus menentukan kapasitas awal saat membuat hashmap, yang harus dekat dengan ukuran yang Anda inginkan.
Jika Anda tidak melakukan ini, peta akan menggunakan ukuran default, mis. 16, dan nilai factorload adalah 0,75. The first 11 calls to put() method will be very fast, but the 12th (16*0.75) call will create a new internal array with length 32 (and the corresponding linked list/tree), and the 13th to 22nd call to put() method will be very fast, but the 23rd (32*0.75) call will recreate (again) a new internal array, and the length of the array will be doubled. Maka operasi pengubahan ukuran internal akan dipicu ketika metode put () disebut 48th, 96th, 192nd…. Jika jumlah data tidak besar, pengoperasian membangun kembali array internal akan sangat cepat, tetapi ketika jumlah data besar, waktu yang dihabiskan dapat berkisar dari detik hingga menit. Dengan menentukan ukuran peta yang diinginkan selama inisialisasi, Anda dapat menghindari konsumsi yang disebabkan oleh pengubah ukuran operasi.
Tetapi ada juga kelemahan di sini: jika Anda mengatur array menjadi sangat besar, misalnya 2^28, tetapi Anda hanya menggunakan 2^26 ember dalam array, maka Anda akan membuang banyak memori (sekitar 2^30 byte dalam contoh ini).
sebagai kesimpulan
Untuk kasus penggunaan yang sederhana, Anda tidak perlu tahu cara kerja HashMap, karena Anda tidak akan melihat perbedaan antara O (1), O (n), dan O (log (n)). Tetapi selalu bermanfaat untuk memahami mekanisme di balik struktur data yang sering digunakan ini. Selain itu, ini adalah pertanyaan wawancara yang khas untuk posisi pengembang Java.
Untuk volume data yang besar, menjadi sangat penting untuk memahami bagaimana hashmap bekerja dan memahami pentingnya fungsi hash untuk kunci.
Saya harap artikel ini dapat membantu Anda memiliki pemahaman yang mendalam tentang implementasi HashMap.