Analisis mendetail dari kelas HashMap

Sebelum beralih ke pembahasan kelas secara mendetail, mari kita fokus pada konsep dasar yang terkait dengan tabel hash. Artikel ini tidak akan membahas metode untuk bekerja dengan pemetaan hash. Hanya operasi penyisipan, pencarian dan penghapusan yang akan dibahas secara jelas dan rinci. Saya rasa tidak akan sulit untuk membaca deskripsi metode yang tersedia untuk HashMap dari Schildt yang sama. Mungkin di masa depan saya akan menulis artikel lain yang membahas tentang metode seperti itu, tetapi untuk saat ini hal ini masih dipertanyakan. Dibandingkan Java 7, kelas HashMap di Java 8 telah mengalami perubahan signifikan (+1000 baris kode). Anda dapat membaca tentang implementasi di Java 7 di sini (tetapi tidak lagi relevan): habr Tabel hash adalah struktur data yang mengimplementasikan antarmuka array asosiatif (model atau entri nilai kunci abstrak), yang menyediakan penyisipan dan pencarian yang sangat cepat: apa pun penyisipan dan pencarian elemen angka (dan terkadang penghapusan) dilakukan dalam waktu yang mendekati konstanta - O(1). Pada dasarnya, ini adalah array biasa, di mana lokasi elemen bergantung pada nilai elemen itu sendiri. Hubungan antara nilai suatu elemen dan posisinya dalam tabel hash ditentukan oleh fungsi hash. Fungsi hash mengambil sepotong data masukan, yang kita sebut key , dan sebagai output, fungsi tersebut menghasilkan bilangan bulat yang dikenal sebagai nilai hash (atau kode hash) . Nilai hash kemudian mengikat kunci kita ke indeks tabel hash tertentu. Untuk operasi dasar: penyisipan, pencarian dan penghapusan, kami menggunakan fungsi hash yang sama, sehingga operasi ini dilakukan dengan cukup cepat. Oleh karena itu, penting agar fungsi hash berperilaku konsisten dan menghasilkan indeks yang sama untuk data masukan yang sama. Perlu dicatat bahwa kode hash yang dihasilkan dapat berupa nilai numerik yang sangat besar, dan array asli dirancang secara kondisional untuk hanya 16 elemen. Mengapa tidak membuat array dengan satu miliar elemen untuk menambahkan sepuluh saja? Oleh karena itu, kita harus mengubah kode hash ini menjadi nilai dari 0 hingga 15 (jika ukuran arraynya 16). Dan untuk ini, transformasi tambahan digunakan. Jadi kami membuat indeks untuk meminimalkan ukuran array. Misalnya, di HashMap sebelum Java 8, metode tambahan ini digunakan untuk menemukan sel yang diinginkan:

static int indexFor(int h, int length) {
        return h & (length-1);
}

Sebagai input, dibutuhkan kode hash yang diperoleh sebagai hasil kerja hashCode()dan panjang array internal (jumlah sel). Dan itu mengembalikan hasil “kode hash” -> bitwise “DAN” -> (panjang array – 1). Kelas HashMapmewarisi dari kelas AbstractMapdan mengimplementasikan antarmuka berikut: Map, Cloneable, Serializable. .method bertanggung jawab atas fungsi hash di Java hashCode(). Implementasi default hashCode()mengembalikan nilai yang disebut kode hash identitas . Bahkan jika suatu kelas menimpa hashCode(), Anda selalu bisa mendapatkan hash ID objek dengan menelepon System.identityHashCode(Object o). Implementasi default hashCode()di OpenJDK tidak ada hubungannya dengan alamat memori, seperti yang terkadang diyakini. Detail lebih lanjut di sini: habr Di HashMap , tabel hash diimplementasikan berdasarkan array (atau, lebih tepatnya, dinamis, karena tabel dapat diperluas) dari daftar tertaut tunggal. Intinya, kita memperoleh kode hash kunci sebagai hasil dari metode ini hashCode(), yang kemudian dimodifikasi (seperti yang akan kita bahas nanti), dan secara internal, menggunakan metode tambahan, nilai yang dihasilkan didistribusikan ke sel yang diperlukan. Elemen array (sel) juga disebut bucket , yang digunakan untuk menyimpan node individual. Masing-masing ember adalah koleksi (daftar atau pohon). Node adalah objek dari kelas bersarang Node(atau TreeNodedalam struktur pohon). Faktanya, di dalam sel array LinkedListhanya terdapat daftar tertaut tunggal, atau pohon merah-hitam, yang mendasari implementasi kelas lain - TreeMap. Opsi dengan pohon merah-hitam tidak sering muncul (bagaimana, apa, dan di mana - di bawah), dan struktur ini cukup sulit untuk dipahami, jadi penekanannya adalah pada node bertipe Node. Node adalah kelas bersarang di dalamnya HashMapyang memiliki bidang-bidang berikut:

