Geekly articles weekly

HashMap Internal di Jawa

[catatan dari penulis terjemahan] Terjemahan dibuat untuk kebutuhan sendiri, tetapi jika ternyata bermanfaat bagi seseorang, maka dunia menjadi setidaknya sedikit, tetapi lebih baik! Artikel asli - Kerja Internal HashMap di Jawa


Pada artikel ini, kita akan melihat bagaimana metode get and put dalam koleksi HashMap bekerja secara internal. Operasi apa yang dilakukan. Bagaimana hashing terjadi. Bagaimana nilai tersebut diambil dengan kunci. Bagaimana pasangan nilai kunci disimpan?


Seperti pada artikel sebelumnya , HashMap berisi larik Node dan Node dapat mewakili kelas yang berisi objek berikut:


  1. int - hash
  2. K adalah kuncinya
  3. V adalah nilainya
  4. Node - item berikutnya

Sekarang kita akan melihat bagaimana semuanya bekerja. Pertama, kita akan melihat proses hashing.


Hashing


Hashing adalah proses mengubah objek ke bentuk integer, dilakukan dengan menggunakan metode hashCode (). Sangat penting untuk mengimplementasikan metode hashCode () dengan benar untuk memastikan kinerja terbaik dari kelas HashMap.


Di sini saya menggunakan kelas Key saya sendiri dan dengan cara ini saya dapat mengganti metode hashCode () untuk menunjukkan berbagai skrip. Kelas kunci saya:


//   Key    hashCode() //  equals() class Key { String key; Key(String key) { this.key = key; } @Override public int hashCode() { return (int)key.charAt(0); } @Override public boolean equals(Object obj) { return key.equals((String)obj); } }

Di sini, metode hashCode () yang diganti menimpa kode ASCII dari karakter pertama dari string. Jadi, jika karakter pertama dari string adalah sama, maka kode hash akan sama. Jangan gunakan logika yang sama di program Anda.


Kode ini hanya untuk tujuan demonstrasi. Karena HashCode menerima kunci null, kode hash nol akan selalu menjadi 0.


Metode HashCode ()


Metode hashCode () digunakan untuk mendapatkan kode hash objek. Metode hashCode () dari kelas Object mengembalikan referensi memori integer (kode hash identitas ). Tanda tangan dari metode public native hashCode() . Ini menunjukkan bahwa metode ini diimplementasikan sebagai asli, karena di java tidak ada metode untuk mendapatkan referensi ke objek. Diijinkan untuk mendefinisikan implementasi metode hashCode () Anda sendiri. Di kelas HashMap, metode hashCode () digunakan untuk menghitung bucket dan karenanya menghitung indeks.


Metode equals ()


Metode equals digunakan untuk menguji dua objek untuk kesetaraan. Metode ini diterapkan di kelas Object. Anda bisa menimpanya di kelas Anda sendiri. Di kelas HashMap, metode equals () digunakan untuk memverifikasi kesetaraan kunci. Dalam hal kunci sama, metode equals () mengembalikan true, jika tidak palsu.


Keranjang


Bucket adalah satu-satunya elemen array HashMap. Digunakan untuk menyimpan node (Nodes). Dua atau lebih node dapat memiliki bucket yang sama. Dalam hal ini, struktur data daftar tertaut digunakan untuk menautkan node. Bucket berbeda dalam kapasitas (kapasitas properti). Hubungan antara bucket dan kapasitas adalah sebagai berikut:


 capacity = number of buckets * load factor

Satu bucket dapat memiliki lebih dari satu node, tergantung pada implementasi metode hashCode (). Semakin baik metode hashCode () Anda diimplementasikan, semakin baik ember Anda akan digunakan.


Perhitungan Indeks HashMap


Kode hash kunci bisa cukup besar untuk membuat array. Kode hash yang dihasilkan dapat berada dalam kisaran tipe integer dan jika kita membuat array dengan ukuran ini, kita dapat dengan mudah mendapatkan outOfMemoryException. Oleh karena itu, kami membuat indeks untuk meminimalkan ukuran array. Intinya, operasi berikut dilakukan untuk menghitung indeks:


 index = hashCode(key) & (n-1).

di mana n sama dengan jumlah ember atau nilai panjang array. Dalam contoh kita, saya menganggap n sebagai nilai default 16.


  • awalnya hashMap kosong: di sini ukuran hashmap adalah 16:

 HashMap map = new HashMap();

HashMap:


  • masukkan pasangan Kunci - Nilai: tambahkan satu kunci pasangan - nilai di akhir HashMap

 map.put(new Key("vishal"), 20);

