Analisis terperinci kelas HashMap

Sebelum beralih kepada perbincangan terperinci tentang kelas, mari fokus pada konsep asas yang dikaitkan dengan jadual cincang. Artikel ini tidak akan membincangkan kaedah untuk bekerja dengan pemetaan cincang. Hanya operasi sisipan, carian dan pemadaman akan dibincangkan dengan jelas dan terperinci. Saya fikir ia tidak sukar untuk membaca penerangan kaedah yang tersedia untuk HashMap daripada Schildt yang sama. Mungkin pada masa akan datang saya akan menulis artikel lain yang dikhaskan untuk kaedah sedemikian, tetapi buat masa ini ini diragui. Berbanding dengan Java 7, kelas HashMap di Java 8 telah mengalami perubahan ketara (+1000 baris kod). Anda boleh membaca tentang pelaksanaan dalam Java 7 di sini (tetapi tidak lagi relevan): habr Jadual cincang ialah struktur data yang melaksanakan antara muka tatasusunan bersekutu (model atau entri nilai kunci abstrak), yang menyediakan sisipan dan carian yang sangat pantas: tanpa mengira penyisipan dan carian elemen nombor (dan kadangkala pemadaman) dilakukan dalam masa yang hampir dengan pemalar - O(1). Pada asasnya, ini ialah tatasusunan biasa, di mana lokasi elemen bergantung pada nilai elemen itu sendiri. Hubungan antara nilai elemen dan kedudukannya dalam jadual cincang ditentukan oleh fungsi cincang. Fungsi cincang mengambil sekeping data input, yang kami panggil key , dan sebagai output ia menghasilkan integer yang dikenali sebagai nilai cincang (atau kod cincang) . Nilai cincang kemudian mengikat kunci kami pada indeks jadual cincang tertentu. Untuk operasi asas: sisipan, carian dan pemadaman, kami menggunakan fungsi cincang yang sama, jadi operasi ini dilakukan dengan agak cepat. Atas sebab ini, adalah penting bahawa fungsi cincang berkelakuan secara konsisten dan mengeluarkan indeks yang sama untuk data input yang sama. Perlu diingat bahawa kod cincang yang terhasil boleh menjadi nilai angka yang besar, dan tatasusunan asal direka bentuk secara bersyarat untuk hanya 16 elemen. Mengapa tidak mencipta tatasusunan dengan satu bilion elemen untuk menambah hanya sepuluh? Oleh itu, entah bagaimana kita mesti mengubah kod cincang ini kepada nilai dari 0 hingga 15 (jika saiz tatasusunan ialah 16). Dan untuk ini, transformasi tambahan digunakan. Jadi kami menjana indeks untuk meminimumkan saiz tatasusunan. Sebagai contoh, dalam HashMap sebelum Java 8, kaedah tambahan ini digunakan untuk mencari sel yang dikehendaki:

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

Sebagai input, ia mengambil kod cincang yang diperoleh hasil daripada kerja hashCode()dan panjang tatasusunan dalaman (bilangan sel). Dan ia mengembalikan hasil "kod hash" -> bitwise "AND" -> (panjang tatasusunan - 1). Kelas HashMapmewarisi daripada kelas AbstractMapdan melaksanakan antara muka berikut: Map, Cloneable, Serializable. Kaedah . bertanggungjawab untuk fungsi cincang dalam Java hashCode(). Pelaksanaan lalai hashCode()mengembalikan nilai yang dipanggil kod cincang identiti . Walaupun kelas mengatasi hashCode(), anda sentiasa boleh mendapatkan cincang ID objek dengan memanggil System.identityHashCode(Object o). Pelaksanaan lalai hashCode()dalam OpenJDK tiada kaitan dengan alamat memori, seperti yang kadangkala dipercayai. Butiran lanjut di sini: habr Dalam HashMap , jadual cincang dilaksanakan berdasarkan tatasusunan (atau, lebih tepat lagi, dinamik, kerana jadual boleh berkembang) senarai terpaut tunggal. Pada asasnya, kami memperoleh kod cincang kunci sebagai hasil daripada kaedah hashCode(), yang kemudiannya diubah suai (seperti yang akan kami pertimbangkan kemudian), dan secara dalaman, menggunakan kaedah tambahan, nilai yang terhasil diedarkan kepada sel yang diperlukan. Elemen tatasusunan (sel) juga dipanggil baldi , yang digunakan untuk menyimpan nod individu. Setiap baldi adalah koleksi (senarai atau pokok). Nod ialah objek kelas bersarang Node(atau TreeNodedalam struktur pokok). Sebenarnya, di dalam sel tatasusunan LinkedListhanya terdapat senarai terpaut tunggal, atau pokok merah-hitam, yang mendasari pelaksanaan kelas lain - TreeMap.