• final int hash— hash dari elemen saat ini, yang kita peroleh sebagai hasil hashing kunci;
• final K key— kunci elemen saat ini. Di sinilah apa yang Anda tentukan sebagai objek pertama dalam metode ini ditulis put();
• V value— nilai elemen saat ini. Dan apa yang Anda tentukan sebagai objek kedua dalam metode ini ditulis di sini put();
• Node < K, V> next— menghubungkan ke node berikutnya dalam keranjang yang sama. Daftarnya terhubung, jadi perlu link bukan ke node berikutnya, jika ada.

Sekarang mari kita lihat field dari kelas HashMap itu sendiri:

• transient Node < K, V> [] table– tabel hash itu sendiri, diimplementasikan berdasarkan array, untuk menyimpan pasangan nilai kunci dalam bentuk node. Di sinilah Node kita disimpan;
• transient int size— jumlah pasangan nilai kunci;
• int threshold— jumlah maksimum elemen, setelah mencapai ukuran tabel hash menjadi dua kali lipat. Dihitung menggunakan rumus (kapasitas * loadFactor);
• final float loadFactor— parameter ini menentukan tingkat beban yang dibutuhkan tabel hash saat ini untuk membuat tabel hash baru, mis. segera setelah tabel hash terisi 75%, tabel hash baru akan dibuat dan elemen saat ini akan dipindahkan ke dalamnya (operasi yang mahal, karena semua elemen harus diulang);
• transient Set< Map.Entry< K,V>> entrySet- berisi cache entrySet(), yang dengannya kita dapat mengulanginya HashMap.

Dan konstanta:

• static final int DEFAULT_INITIAL_CAPACITY= 1 << 4— kapasitas tabel hash default (16);
• static final int MAXIMUM_CAPACITY = 1 << 30— kapasitas maksimum tabel hash (sekitar 1 miliar);
• static final float DEFAULT_LOAD_FACTOR = 0.75f— faktor beban default;
• static final int TREEIFY_THRESHOLD = 8adalah "ambang batas" jumlah elemen dalam satu wadah, yang setelah mencapainya, daftar tertaut internal akan diubah menjadi struktur pohon (pohon merah-hitam).
• static final int UNTREEIFY_THRESHOLD = 6— jika jumlah elemen dalam satu keranjang berkurang menjadi 6, maka transisi terbalik dari pohon ke daftar tertaut akan terjadi;
• static final int MIN_TREEIFY_CAPACITY = 64— kapasitas minimum (jumlah keranjang) dari tabel hash yang memungkinkan transisi ke struktur pohon. Itu. Jika setidaknya terdapat 64 keranjang di tabel hash dan terdapat 8 elemen atau lebih dalam satu keranjang, maka transisi ke struktur pohon akan terjadi.

Konstruktor kelas:

1. public HashMap()— membuat tampilan hash secara default: berdasarkan volume (capacity) = 16dan faktor beban (load factor) = 0.75;
2. public HashMap(Map< ? extends K, ? extends V> m)— membuat pemetaan hash yang diinisialisasi oleh elemen pemetaan lain dengan kapasitas awal yang cukup untuk mengakomodasi elemen pemetaan lain;
3. public HashMap(int initialCapacity)— membuat peta hash dengan kapasitas awal tertentu. Agar HashMap berfungsi dengan baik dan benar, ukuran array internal harus pangkat dua (yaitu 16, 64, 128, dst.);
4. public HashMap(int initialCapacity, float loadFactor)— membuat peta hash dengan parameter yang ditentukan: kapasitas awal dan faktor beban.

