Detalyadong pagsusuri ng klase ng HashMap

Bago lumipat sa isang detalyadong talakayan ng klase, tumuon tayo sa mga pangunahing konsepto na nauugnay sa mga talahanayan ng hash. Hindi tatalakayin ng artikulong ito ang mga pamamaraan para sa pagtatrabaho sa hash mapping. Tanging ang mga operasyon ng pagpapasok, paghahanap at pagtanggal ay tatalakayin nang malinaw at detalyado. Sa palagay ko hindi magiging mahirap basahin ang paglalarawan ng mga pamamaraan na magagamit para sa HashMap mula sa parehong Schildt. Marahil sa hinaharap ay magsusulat ako ng isa pang artikulo na nakatuon sa gayong mga pamamaraan, ngunit sa ngayon ito ay may pagdududa. Kung ikukumpara sa Java 7, ang klase ng HashMap sa Java 8 ay sumailalim sa mga makabuluhang pagbabago (+1000 linya ng code). Mababasa mo ang tungkol sa pagpapatupad sa Java 7 dito (ngunit hindi na nauugnay): habr Ang hash table ay isang istraktura ng data na nagpapatupad ng associative array interface (abstract key-value model o entry), na nagbibigay ng napakabilis na pagpasok at paghahanap: anuman Ang pagpasok at paghahanap ng mga elemento ng numero (at kung minsan ay pagtanggal) ay ginagawa sa isang oras na malapit sa isang pare-pareho - O(1). Sa pangkalahatan, ito ay isang regular na array, kung saan ang lokasyon ng elemento ay nakasalalay sa halaga ng elemento mismo. Ang kaugnayan sa pagitan ng halaga ng isang elemento at ang posisyon nito sa hash table ay tinukoy ng isang hash function. Ang hash function ay kumukuha ng input na piraso ng data, na tinatawag naming key , at bilang output ay gumagawa ito ng integer na kilala bilang hash value (o hash code) . Ang hash value ay nagbibigkis sa aming susi sa isang partikular na hash table index. Para sa mga pangunahing operasyon: pagpasok, paghahanap at pagtanggal, ginagamit namin ang parehong hash function, kaya ang mga operasyong ito ay ginagawa nang mabilis. Para sa kadahilanang ito, mahalaga na ang hash function ay patuloy na kumikilos at naglalabas ng parehong index para sa parehong input data. Kapansin-pansin na ang resultang hash code ay maaaring isang malaking numerong halaga, at ang orihinal na hanay ay may kondisyong idinisenyo para sa 16 na elemento lamang. Bakit hindi lumikha ng isang array na may isang bilyong elemento upang magdagdag lamang ng sampu? Samakatuwid, dapat nating baguhin ang hash code na ito sa mga halaga mula 0 hanggang 15 (kung ang laki ng array ay 16). At para dito, ginagamit ang mga karagdagang pagbabago. Kaya bumubuo kami ng isang index upang mabawasan ang laki ng array. Halimbawa, sa HashMap bago ang Java 8, ginamit ang karagdagang pamamaraang ito upang mahanap ang gustong cell:

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