Pilihan dengan pokok merah-hitam tidak timbul begitu kerap (bagaimana, apa dan di mana - di bawah), dan struktur ini agak sukar untuk difahami, jadi penekanan akan diberikan pada nod jenis Nod. Node ialah kelas bersarang di dalamnya HashMapyang mempunyai medan berikut:

final int hash— cincangan elemen semasa, yang kami perolehi hasil daripada pencincangan kunci;
final K key— kunci elemen semasa. Di sinilah perkara yang anda tentukan sebagai objek pertama dalam kaedah ditulis kepada put();
V value— nilai unsur semasa. Dan apa yang anda tentukan sebagai objek kedua dalam kaedah ditulis di sini put();
Node < K, V> next— pautan ke nod seterusnya dalam bakul yang sama. Senarai disambungkan, jadi ia memerlukan pautan bukan ke nod seterusnya, jika ada.

Sekarang mari kita lihat medan kelas HashMap itu sendiri:

transient Node < K, V> [] table– jadual cincang itu sendiri, dilaksanakan berdasarkan tatasusunan, untuk menyimpan pasangan nilai kunci dalam bentuk nod. Di sinilah Nod kami disimpan;
transient int size— bilangan pasangan nilai kunci;
int threshold— bilangan maksimum elemen, apabila mencapai saiz jadual cincang dua kali ganda. Dikira menggunakan formula (kapasiti * loadFactor);
final float loadFactor— parameter ini menentukan pada tahap beban yang diperlukan oleh jadual cincang semasa untuk mencipta jadual cincang baharu, i.e. sebaik sahaja jadual cincang 75% penuh, jadual cincang baharu akan dibuat dan elemen semasa akan dipindahkan ke dalamnya (operasi yang mahal, kerana semua elemen mesti dicincang semula);
transient Set< Map.Entry< K,V>> entrySet- mengandungi cache entrySet(), yang boleh kita ulangi HashMap.

Dan pemalar:

static final int DEFAULT_INITIAL_CAPACITY= 1 << 4— kapasiti jadual cincang lalai (16);
static final int MAXIMUM_CAPACITY = 1 << 30— kapasiti maksimum yang mungkin bagi jadual cincang (kira-kira 1 bilion);
static final float DEFAULT_LOAD_FACTOR = 0.75f— faktor beban lalai;
static final int TREEIFY_THRESHOLD = 8ialah "ambang" bilangan elemen dalam satu baldi, apabila mencapai senarai pautan dalaman akan ditukar menjadi struktur pokok (pokok merah-hitam).
static final int UNTREEIFY_THRESHOLD = 6— jika bilangan elemen dalam satu bakul berkurangan kepada 6, maka peralihan terbalik daripada pokok kepada senarai terpaut akan berlaku;
static final int MIN_TREEIFY_CAPACITY = 64— kapasiti minimum (bilangan baldi) jadual cincang di mana peralihan kepada struktur pokok boleh dilakukan. Itu. Jika terdapat sekurang-kurangnya 64 baldi dalam jadual cincang dan terdapat 8 atau lebih elemen dalam satu baldi, maka peralihan kepada struktur pokok akan berlaku.

Pembina kelas:

