HashMap Java'да кантип иштейт

HashMapБүгүнкү күндө интервью учурунда талкуулоо үчүн эң сүйүктүү тема экенине көпчүлүгүңүздөр кошуласыздар . Кээде мен кесиптештерим менен ушундай талкууларды өткөрдүм жана бул чындап жардам берди. Эми мен сиз менен ушундай талкуу өткөрөм. Менимче, эгер сизди HashMapтин ички түзүлүшү жана иштеши кызыктырса, анда сиз HashMapтин негиздери менен мурунтан эле таанышсыз , андыктан мен бул бөлүктү өткөрүп жиберем. Бирок, эгер сиз бул үчүн жаңы болсоңуз, мен сизге Java Docs сайтына өтүүнү сунуштайм . Улантуудан мурун, мен сизге мурунку макаламды карап чыгууну сунуштайм: Java'да hashCode жана барабар ыкмасы менен иштөө. Бул макаланын мазмуну:

1. Мүмкүн болгон жалгыз жооп.
2. Hashing деген эмне.
3. Класс жөнүндө бир аз Entry.
4. эмне кылат put().
5. Метод кантип иштейт get().
6. Эскертүүлөр

Мүмкүн болгон жалгыз жооп

Эгер кимдир бирөө менден " HashMap кантип иштейт?" ", Мен жөн гана жооп берем:" Hashing принциптерине ылайык . Бул жөнөкөй болушу мүмкүн эмес. Муну түшүнүү жана кеңейтилген жооп алуу үчүн, сиз Хэшингдин негиздерин билгениңизге ишенишиңиз керек. Туурабы?

Hashing деген эмне

Эң жөнөкөй формада хэшинг – бул ар кандай формуланы/алгоритмди алардын касиеттерине колдонгондон кийин ар кандай өзгөрмө/an objectти уникалдуу codeго айландыруу жолу. Чыныгы хэш-функция төмөнкү эрежени сакташы керек: Хеш-функция бир эле же бирдей an objectтерге колдонулган сайын ошол эле хэш-codeду кайтарып бериши керек. Башка сөз менен айтканда, эки бирдей an object өз кезегинде эле хэш codeдорун кайтарып бериши керек. Бул тууралуу кененирээк бул жерден окуй аласыз: Java тorнде hashCode жана барабар ыкмасы менен иштөө

Кирүү классы жөнүндө бир аз

Аныктама боюнча, карта - бул "баалуулуктарды жана ачкычтарды жуптарда сактаган an object". Абдан жөнөкөй, туурабы? Демек, HashMap ичинде баалуулуктар менен ачкычтардын жуптарын сактаган кандайдыр бир механизм болушу керекпи? Жооп - Ооба. төмөнкүдөй көрүнгөн HashMapички классы бар :Entry

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

Албетте, класстын Entryатрибуттар катары сакталган Ачкыч жана Мааниси бар. Ачкыч катары белгиленген finalжана биз дагы эки кошумча талааны көрөбүз: nextжана hash. Макаланын жүрүшүндө биз бул талаалардын максатын түшүнүүгө аракет кылабыз.

Java put() ыкмасы эмне кылат?

Методду ишке ашырууга киришерден мурун put(), класстын инстанциялары Entryмассивде сакталаарын түшүнүү абдан маанилүү. HashMap классы бул өзгөрмөнү төмөнкүдөй аныктайт:

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

Эми ыкманы ишке ашыруу codeун карап көрүңүз 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;
}

Аны этап-этабы менен аныктап көрөлү:

• Биринчиден, биз ачкыч бар же жок экенин текшеребиз. Эгерде ачкыч жок болсо ( null), маани tableда нөл позициясына жайгаштырылат, анткени маанинин хэш codeу null, это – всегда 0.


• Кийинки кадамда хэш мааниси методду чакыруу менен алынган ачкычтын хэш codeун колдонуу менен эсептелет hashCode(). Бул хэш мааниси an object жайгаштырыла турган массивдеги позицияны эсептөө үчүн колдонулат Entry. JDK дизайнерлери начар жазылган функция hashCode()өтө жогору же өтө төмөн болгон хэш маанисин кайтарышы мүмкүн деп ойлошкон. Бул көйгөйдү чечүү үчүн алар башка hash()функцияны киргизишти жана хэш мааниси массивдин өлчөмүнө дал келүү үчүн an objectтин хэш маанисин ага өткөрүштү.


