HashMap Java-da qanday ishlaydi

Ko'pchiligingiz HashMapbugungi kunda suhbat davomida muhokama qilinadigan eng sevimli mavzu ekanligiga rozi bo'lasiz. Ba'zida men hamkasblarim bilan shunga o'xshash munozaralar o'tkazdim va bu haqiqatan ham yordam berdi. Endi men siz bilan shunday suhbat o'tkazaman. O'ylaymanki, agar siz HashMap-ning ichki qismi va ishlashiga qiziqsangiz, siz HashMap asoslari bilan allaqachon tanishsiz , shuning uchun men bu qismni o'tkazib yuboraman. Ammo agar siz bu bilan yangi bo'lsangiz, men sizga Java Docs saytiga tashrif buyurishingizni maslahat beraman . Davom etishdan oldin, men oldingi maqolamni ko'rib chiqishni tavsiya qilaman: Java'da hashCode va tenglar usuli bilan ishlash. Ushbu maqolaning mazmuni:

1. Yagona mumkin bo'lgan javob.
2. Hashing nima.
3. Sinf haqida bir oz Entry.
4. Nima qiladi put().
5. Usul qanday ishlaydi get().
6. Eslatmalar

Yagona mumkin bo'lgan javob

Agar kimdir mendan " HashMap qanday ishlaydi?" Deb so'rasa. ", Men oddiygina javob beraman:" Hashing tamoyillariga ko'ra . Bu oddiyroq bo'lishi mumkin emas. Buni tushunish va kengaytirilgan javob olish uchun siz Hashing asoslarini bilishingizga ishonch hosil qilishingiz kerak. To'g'rimi?

Hashing nima

Eng oddiy shaklda xeshlash har qanday o'zgaruvchini/ob'ektni ularning xususiyatlariga har qanday formula/algoritmni qo'llaganidan so'ng uni noyob kodga aylantirish usulidir. Haqiqiy xesh funktsiyasi quyidagi qoidaga amal qilishi kerak: Xesh funksiyasi bir xil yoki teng ob'ektlarga qo'llanilganda bir xil xesh kodini qaytarishi kerak. Boshqacha qilib aytganda, ikkita bir xil ob'ekt bir xil xesh kodlarini navbat bilan qaytarishi kerak. Bu haqda ko'proq ma'lumotni bu yerda o'qishingiz mumkin: Java'da hashCode and equals usuli bilan ishlash

Kirish sinfi haqida bir oz

Ta'rifga ko'ra, xarita bu "qiymatlar va kalitlarni juftlik bilan saqlaydigan ob'ekt". Juda oddiy, to'g'rimi? Shunday qilib, HashMap-da qiymatlar va kalitlarning juftlarini saqlaydigan qandaydir mexanizm bo'lishi kerakmi? Javob - Ha. shunga o'xshash HashMapichki sinf mavjud :Entry

static class Entry implements Map.Entry
{
        final K key;
        V value;
        Entry next;
        final int hash;
        ...//остальной code тут…
}

Tabiiyki, sinfda Entryatributlar sifatida saqlanadigan Kalit va Qiymat mavjud. Kalit sifatida belgilangan finalva biz ikkita qo'shimcha maydonni ham ko'ramiz: nextva hash. Maqola davom etar ekan, biz ushbu sohalarning maqsadini tushunishga harakat qilamiz.

Java put() usuli nima qiladi?

Usulni amalga oshirishga kirishishdan oldin , sinf misollari massivda saqlanishini put()tushunish juda muhimdir . EntryHashMap klassi ushbu o'zgaruvchini quyidagicha belgilaydi:

/**
* Размер таблицы, изменяется при необходимости. Длина всегда должна быть
* кратна двум!
*/
    transient Entry[] table;

Endi usulni amalga oshirish kodini ko'rib chiqing put():

/**
* Связывает определенное meaning с определенным ключом в этой карте(map).
* Если карта перед этим содержала meaning для данного ключа, это meaning
* заменится на новое.
*
* @param key
*            ключ с которым указанное meaning должно быть связано.
* @param value
*            meaning которое должно быть связано с ключом.
* @return вернет предыдущее meaning связанное с key, or null
*         если не было значений связанных с key. (Вернет null
*         так же, если перед этим key был связан со meaningм null)
*/
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<k , V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}

modCount++;
addEntry(hash, key, value, i);
return null;
}

Keling, buni bosqichma-bosqich aniqlaymiz:

• Avvalo, biz kalit mavjudligini tekshiramiz. Agar kalit mavjud bo'lmasa ( null), qiymat jadvalning nol holatiga joylashtiriladi, chunki qiymatning xesh kodi null, это – всегда 0.


• Keyingi bosqichda, xesh qiymati usulni chaqirish orqali olingan kalitning xesh kodi yordamida hisoblanadi hashCode(). Ushbu xesh qiymati ob'ekt joylashtiriladigan qatordagi o'rnini hisoblash uchun ishlatiladi Entry. JDK dizaynerlari noto'g'ri yozilgan funksiya hashCode()juda yuqori yoki juda past bo'lgan xesh qiymatini qaytarishi mumkin deb taxmin qilishdi. Ushbu muammoni hal qilish uchun ular boshqa hash()funktsiyani kiritdilar va xesh qiymati massivning o'lchamiga mos kelishi uchun ob'ektning xesh qiymatini unga o'tkazdilar.


• Endi funksiya indexFor(hash, table.length)ob'ekt qo'yiladigan joyni aniq hisoblash uchun chaqiriladi Entry.


• Bu erda asosiy qism boshlanadi. Endi ikkita teng bo'lmagan ob'ektlar teng xesh-kodlarga ega bo'lishi mumkinligini bilganimizga asoslanib, biz savol beramiz: [paqir] massivida ikki xil ob'ekt bir xil holatda joylashtiriladimi? Javob: LinkedList. Esingizda bo'lsa, sinfda Entry" " atributi mavjud next. Bu atribut har doim zanjirdagi keyingi ob'ektga ishora qiladi. Bu aynan xulq-atvor LinkedList.

Shunday qilib, ob'ektlar Entryshaklda saqlanadi LinkedList. Ob'ekt Entryma'lum bir joyga joylashtirilishi kerak bo'lganda, HashMap o'sha joyda allaqachon kirish mavjudligini tekshiradi. Agar kirish bo'lmasa, ob'ekt shu pozitsiyaga joylashtiriladi. Agar bu holatda ob'ekt allaqachon mavjud bo'lsa, keyingi atribut tekshiriladi. Agar u qaytsa nullva joriy ob'ekt Entrykeyingi havolaga aylansa LinkedList. Agar keyingi o'zgaruvchi bo'lmasa null, protsedura topilmaguncha keyingisi uchun takrorlanadi null. Agar boshqa qiymatga ega, lekin avvalgidek bir xil kalitga ega boshqa ob'ektni qo'ysak nima bo'ladi? Mantiqan bu eski qiymatni almashtirishga olib kelishi kerak. Bu qanday sodir bo'ladi? Umuman olganda, ob'ektning o'rnini aniqlagandan so'ng , hisoblangan pozitsiyaga Entryo'tayotganda , u har bir ob'ekt uchun kalit solishtirish usulini chaqiradi . Ushbu ob'ektlarning barchasi o'xshash xesh kodlariga ega bo'lishi mumkin, ammo usul haqiqiy o'xshashlikni tekshiradi. Bu faqat ichidagi qiymatni almashtiradi . Shunday qilib, HashMap barcha kalitlarning o'ziga xosligini kafolatlaydi. LinkedListHashMapEntryEntryLinkedListequals()Entry

Java get() usuli qanday ishlaydi?

Endi bizda kalit-qiymat juftlari qanday saqlanishi haqida fikrimiz bor HashMap. Keyingi katta savol: Ob'ekt HashMap dan metodga o'tkazilganda nima sodir bo'ladi get()? Ob'ektning qiymati qanday aniqlanadi? Biz javobni allaqachon bilishimiz kerak, chunki kalitning o'ziga xosligini usulda aniqlash usuli put()xuddi shunday mantiqqa ega get(). Argument sifatida berilgan ob'ektning kalitini aniqlagandan so'ng HashMap, u shunchaki mos keladigan qiymatni qaytaradi Entry. Hech qanday moslik topilmasa, usul get()qaytadi null. Keling, kodni ko'rib chiqaylik:

public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<k,V>e=table[indexFor(hash,table.length)];e!=null;e=e.next){
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}

put()Yuqoridagi kod shu nuqtagacha bo'lgan usulga o'xshaydi if (e.hash == hash && ((k = e.key) == key || key.equals(k))), shundan so'ng u ob'ekt qiymatini qaytaradi.

Eslatmalar

• Ob'ektda saqlanadigan ma'lumotlar strukturasi nomi va turiga Entryega bo'lgan massivdir .tableEntry
• Massivdagi har bir alohida pozitsiya chelak deb ataladi, chunki u LinkedListob'ektlarning birinchi elementini o'z ichiga olishi mumkin Entry.
• hashCode()Ob'ektning o'rnini hisoblash uchun kalit talab qilinadi Entry.
• equals()Kalit xaritadagi kalitning o'ziga xosligini tekshirish uchun ishlatiladi( map).
• hashCode()va Qadriyatlar usullarda va da equals()ishlatilmaydi .get()set()HashMap
• Qiymatli kalitlar uchun xesh-kod nullhar doim 0 ga teng. Bunday ob'ekt Entryhar doim massivning nol holatida saqlanadi.

Umid qilamanki, men ushbu maqolada o'z fikrlarimni to'g'ri etkazdim. Agar xatolar topsangiz yoki savollaringiz bo'lsa, ularni sharhlarda qoldiring. Baxtli o'rganish!