Langkah-langkah:


  1. Hitung nilai kunci {"vishal"}. Ini akan dihasilkan sebagai 118.


  2. Hitung indeks menggunakan metode index , yang akan menjadi 6.


  3. Buat objek simpul.


     { int hash = 118 // {"vishal"}  ,  //   Key Key key = {"vishal"} Integer value = 20 Node next = null }

  4. Tempatkan objek pada posisi dengan indeks 6, jika ruang kosong.



HashMap sekarang terlihat seperti ini:



  • menambahkan pasangan nilai kunci lainnya: sekarang tambahkan pasangan lain

 map.put(new Key("sachin"), 30);

Langkah-langkah:


  1. Hitung nilai kunci {"sachin"}. Ini akan dihasilkan sebagai 115.


  2. Hitung indeks menggunakan metode index , yang akan menjadi 3.


  3. Buat objek simpul.


     { int hash = 115 Key key = {"sachin"} Integer value = 30 Node next = null }

  4. Tempatkan objek pada posisi dengan indeks 3, jika ruang kosong.



HashMap sekarang terlihat seperti ini:



  • dalam kasus tabrakan: sekarang tambahkan pasangan lain

 map.put(new Key("vaibhav"), 40);

Langkah-langkah:


  1. Hitung nilai kunci {"vaibhav"}. Ini akan dihasilkan sebagai 118.


  2. Hitung indeks menggunakan metode index , yang akan menjadi 6.


  3. Buat objek simpul.


     { int hash = 118 Key key = {"vaibhav"} Integer value = 20 Node next = null }

  4. Tempatkan objek pada posisi dengan indeks 6, jika ruang kosong.


  5. Dalam hal ini, objek lain sudah ada di posisi dengan indeks 6, kasus ini disebut tabrakan.


  6. Dalam hal ini, periksa dengan metode hashCode () dan equals () yang kedua kunci sama.


  7. Jika kuncinya sama, ganti nilainya sekarang dengan yang baru.


  8. Jika tidak, tautkan objek baru dan lama menggunakan struktur data "daftar tertaut" dengan menentukan tautan ke objek berikutnya di objek saat ini dan menyimpan keduanya di bawah indeks 6.



HashMap sekarang terlihat seperti ini:



[catatan dari penulis terjemahan] Gambar diambil dari artikel asli dan awalnya mengandung kesalahan. Referensi ke objek berikutnya dalam objek vishal dengan indeks 6 tidak nol, itu berisi pointer ke objek vaibhav.


  • kami mendapatkan nilai dengan kunci sachin:

 map.get(new Key("sachin"));

Langkah-langkah:


  1. Hitung kode hash objek {{sachin »}. Itu dihasilkan sebagai 115.


  2. Hitung indeks menggunakan metode index , yang akan menjadi 3.


  3. Pergi ke indeks 3 dan bandingkan kunci elemen pertama dengan nilai yang ada. Jika mereka sama, putar nilainya, jika tidak, periksa elemen berikutnya, jika ada.


  4. Dalam kasus kami, elemen ditemukan dan nilai kembali adalah 30.



  • kami mendapatkan nilai dengan vaibahv kunci:

 map.get(new Key("vaibhav"));

Langkah-langkah:


  1. Hitung kode hash dari objek {"vaibhav"}. Itu dihasilkan sebagai 118.


  2. Hitung indeks menggunakan metode index , yang akan menjadi 6.


  3. Pergi ke indeks 6 dan bandingkan kunci elemen pertama dengan nilai yang ada. Jika mereka sama, putar nilainya, jika tidak, periksa elemen berikutnya, jika ada.


  4. Dalam hal ini, itu tidak ditemukan dan objek simpul berikutnya bukan nol.


  5. Jika objek simpul berikutnya adalah nol, kembalikan nol.


  6. Jika objek simpul berikutnya bukan nol, buka dan ulangi tiga langkah pertama hingga elemen ditemukan atau objek simpul berikutnya adalah nol.



 // Java    //   HashMap import java.util.HashMap; class Key { String key; Key(String key) { this.key = key; } @Override public int hashCode() { int hash = (int)key.charAt(0); System.out.println("hashCode for key: " + key + " = " + hash); return hash; } @Override public boolean equals(Object obj) { return key.equals(((Key)obj).key); } } // Driver class public class GFG { public static void main(String[] args) { HashMap map = new HashMap(); map.put(new Key("vishal"), 20); map.put(new Key("sachin"), 30); map.put(new Key("vaibhav"), 40); System.out.println(); System.out.println("Value for key sachin: " + map.get(new Key("sachin"))); System.out.println("Value for key vaibhav: " + map.get(new Key("vaibhav"))); } }

Kesimpulan:


 hashCode for key: vishal = 118 hashCode for key: sachin = 115 hashCode for key: vaibhav = 118 hashCode for key: sachin = 115 Value for key sachin: 30 hashCode for key: vaibhav = 118 Value for key vaibhav: 40

Perubahan di Java 8


Seperti yang telah kita ketahui jika terjadi tabrakan, objek node disimpan dalam struktur data "linked list" dan metode equals () digunakan untuk membandingkan kunci. Ini adalah perbandingan untuk menemukan kunci yang tepat dalam daftar tertaut - operasi linier dan, dalam kasus terburuk, kompleksitasnya adalah O (n) .


Untuk memperbaiki masalah ini di Java 8, setelah mencapai ambang tertentu, pohon seimbang digunakan sebagai pengganti daftar tertaut. Ini berarti bahwa HashMap pada awalnya menyimpan objek dalam daftar tertaut, tetapi setelah jumlah elemen dalam hash mencapai ambang tertentu, transisi ke pohon seimbang terjadi. Yang meningkatkan kinerja dalam kasus terburuk dari O (n) ke O (log n).


Poin penting


  1. Kompleksitas operasi get () dan put () hampir konstan sampai re-hashing dilakukan.
  2. Dalam kasus tabrakan, jika indeks dari dua atau lebih objek node adalah sama, objek node terhubung menggunakan daftar tertaut, mis. tautan ke objek simpul kedua disimpan di yang pertama, ke yang ketiga di yang kedua, dll.
  3. Jika kunci yang diberikan sudah ada di HashMap, nilainya ditimpa.
  4. Kode hash nol adalah 0.
  5. Ketika suatu objek diperoleh dengan kunci, transisi melalui daftar tertaut terjadi sampai objek ditemukan atau tautan ke objek berikutnya adalah nol.

Source: https://habr.com/ru/post/id421179/

More articles:


All Articles