• Эми функция indexFor(hash, table.length)an objectтин так ордун эсептөө үчүн чакырылат Entry.


• Бул жерде негизги бөлүгү башталат. Эми, эки бирдей эмес an objectилердин бирдей хэш codeдору болушу мүмкүн экенин билгенибизге таянып, биз суроо беребиз: [чака] массивинде эки башка an object бирдей абалда жайгашабы? Жооп LinkedList. Эсиңизде болсо, класста Entry" " атрибуту бар next. Бул атрибут ар дайым чынжырдагы кийинки an objectти көрсөтөт. Бул так жүрүм-турум LinkedList.

Ошентип, an objectтер Entryформада сакталат LinkedList. Объект Entryбелгилүү бир жерге жайгаштырылганда, HashMap ал жерде мурунтан эле жазуу бар же жок экенин текшерет. Эгерде эч кандай жазуу жок болсо, анда an object ушул позицияга жайгаштырылат. Бирок, бул позицияда an object бар болсо, кийинки атрибут текшерилет. Эгерде ал кайтып келсе nullжана учурдагы an object Entryкийинки шилтеме болуп калса LinkedList. Эгерде кийинки өзгөрмө жок болсо null, proceduresа кийинкиси үчүн ал табылганга чейин кайталанат null. Эгер башка мааниге ээ, бирок мурункудай эле ачкыч менен башка an objectти койсокчу? Логикалык жактан бул эски маанини алмаштырууга алып келиши керек. Бул кантип болот? Жалпысынан алганда, an objectтин ордун аныктагандан кийин , эсептелген позицияга Entryөтүп жатканда , ар бир an object үчүн негизги салыштыруу ыкмасын чакырат . Бул an objectтердин баарында окшош хэш codeдору болушу мүмкүн, бирок ыкма чыныгы окшоштуктарды текшерет. Бул ичиндеги маанини гана алмаштырат . Ошентип, HashMap бардык ачкычтардын уникалдуулугуна кепилдик берет. LinkedListHashMapEntryEntryLinkedListequals()Entry

Java get() ыкмасы кантип иштейт?

Эми бизде ачкыч-маани жуптары кантип сакталаары жөнүндө түшүнүк бар HashMap. Кийинки чоң суроо: an object HashMapдан методго өткөндө эмне болот get()? Объекттин баасы кантип аныкталат? Жоопту биз мурунтан эле бorшибиз керек, анткени методдо ачкычтын уникалдуулугун аныктоо ыкмасы put()ошол эле логикага ээ get(). Аргумент катары берилген an objectтин ачкычын аныктагандан кийин HashMap, ал жөн гана тиешелүү маанисин кайтарат Entry. Эгерде эч кандай дал келүү табылбаса, ыкма get()кайтып келет null. Келгиле, codeду карап көрөлү:

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()Жогорудагы code ушул учурга чейинки ыкмага окшош if (e.hash == hash && ((k = e.key) == key || key.equals(k))), андан кийин ал жөн гана an objectтин маанисин кайтарат.

Эскертүүлөр

• Объектте сактала турган маалымат структурасы аты жана түрү Entryбар массив болуп саналат .tableEntry
• Массивдеги ар бир жеке позиция чака деп аталат, анткени ал LinkedListan objectтердин биринчи элементин камтышы мүмкүн Entry.
• hashCode()Ачкыч an objectтин ордун эсептөө үчүн талап кылынат Entry.
• equals()Ачкыч картадагы ачкычтын уникалдуулугун текшерүү үчүн колдонулат( map).
• hashCode()жана equals()баалуулуктар методдордо get()жана .set()HashMap
• Маанилүү ачкычтар үчүн хэш codeу nullар дайым 0. Жана мындай an object Entryар дайым массивдин нөлдүк абалында сакталат.

Бул макалада мен өз оюмду туура айттым деп ишенем. Ката тапсаңыз же суроолоруңуз болсо, аларды комментарийлерде калтырыңыз. Бактылуу окуу!