public HashMap()— mencipta paparan cincang secara lalai: mengikut kelantangan (capacity) = 16dan dengan faktor beban (load factor) = 0.75;
public HashMap(Map< ? extends K, ? extends V> m)— mencipta pemetaan cincang yang dimulakan oleh elemen pemetaan lain yang diberikan dengan kapasiti awal yang cukup untuk menampung elemen pemetaan lain;
public HashMap(int initialCapacity)— mencipta peta cincang dengan kapasiti awal yang diberikan. Untuk HashMap berfungsi dengan betul dan betul, saiz tatasusunan dalaman mestilah kuasa dua (iaitu 16, 64, 128, dsb.);
public HashMap(int initialCapacity, float loadFactor)— mencipta peta cincang dengan parameter yang ditentukan: kapasiti awal dan faktor beban.

Kelas melaksanakan antara muka Mapdan memanjangkan kelas AbstractMaptanpa menambah kaedahnya sendiri. Peta cincang tidak menjamin susunan elemennya. Oleh itu, susunan unsur-unsur yang dimasukkan ke dalam peta cincang tidak semestinya susunan unsur-unsur itu diperoleh semula oleh lelaran. Menambah Objek Menambah pasangan nilai kunci dilakukan menggunakan put(). Mari lihat langkah-langkah yang terlibat semasa menambah objek:

Nilai cincang kunci objek yang dimasukkan dikira. Cincang kunci dikira dengan kaedah static final int hash(Object key)yang sudah mengakses hashCode()kaedah utama yang kita tahu. Untuk melakukan ini, sama ada kaedah yang diganti hashCode()atau pelaksanaan lalainya digunakan. Transformasi tambahan dalam kaedah hash():
```
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
```
Почему бы просто не вычислить с помощью hashCode()? Это сделано из-за того, что hashCode() можно реализовать так, что только нижние биты int'a будут заполнены. Например, для Integer, Float – если мы в HashMap кладем маленькие значения, то у них и биты хеш-codeов будут заполнены только нижние. В таком случае ключи в HashMap будут иметь тенденцию скапливаться в нижних ячейках, а верхние будут оставаться пустыми, что не очень эффективно. На то, в Howой бакет попадёт новая запись, влияют только младшие биты хеша. Поэтому и придумали различными манипуляциями подмешивать старшие биты хеша в младшие, чтобы улучшить распределение по бакетам (чтобы старшие биты родного хеша an object начали вносить коррективы в то, в Howой бакет попадёт an object) и, How следствие, производительность. Потому и придумана дополнительная функция hash внутри HashMap.
Вычисляем индекс бакета (ячейки массива), в который будет добавлен наш элемент:
```
i = (n - 1) & hash
```
где n – длина массива.
Создается an object Node.
Теперь, зная индекс в массиве, мы получаем список (цепочку) элементов, привязанных к этой ячейке. Если в бакете пусто, тогда просто размещаем в нем элемент. Иначе хэш и ключ нового element поочередно сравниваются с хешами и ключами элементов из списка и, при совпадении этих параметров, meaning element перезаписывается. Если совпадений не найдено, элемент добавляется в конец списка.

Теперь к очень подробному примеру.
1. Создадим an object класса HashMap:
```
HashMap < String, Integer> map = new HashMap<>();
```
2. С помощью метода put() добавим в хеш-отображение первую пару «ключ-meaning»:
```
map.put("KING", 100);
```
  В этот момент внутри вызывается метод putVal().
3. С помощью хеш-функции, роль которой играет метод hash, вычисляется хеш-code ключа, внутри которого предварительно вычисляется хеш-code с помощью метода hashCode() (в данном случае класса String), в результате чего мы получаем его «предварительное meaning» – 2306967. Может проверить в IDEA с помощью
```
System.out.println("KING".hashCode());
```
  Полученный хеш-code модифицируется по формуле: (хеш-code) ^ (хеш-code>>> 16), и в результате получаем окончательный хеш-code – 2306996.
4. Проверяем таблицу на «пустоту»:
```
if ((tab = table) == null || (n = tab.length) == 0)
```
  где [] tab — сама хеш-table: ссылаем tab и table (напомню, что это поле класса HashMap, которое хранит массив для наших элементов) на один и тот же массив, а int n – дополнительная переменная-счетчик.
  
  Так How проверка вернёт true (потому что массив для таблицы не был создан с помощью оператора new в конструкторе), будет вызван метод resize(), который собственно и создаст таблицу размером на 16 элементов. Да-да, конструкторы класса ниHowой таблицы не создают. Вместо этого всегда происходит вызов метода resize() при первом добавлении element. Длина созданной таблицы (считай длина массива) будет записана в переменную n – n = (tab = resize()).length, которая в дальнейшем используется для вычисления бакета.