Bilang input, kinuha nito ang hash code na nakuha bilang resulta ng trabaho hashCode()at ang haba ng internal array (bilang ng mga cell). At ibinalik nito ang resulta na "hash code" -> bitwise "AT" -> (haba ng array - 1). Nagmana ang klase HashMapmula sa klase AbstractMapat ipinapatupad ang mga sumusunod na interface: Map, Cloneable, Serializable. Ang .method ay responsable para sa hash function sa Java hashCode(). Ang default na pagpapatupad hashCode()ay nagbabalik ng isang halaga na tinatawag na identity hash code . Kahit na na-override ng isang klase hashCode(), maaari mong palaging makuha ang hash ng ID ng object sa pamamagitan ng pagtawag sa System.identityHashCode(Object o). Ang default na pagpapatupad hashCode()sa OpenJDK ay walang kinalaman sa memorya ng address, tulad ng kung minsan ay pinaniniwalaan. Higit pang mga detalye dito: habr Sa HashMap , ang hash table ay ipinapatupad batay sa isang array (o, mas tiyak, dynamic, dahil ang talahanayan ay maaaring lumawak) ng isa-isang naka-link na mga listahan. Mahalaga, nakuha namin ang hash code ng susi bilang isang resulta ng pamamaraan hashCode(), na pagkatapos ay binago (tulad ng isasaalang-alang namin sa ibang pagkakataon), at sa loob, gamit ang isang karagdagang pamamaraan, ang mga resultang halaga ay ipinamamahagi sa mga kinakailangang cell. Ang mga elemento ng array (mga cell) ay tinatawag ding mga bucket , na ginagamit upang mag-imbak ng mga indibidwal na node. Ang bawat balde ay isang koleksyon (listahan o puno). Ang node ay isang object ng isang nested class Node(o TreeNodesa isang tree structure). Sa katunayan, sa loob ng array cell ay namamalagi LinkedListlamang ng isang solong naka-link na listahan, o isang pulang-itim na puno, na sumasailalim sa pagpapatupad ng isa pang klase - TreeMap. Ang pagpipilian na may pulang-itim na puno ay hindi madalas na lumitaw (paano, ano at saan - sa ibaba), at ang istraktura na ito ay medyo mahirap maunawaan, kaya ang diin ay nasa isang node ng uri ng Node. Ang node ay isang nested na klase sa loob HashMapna mayroong mga sumusunod na field:

• final int hash— ang hash ng kasalukuyang elemento, na nakukuha natin bilang resulta ng pag-hash ng susi;
• final K key— ang susi ng kasalukuyang elemento. Ito ay kung saan kung ano ang iyong tinukoy bilang ang unang bagay sa pamamaraan ay nakasulat sa put();
• V value— ang halaga ng kasalukuyang elemento. At kung ano ang iyong tinukoy bilang pangalawang bagay sa pamamaraan ay nakasulat dito put();
• Node < K, V> next— link sa susunod na node sa loob ng parehong basket. Ang listahan ay konektado, kaya kailangan nito ng isang link hindi sa susunod na node, kung mayroon man.

Ngayon tingnan natin ang mga field ng HashMap class mismo:

• transient Node < K, V> [] table– ang hash table mismo, na ipinatupad batay sa isang array, para sa pag-iimbak ng mga pares ng key-value sa anyo ng mga node. Dito nakaimbak ang aming mga Node;
• transient int size— bilang ng mga pares ng key-value;
• int threshold— ang maximum na bilang ng mga elemento, kapag naabot kung saan doble ang laki ng hash table. Kinakalkula gamit ang formula (kapasidad * loadFactor);
• final float loadFactor— tinutukoy ng parameter na ito kung anong antas ng pag-load ang kailangan ng kasalukuyang hash table upang lumikha ng bagong hash table, i.e. sa sandaling ang hash table ay 75% na puno, isang bagong hash table ang gagawin at ang kasalukuyang mga elemento ay ililipat dito (isang magastos na operasyon, dahil ang lahat ng mga elemento ay dapat na muling i-rehash);
• transient Set< Map.Entry< K,V>> entrySet- naglalaman ng isang naka-cache entrySet(), na kung saan maaari naming umulit HashMap.

At mga pare-pareho:

