HashMap synpynyň jikme-jik derňewi

Synp barada jikme-jik pikir alyşmaga geçmezden ozal, hash tablisalary bilen baglanyşykly esasy düşünjelere üns bereliň. Bu makalada hash kartasy bilen işlemegiň usullary ara alnyp maslahatlaşylmaz. Diňe goýmak, gözlemek we öçürmek amallary aýdyň we jikme-jik ara alnyp maslahatlaşylar. Şol bir Şildtden HashMap üçin elýeterli usullaryň düşündirişini okamak kyn bolmaz diýip pikir edýärin. Belki, geljekde şeýle usullara bagyşlanan başga bir makala ýazaryn, ýöne häzirlikçe bu sorag. Java 7 bilen deňeşdirilende, Java 8-de HashMap synpynda düýpli üýtgeşmeler boldy (+1000 setir kod). Java 7-de ýerine ýetirilişi barada şu ýerden okap bilersiňiz (ýöne indi ähmiýeti ýok): habr Haş tablisasy assosiatiw massiw interfeýsini (abstrakt açar baha modeli ýa-da giriş) amala aşyrýan maglumat gurluşy bolup , örän çalt girizmegi we gözlemegi üpjün edýär: garamazdan san elementlerini goýmak we gözlemek (we käwagt öçürmek) hemişelik - O (1) ýakyn wagtda ýerine ýetirilýär. Aslynda, bu yzygiderli massiw, elementiň ýerleşişi elementiň bahasyna baglydyr. Bir elementiň bahasy bilen hash tablisasyndaky ornunyň arasyndaky baglanyşyk hash funksiýasy bilen kesgitlenýär. Haş funksiýasy , açar diýip atlandyrýan giriş maglumatlarymyzy alýar we çykyş hökmünde hash bahasy (ýa-da hash kody) diýlip atlandyrylýan bitewi bitewi san çykarýar . Soňra hash bahasy açarymyzy belli bir hash tablisasynyň indeksine baglaýar. Esasy amallar üçin: goýmak, gözlemek we pozmak, şol bir hash funksiýasyny ulanýarys, şonuň üçin bu amallar gaty çalt ýerine ýetirilýär. Şol sebäpli hash funksiýasynyň yzygiderli hereket etmegi we şol bir giriş maglumatlary üçin şol bir görkezijini çykarmagy möhümdir. Alnan hash kodunyň ägirt uly san bahasy bolup biljekdigini we asyl massiwiň şertli ýagdaýda diňe 16 element üçin döredilendigini bellemelidiris. Diňe on goşmak üçin milliard elementli massiw döretmeli däl? Şonuň üçin bu hash koduny nädip 0-dan 15-e çenli bahalara öwürmeli (massiwiň ululygy 16 bolsa). Munuň üçin goşmaça üýtgeşmeler ulanylýar. Şeýlelik bilen, massiwiň ululygyny azaltmak üçin indeks döredýäris. Mysal üçin, Java 8-den öň HashMap-da islenýän öýjügi tapmak üçin bu goşmaça usul ulanyldy:

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