5. Pada masa yang sama, kami mengira indeks baldi di mana objek kami akan diletakkan dan menyemak sama ada sudah ada unsur di dalamnya. Kami mengira:
```
i = (n - 1) & hash
i = (16 - 1) & 2306996
i = 4
```
  semak:
```
if ((p = tab[i = (n - 1) & hash]) == null)
```
6. Oleh kerana hasil daripada semakan kami mendapat kebenaran (tiada unsur dalam baldi), objek Nod dengan medan berikut akan dihasilkan:
```
{
int hash = 2306996 — сгенерированный хеш-code
String key = {"KING"} — ключ
Integer value = 100 — meaning
Node next = null — link на следующий узел
}
```
  Objek Node kami yang dihasilkan akan ditambahkan pada baldi di bawah indeks [4]:
```
tab[i] = newNode(hash, key, value, null);
tab[4] = newNode(2306996, “KING”, 100, null);
```
  newNode()ialah kaedah yang hanya mengembalikan objek kelas Node.
7. Selepas menambah, semakan akan dibuat untuk melihat sama ada bilangan elemen semasa melebihi parameter threshold:
```
if (++size > threshold)
    resize();
```
  Jika melebihi, maka kaedah akan dipanggil resize()untuk meningkatkan saiz jadual cincang.
  
  Pada ketika ini, kaedah putVal()(dan , masing-masing put()) akan menyelesaikan kerjanya.
  
  Hasilnya boleh ditunjukkan secara grafik seperti berikut:
  
  Secara umum, inilah yang kelihatan seperti menambah Node (pasangan nilai kunci) pada jadual cincang jika baldi yang dikehendaki kosong . Sekarang mari cuba tambah elemen yang akan membawa kepada perlanggaran (apabila terdapat lebih daripada satu elemen dalam satu baldi).

Sedikit tentang perlanggaran Keadaan apabila kekunci yang berbeza berakhir dalam baldi yang sama (walaupun dengan cincang yang berbeza) dipanggil perlanggaran atau perlanggaran. Walaupun jadual cincang lebih besar daripada set data dan fungsi cincang yang baik telah dipilih, ini tidak menjamin bahawa perlanggaran tidak akan berlaku. Dan nilai hash adalah terhad kepada julat nilai int (kira-kira 4 bilion). Nilai baharu yang terhasil juga perlu ditulis di suatu tempat, dan untuk ini anda perlu menentukan di mana tepatnya ia akan ditulis. Ini dipanggil penyelesaian konflik. Terdapat dua pendekatan:

kaedah rantaian atau rantaian luaran (dilaksanakan dalam HashMap) - i.e. sel sebenarnya mengandungi senarai (rantai). Dan senarai itu mungkin sudah mengandungi beberapa nilai (tidak semestinya dengan kod cincang yang sama).
kaedah penyelidikan linear atau pengalamatan terbuka (dilaksanakan dalam IdentityHashMap) - terdiri daripada mencari sel kosong pertama selepas yang ditunjuk oleh fungsi cincang;

Anda boleh membaca tentang perlanggaran di sini: klik