• static final int DEFAULT_INITIAL_CAPACITY= 1 << 4— default na kapasidad ng hash table (16);
• static final int MAXIMUM_CAPACITY = 1 << 30— ang pinakamataas na posibleng kapasidad ng hash table (humigit-kumulang 1 bilyon);
• static final float DEFAULT_LOAD_FACTOR = 0.75f— default na kadahilanan ng pagkarga;
• static final int TREEIFY_THRESHOLD = 8ay ang "threshold" ng bilang ng mga elemento sa isang bucket, kapag naabot kung saan ang panloob na naka-link na listahan ay mako-convert sa isang istraktura ng puno (pula-itim na puno).
• static final int UNTREEIFY_THRESHOLD = 6— kung ang bilang ng mga elemento sa isang basket ay bumaba sa 6, pagkatapos ay isang reverse transition mula sa isang puno patungo sa isang naka-link na listahan ay magaganap;
• static final int MIN_TREEIFY_CAPACITY = 64— ang pinakamababang kapasidad (bilang ng mga balde) ng hash table kung saan posible ang paglipat sa isang istraktura ng puno. Yung. Kung mayroong hindi bababa sa 64 na bucket sa hash table at mayroong 8 o higit pang mga elemento sa isang bucket, pagkatapos ay isang paglipat sa isang istraktura ng puno ay magaganap.

Mga tagabuo ng klase:

1. public HashMap()— lumilikha ng hash display bilang default: volume (capacity) = 16at load factor (load factor) = 0.75;
2. public HashMap(Map< ? extends K, ? extends V> m)— lumilikha ng hash mapping na sinimulan ng mga elemento ng isa pang ibinigay na pagmamapa na may paunang kapasidad na sapat upang mapaunlakan ang mga elemento ng isa pang pagmamapa;
3. public HashMap(int initialCapacity)— lumilikha ng hash map na may ibinigay na paunang kapasidad. Para gumana nang tama at tama ang HashMap, dapat na dalawang kapangyarihan ang laki ng panloob na array (ibig sabihin, 16, 64, 128, atbp.);
4. public HashMap(int initialCapacity, float loadFactor)— lumilikha ng hash map na may mga tinukoy na parameter: paunang kapasidad at load factor.

Ang isang klase ay nagpapatupad ng isang interface Mapat nagpapalawak ng isang klase AbstractMapnang hindi nagdaragdag ng sarili nitong mga pamamaraan. Hindi ginagarantiyahan ng hash map ang pagkakasunud-sunod ng mga elemento nito. Samakatuwid, ang pagkakasunud-sunod kung saan ang mga elemento ay ipinasok sa hash map ay hindi nangangahulugang ang pagkakasunud-sunod kung saan sila ay nakuha ng iterator. Pagdaragdag ng mga Bagay Ang pagdaragdag ng key-value pair ay ginagawa gamit ang put(). Tingnan natin ang mga hakbang na kasangkot kapag nagdaragdag ng isang bagay:

1. Kinakalkula ang hash value ng key ng ipinasok na bagay. Ang key hash ay kinakalkula sa pamamagitan ng isang paraan static final int hash(Object key)na ina-access na ang hashCode()pangunahing paraan na alam natin. Upang gawin ito, hashCode()ginagamit ang alinman sa isang overridden na paraan o ang default na pagpapatupad nito. Mga karagdagang pagbabago sa pamamaraan 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. Kasabay nito, kinakalkula namin ang index ng bucket kung saan ilalagay ang aming bagay at suriin kung mayroon nang mga elemento sa loob nito. Kinakalkula namin:

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

      suriin:

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

   6. Dahil bilang resulta ng tseke ay nagiging totoo tayo (walang elemento sa bucket), bubuo ang isang Node object na may mga sumusunod na field:

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

      Ang aming nabuong Node object ay idaragdag sa bucket sa ilalim ng index [4]:

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

      newNode()ay isang paraan na nagbabalik lamang ng isang bagay ng klase ng Node.

   7. Pagkatapos idagdag, isasagawa ang pagsusuri upang makita kung ang kasalukuyang bilang ng mga elemento ay lumampas sa parameter threshold:

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

      Kung lumampas, tatawagin ang isang paraan resize()upang madagdagan ang laki ng hash table.

      Sa puntong ito, ang pamamaraan putVal()(at , ayon sa pagkakabanggit put()) ay makumpleto ang gawain nito.

      Ang resulta ay maaaring graphical na kinakatawan tulad ng sumusunod:

      Sa pangkalahatan, ganito ang hitsura ng pagdaragdag ng Node (key-value pair) sa isang hash table kung walang laman ang gustong bucket . Ngayon subukan nating magdagdag ng isang elemento na hahantong sa isang banggaan (kapag mayroong higit sa isang elemento sa isang bucket).

