Analisis rinci babagan kelas HashMap

Sadurunge pindhah menyang diskusi rinci babagan kelas, ayo fokus ing konsep dhasar sing ana gandhengane karo tabel hash. Artikel iki ora bakal ngrembug cara kanggo nggarap pemetaan hash. Mung operasi sisipan, telusuran lan pambusakan bakal dibahas kanthi jelas lan rinci. Aku ora bakal angel maca katrangan babagan cara sing kasedhiya kanggo HashMap saka Schildt sing padha. Mbok menawa ing mangsa ngarep aku bakal nulis artikel liyane sing dikhususake kanggo metode kasebut, nanging saiki isih ana pitakonan. Dibandhingake karo Java 7, kelas HashMap ing Jawa 8 wis ngalami owah-owahan sing signifikan (+1000 baris kode). Sampeyan bisa maca babagan implementasine ing Jawa 7 ing kene (nanging ora relevan maneh): habr Tabel hash minangka struktur data sing ngetrapake antarmuka array asosiatif (model utawa entri nilai kunci abstrak), sing nyedhiyakake sisipan lan telusuran sing cepet banget: preduli. saka sisipan lan telusuran unsur nomer (lan kadhangkala pambusakan) ditindakake ing wektu sing cedhak karo konstanta - O (1). Ateges, iki minangka array biasa, ing ngendi lokasi unsur gumantung marang nilai unsur kasebut. Hubungan antarane nilai unsur lan posisi ing tabel hash ditemtokake dening fungsi hash. Fungsi hash njupuk potongan data input, sing diarani kunci , lan minangka output ngasilake integer sing dikenal minangka nilai hash (utawa kode hash) . Nilai hash banjur ngiket kunci kita menyang indeks tabel hash tartamtu. Kanggo operasi dhasar: nglebokake, nggoleki lan mbusak, kita nggunakake fungsi hash sing padha, mula operasi kasebut ditindakake kanthi cepet. Mulane, penting yen fungsi hash tumindak kanthi konsisten lan ngasilake indeks sing padha kanggo data input sing padha. Wigati dicathet menawa kode hash sing diasilake bisa dadi nilai numerik sing ageng, lan susunan asline mung dirancang kanggo 16 unsur. Apa ora nggawe larik karo milyar unsur kanggo nambah mung sepuluh? Mulane, kita kudu ngowahi kode hash iki dadi nilai saka 0 nganti 15 (yen ukuran array 16). Lan kanggo iki, transformasi tambahan digunakake. Supaya kita ngasilake indeks kanggo nyilikake ukuran array. Contone, ing HashMap sadurunge Java 8, cara tambahan iki digunakake kanggo nemokake sel sing dikarepake:

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

Minangka input, njupuk kode hash sing dipikolehi minangka asil karya hashCode()lan dawa array internal (jumlah sel). Lan ngasilake asil "kode hash" -> bitwise "AND" -> (panjang array - 1). Kelas HashMapwarisan saka kelas AbstractMaplan ngleksanakake antarmuka ing ngisor iki: Map, Cloneable, Serializable. .metode tanggung jawab kanggo fungsi hash ing Jawa hashCode(). Implementasi standar hashCode()ngasilake nilai sing diarani kode hash identitas . Malah yen kelas overrides hashCode(), sampeyan bisa tansah njaluk obyek ID hash dening nelpon System.identityHashCode(Object o). Implementasi standar hashCode()ing OpenJDK ora ana hubungane karo alamat memori, kaya sing kadhangkala dipercaya. Rincian liyane ing kene: habr Ing HashMap , tabel hash dileksanakake adhedhasar array (utawa, luwih tepat, dinamis, amarga tabel bisa nggedhekake) dhaptar sing disambung. Ateges, kita entuk kode hash kunci minangka asil saka metode kasebut hashCode(), sing banjur diowahi (kaya sing bakal kita nimbang mengko), lan sacara internal, kanthi nggunakake metode tambahan, nilai sing diasilake disebarake menyang sel sing dibutuhake. Unsur array (sel) uga disebut ember , sing digunakake kanggo nyimpen simpul individu. Saben ember minangka koleksi (dhaptar utawa wit). Node minangka obyek saka kelas bersarang Node(utawa TreeNodeing struktur wit). Nyatane, nang sel Uploaded LinkedListmung dumunung siji-sijine disambung dhaftar, utawa wit abang-ireng, kang underlies implementasine saka kelas liyane - TreeMap. Opsi karo wit abang-ireng ora asring muncul (carane, apa lan ing ngendi - ing ngisor iki), lan struktur iki cukup angel dimengerteni, mula penekanan bakal ana ing simpul saka jinis Node. Node minangka kelas bersarang ing njero HashMapsing nduweni kolom ing ngisor iki:

• final int hash- hash saka unsur saiki, sing dipikolehi minangka asil hashing tombol;
• final K key- tombol saka unsur saiki. Iki ngendi sampeyan nemtokake minangka obyek pisanan ing cara ditulis kanggo put();
• V value- Nilai saka unsur saiki. Lan apa sing sampeyan nemtokake minangka obyek kapindho ing cara ditulis ing kene put();
• Node < K, V> next- link menyang simpul sabanjuré ing basket padha. Dhaptar kasebut disambungake, mula mbutuhake link ora menyang simpul sabanjure, yen ana.

Saiki ayo goleki lapangan kelas HashMap dhewe:

• transient Node < K, V> [] table- tabel hash dhewe, diimplementasikake kanthi basis array, kanggo nyimpen pasangan kunci-nilai ing wangun simpul. Iki ngendi Node kita disimpen;
• transient int size- nomer pasangan kunci-nilai;
• int threshold- jumlah maksimum unsur, nalika tekan ukuran tabel hash tikel. Dietung nggunakake rumus (kapasitas * loadFactor);
• final float loadFactor- parameter iki nemtokake apa tingkat beban tabel hash saiki perlu kanggo nggawe tabel hash anyar, i.e. sanalika tabel hash kebak 75%, tabel hash anyar bakal digawe lan unsur saiki bakal dipindhah menyang (operasi larang regane, amarga kabeh unsur kudu rehashed);
• transient Set< Map.Entry< K,V>> entrySet- ngandhut cached entrySet(), karo kang kita bisa iterate HashMap.

Lan konstanta:

• static final int DEFAULT_INITIAL_CAPACITY= 1 << 4- kapasitas tabel hash standar (16);
• static final int MAXIMUM_CAPACITY = 1 << 30- kapasitas maksimal tabel hash (kira-kira 1 milyar);
• static final float DEFAULT_LOAD_FACTOR = 0.75f- faktor beban standar;
• static final int TREEIFY_THRESHOLD = 8minangka "ambang" saka jumlah unsur ing siji ember, nalika tekan dhaptar sing disambung internal bakal diowahi dadi struktur wit (wit abang-ireng).
• static final int UNTREEIFY_THRESHOLD = 6- yen jumlah unsur ing siji basket suda kanggo 6, banjur transisi mbalikke saka wit menyang dhaftar disambung bakal kelakon;
• static final int MIN_TREEIFY_CAPACITY = 64- kapasitas minimal (jumlah ember) saka tabel hash ing ngendi transisi menyang struktur wit bisa. Sing. Yen paling ora ana 64 ember ing tabel hash lan ana 8 utawa luwih unsur ing siji ember, banjur transisi menyang struktur wit bakal kedadeyan.

Konstruktor kelas:

1. public HashMap()- nggawe tampilan hash kanthi standar: kanthi volume (capacity) = 16lan kanthi faktor beban (load factor) = 0.75;
2. public HashMap(Map< ? extends K, ? extends V> m)- nggawe pemetaan hash sing diinisialisasi dening unsur pemetaan liyane sing diwenehake kanthi kapasitas awal sing cukup kanggo nampung unsur pemetaan liyane;
3. public HashMap(int initialCapacity)- nggawe peta hash kanthi kapasitas awal sing diwenehake. Supaya HashMap bisa digunakake kanthi bener lan bener, ukuran array internal kudu dadi loro (yaiku 16, 64, 128, lsp);
4. public HashMap(int initialCapacity, float loadFactor)- nggawe peta hash kanthi paramèter sing ditemtokake: kapasitas awal lan faktor beban.