Dengan menggunakan kaedah tersebut, put()kami akan menambah satu lagi pasangan nilai kunci pada pemetaan cincang:
```
map.put("BLAKE", 10);
```
Kami mengira "cincang awal" - 63281361. Kami mengubah suainya dan hasilnya kami mendapat kod cincang akhir - 63281940.
Memandangkan semakan pertama untuk "kekosongan" kini akan kembali palsu (tidak perlu membuat jadual), kami segera mengira indeks baldi di mana objek kami akan diletakkan:
```
i = (n - 1) & hash
i = (16 - 1) & 63281940
i = 4
```
Baldi pada indeks yang ditentukan diperiksa untuk kehadiran elemen di dalamnya, dan oleh kerana keadaan if ((p = tab[i = (n - 1) & hash]) == null)tidak dipenuhi dalam kes ini (sudah ada elemen dalam baldi), maka kita pergi ke blok else.
Pertama sekali, kami membandingkan elemen yang ditambahkan dengan elemen pertama senarai terpaut di dalam baldi:
```
(p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
```
При проверке сначала сравниваются хеши ключей. Если этот «участок» (p.hash == hash) возвращает false, тогда остальная часть условия игнорируется (&&), так How an objectы гарантированно разные. Иначе затем сравниваются ключи по ссылке (==) и в случае неequalsства, ключи сравниваются уже посредством метода equals(). Сравнение осуществляется в таком порядке во благо производительности. Если все три выражения возвращают true, это означает, что ключи равны и новый элемент будет записан в дополнительную переменную, чтобы в дальнейшем с её помощью перезаписать meaning у ключа:
```
if (e != null) { // existing mapping for key
      V oldValue = e.value;
      if (!onlyIfAbsent || oldValue == null)
      e.value = value;
      afterNodeAccess(e);
       return oldValue;
 }
```
В результате сравнения ключей мы получаем false уже на первом этапе (разные хеши).
Игнорируем condition (p instanceof TreeNode), так How структура в бакете не является древовидной на данном этапе.
Далее переходим в цикл for, где в пределах одного бакета проверяем у элементов указатель на следующий элемент next, и если он equals null (значит элемент в списке последний и единственный), добавляем новый элемент Node в конец списка:
```
if ((e = p.next) == null){
	p.next = newNode(hash, key, value, null)
... };
```
Вы можете спросить, а где же проверка на equalsство ключей? Мы же не можем просто взять и добавить новый элемент. Так вот она уже была заранее осуществлена в пункте (5). Благодаря этому, теперь мы можем просто проверить указатель этого element, и так How он сейчас equals null, можно сделать вывод о том, что в списке только один элемент. И так How мы уже проверяли их ключи, мы можем безболезненно добавлять новый элемент.

Если же при первой итерации указатель не equals null, это говорит о том, что в списке How минимум два element, поэтому в таком случае мы переходим к следующему условия и сравниваем ключ добавляемого element со всеми ключами элементов в списке (способом, описанным в пятом пункте).
```
if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
```
Если при сравнении ключей будет найдено совпадение, новый элемент будет записан в дополнительную переменную, чтобы в дальнейшем с её помощью перезаписать meaning у ключа.

После добавления второго element наш an object HashMap графически выглядит так:

В итоге, добавление элементов при коллизии (в пределах одного бакета) выглядит следующим образом:
- проверяем с помощью методов hashCode() и equals(), что оба ключа одинаковы.
- если ключи одинаковы, заменить текущее meaning новым.
- иначе связать новый и старый an objectы с помощью структуры данных "связный список", указав ссылку на следующий an object в текущем и сохранить оба под нужным индексом; либо осуществить переход к древовидной структуре
После каждой итерации (добавления нового element) в цикле for увеличивается счетчик, который отвечает за количество элементов в бакете:
```
for (int binCount = 0; ; ++binCount)
```
До тех пор, пока их количество не станет равно or больше 7:
```
binCount >= TREEIFY_THRESHOLD – 1
```
В таком случае произойдет вызов метода treeifyBin()treeify()для непосредственного построения древовидной структуры. Однако, если количество бакетов в текущей хеш-таблице меньше 64:
```
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
```
Daripada pergi ke struktur pokok, kaedah akan dipanggil resize()untuk meningkatkan saiz jadual cincang, mengagihkan semula elemen. treeify()seterusnya, senarai yang dipautkan TreeNodebertukar menjadi pokok merah-hitam. Kaedah ini resize()berulang melalui semua elemen storan semasa, mengira semula indeksnya (dengan mengambil kira saiz baharu) dan mengagihkan semula elemen ke dalam tatasusunan baharu.