Kaunti tungkol sa mga banggaan Ang sitwasyon kung kailan napunta ang iba't ibang mga susi sa iisang bucket (kahit na may iba't ibang mga hash) ay tinatawag na banggaan o banggaan. Kahit na ang talahanayan ng hash ay mas malaki kaysa sa set ng data at napili ang isang mahusay na function ng hash, hindi nito ginagarantiyahan na hindi magaganap ang mga banggaan. At ang halaga ng hash ay limitado sa hanay ng mga halaga ng int (mga 4 bilyon). Ang resultang bagong halaga ay kailangan ding isulat sa isang lugar, at para dito kailangan mong matukoy kung saan eksakto ito isusulat. Ito ay tinatawag na conflict resolution. Mayroong dalawang mga diskarte:

• external chaining o chaining method (ipinatupad sa HashMap) - i.e. ang cell ay talagang naglalaman ng isang listahan (chain). At ang listahan ay maaaring naglalaman na ng ilang mga halaga (hindi kinakailangang may parehong hash code).
• linear probing o open addressing method (ipinatupad sa IdentityHashMap) - binubuo ng paghahanap para sa unang walang laman na cell pagkatapos ng itinuro ng hash function;

Maaari mong basahin ang tungkol sa mga banggaan dito: i-click

1. Gamit ang pamamaraan, put()magdaragdag kami ng isa pang pares ng key-value sa hash mapping:

   map.put("BLAKE", 10);

2. Kinakalkula namin ang "preliminary hash" - 63281361. Binabago namin ito at bilang resulta ay nakuha namin ang panghuling hash code - 63281940.

3. Dahil ang unang check para sa "emptiness" ay magbabalik na ngayon ng false (hindi na kailangang gumawa ng table), agad naming kinakalkula ang index ng bucket kung saan ilalagay ang aming object:

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

4. Ang bucket sa tinukoy na index ay sinuri para sa pagkakaroon ng mga elemento sa loob nito, at dahil ang kondisyon if ((p = tab[i = (n - 1) & hash]) == null)ay hindi natutugunan sa kasong ito (mayroon nang elemento sa bucket), pagkatapos ay pumunta kami sa block else.

5. Una sa lahat, inihahambing namin ang elementong idinaragdag sa unang elemento ng naka-link na listahan sa loob ng bucket:

   (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)

   Sa halip na pumunta sa istraktura ng puno, tatawagin ang isang paraan resize()upang palakihin ang laki ng hash table, muling pamamahagi ng mga elemento. treeify()sa turn, ang naka-link na listahan ng TreeNodemga nagko-convert sa isang pulang-itim na puno. Ang pamamaraan resize()ay umuulit sa lahat ng mga elemento ng kasalukuyang imbakan, muling kinakalkula ang kanilang mga indeks (isinasaalang-alang ang bagong laki) at muling ipinamamahagi ang mga elemento sa isang bagong hanay.

   Sa madaling sabi, nang hindi pumunta sa mga detalye ng istraktura ng pulang-itim na puno, ang mga sumusunod ay nangyayari:

   1. Ang unang elemento ng listahan ay nakasulat bilang ugat ng buong puno (itim):

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

   2. Para sa iba pang mga elemento:

      ipamahagi ang mga ito sa kaliwa o kanan depende sa halaga ng hash:

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

      Ang lahat ng kaliwang bata ay dapat na mas mababa sa (o katumbas ng) kanilang root node, habang ang lahat ng mga tamang bata ay dapat na mas malaki.

   3. Kung ang dalawang elemento ay may parehong mga hash at hindi maihahambing sa anumang iba pang paraan (hindi nila ipinapatupad ang interface Comparable), ginagambala namin ang pagtatayo ng puno at tinatawagan ang pamamaraan tieBreakOrder(), na kung saan ay gumagamit ng katutubong paraan System.identityHashCode()upang kalkulahin ang isang natatanging hash code sa buong mundo .

      Higit pang mga detalye dito: link sa artikulo

   4. Sinusuri namin ang mga elemento ng puno (mga bagay TreeNode) hanggang sa makita ang isang bata (kaliwa o kanan) na zero na elemento.

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

   5. Magdagdag ng child node (kaliwa o kanan depende sa dir):

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

   6. Dahil ang pagdaragdag ng bagong elemento ay maaaring masira ang balanse ng puno, tinatawag namin ang paraan para sa muling pagbabalanse:

      root = balanceInsertion(root, x);

      Mababasa mo ang tungkol sa pagbabalanse ng CCH dito: habr

   7. Pagkatapos ng pagbabalanse, maaaring magbago ang root element. Inaayos namin ito sa pamamagitan ng pagtawag sa isang paraan na ginagarantiyahan na ang ugat na ipinasa dito ang magiging unang node:

      moveRootToFront(tab, root)

      Malinaw mong makikita kung paano binuo ang isang pulang-itim na puno at nagbabalanse sa sarili dito: visualization

Iyon lang, sa prinsipyo, at gamit ang isang halimbawa, ipagpalagay natin na gusto nating idagdag ang mga sumusunod na pangalan bilang mga susi: KING, MARY, JOSE, ANNA, FRED, TONY, ALEX, PEPE. At sabihin nating mayroon tayong hindi bababa sa 64 na bucket sa hash table, at lahat ng elementong ito ay naipon sa isang bucket. Sa istruktura, ang bucket na ito ay magiging ganito (ang mga elemento ay pinagsunod-sunod ayon sa hash code): Uri ng CCHD: Tingnan ang loob ng balde: Pagkuha ng mga elemento (pagkuha ng isang halaga sa pamamagitan ng key) Tungkol sa pagdaragdag ng operasyon, ito ay medyo simple. Ang algorithm (kapag may naka-link na listahan sa bucket) ay maaaring isulat tulad nito:

1. Kalkulahin ang hash code ng key.
2. Kalkulahin ang bucket index.
3. Pumunta sa index at ihambing ang susi ng unang elemento sa umiiral na halaga. Kung pantay ang mga ito, ibalik ang halaga, kung hindi, tingnan ang susunod na elemento, kung mayroon ito.
4. Kung null ang susunod na object ng Node, ibalik ang null.
5. Kung ang susunod na Node object ay hindi null, pumunta dito at ulitin ang unang tatlong hakbang hanggang sa ang elemento ay matagpuan o ang susunod na Node object ay null.

Gamit ang pamamaraan, get()nakukuha namin ang halaga para sa "KING" key:

map.get("KING");

Sa loob, ang pamamaraan ay tinatawag na getNode(int hash, Object key), kung saan ang susi mismo (“KING”) at ang hash nito (2306996) ay ipinapasa, na paunang kinakalkula sa parehong paraan tulad ng sa panahon ng operasyon put().

1. Sinusuri namin:

   1. mayroon bang hash table:(tab = table) != null

      Ipaalala ko sa iyo na kapag gumagawa ng isang HashMap, ang isang array para sa talahanayan ay hindi nilikha sa constructor; ito ay nangyayari sa ibang pagkakataon sa method resize(), na palaging tinatawag kapag nagdaragdag ng unang elemento sa hash table. Samakatuwid, kung walang mga elementong naidagdag sa HashMap, walang panloob na hanay upang mag-imbak ng mga elemento.

   2. kung ang nakaraang expression ay bumalik na totoo, kailangan mong tiyakin na ang haba ng panloob na array ay mas malaki sa 0:(n = tab.length) > 0;

   3. kung ang nakaraang expression ay nagbabalik din ng totoo, pumunta sa bucket sa index (sa aming kaso 4), na dati ay kinakalkula, at suriin ito para sa pagkakaroon ng mga elemento:

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

   4. Inihahambing namin ang susi na hinahanap namin sa susi ng unang elemento sa listahan sa loob ng balde, dahil sa karamihan ng mga balde magkakaroon (hindi saanman kami ay may banggaan) isang elemento lamang (ang aming kaso). Tulad ng sa kaso ng pamamaraan put(), ang mga hash ay inihambing, at kung magkatugma ang mga ito, ang mga susi ay inihahambing sa pamamagitan ng sanggunian, at pagkatapos lamang ng equals().

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

      Dahil sa aming kaso, ang key na "KING" ay mauuna sa key na "BLAKE" (sa loob ng isang naka-link na listahan, ang mga bagong elemento ay idinagdag sa dulo, at ang KING ay unang idinagdag), hihinto kami sa puntong ito at ibabalik ang unang bagay ng i-type ang Node sa get() na pamamaraan, na "nang-agaw" mula sa kanya ng isang patlang na may halaga (100):

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

2. Kung mayroong higit sa isang elemento sa loob ng bucket, kung gayon:

   1. kung ang bucket ay isang naka-link na listahan, dumaan kami sa listahan sa bawat isa sa mga elemento sa isang loop do – whilehanggang sa mahanap ang isang tugma:

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

   2. kung ang bucket ay isang istraktura ng puno, kung gayon ang pamamaraan ay tinatawag ding getTreeNode(), na kung saan ay gumagamit ng paraan upang mahanap ang kinakailangang key find(). Nagsasagawa kami ng paghahanap ng puno - inihahambing ang mga hash at tinutukoy ang kaliwa o kanang root node sa paghahanap. Kung ang mga susi ay pantay (sa pamamagitan ng sanggunian o sa pamamagitan ng equals), ibalik ang node na ito. Kung ang kaliwa o kanang child node ay null, inihahambing din namin ang mga key gamit ang compareTo (kung ipinapatupad ng mga key ang interface Comparable), kung hindi, nagsasagawa kami ng recursive na paghahanap sa puno (kanan o kaliwang subtree) hanggang sa may mahanap na tugma.

Pag-alis ng mga bagay mula sa isang HashMap Dahil nauubusan na ang espasyo sa artikulo, maikling ilalarawan ko kung paano nangyayari ang pagtanggal sa pamamagitan ng key. Ang algorithm ay halos magkapareho:

• pumunta sa nais na balde (muli, ito ay paunang kinakalkula);

• kung mayroon lamang isang bagay sa bucket (nasusuri namin ang null pointer nito) inihambing namin ang mga hash, mga link at equals(kung biglang ang mga hash ay hindi pantay). Nakahanap ng kapareha? Mahusay, ito ang aming susi - tanggalin ito (=null) at ibalik ang halaga ng key na ito.

• kung mayroong higit sa isang elemento sa bucket, sinusuri namin ang bawat elemento sa isang loop hanggang sa mahanap namin ang elemento o maabot ang dulo ng listahan.

• kung hindi natagpuan ang elemento, ibinabalik namin ang null.

Sa sitwasyon na may isang puno, mayroong isang medyo nakakalito na pagpapatupad, na mas mahusay na hindi malaman ang tungkol sa at matulog nang mahimbing (ang paglalarawan ng pamamaraan ay nagsasabi na ang pagpapatupad ay mas kumplikado kaysa sa isang regular na operasyon ng pagtanggal sa isang pulang itim. puno). Bukod dito, kapag natanggal, ang bilang ng mga node sa isang bucket ay maaaring bumalik sa 6, at pagkatapos ay ang puno ay itatayong muli sa isang naka-link na listahan. Kung ikaw ay hindi isang developer na may maraming mga taon ng karanasan, ito ay hindi sa lahat ng kailangan upang malaman at maunawaan ito (at simpleng hindi kinakailangan).