hashCode()Giriş hökmünde, işiň we içerki massiwiň uzynlygy (öýjükleriň sany) netijesinde alnan hash koduny aldy . Netijäni bolsa “hash kody” -> birneme “AND” -> (massiwiň uzynlygy - 1) gaýtardy. Synp HashMapsynpdan miras alýar we AbstractMapaşakdaky interfeýsleri amala aşyrýar: Map,, Cloneable. Serializable.Metod Java-daky hash funksiýasyna jogapkärdir hashCode(). Adaty ýerine ýetiriş, şahsyýet hash kodyhashCode() diýilýän bahany yzyna gaýtaryp berýär . Bir synp ýok bolsa-da , elmydama jaň edip obýektiň ID hashini alyp bilersiňiz . OpenJDK-da deslapky ýerine ýetiriş, käwagt ynanylyşy ýaly, ýat salgysy bilen hiç hili baglanyşygy ýok. Bu ýerde has jikme-jiklikler: habr “HashMap” -da hash tablisasy ýeke-täk baglanyşdyrylan sanawlaryň massiwine (ýa-da has takygy dinamiki, sebäbi tablisa giňelip bilýär) esaslanýar. Aslynda, soňra üýtgedilen (soňrak serederis) usulyň netijesinde açaryň hash koduny alýarys we içerde goşmaça usul ulanyp, emele gelen bahalar zerur öýjüklere paýlanýar. Array elementlerine (öýjüklere) aýratyn düwünleri saklamak üçin ulanylýan çelekler hem diýilýär . Çelekleriň hersi ýygyndydyr (sanaw ýa-da agaç). Düwün, höwürtgelenen synpyň obýekti (ýa-da agaç gurluşynda). Aslynda, massiw öýjüginiň içinde diňe bir baglanyşdyrylan sanaw ýa-da başga bir synpyň durmuşa geçirilmeginiň esasyny düzýän gyzyl-gara agaç ýerleşýär - . hashCode()System.identityHashCode(Object o)hashCode()hashCode()NodeTreeNodeLinkedListTreeMap

Gyzyl-gara agaçly wariant beýle ýygy-ýygydan ýüze çykmaýar (nädip, näme we nirede - aşakda) we bu gurluşa düşünmek gaty kyn, şonuň üçin düwün görnüşiniň düwünine üns berler. Düwün,HashMap içindäki aşakdaky meýdanlary bolan içerki synpdyr :

final int hash- açary ýuwmagyň netijesinde alýan häzirki elementiň hasy;
final K key- häzirki elementiň açary. Usulda ilkinji obýekt hökmünde kesgitlän zadyňyz şu ýere ýazylýar put();
V value- häzirki elementiň bahasy. Usulda ikinji obýekt hökmünde kesgitlän zadyňyz şu ýerde ýazylýar put();
Node < K, V> next- şol sebediň içindäki indiki düwün bilen baglanyşyk. Sanaw birikdirildi, şonuň üçin indiki düwün bilen däl-de, bir baglanyşyk bar bolsa.

Indi “HashMap” synpynyň meýdanlaryna seredeliň:

transient Node < K, V> [] table- düwme görnüşinde açar bahaly jübütleri saklamak üçin massiw esasynda ýerine ýetirilen hash tablisasynyň özi. Bu ýerde düwünlerimiz saklanýar;
transient int size- açar bahaly jübütleriň sany;
int threshold- hash tablisasynyň ululygy iki esse artan elementleriň sany. Formula (kuwwat * loadFactor) ulanyp hasaplanýar;
final float loadFactor- bu parametr, täze hash tablisasyny döretmek üçin häzirki hash tablisasynyň haýsy derejede ýüklenmelidigini kesgitleýär. Haş tablisasy 75% doly bolansoň, täze hash tablisasy dörediler we häzirki elementler oňa geçiriler (gymmat bahaly amal, sebäbi ähli elementler täzeden işlenmeli);
transient Set< Map.Entry< K,V>> entrySet- keş görnüşinde bolup entrySet(), ony gaýtalap bileris HashMap.

Yzygiderli:

static final int DEFAULT_INITIAL_CAPACITY= 1 << 4- deslapky hash tablisasynyň kuwwaty (16);
static final int MAXIMUM_CAPACITY = 1 << 30- hash tablisasynyň mümkin bolan iň ýokary kuwwaty (takmynan 1 milliard);
static final float DEFAULT_LOAD_FACTOR = 0.75f- esasy ýük faktory;
static final int TREEIFY_THRESHOLD = 8bir çelekdäki elementleriň sanynyň “bosagasy” bolup, içerki baglanyşyk sanawy agaç gurluşyna (gyzyl-gara agaç) öwrüler.
static final int UNTREEIFY_THRESHOLD = 6- bir sebetdäki elementleriň sany 6-a çenli azalsa, agaçdan baglanyşyk sanawyna ters geçiş bolar;
static final int MIN_TREEIFY_CAPACITY = 64- agaç gurluşyna geçmegiň mümkin bolan hash tablisasynyň iň pes kuwwaty (çelekleriň sany). Bular. Haş tablisasynda azyndan 64 çelek bar bolsa we bir çelekde 8 ýa-da has köp element bar bolsa, agaç gurluşyna geçiş bolar.

Synp gurluşykçylary:

public HashMap()- tertip boýunça hash displeýini döredýär: göwrümi (capacity) = 16we ýük faktory bilen (load factor) = 0.75;
public HashMap(Map< ? extends K, ? extends V> m)- başga bir kartalaşdyrmagyň elementlerini ýerleşdirmek üçin ýeterlik bolan başlangyç kuwwaty bolan başga bir berlen kartanyň elementleri bilen başlanan hash kartasyny döredýär;
public HashMap(int initialCapacity)- berlen başlangyç kuwwatly hash kartasyny döredýär. “HashMap” -yň dogry we dogry işlemegi üçin içerki massiwiň ululygy iki güýç bolmaly (ýagny 16, 64, 128 we ş.m.);
public HashMap(int initialCapacity, float loadFactor)- görkezilen parametrler bilen hash kartasyny döredýär: başlangyç kuwwat we ýük faktory.

Bir synp interfeýsi amala aşyrýar we öz usullaryny goşmazdan Mapsynpy giňeldýär . Haş kartasy elementleriniň tertibini kepillendirmeýär. Şonuň üçin elementleriň hash kartasyna giriziliş tertibi hökmany suratda iterator tarapyndan alynýan tertip däl. Obýektleri goşmak Açar bahaly jübüt goşmak, ulanylýar . Obýekt goşanyňyzda ýerine ýetirilen ädimlere seredeliň: AbstractMapput()

Girizilen obýektiň açarynyň hash bahasy hasaplanýar. Esasy hash, bilýän esasy usulymyza static final int hash(Object key)eýýäm girýän usul bilen hasaplanýar . hashCode()Munuň üçin ýa-da artykmaç usul hashCode()ýa-da deslapky ýerine ýetiriş ulanylýar. Usulda goşmaça üýtgeşmeler 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. Şol bir wagtyň özünde, obýektimiziň ýerleşdiriljek çelegiň indeksini hasaplaýarys we onda eýýäm elementleriň bardygyny ýa-da ýokdugyny barlaýarys. Hasaplaýarys:
```
i = (n - 1) & hash
i = (16 - 1) & 2306996
i = 4
```
  barla:
```
if ((p = tab[i = (n - 1) & hash]) == null)
```
6. Barlagyň netijesinde hakykat bolýandygymyz üçin (çelekde element ýok), aşakdaky meýdanlar bilen düwün obýekti dörediler:
```
{
int hash = 2306996 — сгенерированный хеш-code
String key = {"KING"} — ключ
Integer value = 100 — meaning
Node next = null — link на следующий узел
}
```
  Döredilen düwün obýektimiz, indeksiň aşagyndaky çelege goşular [4]:
```
tab[i] = newNode(hash, key, value, null);
tab[4] = newNode(2306996, “KING”, 100, null);
```
  newNode()düwün synpynyň obýektini diňe yzyna gaýtaryp berýän usuldyr.
7. Goşandan soň, häzirki elementleriň sanynyň parametrden ýokarydygyny ýa-da ýokdugyny barlamak üçin barlag geçiriler threshold:
```
if (++size > threshold)
    resize();
```
  resize()Artyk bolsa, hash tablisasynyň göwrümini köpeltmek üçin bir usul çagyrylar .
  
  Bu pursatda usul putVal()(we degişlilikde put()) işini tamamlar.
  
  Netijäni grafiki görnüşde görkezip bolar:
  
  Umuman aýdylanda, hash tablisasyna düwün (açar-baha jübüti) goşmak, islenýän çelek boş bolsa meňzeýär . Indi çaknyşmaga sebäp boljak element goşmaga synanyşalyň (bir çelekde birden köp element bar bolsa).