Secara ringkas, tanpa membincangkan butiran struktur pokok merah-hitam, perkara berikut berlaku:
1. Elemen pertama senarai ditulis sebagai akar keseluruhan pokok (hitam):
```
if (root == null) {
    x.parent = null;
    x.red = false;
    root = x;
}
```
2. Untuk elemen lain:
  
  mengedarkannya ke kiri atau kanan bergantung pada nilai cincang:
```
if ((ph = p.hash) > h)
    dir = -1;
else if (ph < h)
    dir = 1;
```
  Semua anak kiri mestilah kurang daripada (atau sama dengan) nod akar mereka, manakala semua anak kanan mestilah lebih besar.
3. Jika dua elemen mempunyai cincang yang sama dan tidak boleh dibandingkan dengan cara lain (mereka tidak melaksanakan antara muka Comparable), kami mengganggu pembinaan pepohon dan memanggil kaedah itu tieBreakOrder(), yang seterusnya menggunakan kaedah asli System.identityHashCode()untuk mengira kod cincang unik di seluruh dunia .
  
  Butiran lanjut di sini: pautan ke artikel
4. Kami menyemak elemen pokok (objek TreeNode) sehingga unsur sifar kanak-kanak (kiri atau kanan) ditemui.
```
if ((p = (dir <= 0) ? p.left : p.right) == null)
```
5. Tambahkan nod anak (kiri atau kanan bergantung pada dir):
```
x.parent = xp;
if (dir <= 0)
    xp.left = x;
else
    xp.right = x;
```
6. Memandangkan penambahan elemen baharu boleh mengganggu keseimbangan pokok, kami memanggil kaedah untuk mengimbangi semula:
```
root = balanceInsertion(root, x);
```
  Anda boleh membaca tentang mengimbangi CCH di sini: habr
7. Selepas mengimbangi, elemen akar mungkin berubah. Kami membetulkannya dengan memanggil kaedah yang menjamin bahawa akar yang dihantar kepadanya akan menjadi nod pertama:
```
moveRootToFront(tab, root)
```
  Anda boleh melihat dengan jelas cara pokok merah-hitam dibina dan mengimbangi diri di sini: visualisasi

Itu sahaja, pada dasarnya, dan menggunakan contoh, mari kita anggap bahawa kita ingin menambah nama berikut sebagai kunci: KING, MARY, JOSE, ANNA, FRED, TONY, ALEX, PEPE. Dan katakan bahawa kita mempunyai sekurang-kurangnya 64 baldi dalam jadual cincang, dan semua elemen ini telah terkumpul dalam satu baldi. Secara struktur, baldi ini akan kelihatan seperti ini (elemen diisih mengikut kod cincang): Jenis CCHD:

Lihat di dalam baldi:

Mendapatkan semula elemen (mendapatkan semula nilai dengan kunci) Mengenai operasi menambah, ia agak mudah. Algoritma (apabila terdapat senarai terpaut dalam baldi) boleh ditulis seperti ini:

Kira kod cincang kunci.
Kira indeks baldi.
Pergi melalui indeks dan bandingkan kunci elemen pertama dengan nilai sedia ada. Jika ia sama, kembalikan nilai, jika tidak, semak elemen seterusnya, jika ia wujud.
Jika objek Nod seterusnya adalah null, kembalikan null.
Jika objek Nod seterusnya bukan nol, pergi kepadanya dan ulangi tiga langkah pertama sehingga elemen ditemui atau objek Node seterusnya adalah nol.

Menggunakan kaedah, get()kami mendapat nilai untuk kunci "KING":

map.get("KING");

Di dalam, kaedah dipanggil getNode(int hash, Object key), yang mana kunci itu sendiri (“KING”) dan cincangnya (2306996) diluluskan, yang diprakira dengan cara yang sama seperti semasa operasi put().

Kami menyemak:
1. adakah jadual hash wujud:(tab = table) != null
  
  Biar saya ingatkan anda bahawa apabila mencipta HashMap, tatasusunan untuk jadual tidak dibuat dalam pembina; ini berlaku kemudian dalam method resize(), yang selalu dipanggil apabila menambah elemen pertama pada jadual cincang. Oleh itu, jika tiada unsur telah ditambahkan pada HashMap, tiada tatasusunan dalaman untuk menyimpan elemen.