A kelas ngleksanakake antarmuka Maplan ngluwihi kelas AbstractMaptanpa nambah cara dhewe. Peta hash ora njamin urutan unsur kasebut. Mulane, urutan unsur sing dilebokake ing peta hash ora mesthi urutan sing dijupuk dening iterator. Nambahake Obyek Nambahake pasangan kunci-nilai wis rampung nggunakake put(). Ayo ndeleng langkah-langkah nalika nambah obyek:

1. Nilai hash saka kunci obyek sing dilebokake diitung. Hash tombol diitung kanthi cara static final int hash(Object key)sing wis ngakses hashCode()metode kunci sing kita kenal. Kanggo nindakake iki, salah siji cara overridden hashCode()utawa implementasine standar digunakake. Transformasi tambahan ing metode 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.

2. Вычисляем индекс бакета (ячейки массива), в который будет добавлен наш элемент:

   
   i = (n - 1) & hash

   где n – длина массива.

3. Создается an object Node.

4. Теперь, зная индекс в массиве, мы получаем список (цепочку) элементов, привязанных к этой ячейке. Если в бакете пусто, тогда просто размещаем в нем элемент. Иначе хэш и ключ нового 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. Ing wektu sing padha, kita ngetung indeks ember ing ngendi obyek bakal diselehake lan mriksa apa wis ana unsur. Kita ngitung:

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

      mrikso:

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

   6. Amarga minangka asil saka mriksa kita entuk bener (ora ana unsur ing ember), obyek Node kanthi kolom ing ngisor iki bakal diasilake:

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

      Objek Node sing digawe bakal ditambahake menyang ember ing indeks [4]:

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

      newNode()minangka cara sing mung ngasilake obyek saka kelas Node.

   7. Sawise ditambahake, priksa bakal ditindakake kanggo ndeleng manawa jumlah unsur saiki ngluwihi parameter threshold:

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

      Yen ngluwihi, banjur cara bakal diarani resize()kanggo nambah ukuran tabel hash.

      Ing titik iki, cara putVal()(lan, mungguh put()) bakal ngrampungake karyane.

      Asil kasebut bisa dituduhake kanthi grafis kaya ing ngisor iki:

      Umumé, iki sing nambah Node (pasangan kunci-nilai) menyang tabel hash katon yen ember sing dikarepake kosong . Saiki ayo nyoba nambah unsur sing bakal nyebabake tabrakan (yen ana luwih saka siji unsur ing siji ember).

A little about collisions Kahanan nalika tombol beda mungkasi ing ember padha (sanajan karo Hash beda) diarani tabrakan utawa tabrakan. Sanajan tabel hash luwih gedhe tinimbang set data lan fungsi hash sing apik wis dipilih, iki ora njamin tabrakan ora bakal kedadeyan. Lan nilai hash diwatesi ing sawetara nilai int (udakara 4 milyar). Nilai anyar sing diasilake uga kudu ditulis nang endi wae, lan kanggo iki sampeyan kudu nemtokake ngendi persis bakal ditulis. Iki diarani resolusi konflik. Ana rong pendekatan:

• chaining external utawa cara chaining (dilaksanakake ing HashMap) - i.e. sel bener ngemot dhaftar (chain). Lan dhaptar kasebut bisa uga ngemot sawetara nilai (ora kudu nganggo kode hash sing padha).
• linear probing utawa cara mbukak alamat (dilaksanakake ing IdentityHashMap) - kasusun saka nggoleki sel kosong pisanan sawise siji nuding dening fungsi hash;

Sampeyan bisa maca babagan tabrakan ing kene: klik

1. Nggunakake metode kasebut, put()kita bakal nambah pasangan nilai kunci liyane menyang pemetaan hash:

   map.put("BLAKE", 10);

2. Kita ngetung "hash awal" - 63281361. Kita ngowahi lan minangka asil entuk kode hash final - 63281940.

3. Wiwit mriksa pisanan "kosong" saiki bakal bali palsu (ora perlu nggawe tabel), kita langsung ngetung indeks ember ing ngendi obyek bakal diselehake:

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

4. Ember ing indeks kasebut dicenthang kanggo anané unsur, lan amarga kondisi kasebut if ((p = tab[i = (n - 1) & hash]) == null)ora ditemokake ing kasus iki (wis ana unsur ing ember), banjur pindhah menyang blok else.

5. Kaping pisanan, kita mbandhingake unsur sing ditambahake karo unsur pisanan saka dhaptar sing disambung ing ember:

   (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 уже на первом этапе (разные хеши).

6. Игнорируем condition (p instanceof TreeNode), так How структура в бакете не является древовидной на данном этапе.

7. Далее переходим в цикл 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 в текущем и сохранить оба под нужным индексом; либо осуществить переход к древовидной структуре

8. После каждой итерации (добавления нового 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)

   Tinimbang menyang struktur wit, cara bakal diarani resize()kanggo nambah ukuran tabel hash, nyebarake unsur kasebut. treeify()ing siji, dhaftar disambung TreeNodengowahi menyang wit abang-ireng. Cara kasebut resize()ngliwati kabeh unsur panyimpenan saiki, ngitung maneh indeks kasebut (njupuk ukuran anyar) lan nyebarake unsur kasebut menyang array anyar.

   Sedhela, tanpa nerangake rincian struktur wit abang-ireng, kedadeyan ing ngisor iki:

   1. Unsur pisanan saka dhaptar ditulis minangka oyod saka kabeh wit (ireng):

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

   2. Kanggo unsur liyane:

      disebarake ing sisih kiwa utawa tengen gumantung saka nilai hash:

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

      Kabeh bocah kiwa kudu kurang saka (utawa padha karo) simpul akar, dene kabeh bocah tengen kudu luwih gedhe.

   3. Yen rong unsur duwe hash sing padha lan ora bisa dibandhingake kanthi cara liya (ora ngleksanakake antarmuka Comparable), kita ngganggu pambangunan wit kasebut lan nelpon metode kasebut tieBreakOrder(), sing banjur nggunakake metode asli System.identityHashCode()kanggo ngetung kode hash sing unik ing saindenging jagad. .

      Rincian liyane ing kene: link menyang artikel

   4. Kita mriksa unsur wit (obyek TreeNode) nganti ana unsur nol bocah (kiwa utawa tengen) ditemokake.

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

   5. Tambah simpul anak (ngiwa utawa nengen gumantung ing dir):

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

   6. Amarga nambahake unsur anyar bisa ngganggu keseimbangan wit, kita nyebutake cara kanggo ngimbangi maneh:

      root = balanceInsertion(root, x);

      Sampeyan bisa maca babagan ngimbangi CCH ing kene: habr

   7. Sawise imbangan, unsur ROOT bisa diganti. Kita ndandani iki kanthi nelpon cara sing njamin yen oyod kasebut bakal dadi simpul pertama:

      moveRootToFront(tab, root)

      Sampeyan bisa ndeleng kanthi jelas carane wit abang-ireng dibangun lan ngimbangi awake dhewe ing kene: visualisasi

Iku kabeh, ing prinsip, lan nggunakake conto, ayo nganggep yen kita pengin nambah jeneng ing ngisor iki minangka kunci: KING, MARY, JOSE, ANNA, FRED, TONY, ALEX, PEPE. Lan ayo ngomong yen kita duwe paling ora 64 ember ing tabel hash, lan kabeh unsur kasebut wis diklumpukake ing siji ember. Secara struktural, ember iki bakal katon kaya iki (unsur diurutake miturut kode hash): Jinis CCHD: Deleng ing jero ember: Nompo unsur (njupuk nilai dening tombol) Babagan operasi nambah, iku cukup prasaja. Algoritma (nalika ana dhaptar sing disambung ing ember) bisa ditulis kaya iki:

1. Etung kode hash saka kunci.
2. Ngitung indeks ember.
3. Bukak indeks lan mbandhingake kunci unsur pisanan karo nilai sing ana. Yen padha, bali Nilai, digunakake mriksa unsur sabanjuré, yen ana.
4. Yen obyek Node sabanjuré null, bali null.
5. Yen obyek Node sabanjuré ora null, pindhah menyang lan baleni telung langkah pisanan nganti unsur ketemu utawa obyek Node sabanjuré null.

Nggunakake metode kasebut, get()kita entuk nilai kanggo tombol "KING":

map.get("KING");

Ing njero, metode kasebut diarani getNode(int hash, Object key), ing ngendi tombol kasebut dhewe ("KING") lan hash (2306996) dilewati, sing wis diwilang kanthi cara sing padha nalika operasi put().

1. Kita mriksa:

   1. apa tabel hash uga ana:(tab = table) != null

      Ayo kula ngelingake yen nalika nggawe HashMap, array kanggo tabel ora digawe ing konstruktor; iki kedadeyan mengko ing metode resize(), sing tansah diarani nalika nambah unsur pisanan ing tabel hash. Mulane, yen ora ana unsur sing ditambahake ing HashMap, ora ana array internal kanggo nyimpen unsur kasebut.

   2. yen ekspresi sadurunge bali bener, sampeyan kudu nggawe manawa dawa array internal luwih saka 0:(n = tab.length) > 0;

   3. Yen ekspresi sadurunge uga bali bener, pindhah menyang ember ing indeks (ing kasus kita 4), sing wis diwilang sadurunge, lan priksa manawa ana unsur:

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

   4. Kita mbandhingake kunci sing kita goleki karo kunci unsur pisanan ing dhaptar ing ember, amarga ing paling ember bakal ana (ora ana tabrakan ing endi wae) mung siji unsur (kasus kita). Kaya ing kasus cara put(), hash dibandhingake, lan yen padha cocog, tombol dibandhingake karo referensi, lan mung banjur equals().

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

      Wiwit ing kasus kita, tombol "KING" bakal ndhisiki tombol "BLAKE" (ing dhaptar sing disambung, unsur-unsur anyar ditambahake ing pungkasan, lan KING ditambahake dhisik), kita bakal mandheg ing titik iki lan bali obyek pisanan saka ketik Node menyang metode get (), sing "ngrebut" saka lapangan kanthi nilai (100):

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

2. Yen ana luwih saka siji unsur ing ember, banjur:

   1. yen ember minangka dhaptar sing digandhengake, kita mbukak dhaptar liwat saben unsur ing daur ulang do – whilenganti cocog ditemokake:

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

   2. yen ember minangka struktur wit, banjur cara kasebut uga diarani getTreeNode(), sing banjur nggunakake cara kanggo nemokake kunci sing dibutuhake find(). Kita nindakake telusuran wit - hashes dibandhingake lan simpul ROOT kiwa utawa tengen kanggo nggoleki ditemtokake. Yen tombol padha (kanthi referensi utawa dening equals), bali simpul iki. Yen kelenjar anak kiwa utawa tengen null, kita tambahan mbandhingaké tombol nggunakake compareTo (yen tombol ngleksanakake antarmuka Comparable), digunakake kita nindakake search rekursif liwat wit (subtree tengen utawa kiwa) nganti match ketemu.

Mbusak obyek saka HashMap Wiwit spasi ing artikel wis entek, aku bakal njlèntrèhaké sedhela carane pambusakan ana dening tombol. Algoritma kasebut meh padha:

• pindhah menyang ember sing dikarepake (maneh, wis diwilang sadurunge);

• yen ana mung siji obyek ing ember (kita mriksa null pointer sawijining) kita mbandhingaké hash, pranala lan equals(yen dumadakan hash ora padha). Nemokake sing cocog? Apik, iki kunci kita - mbusak (= null) lan bali nilai kunci iki.

• yen ana luwih saka siji unsur ing ember, kita mriksa saben unsur ing daur ulang nganti kita nemokake unsur utawa tekan mburi dhaftar.

• yen unsur ora ketemu, bali null.

Ing kahanan karo wit ana implementasine rada angel, kang iku luwih apik kanggo ora ngerti bab lan turu soundly (gambaran saka cara malah ngandika sing implementasine luwih rumit tinimbang ing operasi pambusakan biasa ing abang-ireng. wit). Menapa malih, nalika dibusak, jumlah simpul ing siji ember bisa bali menyang 6, lan banjur wit bakal dibangun maneh menyang dhaftar disambung. Yen sampeyan dudu pangembang kanthi pengalaman pirang-pirang taun, ora perlu ngerti lan ngerti iki (lan mung ora perlu).