Çaknyşyklar barada azajyk Dürli düwmeleriň bir bedrä (hatda dürli heşler bilen) gutarýan ýagdaýyna çaknyşyk ýa-da çaknyşyk diýilýär. Haş tablisasy maglumatlar toplumyndan has uly we gowy hash funksiýasy saýlanan hem bolsa, bu çaknyşyklaryň ýüze çykmajakdygyny kepillendirmeýär. Haş bahasy bolsa int bahalarynyň diapazony bilen çäklenýär (takmynan 4 milliard). Netijede täze baha bir ýerde ýazylmaly we munuň üçin nirede ýazyljakdygyny kesgitlemeli. Muňa dawa çözmek diýilýär. Iki çemeleşme bar:

daşarky zynjyr ýa-da zynjyr usuly (HashMap-da durmuşa geçirilýär) - ýagny öýjük aslynda sanawy (zynjyry) öz içine alýar. Sanawda eýýäm birnäçe bahalar bolup biler (hökmany suratda şol bir hash kody bilen däl).
çyzykly gözleg ýa-da açyk salgylanma usuly (IdentityHashMap-da amala aşyrylýar) - hash funksiýasy bilen görkezileninden soň ilkinji boş öýjügi gözlemekden ybarat;

Çaknyşyklar hakda şu ýerden okap bilersiňiz: basyň

Usuly ulanyp, put()hash kartasyna başga bir möhüm ähmiýetli jübüt goşarys:
```
map.put("BLAKE", 10);
```
“Deslapky hash” - 63281361 hasaplaýarys. Ony üýtgedýäris we netijede iň soňky hash koduny alýarys - 63281940.
“Boşluk” baradaky ilkinji barlag indi ýalňyş gaýdyp geler (tablisa döretmegiň zerurlygy ýok), obýektimiziň ýerleşdiriljek çeleginiň görkezijisini derrew hasaplaýarys:
```
i = (n - 1) & hash
i = (16 - 1) & 63281940
i = 4
```
Görkezilen indeksdäki çelek, elementleriň bardygyny barlaýar we if ((p = tab[i = (n - 1) & hash]) == null)bu ýagdaýda şert ýerine ýetirilmänsoň (çelekde eýýäm bir element bar), soň bolsa bloklara geçýäris else.
Ilki bilen, goşulýan elementi çelegiň içindäki baglanyşyk sanawynyň birinji elementi bilen deňeşdirýäris:
```
(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)
```
resize()Agaç gurluşyna gitmegiň ýerine, elementleri paýlap, hash tablisasynyň göwrümini köpeltmek usuly çagyrylar . öz gezeginde gyzyl-gara agaja öwrülenleriň treeify()sanawy . TreeNodeUsul resize()häzirki ammaryň ähli elementleriniň üsti bilen gaýtalanýar, indekslerini täzeden hasaplaýar (täze ululygy göz öňünde tutup) we elementleri täze massiwde paýlaýar.

Gysgaça, gyzyl-gara agajyň gurluşy barada jikme-jik maglumat bermezden aşakdakylar bolýar:
1. Sanawyň birinji elementi tutuş agajyň kökü (gara) hökmünde ýazylýar:
```
if (root == null) {
    x.parent = null;
    x.red = false;
    root = x;
}
```
2. Beýleki elementler üçin:
  
  hash bahasyna baglylykda olary çepe ýa-da saga paýlaň:
```
if ((ph = p.hash) > h)
    dir = -1;
else if (ph < h)
    dir = 1;
```
  Lefthli çep çagalar kök düwüninden pes bolmaly (ýa-da deň bolmaly), sag çagalaryň hemmesi uly bolmaly.
3. Iki elementiň birmeňzeş hasasy bar bolsa we başga bir görnüşde deňeşdirip bolmaýan bolsa (interfeýsi amala aşyrmaýarlar Comparable), agajyň gurluşygyna päsgel berýäris we bu usul öz gezeginde dünýä derejesinde üýtgeşik hash koduny hasaplamak üçin tieBreakOrder()ýerli usuly ulanýar. System.identityHashCode().
  
  Has giňişleýin maglumat: makala baglanyşyk
4. Çaga elementlerini (zatlary TreeNode) çaga (çep ýa-da sag) nol element tapylýança barlaýarys.
```
if ((p = (dir <= 0) ? p.left : p.right) == null)
```
5. Çaga düwünini goşuň (direktora baglylykda çep ýa-da saga):
```
x.parent = xp;
if (dir <= 0)
    xp.left = x;
else
    xp.right = x;
```
6. Täze element goşmak agajyň deňagramlylygyny bozup biljekdigi sebäpli, deňagramlaşdyrmagyň usuly diýýäris:
```
root = balanceInsertion(root, x);
```
  CCH-ni deňleşdirmek barada şu ýerden okap bilersiňiz: habr
7. Deňagramlaşdyrylandan soň kök elementi üýtgäp biler. Muny köküň ilkinji düwün boljakdygyny kepillendirýän usuly çagyryp düzedýäris:
```
moveRootToFront(tab, root)
```
  Gyzyl-gara agajyň nädip gurlandygyny we öz-özüni deňleşdirýändigini aç-açan görüp bilersiňiz: wizuallaşdyrma

Bularyň hemmesi, esasan we mysal ulanyp, aşakdaky atlary açar hökmünde goşmak isleýäris diýip pikir edeliň: KING, MARY, JOSE, ANNA, FRED, TONY, ALEX, PEPE. Haş tablisasynda azyndan 64 bedre bar we bu elementleriň hemmesi bir çelekde jemlenendigini aýdalyň. Gurluş taýdan bu çelek şeýle bolar (elementler hash kody boýunça tertiplenýär): CCHD görnüşi:

Çelegiň içine serediň:

Elementleri almak (açar bilen bahany almak) Goşmak amaly barada aýdylanda, bu gaty ýönekeý. Algoritm (çelekde baglanyşyk sanawy bar bolsa) şeýle ýazylyp bilner:

Düwmäniň hash koduny hasaplaň.
Çelek indeksini hasaplaň.
Indeksden geçiň we birinji elementiň açaryny bar bolan baha bilen deňeşdiriň. Deň bolsa, bahany yzyna gaýtaryň, ýogsam indiki elementiň bardygyny barlaň.
Indiki düwün obýekti ýok bolsa, null yzyna gaýtaryň.
Indiki düwün obýekti ýok bolsa, oňa gidiň we element tapylýança ýa-da indiki düwün obýekti ýok bolýança ilkinji üç ädimi gaýtalaň.

Usuly ulanyp, get()“KING” düwmesiniň bahasyny alarys:

map.get("KING");

Içinde, açar özi (“KING”) we hash (2306996) geçýän usul diýilýär getNode(int hash, Object key), bu amal wagtynda bolşy ýaly öňünden hasaplanýar put().

Barlaýarys:
1. hatda hash tablisasy hem barmy:(tab = table) != null
  
  “HashMap” döredilende, konstruktorda tablisa üçin bir massiw döredilmeýändigini ýatladýaryn, bu resize()hash tablisasyna ilkinji element goşulanda hemişe çagyrylýan usulda bolýar. Şonuň üçin “HashMap” -a hiç hili element goşulmadyk bolsa, elementleri saklamak üçin içerki massiw ýok.
2. öňki aňlatma hakykata gaýdyp gelse, içerki massiwiň uzynlygynyň 0-dan ulydygyna göz ýetirmeli:(n = tab.length) > 0;
3. öňki aňlatma hem hakykata gaýdyp gelse, öň hasaplanan indeksdäki çelege gidiň (biziň ýagdaýymyzda 4) we elementleriň bardygyny barlaň:
```
(first = tab[(n - 1) & hash]) != null)
```
4. Gözleýän açarymyzy çelegiň içindäki sanawdaky birinji elementiň açary bilen deňeşdirýäris, sebäbi çelekleriň köpüsinde diňe bir element (biziň ýagdaýymyz) bolmaz. Usulda bolşy ýaly put(), haslar deňeşdirilýär we gabat gelýän bolsa, düwmeler salgylanma bilen deňeşdirilýär we diňe şondan soň equals().
```
if (first.hash == hash && // always check first node
    ((k = first.key) == key || (key != null && key.equals(k))))
```
  Biziň ýagdaýymyzda, “Patyşa” açary “BLAKE” açaryndan öňe geçer (baglanyşdyrylan sanawyň içinde soňuna täze elementler goşular we KING ilki goşuldy), şu pursatda durarys we ilkinji obýektini yzyna gaýtaryp bereris; ondan (100) bahasy bolan bir meýdany “alýan” (get) usulyna düwün ýazyň:
```
return (e = getNode(hash(key), key)) == null ? null : e.value;
```
Çelegiň içinde birden köp element bar bolsa, onda:
1. do – whileçelek birleşdirilen sanaw bolsa, sanaw tapylýança elementleriň hersinden aýlawda geçýäris :
```
do {
    if (e.hash == hash &&
        ((k = e.key) == key || (key != null && key.equals(k))))
        return e;
} while ((e = e.next) != null);
```
2. çelek agaç gurluşy bolsa, bu usul goşmaça atlandyrylýar getTreeNode(), bu bolsa öz gezeginde zerur açary tapmak üçin usuly ulanýar find(). Agaç gözlegini geçirýäris - haslar deňeşdirilýär we gözlemek üçin çep ýa-da sag kök düwünleri kesgitlenýär. Düwmeler deň bolsa (salgylanma ýa-da boýunça equals), bu düwmäni yzyna gaýtaryň. Çep ýa-da sag çaga düwünleri boş bolsa, goşmaçalar bilen deňeşdirmek üçin (düwmeler interfeýsi durmuşa geçirýän bolsa Comparable) deňeşdirýäris, ýogsam bir oýun tapylýança agajyň (sag ýa-da çep aşaky) gözlegini geçirýäris.

HashMap-dan obýektleri aýyrmak Makaladaky boşluk gutaransoň, açar bilen pozulmagyň nähili bolýandygyny gysgaça düşündirerin. Algoritm gaty meňzeýär:

islenýän çelege git (ýene-de öňünden hasaplanýar);
çelekde diňe bir zat bar bolsa (onuň null görkezijisini barlaýarys) haslary, baglanyşyklary deňeşdirýäris we equals(birden haslar deň däl bolsa). Duşuşyk tapdyňyzmy? Ajaýyp, bu biziň açarymyz - ony pozuň (= null) we bu açaryň bahasyny yzyna gaýtaryň.
çelekde birden köp element bar bolsa, elementi tapýançak ýa-da sanawyň soňuna çenli her elementi aýlawda barlaýarys.
element tapylmasa, null gaýdyp geleris.

Agaç bilen baglanyşykly ýagdaýlarda, gaty bilmezlik we gowy uklamak has çylşyrymly ýerine ýetiriş bar (usulyň beýany, hatda gyzyl-gara reňkde yzygiderli öçürmekden has çylşyrymlydygyny aýdýar) agaç). Mundan başga-da, öçürilende bir çelekdäki düwünleriň sany 6-a gaýdyp biler we agaç täzeden baglanyşdyrylan sanawda täzeden gurlar. Köp ýyllyk tejribesi bolan işläp düzüjisi däl bolsaňyz, muny bilmek we düşünmek asla zerur däl (we diňe zerur däl).

Teswirler

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