2. jika ungkapan sebelumnya kembali benar, anda perlu memastikan bahawa panjang tatasusunan dalaman lebih besar daripada 0:(n = tab.length) > 0;
3. jika ungkapan sebelumnya juga kembali benar, pergi ke baldi di indeks (dalam kes kami 4), yang telah dikira sebelum ini, dan semak untuk kehadiran unsur:
```
(first = tab[(n - 1) & hash]) != null)
```
4. Kami membandingkan kunci yang kami cari dengan kunci elemen pertama dalam senarai di dalam baldi, kerana dalam kebanyakan baldi akan ada (bukan di mana-mana sahaja kami berlanggar) hanya satu elemen (kes kami). Seperti dalam kes kaedah put(), cincang dibandingkan, dan jika ia sepadan, kunci dibandingkan dengan rujukan, dan hanya kemudian dengan equals().
```
if (first.hash == hash && // always check first node
    ((k = first.key) == key || (key != null && key.equals(k))))
```
  Memandangkan dalam kes kami, kekunci "KING" akan mendahului kekunci "BLAKE" (dalam senarai terpaut, elemen baharu ditambah pada penghujung, dan KING telah ditambah dahulu), kami akan berhenti pada ketika ini dan mengembalikan objek pertama taip Node kepada kaedah get(), yang "merampas" daripadanya medan dengan nilai (100):
```
return (e = getNode(hash(key), key)) == null ? null : e.value;
```
Jika terdapat lebih daripada satu elemen di dalam baldi, maka:
1. jika baldi ialah senarai terpaut, kami pergi melalui senarai melalui setiap elemen dalam gelung do – whilesehingga padanan ditemui:
```
do {
    if (e.hash == hash &&
        ((k = e.key) == key || (key != null && key.equals(k))))
        return e;
} while ((e = e.next) != null);
```
2. jika baldi adalah struktur pokok, maka kaedah itu juga dipanggil getTreeNode(), yang seterusnya menggunakan kaedah untuk mencari kunci yang diperlukan find(). Kami menjalankan carian pokok - cincang dibandingkan dan nod akar kiri atau kanan untuk carian ditentukan. Jika kekunci adalah sama (dengan rujukan atau oleh equals), kembalikan nod ini. Jika nod anak kiri atau kanan adalah batal, kami juga membandingkan kekunci menggunakan compareTo (jika kekunci melaksanakan antara muka Comparable), jika tidak, kami melakukan carian rekursif melalui pepohon (subpokok kanan atau kiri) sehingga padanan ditemui.

Mengalih keluar objek daripada HashMap Memandangkan ruang dalam artikel kehabisan, saya akan menerangkan secara ringkas bagaimana pemadaman berlaku dengan kunci. Algoritmanya sangat serupa:

pergi ke baldi yang dikehendaki (sekali lagi, ia telah dikira terlebih dahulu);
jika terdapat hanya satu objek dalam baldi (kami menyemak penuding nolnya) kami membandingkan cincang, pautan dan equals(jika tiba-tiba cincang tidak sama). Temui jodoh? Bagus, ini kunci kami - padamkannya (=null) dan kembalikan nilai kunci ini.
jika terdapat lebih daripada satu elemen dalam baldi, kami menyemak setiap elemen dalam gelung sehingga kami menjumpai elemen atau mencapai penghujung senarai.
jika elemen itu tidak dijumpai, kami mengembalikan null.

Dalam keadaan dengan pokok, terdapat pelaksanaan yang agak rumit, yang lebih baik tidak diketahui dan tidur dengan nyenyak (penerangan kaedah itu bahkan mengatakan bahawa pelaksanaannya lebih rumit daripada dalam operasi pemadaman biasa dalam merah-hitam pokok). Selain itu, apabila dipadamkan, bilangan nod dalam satu baldi boleh kembali kepada 6, dan kemudian pokok itu akan dibina semula ke dalam senarai terpaut. Jika anda bukan pembangun dengan pengalaman bertahun-tahun, ia tidak perlu sama sekali untuk mengetahui dan memahami perkara ini (dan sememangnya tidak perlu).

Komen

TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION