HashMap sinfining batafsil tahlili

Sinfning batafsil muhokamasiga o'tishdan oldin, keling, xesh-jadvallar bilan bog'liq asosiy tushunchalarga e'tibor qarataylik. Ushbu maqolada hash xaritalash bilan ishlash usullari muhokama qilinmaydi. Faqat kiritish, qidirish va o'chirish operatsiyalari aniq va batafsil muhokama qilinadi. Menimcha , xuddi shu Schildtdan HashMap uchun mavjud usullarning tavsifini o'qish qiyin bo'lmaydi. Ehtimol, kelajakda men bunday usullarga bag'ishlangan yana bir maqola yozaman, ammo hozircha bu savol ostida. Java 7 bilan solishtirganda, Java 8-dagi HashMap klassi sezilarli o'zgarishlarga duch keldi (+1000 kod satri). Java 7 da amalga oshirish haqida bu yerda oʻqishingiz mumkin (lekin endi ahamiyatli emas): habr Xesh-jadval assotsiativ massiv interfeysini (mavhum kalit-qiymat modeli yoki yozuv) amalga oshiradigan maʼlumotlar strukturasi boʻlib , u juda tez kiritish va qidirishni taʼminlaydi: son elementlarini kiritish va qidirish (ba'zan o'chirish) doimiy - O(1) ga yaqin vaqt ichida amalga oshiriladi. Aslida, bu oddiy massiv bo'lib, unda elementning joylashuvi elementning o'zi qiymatiga bog'liq. Elementning qiymati va uning xesh jadvalidagi o'rni o'rtasidagi bog'liqlik xesh funktsiyasi bilan belgilanadi. Xesh funktsiyasi kirish ma'lumotlar qismini oladi, biz uni kalit deb ataymiz va chiqish sifatida u hash qiymati (yoki xesh kodi) deb nomlanuvchi butun sonni hosil qiladi . Keyin xesh qiymati bizning kalitimizni ma'lum bir xesh jadvali indeksiga bog'laydi. Asosiy operatsiyalar uchun: kiritish, qidirish va o'chirish, biz bir xil xesh funktsiyasidan foydalanamiz, shuning uchun bu operatsiyalar juda tez amalga oshiriladi. Shu sababli, xesh funksiyasi izchil harakat qilishi va bir xil kirish ma'lumotlari uchun bir xil indeksni chiqarishi muhimdir. Shuni ta'kidlash kerakki, natijada olingan xesh-kod juda katta raqamli qiymat bo'lishi mumkin va asl massiv shartli ravishda faqat 16 element uchun mo'ljallangan. Nega faqat o'nta qo'shish uchun milliard elementli massiv yaratmaslik kerak? Shuning uchun, biz qandaydir tarzda ushbu xesh kodini 0 dan 15 gacha qiymatlarga aylantirishimiz kerak (agar massiv hajmi 16 bo'lsa). Va buning uchun qo'shimcha transformatsiyalar qo'llaniladi. Shunday qilib, biz massiv hajmini minimallashtirish uchun indeks hosil qilamiz. Masalan, Java 8-dan oldin HashMap-da kerakli katakni topish uchun ushbu qo'shimcha usul ishlatilgan:

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

Kirish sifatida u ish natijasida olingan xesh kodini hashCode()va ichki massivning uzunligini (hujayralar soni) oldi. Va natijada "xesh-kod" -> bit bo'yicha "VA" -> (massiv uzunligi - 1) natijani qaytardi. Sinf HashMapsinfdan meros oladi AbstractMapva quyidagi interfeyslarni amalga oshiradi: Map, Cloneable, Serializable. .usuli Java'da xesh funksiyasi uchun javobgardir hashCode(). Standart dastur identifikator xesh kodihashCode() deb nomlangan qiymatni qaytaradi . Agar sinf bekor qilinsa ham , siz har doim qo'ng'iroq qilish orqali ob'ekt identifikatori xeshini olishingiz mumkin . OpenJDK-dagi standart dastur, ba'zida ishonganidek, xotira manzili bilan hech qanday aloqasi yo'q. Batafsil ma'lumot bu yerda: habr HashMap-da xesh-jadval yakka bog'langan ro'yxatlar massivi (yoki aniqrog'i, dinamik, chunki jadval kengayishi mumkin) asosida amalga oshiriladi. Asosan, biz kalitning xesh kodini usul natijasida olamiz , keyin u o'zgartiriladi (keyinroq ko'rib chiqamiz) va ichki qo'shimcha usul yordamida olingan qiymatlar kerakli hujayralarga taqsimlanadi. Massiv elementlari (hujayralar) ham deyiladi chelaklar , ular alohida tugunlarni saqlash uchun ishlatiladi. Chelaklarning har biri to'plamdir (ro'yxat yoki daraxt). Tugun - ichki o'rnatilgan sinf ob'ekti (yoki daraxt tuzilishida). Darhaqiqat, massiv katakchasi ichida faqat bitta bog'langan ro'yxat yoki boshqa sinfni amalga oshirish asosida joylashgan qizil-qora daraxt yotadi - . hashCode()System.identityHashCode(Object o)hashCode()hashCode()NodeTreeNodeLinkedListTreeMap Qizil-qora daraxtli variant tez-tez paydo bo'lmaydi (qanday qilib, nima va qaerda - quyida) va bu tuzilmani tushunish juda qiyin, shuning uchun asosiy e'tibor tugun tipidagi tugunga qaratiladi. Node - ichki o'rnatilgan sinf bo'lib HashMap, uning ichida quyidagi maydonlar mavjud:

• final int hash— kalitni xeshlash natijasida olingan joriy elementning xeshi;
• final K key— joriy elementning kaliti. Usulda birinchi ob'ekt sifatida ko'rsatgan narsa shu yerda yoziladi put();
• V value— joriy elementning qiymati. Va usulda ikkinchi ob'ekt sifatida ko'rsatgan narsa shu erda yozilgan put();
• Node < K, V> next— xuddi shu savatdagi keyingi tugunga havola. Ro'yxat ulangan, shuning uchun agar mavjud bo'lsa, keyingi tugunga emas, balki havola kerak.

Endi HashMap sinfining maydonlarini ko'rib chiqamiz:

• transient Node < K, V> [] table– kalit-qiymat juftlarini tugunlar ko'rinishida saqlash uchun massiv asosida amalga oshirilgan xesh-jadvalning o'zi. Bu bizning tugunlarimiz saqlanadigan joy;
• transient int size— kalit-qiymat juftliklari soni;
• int threshold— elementlarning maksimal soni, unga yetganda xesh-jadvalning o'lchami ikki baravar ortadi. Formuladan foydalanib hisoblangan (imkoniyat * yuklanish faktori);
• final float loadFactor— bu parametr joriy xesh-jadval yangi xesh-jadvalni yaratish uchun qanday yuklanish darajasida kerakligini aniqlaydi, ya'ni. xesh-jadval 75% to'lishi bilanoq, yangi xesh-jadval yaratiladi va joriy elementlar unga ko'chiriladi (xarajat operatsiya, chunki barcha elementlarni qayta tiklash kerak);
• transient Set< Map.Entry< K,V>> entrySet- keshlanganni o'z ichiga oladi entrySet(), biz uni takrorlashimiz mumkin HashMap.

Va doimiylar:

• static final int DEFAULT_INITIAL_CAPACITY= 1 << 4— standart xesh-jadval sig'imi (16);
• static final int MAXIMUM_CAPACITY = 1 << 30— xesh-jadvalning mumkin bo'lgan maksimal sig'imi (taxminan 1 milliard);
• static final float DEFAULT_LOAD_FACTOR = 0.75f— standart yuk koeffitsienti;
• static final int TREEIFY_THRESHOLD = 8- bu bitta chelakdagi elementlar sonining "eshigi" bo'lib, unga erishilganda ichki bog'langan ro'yxat daraxt tuzilishiga (qizil-qora daraxt) aylanadi.
• static final int UNTREEIFY_THRESHOLD = 6— agar bitta savatdagi elementlar soni 6 tagacha kamaysa, u holda daraxtdan bog'langan ro'yxatga teskari o'tish sodir bo'ladi;
• static final int MIN_TREEIFY_CAPACITY = 64- daraxt tuzilishiga o'tish mumkin bo'lgan hash-jadvalning minimal sig'imi (chelaklar soni). Bular. Agar xesh jadvalida kamida 64 chelak bo'lsa va bitta chelakda 8 yoki undan ortiq element mavjud bo'lsa, unda daraxt tuzilishiga o'tish sodir bo'ladi.

Sinf konstruktorlari:

1. public HashMap()— sukut bo'yicha xesh-displeyni yaratadi: hajm bo'yicha (capacity) = 16va yuk koeffitsienti bilan (load factor) = 0.75;
2. public HashMap(Map< ? extends K, ? extends V> m)— boshqa xaritalash elementlarini joylashtirish uchun yetarli bo'lgan boshlang'ich sig'imga ega bo'lgan boshqa berilgan xaritalash elementlari tomonidan inisializatsiyalangan xesh xaritalashni yaratadi;
3. public HashMap(int initialCapacity)— berilgan boshlang‘ich sig‘imga ega xesh-xaritani yaratadi. HashMap to'g'ri va to'g'ri ishlashi uchun ichki massivning o'lchami ikkita (ya'ni 16, 64, 128 va boshqalar) bo'lishi kerak;
4. public HashMap(int initialCapacity, float loadFactor)— belgilangan parametrlarga ega xesh xaritasini yaratadi: dastlabki quvvat va yuk koeffitsienti.

Sinf interfeysni amalga oshiradi Mapva sinfni AbstractMapo'z usullarini qo'shmasdan kengaytiradi. Xesh xaritasi uning elementlari tartibini kafolatlamaydi. Shuning uchun, elementlarning xesh xaritasiga kiritilish tartibi ularni iterator tomonidan olish tartibi bo'lishi shart emas. Ob'ektlarni qo'shish Kalit-qiymat juftligini qo'shish yordamida amalga oshiriladi put(). Ob'ektni qo'shish bilan bog'liq qadamlarni ko'rib chiqaylik:

1. Kiritilgan ob'ekt kalitining xesh qiymati hisoblanadi. Kalit xesh biz bilgan kalit usuliga static final int hash(Object key)allaqachon kirish usuli bilan hisoblanadi . hashCode()Buning uchun bekor qilingan usul hashCode()yoki uning sukut bo'yicha amalga oshirilishi qo'llaniladi. Usuldagi qo'shimcha o'zgarishlar 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. Shu bilan birga, biz ob'ektimiz joylashtiriladigan chelak indeksini hisoblaymiz va unda allaqachon elementlar mavjudligini tekshiramiz. Biz hisoblaymiz:

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

      tekshiring:

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

   6. Tekshirish natijasida biz haqiqatga erishamiz (paqirda hech qanday element yo'q), quyidagi maydonlarga ega Node ob'ekti yaratiladi:

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

      Bizning yaratilgan Node ob'ektimiz indeks ostidagi paqirga qo'shiladi [4]:

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

      newNode()oddiygina Node sinfining ob'ektini qaytaradigan usuldir.

   7. Qo'shgandan so'ng, elementlarning joriy soni parametrdan oshib ketganligini tekshirish amalga oshiriladi threshold:

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

      resize()Agar oshib ketgan bo'lsa, xesh jadvalining hajmini oshirish uchun usul chaqiriladi .

      Bu vaqtda usul putVal()(va mos ravishda put()) o'z ishini yakunlaydi.

      Natijani grafik tarzda quyidagicha ifodalash mumkin:

      Umuman olganda, agar kerakli chelak bo'sh bo'lsa, xesh jadvaliga tugunni (kalit-qiymat juftligini) qo'shish shunday ko'rinadi . Keling, to'qnashuvga olib keladigan elementni qo'shishga harakat qilaylik (bir chelakda bir nechta element mavjud bo'lganda).

To'qnashuvlar haqida bir oz Turli xil kalitlar bir chelakda (hatto turli xil xeshlar bilan) tugashi to'qnashuv yoki to'qnashuv deb ataladi. Xesh jadvali ma'lumotlar to'plamidan kattaroq bo'lsa va yaxshi xesh funktsiyasi tanlangan bo'lsa ham, bu to'qnashuvlar sodir bo'lmasligiga kafolat bermaydi. Va xesh qiymati int qiymatlari oralig'i bilan cheklangan (taxminan 4 milliard). Olingan yangi qiymat ham biror joyga yozilishi kerak va buning uchun aynan qayerda yozilishini aniqlash kerak. Bu konfliktni hal qilish deb ataladi. Ikkita yondashuv mavjud:

• tashqi zanjir yoki zanjir usuli (HashMapda amalga oshiriladi) - ya'ni. hujayra aslida ro'yxatni (zanjirni) o'z ichiga oladi. Va ro'yxat allaqachon bir nechta qiymatlarni o'z ichiga olishi mumkin (bir xil xesh-kod bilan emas).
• chiziqli tekshirish yoki ochiq manzillash usuli (IdentityHashMap-da amalga oshirilgan) - xesh funktsiyasi ko'rsatganidan keyin birinchi bo'sh katakchani qidirishdan iborat;

To'qnashuvlar haqida bu erda o'qishingiz mumkin: bosing

1. Usuldan foydalanib, put()biz xesh xaritalash uchun yana bir kalit-qiymat juftligini qo'shamiz:

   map.put("BLAKE", 10);

2. Biz "dastlabki hash" ni hisoblaymiz - 63281361. Biz uni o'zgartiramiz va natijada biz yakuniy hash kodini olamiz - 63281940.

3. Birinchi "bo'shlik" tekshiruvi endi noto'g'ri bo'lganligi sababli (jadval yaratishning hojati yo'q), biz darhol ob'ektimiz joylashtiriladigan chelak indeksini hisoblaymiz:

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

4. Belgilangan indeksdagi chelak undagi elementlarning mavjudligi uchun tekshiriladi va if ((p = tab[i = (n - 1) & hash]) == null)bu holda shart bajarilmaganligi sababli (paqirda allaqachon element mavjud), keyin biz blokga o'tamiz else.

5. Avvalo, biz qo'shilgan elementni chelak ichidagi bog'langan ro'yxatning birinchi elementi bilan taqqoslaymiz:

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

   resize()Daraxt tuzilishiga o'tish o'rniga, elementlarni qayta taqsimlash, xesh jadvalining hajmini oshirish usuli chaqiriladi . o'z navbatida, qizil-qora daraxtga aylanadigan treeify()bog'langan ro'yxat . TreeNodeUsul resize()joriy xotiraning barcha elementlarini takrorlaydi, ularning indekslarini qayta hisoblaydi (yangi o'lchamni hisobga olgan holda) va elementlarni yangi massivga qayta taqsimlaydi.

   Qisqacha aytganda, qizil-qora daraxtning tuzilishi haqida batafsil ma'lumot bermasdan, quyidagilar sodir bo'ladi:

   1. Ro'yxatning birinchi elementi butun daraxtning ildizi sifatida yoziladi (qora):

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

   2. Boshqa elementlar uchun:

      hash qiymatiga qarab ularni chapga yoki o'ngga taqsimlang:

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

      Barcha chap bolalar ildiz tugunidan kichik (yoki teng) bo'lishi kerak, barcha o'ng bolalar esa kattaroq bo'lishi kerak.

   3. Agar ikkita element bir xil xeshlarga ega bo'lsa va ularni boshqa yo'l bilan taqqoslab bo'lmasa (ular interfeysni amalga oshirmasa Comparable), biz daraxtning qurilishini to'xtatamiz va usulni chaqiramiz , bu esa o'z navbatida global noyob xesh kodini hisoblash uchun tieBreakOrder()mahalliy usuldan foydalanadi. System.identityHashCode().

      Batafsil ma'lumot bu yerda: maqolaga havola

   4. Biz daraxt elementlarini (ob'ektlar TreeNode) bola (chap yoki o'ng) nol elementi topilmaguncha tekshiramiz.

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

   5. Bola tugunini qo'shing (direktga qarab chap yoki o'ng):

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

   6. Yangi elementni qo'shish daraxtning muvozanatini buzishi mumkinligi sababli, biz muvozanatni tiklash usulini chaqiramiz:

      root = balanceInsertion(root, x);

      CCHni muvozanatlash haqida bu erda o'qishingiz mumkin: habr

   7. Balanslashtirgandan so'ng, ildiz elementi o'zgarishi mumkin. Buni, unga o'tgan ildiz birinchi tugun bo'lishini kafolatlaydigan usulni chaqirish orqali tuzatamiz:

      moveRootToFront(tab, root)

      Siz bu erda qizil-qora daraxt qanday qurilganini va o'z-o'zini muvozanatlashini aniq ko'rishingiz mumkin: vizualizatsiya

Hammasi, printsipial jihatdan va misoldan foydalanib, biz quyidagi nomlarni kalit sifatida qo'shmoqchimiz deb faraz qilaylik: KING, MERY, XOSE, ANNA, FRED, TONY, ALEX, PEPE. Aytaylik, xesh jadvalida bizda kamida 64 chelak bor va bu elementlarning barchasi bitta chelakda to'plangan. Strukturaviy ravishda, bu chelak quyidagicha ko'rinadi (elementlar xesh-kod bo'yicha tartiblangan): CCHD turi: Chelak ichidagi ko'rish: Elementlarni olish (qiymatni kalit bo'yicha olish) Qo'shish operatsiyasiga kelsak, bu juda oddiy. Algoritm (paqirda bog'langan ro'yxat mavjud bo'lganda) quyidagicha yozilishi mumkin:

1. Kalitning xesh kodini hisoblang.
2. Paqir indeksini hisoblang.
3. Indeksdan o'ting va birinchi elementning kalitini mavjud qiymat bilan solishtiring. Agar ular teng bo'lsa, qiymatni qaytaring, aks holda keyingi element mavjudligini tekshiring.
4. Agar keyingi tugun ob'ekti null bo'lsa, nullni qaytaring.
5. Agar keyingi Node ob'ekti null bo'lmasa, unga o'ting va element topilguncha yoki keyingi Node ob'ekti null bo'lgunga qadar dastlabki uchta qadamni takrorlang.

Usuldan foydalanib, get()biz "KING" kalitining qiymatini olamiz:

map.get("KING");

Ichkarida usul chaqiriladi getNode(int hash, Object key), unga kalitning o'zi ("KING") va uning xeshi (2306996) uzatiladi, bu operatsiya paytida bo'lgani kabi oldindan hisoblab chiqiladi put().

1. Biz tekshiramiz:

   1. hatto hash jadvali mavjudmi:(tab = table) != null

      Sizga eslatib o'tamanki, HashMap yaratishda jadval uchun massiv konstruktorda yaratilmaydi; bu keyinchalik resize()xesh jadvaliga birinchi element qo'shilganda chaqiriladigan usulda keyinroq sodir bo'ladi. Shuning uchun, agar HashMap-ga hech qanday element qo'shilmagan bo'lsa, elementlarni saqlash uchun oddiygina ichki massiv yo'q.

   2. agar oldingi ifoda rost bo'lsa, ichki massiv uzunligi 0 dan katta ekanligiga ishonch hosil qilishingiz kerak:(n = tab.length) > 0;

   3. agar oldingi ifoda ham rost bo'lsa, avval hisoblangan indeksdagi chelakka (bizning holatimizda 4) o'ting va elementlarning mavjudligini tekshiring:

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

   4. Biz izlayotgan kalitni chelak ichidagi ro'yxatdagi birinchi elementning kaliti bilan taqqoslaymiz, chunki ko'pchilik chelaklarda (hamma joyda bizda to'qnashuvlar bo'lmaydi) faqat bitta element (bizning ishimiz) bo'ladi. Usul holatida bo'lgani kabi put(), xeshlar solishtiriladi va agar ular mos kelsa, kalitlar mos yozuvlar bo'yicha va faqat keyin tomonidan taqqoslanadi equals().

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

      Bizning holatimizda "KING" kaliti "BLAKE" kalitidan oldin bo'lgani uchun (bog'langan ro'yxatda yangi elementlar oxiriga qo'shiladi va birinchi navbatda KING qo'shiladi), biz shu nuqtada to'xtab, birinchi ob'ektni qaytaramiz. Get() usuliga Node ni kiriting, u undan (100) qiymatiga ega bo'lgan maydonni "tortib oladi":

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