Sebuah kelas mengimplementasikan antarmuka Mapdan memperluas kelas AbstractMaptanpa menambahkan metodenya sendiri. Peta hash tidak menjamin urutan elemen-elemennya. Oleh karena itu, urutan elemen yang dimasukkan ke dalam peta hash belum tentu urutan pengambilannya oleh iterator. Menambahkan Objek Menambahkan pasangan nilai kunci dilakukan dengan menggunakan put(). Mari kita lihat langkah-langkah yang terlibat saat menambahkan objek:

1. Nilai hash dari kunci objek yang dimasukkan dihitung. Hash kunci dihitung dengan metode static final int hash(Object key)yang sudah mengakses hashCode()metode kunci yang kita ketahui. Untuk melakukan ini, digunakan metode yang diganti hashCode()atau implementasi defaultnya. Transformasi tambahan dalam metode hash():

   static final int hash(Object key) {
           int h;
           return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
   }

   Mengapa tidak menghitung saja menggunakan hashCode()? Hal ini dilakukan karena hashCode()dapat diimplementasikan sehingga hanya bagian bawah int'a saja yang terisi. Misalnya, untuk Integer, Float- jika kita memasukkan nilai kecil ke dalam HashMap, maka hanya nilai yang lebih rendah yang akan diisi bit kode hashnya. Dalam hal ini, kunci dalam HashMap akan cenderung terakumulasi di sel bawah, sedangkan sel atas akan tetap kosong, dan ini sangat tidak efisien. Hanya bit hash yang paling tidak signifikan yang memengaruhi keranjang mana yang akan dimasuki entri baru. Itu sebabnya kami melakukan berbagai manipulasi untuk mencampurkan bit tinggi dari hash ke dalam bit rendah untuk meningkatkan distribusi di seluruh keranjang (sehingga bit tinggi dari hash asli objek mulai melakukan penyesuaian pada keranjang mana objek tersebut akan berakhir. up in) dan, sebagai hasilnya, kinerja. Itu sebabnya fungsi tambahan diciptakan hashdi dalam HashMap.

2. Kami menghitung indeks keranjang (sel array) yang akan ditambahkan elemen kami:

   
   i = (n - 1) & hash

   di mana n adalah panjang array.

3. Objek Node dibuat.

4. Sekarang, mengetahui indeks dalam array, kita mendapatkan daftar (rantai) elemen yang terkait dengan sel ini. Jika embernya kosong, maka kita cukup menempatkan elemen di dalamnya. Иначе хэш и ключ нового element поочередно сравниваются с хешами и ключами элементов из списка и, при совпадении этих параметров, meaning element перезаписывается. Если совпадений не найдено, элемент добавляется в конец списка.

   Sekarang ke contoh yang sangat detail.

   1. Mari kita buat objek dari kelas HashMap:

      HashMap < String, Integer> map = new HashMap<>();

   2. Dengan menggunakan metode ini, put()kami menambahkan pasangan nilai kunci pertama ke peta hash:

      map.put("KING", 100);

      Saat ini, metode tersebut dipanggil secara internal putVal().

   3. Menggunakan fungsi hash, yang perannya dimainkan oleh metode hash, kode hash dari kunci dihitung , di dalamnya kode hash dihitung terlebih dahulu menggunakan metode hashCode() (dalam hal ini, kelas String), sebagai sebagai hasilnya kita memperoleh "nilai awal" - 2306967 . Dapat memeriksa di IDEA menggunakan

      System.out.println("KING".hashCode());

      Kode hash yang dihasilkan dimodifikasi menggunakan rumus: (хеш-code) ^ (хеш-code>>> 16), dan sebagai hasilnya kita mendapatkan kode hash akhir – 2306996 .

   4. Kami memeriksa tabel untuk "kekosongan":

      if ((tab = table) == null || (n = tab.length) == 0)

      Di mana[] tab — сама хеш-table: ссылаем tab и table (напомню, что это поле класса HashMap, которое хранит массив для наших элементов) на один и тот же массив, а int n – дополнительная переменная-счетчик.

      Karena pemeriksaan akan mengembalikan nilai true (karena array untuk tabel tidak dibuat menggunakan operator baru di konstruktor), metode ini akan dipanggil resize(), yang sebenarnya akan membuat tabel yang terdiri dari 16 elemen. Ya, konstruktor kelas tidak membuat tabel apa pun. Sebaliknya, metode ini selalu dipanggil resize()saat pertama kali sebuah elemen ditambahkan. Panjang tabel yang dibuat (pertimbangkan panjang array) akan ditulis ke variabel n – n = (tab = resize()).length, yang selanjutnya digunakan untuk menghitung bucket.

   5. Pada saat yang sama, kami menghitung indeks keranjang tempat objek kami akan ditempatkan dan memeriksa apakah sudah ada elemen di dalamnya. Kami menghitung:

      
      i = (n - 1) & hash
      i = (16 - 1) & 2306996
      i = 4

      memeriksa:

      
      if ((p = tab[i = (n - 1) & hash]) == null)

   6. Karena sebagai hasil pemeriksaan kita mendapatkan nilai true (tidak ada elemen di bucket), objek Node dengan bidang berikut akan dihasilkan:

      
      {
      int hash = 2306996 — сгенерированный хеш-code
      String key = {"KING"} — ключ
      Integer value = 100 — meaning
      Node next = null — link на следующий узел
      }

      Objek Node yang kita hasilkan akan ditambahkan ke bucket di bawah indeks [4]:

      tab[i] = newNode(hash, key, value, null);
      tab[4] = newNode(2306996, “KING”, 100, null);

      newNode()adalah metode yang hanya mengembalikan objek kelas Node.

   7. Setelah menambahkan, pemeriksaan akan dilakukan untuk melihat apakah jumlah elemen saat ini melebihi parameter threshold:

      if (++size > threshold)
          resize();

      Jika melebihi, maka metode tersebut akan dipanggilresize() для увеличения размера хеш-таблицы.

      Ini adalah metodenya putVal()(masing-masingput()) завершит свою работу.

      Hasilnya dapat direpresentasikan secara grafis sebagai berikut:

      Secara umum, seperti inilah tampilan penambahan Node (pasangan nilai kunci) ke tabel hash jika keranjang yang diinginkan kosong . Sekarang mari kita coba menambahkan elemen yang akan menyebabkan tabrakan (bila ada lebih dari satu elemen dalam satu keranjang).

Sedikit tentang tabrakan Situasi ketika kunci yang berbeda berakhir di keranjang yang sama (bahkan dengan hash yang berbeda) disebut tabrakan atau tabrakan. Meskipun tabel hash lebih besar dari kumpulan data dan fungsi hash yang baik telah dipilih, hal ini tidak menjamin bahwa tabrakan tidak akan terjadi. Dan nilai hash dibatasi pada kisaran nilai int (sekitar 4 miliar). Nilai baru yang dihasilkan juga perlu ditulis di suatu tempat, dan untuk ini Anda perlu menentukan di mana tepatnya nilai tersebut akan ditulis. Ini disebut resolusi konflik. Ada dua pendekatan:

• metode rantai atau rantai eksternal (diimplementasikan di HashMap) - mis. sel sebenarnya berisi daftar (rantai). Dan daftar tersebut mungkin sudah berisi beberapa nilai (tidak harus dengan kode hash yang sama).
• metode probing linier atau pengalamatan terbuka (diimplementasikan dalam IdentityHashMap) - terdiri dari pencarian sel kosong pertama setelah sel yang ditunjuk oleh fungsi hash;

Anda dapat membaca tentang tabrakan di sini: klik

1. Dengan menggunakan metode ini, put()kita akan menambahkan pasangan nilai kunci lainnya ke pemetaan hash:

   map.put("BLAKE", 10);

2. Kami menghitung “hash awal” – 63281361. Kami memodifikasinya dan sebagai hasilnya kami mendapatkan kode hash akhir – 63281940.

3. Karena pemeriksaan pertama untuk "kekosongan" sekarang akan menghasilkan nilai salah (tidak perlu membuat tabel), kami segera menghitung indeks keranjang tempat objek kami akan ditempatkan:

   
   i = (n - 1) & hash
   i = (16 - 1) & 63281940
   i = 4

4. Bucket pada indeks yang ditentukan diperiksa keberadaan elemen di dalamnya, dan karena kondisi if ((p = tab[i = (n - 1) & hash]) == null)dalam kasus ini tidak terpenuhi (sudah ada elemen di bucket), maka kita pergi ke blok else.

5. Pertama-tama, kita membandingkan elemen yang ditambahkan dengan elemen pertama dari daftar tertaut di dalam keranjang:

   (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))

   Saat memeriksa, hash kunci dibandingkan terlebih dahulu. Jika "bagian" ini (p.hash == hash)menghasilkan nilai salah, maka kondisi lainnya akan diabaikan ( &&) karena objeknya dijamin berbeda. Jika tidak, kunci-kunci tersebut kemudian dibandingkan dengan referensi (==) dan jika terjadi ketidaksetaraan, kunci-kunci tersebut dibandingkan menggunakan metode equals(). Perbandingan dibuat dalam urutan ini demi kinerja. Jika ketiga ekspresi menghasilkan nilai benar, ini berarti kuncinya sama dan elemen baru akan ditulis ke variabel tambahan untuk kemudian menimpa nilai kunci:

   if (e != null) { // existing mapping for key
         V oldValue = e.value;
         if (!onlyIfAbsent || oldValue == null)
         e.value = value;
         afterNodeAccess(e);
          return oldValue;
    }

   Sebagai hasil dari membandingkan kunci, kami sudah mendapatkan false pada tahap pertama (hash berbeda).

6. Kita mengabaikan kondisi ( p instanceof TreeNode) karena struktur dalam ember tidak seperti pohon pada tahap ini.

7. Selanjutnya, kita masuk ke loop for, di mana dalam satu ember kita memeriksa elemen untuk penunjuk ke elemen berikutnya next, dan jika null (yang berarti elemen dalam daftar adalah yang terakhir dan satu-satunya), kita menambahkan Node baru elemen ke akhir daftar:

   if ((e = p.next) == null){
   	p.next = newNode(hash, key, value, null)
   ... };

   Anda mungkin bertanya, di mana kuncinya untuk memeriksa kesetaraan? Kita tidak bisa langsung saja menambahkan elemen baru. Jadi sudah dilaksanakan terlebih dahulu pada ayat (5). Berkat ini, kita sekarang dapat dengan mudah memeriksa penunjuk elemen ini, dan karena sekarang bernilai nol, kita dapat menyimpulkan bahwa hanya ada satu elemen dalam daftar. Dan karena kita sudah memeriksa kuncinya, kita dapat menambahkan elemen baru dengan aman.

   Jika pada iterasi pertama penunjuknya tidak nol, ini menunjukkan bahwa setidaknya ada dua elemen dalam daftar, jadi dalam hal ini kita beralih ke kondisi berikutnya dan membandingkan kunci dari elemen yang ditambahkan dengan semua kunci dari elemen tersebut. elemen dalam daftar (dengan cara yang dijelaskan dalam paragraf kelima).

   if (e.hash == hash &&
                           ((k = e.key) == key || (key != null && key.equals(k))))

   Jika ditemukan kecocokan saat membandingkan kunci, elemen baru akan ditulis ke variabel tambahan untuk kemudian menimpa nilai kunci tersebut.

   Setelah menambahkan elemen kedua, objek HashMap kita secara grafis terlihat seperti ini:

   Hasilnya, penambahan elemen selama tumbukan (dalam satu keranjang) terlihat seperti ini:

   • Kami memeriksa menggunakan metode hashCode()dan equals()apakah kedua kunci itu sama.
   • jika kuncinya sama, ganti nilai saat ini dengan yang baru.
   • jika tidak, hubungkan objek baru dan lama menggunakan struktur data “daftar tertaut”, yang menunjukkan tautan ke objek berikutnya di objek saat ini dan simpan keduanya di bawah indeks yang diinginkan; atau beralih ke struktur pohon

8. Setelah setiap iterasi (menambahkan elemen baru), loop for menambah penghitung, yang bertanggung jawab atas jumlah elemen dalam bucket:

   for (int binCount = 0; ; ++binCount)

   Sampai jumlahnya sama dengan atau lebih besar dari 7:

   binCount >= TREEIFY_THRESHOLD – 1

   Dalam hal ini, suatu metode akan dipanggil treeifyBin()treeify()untuk membangun struktur pohon secara langsung. Namun, jika jumlah keranjang di tabel hash saat ini kurang dari 64:

   if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)

   Alih-alih menuju ke struktur pohon, sebuah metode akan dipanggil resize()untuk meningkatkan ukuran tabel hash, mendistribusikan ulang elemen-elemennya. treeify()pada gilirannya, daftar tertaut dari TreeNodekonversi menjadi pohon merah-hitam. Metode ini resize()mengulangi semua elemen penyimpanan saat ini, menghitung ulang indeksnya (dengan mempertimbangkan ukuran baru) dan mendistribusikan ulang elemen ke dalam array baru.

   Secara singkat, tanpa merinci struktur pohon merah-hitam, terjadi hal berikut:

   1. Elemen pertama dari daftar ditulis sebagai akar dari keseluruhan pohon (hitam):

      if (root == null) {
          x.parent = null;
          x.red = false;
          root = x;
      }

   2. Untuk elemen lainnya:

      mendistribusikannya ke kiri atau kanan tergantung pada nilai hash:

      if ((ph = p.hash) > h)
          dir = -1;
      else if (ph < h)
          dir = 1;

      Semua anak kiri harus lebih kecil dari (atau sama dengan) simpul akarnya, sedangkan semua anak kanan harus lebih besar.

   3. Jika dua elemen memiliki hash yang sama dan tidak dapat dibandingkan dengan cara lain (mereka tidak mengimplementasikan antarmuka Comparable), kami menghentikan konstruksi pohon dan memanggil metode tersebut tieBreakOrder(), yang selanjutnya menggunakan metode asli System.identityHashCode()untuk menghitung kode hash unik secara global .

      Detail lebih lanjut di sini: tautan ke artikel

   4. Kami memeriksa elemen pohon (objek TreeNode) hingga elemen nol anak (kiri atau kanan) ditemukan.

      if ((p = (dir <= 0) ? p.left : p.right) == null)

   5. Tambahkan node anak (kiri atau kanan tergantung dir):

      x.parent = xp;
      if (dir <= 0)
          xp.left = x;
      else
          xp.right = x;

   6. Karena menambahkan elemen baru dapat mengganggu keseimbangan pohon, kami menyebut metode penyeimbangan kembali:

      root = balanceInsertion(root, x);

      Anda dapat membaca tentang penyeimbangan CCH di sini: habr

   7. Setelah penyeimbangan, elemen root dapat berubah. Kami memperbaikinya dengan memanggil metode yang menjamin bahwa root yang diteruskan ke sana akan menjadi node pertama:

      moveRootToFront(tab, root)

      Anda dapat melihat dengan jelas bagaimana pohon merah-hitam dibangun dan menyeimbangkan diri di sini: visualisasi

Itu saja, pada prinsipnya, dan dengan menggunakan contoh, asumsikan kita ingin menambahkan nama berikut sebagai kunci: KING, MARY, JOSE, ANNA, FRED, TONY, ALEX, PEPE. Dan katakanlah kita memiliki setidaknya 64 keranjang di tabel hash, dan semua elemen ini telah terakumulasi dalam satu keranjang. Secara struktural, keranjang ini akan terlihat seperti ini (elemen diurutkan berdasarkan kode hash): Jenis CCHD: Lihat di dalam ember: Mengambil elemen (mengambil nilai berdasarkan kunci) Mengenai operasi penambahan, cukup sederhana. Algoritmenya (bila ada daftar tertaut di keranjang) dapat ditulis seperti ini:

1. Hitung kode hash kunci.
2. Hitung indeks keranjang.
3. Telusuri indeks dan bandingkan kunci elemen pertama dengan nilai yang ada. Jika sama, kembalikan nilainya, jika tidak, periksa elemen berikutnya, jika ada.
4. Jika objek Node berikutnya adalah null, kembalikan null.
5. Jika objek Node berikutnya bukan null, buka objek tersebut dan ulangi tiga langkah pertama hingga elemen ditemukan atau objek Node berikutnya bernilai null.

Dengan menggunakan metode ini, get()kita mendapatkan nilai untuk kunci “KING”:

map.get("KING");

Di dalam, metode ini disebut getNode(int hash, Object key), yang mana kunci itu sendiri (“KING”) dan hashnya (2306996) diteruskan, yang telah dihitung sebelumnya dengan cara yang sama seperti selama operasi put().

1. Kami memeriksa:

   1. apakah tabel hash ada:(tab = table) != null

      Izinkan saya mengingatkan Anda bahwa saat membuat HashMap, array untuk tabel tidak dibuat di konstruktor; ini terjadi nanti dalam metode resize(), yang selalu dipanggil saat menambahkan elemen pertama ke tabel hash. Oleh karena itu, jika tidak ada elemen yang ditambahkan ke HashMap, maka tidak ada array internal untuk menyimpan elemen tersebut.

   2. jika ekspresi sebelumnya mengembalikan nilai benar, Anda perlu memastikan bahwa panjang array internal lebih besar dari 0:(n = tab.length) > 0;

   3. jika ekspresi sebelumnya juga mengembalikan nilai benar, buka keranjang di indeks (dalam kasus kami 4), yang telah dihitung sebelumnya, dan periksa keberadaan elemen:

      (first = tab[(n - 1) & hash]) != null)

   4. Kami membandingkan kunci yang kami cari dengan kunci elemen pertama dalam daftar di dalam keranjang, karena di sebagian besar keranjang akan ada (tidak di semua tempat kami mengalami tabrakan) hanya satu elemen (kasus kami). Seperti dalam kasus metode ini put(), hash dibandingkan, dan jika cocok, kuncinya dibandingkan dengan referensi, dan hanya kemudian dengan equals().

      if (first.hash == hash && // always check first node
          ((k = first.key) == key || (key != null && key.equals(k))))

      Karena dalam kasus kita, kunci “KING” akan mendahului kunci “BLAKE” (dalam daftar tertaut, elemen baru ditambahkan di akhir, dan KING ditambahkan terlebih dahulu), kita akan berhenti di titik ini dan mengembalikan objek pertama dari ketik Node ke metode get(), yang “mengambil” bidang dengan nilai (100):

      return (e = getNode(hash(key), key)) == null ? null : e.value;

2. Jika terdapat lebih dari satu elemen di dalam keranjang, maka:

   1. jika keranjangnya adalah daftar tertaut, kita menelusuri daftar tersebut melalui masing-masing elemen dalam satu lingkaran do – whilehingga kecocokan ditemukan:

      do {
          if (e.hash == hash &&
              ((k = e.key) == key || (key != null && key.equals(k))))
              return e;
      } while ((e = e.next) != null);

   2. jika ember adalah struktur pohon, maka metode ini juga disebut getTreeNode(), yang selanjutnya menggunakan metode untuk menemukan kunci yang diperlukan find(). Kami melakukan pencarian pohon - hash dibandingkan dan simpul akar kiri atau kanan untuk pencarian ditentukan. Jika kuncinya sama (dengan referensi atau dengan equals), kembalikan node ini. Jika node anak kiri atau kanan adalah null, kami juga membandingkan kunci menggunakan bandingkanTo (jika kunci mengimplementasikan antarmuka Comparable), jika tidak, kami melakukan pencarian rekursif melalui pohon (subpohon kanan atau kiri) hingga ditemukan kecocokan.

Menghapus objek dari HashMap Karena ruang dalam artikel hampir habis, saya akan menjelaskan secara singkat bagaimana penghapusan dilakukan berdasarkan kunci. Algoritmenya sangat mirip:

• pergi ke ember yang diinginkan (sekali lagi, ini sudah dihitung sebelumnya);

• jika hanya ada satu objek di dalam ember (kami memeriksa penunjuk nolnya) kami membandingkan hash, tautan, dan equals(jika tiba-tiba hashnya tidak sama). Menemukan kecocokan? Bagus, ini kunci kami - hapus (=null) dan kembalikan nilai kunci ini.

• jika ada lebih dari satu elemen dalam keranjang, kami memeriksa setiap elemen dalam satu lingkaran hingga kami menemukan elemen tersebut atau mencapai akhir daftar.

• jika elemen tidak ditemukan, kami mengembalikan null.

Dalam situasi dengan pohon, ada implementasi yang agak rumit, yang lebih baik tidak diketahui dan tidur nyenyak (deskripsi metode bahkan mengatakan bahwa implementasinya lebih rumit daripada operasi penghapusan biasa dalam warna merah-hitam pohon). Terlebih lagi, ketika dihapus, jumlah node dalam satu bucket dapat kembali menjadi 6, dan kemudian pohon tersebut akan dibangun kembali menjadi daftar tertaut. Jika Anda bukan seorang pengembang dengan pengalaman bertahun-tahun, sama sekali tidak perlu mengetahui dan memahami hal ini (dan memang tidak perlu).