HashMap Java тілінде қалай жұмыс істейді

Сіздердің көпшілігіңіз келісетін боларсыздар HashMap, бүгінгі таңда сұхбат кезінде талқылау үшін ең сүйікті тақырып. Кейде мен әріптестеріммен осындай пікірталастар өткіздім және бұл шынымен көмектесті. Енді мен сіздермен осындай пікірталас өткіземін. Менің ойымша, егер сізді HashMap бағдарламасының ішкі құрылымы мен жұмысы қызықтырса, онда сіз HashMap негіздерімен бұрыннан таныссыз , сондықтан мен бұл бөлікті өткізіп жіберемін. Бірақ егер сіз мұны жаңадан бастасаңыз, мен сізге Java Docs сайтына баруды ұсынамын . Әрі қарай қозғалмас бұрын, мен сізге алдыңғы мақаламды қарап шығуды ұсынамын: Java тіліндегі hashCode және equals әдісімен жұмыс істеу. Осы мақаланың мазмұны:

1. Жалғыз мүмкін жауап.
2. Хэшинг дегеніміз не.
3. Сынып туралы аздап Entry.
4. не істейді put().
5. Әдіс қалай жұмыс істейді get().
6. Ескертпелер

Жалғыз мүмкін жауап

Егер біреу маған « HashMap қалай жұмыс істейді?» Деп түсіндіруімді сұраса. ", Мен жай ғана жауап беремін:" Хэшинг принциптеріне сәйкес . Бұл қарапайым болуы мүмкін емес еді. Мұны түсіну және кеңейтілген жауап алу үшін сіз Хэшинг негіздерін білетініңізге сенімді болуыңыз керек. Дұрыс па?

Хэшинг дегеніміз не

Ең қарапайым түрде хэштеу – кез келген айнымалыны/an objectіні олардың қасиеттеріне кез келген формуланы/алгоритмді қолданғаннан кейін бірегей codeқа түрлендіру тәсілі. Шынайы хэш функциясы келесі ережені орындауы керек: Хэш функциясы бірдей немесе тең нысандарға қолданылған сайын бірдей хэш codeын қайтаруы керек. Басқаша айтқанда, екі бірдей нысан бірдей хэш-codeтарды кезекпен қайтаруы керек. Бұл туралы толығырақ мына жерден оқи аласыз: Java тіліндегі hashCode және equals әдісімен жұмыс істеу

Кіру сыныбы туралы аздап

Анықтамасы бойынша карта «мәндер мен кілттерді жұпта сақтайтын нысан». Өте қарапайым, солай ма? Сонымен, 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()түсіну өте маңызды . EntryHashMap сыныбы бұл айнымалыны келесідей анықтайды:

/**
* Размер таблицы, изменяется при необходимости. Длина всегда должна быть
* кратна двум!
*/
    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), мән кестеде нөлдік орынға қойылады, себебі мәннің хэш codeы null, это – всегда 0.


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


• Енді функция indexFor(hash, table.length)an object орналасатын нақты орынды есептеу үшін шақырылады Entry.


• Негізгі бөлім осы жерден басталады. Енді екі тең емес нысанның хэш-codeтары бірдей болуы мүмкін екенін білетінімізге сүйене отырып, біз сұрақ қоямыз: [bucket] массивінде екі түрлі нысан бір орында орналаса ма? Жауап: LinkedList. Естеріңізде болса, сыныпта Entry« » атрибуты бар next. Бұл атрибут әрқашан тізбектегі келесі нысанды көрсетеді. Бұл дәл мінез-құлық LinkedList.

Сонымен, нысандар Entryпішінде сақталады LinkedList. Нысан Entryбелгілі бір жерге орналастырылған кезде, HashMap сол жерде жазба бар-жоғын тексереді. Ешқандай жазба болмаса, нысан осы позицияға орналастырылады. Дегенмен, осы позицияда нысан бар болса, келесі төлсипат тексеріледі. Егер ол қайтарылса nullжәне ағымдағы нысан Entryкелесі сілтемеге айналса LinkedList. Келесі айнымалы болмаса null, ол табылғанша proceduresа келесі үшін қайталанады null. Мәні басқа, бірақ бұрынғыдай кілті бар басқа нысанды қойсақ ше? Логикалық түрде бұл ескі мәнді ауыстыруға әкелуі керек. Бұл қалай болады? Жалпы, нысанның орнын анықтағаннан кейін есептелген орынға Entryөту кезінде ол әрбір нысан үшін кілтті салыстыру әдісін шақырады . Осы нысандардың барлығында ұқсас хэш codeтары болуы мүмкін, бірақ әдіс шынайы ұқсастықты тексереді. Бұл тек ішіндегі мәнді ауыстырады . Осылайша, HashMap барлық кілттердің бірегейлігіне кепілдік береді. LinkedListHashMapEntryEntryLinkedListequals()Entry

Java get() әдісі қалай жұмыс істейді?

Енді бізде кілт-мән жұптары қалай сақталатыны туралы түсінік бар HashMap. Келесі үлкен сұрақ: нысан HashMap-тен әдіске өткенде не болады get()? Объектінің мәні қалай анықталады? Жауапты біз бұрыннан білуіміз керек, өйткені әдісте кілттің бірегейлігін анықтау әдісі put()әдіс қолданылатын логикаға ие get(). Аргумент ретінде берілген нысанның кілтін анықтағаннан кейін HashMap, ол жай ғана сәйкес мәнін қайтарады Entry. Сәйкестік табылмаса, әдіс get()қайтарылады null. Кодты қарастырайық:

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))), содан кейін ол жай ғана нысанның мәнін қайтарады.

Ескертпелер

• Нысанда сақталатын деректер құрылымы аты мен түрі Entryбар массив болып табылады .tableEntry
• Жиымдағы әрбір жеке позиция шелек деп аталады, себебі ол LinkedListнысандардың бірінші элементін қамтуы мүмкін Entry.
• hashCode()Кілт нысанның орнын есептеу үшін қажет Entry.
• equals()Кілт картадағы кілттің бірегейлігін тексеру үшін қолданылады( map).
• hashCode()және Мәндер әдістерде және ішінде equals()пайдаланылмайды .get()set()HashMap
• Мәні бар кілттерге арналған хэш codeы nullәрқашан 0 болады. Ал мұндай нысан Entryәрқашан массивтің нөлдік орнында сақталады.

Мен бұл мақалада өз ойымды дұрыс жеткіздім деп үміттенемін. Қателерді тапсаңыз немесе сұрақтарыңыз болса, оларды түсініктемелерде қалдырыңыз. Бақытты оқу!