2. Agar chelak ichida bir nechta element bo'lsa, unda:

   1. do – whileagar chelak bog'langan ro'yxat bo'lsa, moslik topilmaguncha biz ro'yxatni tsikldagi elementlarning har biri orqali ko'rib chiqamiz :

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

   2. agar chelak daraxt tuzilishi bo'lsa, u holda usul qo'shimcha ravishda chaqiriladi getTreeNode(), bu esa o'z navbatida kerakli kalitni topish uchun usuldan foydalanadi find(). Biz daraxt qidirishni amalga oshiramiz - xeshlar solishtiriladi va qidirish uchun chap yoki o'ng ildiz tugunlari aniqlanadi. Agar tugmalar teng bo'lsa (mos yozuvlar bo'yicha yoki tomonidan equals), bu tugunni qaytaring. Agar chap yoki o'ng pastki tugunlar null bo'lsa, biz qo'shimcha ravishda compareTo yordamida kalitlarni solishtiramiz (agar kalitlar interfeysni amalga oshirsa Comparable), aks holda daraxt bo'ylab (o'ng yoki chap pastki daraxt) mos keladigan topilmaguncha rekursiv qidiruvni amalga oshiramiz.

HashMap-dan ob'ektlarni olib tashlash Maqolada bo'sh joy tugashi sababli, kalit yordamida o'chirish qanday sodir bo'lishini qisqacha tasvirlab beraman. Algoritm juda o'xshash:

• kerakli chelakka o'ting (yana, u oldindan hisoblab chiqilgan);

• chelakda faqat bitta ob'ekt bo'lsa (biz uning null ko'rsatgichini tekshiramiz) biz xeshlarni, havolalarni va equals(agar to'satdan xeshlar teng bo'lmasa) solishtiramiz. Gugurt topdingizmi? Ajoyib, bu bizning kalitimiz - uni o'chiring (=null) va ushbu kalitning qiymatini qaytaring.

• agar chelakda bir nechta element mavjud bo'lsa, biz elementni topgunimizcha yoki ro'yxatning oxiriga yetguncha har bir elementni tsiklda tekshiramiz.

• agar element topilmasa, biz nullni qaytaramiz.

Daraxt bilan bog'liq vaziyatda juda qiyin amalga oshirish mavjud, bu haqda bilmaslik va uxlash yaxshiroqdir (usulning tavsifi hatto qizil-qora rangdagi oddiy o'chirish operatsiyasiga qaraganda amalga oshirish murakkabroq ekanligini aytadi. daraxt). Bundan tashqari, o'chirilganda, bitta chelakdagi tugunlar soni 6 ga qaytishi mumkin va keyin daraxt bog'langan ro'yxatga qayta tiklanadi. Agar siz ko'p yillik tajribaga ega dasturchi bo'lmasangiz, buni bilish va tushunish umuman shart emas (va shunchaki shart emas).