HashMap Java-da necə işləyir

Çoxunuz razılaşarsınız ki HashMap, bu gün müsahibələr zamanı müzakirə üçün ən sevimli mövzudur. Bəzən həmkarlarımla belə müzakirələr aparırdım və bu, həqiqətən də kömək etdi. İndi sizinlə belə bir müzakirə aparacağam. Güman edirəm ki, əgər HashMap-ın daxili xüsusiyyətləri və işləməsi ilə maraqlanırsınızsa, o zaman HashMap- ın əsasları ilə artıq tanışsınız , ona görə də bu hissəni atlayacağam. Ancaq bu işdə yenisinizsə, sizə Java Sənədlər saytına keçməyi təklif edirəm . Davam etməzdən əvvəl əvvəlki məqaləmə baxmağınızı çox tövsiyə edirəm: Java-da hashCode və bərabər üsulla işləmək. Bu məqalənin məzmunu:

1. Tək mümkün cavab.
2. Hashing nədir.
3. Sinif haqqında bir az Entry.
4. Nə edir put().
5. Metod necə işləyir get().
6. Qeydlər

Tək mümkün cavab

Əgər kimsə məndən " HashMap necə işləyir?" ", Mən sadəcə cavab verəcəyəm: " Hashing prinsiplərinə görə ." Daha sadə ola bilməzdi. Bunu başa düşmək və geniş cavab almaq üçün Hashing-in əsaslarını bildiyinizə əmin olmalısınız. Düzdür?

Hashing nədir

Ən sadə formada heşinq hər hansı bir dəyişəni/obyekti xassələrinə hər hansı formula/alqoritmi tətbiq etdikdən sonra unikal koda çevirmək üsuludur. Həqiqi hash funksiyası aşağıdakı qaydaya əməl etməlidir: Haş funksiyası eyni və ya bərabər obyektlərə tətbiq edildikdə eyni hash kodunu qaytarmalıdır. Başqa sözlə, iki eyni obyekt öz növbəsində eyni hash kodları qaytarmalıdır. Bu barədə daha ətraflı burada oxuya bilərsiniz: Java-da hashCode and equals metodu ilə işləmək

Giriş sinfi haqqında bir az

Tərifinə görə, xəritə “dəyərləri və açarları cüt-cüt saxlayan obyektdir”. Olduqca sadə, elə deyilmi? Beləliklə, HashMap-da Dəyərlər və Açar cütlərini saxlayan bir növ mexanizm olmalıdır? Cavab - Bəli. bu kimi görünən HashMapdaxili sinif var :Entry

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

Təbii ki, sinifdə Entryatributlar kimi saxlanılan Açar və Dəyər var. Açar kimi qeyd olunur finalvə biz iki əlavə sahəni də görürük: nextvə hash. Məqalə irəlilədikcə bu sahələrin məqsədini anlamağa çalışacağıq.

Java put() metodu nə edir?

Metodun tətbiqinə başlamazdan əvvəl , sinif nümunələrinin bir massivdə saxlandığını put()başa düşmək çox vacibdir . EntryHashMap sinfi bu dəyişəni aşağıdakı kimi müəyyən edir:

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

İndi metodun icra koduna nəzər salın 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;
}

Bunu addım-addım anlayaq:

• Əvvəlcə açarın olub olmadığını yoxlayırıq. Açar mövcud deyilsə ( null), dəyər cədvəldə sıfır mövqedə yerləşdirilir, çünki dəyərin hash kodu null, это – всегда 0.


• Növbəti addımda hash dəyəri metodu çağırmaqla əldə edilən açarın hash kodundan istifadə etməklə hesablanır hashCode(). Bu hash dəyəri obyektin yerləşdiriləcəyi massivdəki mövqeyi hesablamaq üçün istifadə olunur Entry. JDK dizaynerləri pis yazılmış funksiyanın hashCode()çox yüksək və ya çox aşağı hash dəyərini qaytara biləcəyini güman edirdilər. Bu problemi həll etmək üçün onlar başqa bir hash()funksiya təqdim etdilər və hash dəyərinin massivin ölçüsünə uyğun olması üçün obyektin hash dəyərini ona keçirdilər.


• İndi funksiya indexFor(hash, table.length)obyektin yerləşdiriləcəyi yeri dəqiq hesablamaq üçün çağırılır Entry.


• Əsas hissə buradan başlayır. İndi bildiyimizə əsasən - iki qeyri-bərabər obyektin bərabər hash kodları ola bilər, biz sual veririk: [bucket] massivində eyni mövqedə iki müxtəlif obyekt yerləşdiriləcəkmi?Cavab LinkedList. Yadınızdadırsa, sinfin Entry" " atributu var next. Bu atribut həmişə zəncirdəki növbəti obyektə işarə edir. Bu, məhz davranışdır LinkedList.

Beləliklə, obyektlər Entryformada saxlanılır LinkedList. Obyekt Entrymüəyyən bir yerə yerləşdirilməli olduqda, HashMap həmin yerdə artıq bir girişin olub olmadığını yoxlayır. Əgər giriş yoxdursa, o zaman obyekt bu mövqeyə yerləşdirilir. Bununla belə, bu mövqedə artıq obyekt varsa, növbəti atribut yoxlanılır. Qaytardıqda və cari nullobyekt . Növbəti dəyişən deyilsə , tapılana qədər prosedur növbəti üçün təkrarlanır . Fərqli dəyəri olan, lakin əvvəlki kimi eyni açarı olan başqa bir obyekt qoysaq nə olar? Məntiqi olaraq bu, köhnə dəyərin dəyişdirilməsi ilə nəticələnməlidir. Bu necə baş verir? Ümumiyyətlə, obyektin mövqeyini təyin etdikdən sonra hesablanmış mövqeyə keçərkən hər bir obyekt üçün əsas müqayisə metodunu çağırır . Bu obyektlərin hamısının oxşar hash kodları ola bilər, lakin metod əsl oxşarlığı yoxlayacaq. Bu, yalnız daxilindəki dəyəri əvəz edəcək . Beləliklə, HashMap bütün açarların unikallığına zəmanət verir. EntryLinkedListnullnullEntryLinkedListHashMapEntryEntryLinkedListequals()Entry

Java get() metodu necə işləyir?

İndi açar-dəyər cütlərinin necə saxlandığı barədə bir fikrimiz var HashMap. Növbəti böyük sual budur: Obyekt HashMap-dan metoda ötürüləndə nə baş verir get()? Bir obyektin dəyəri necə müəyyən edilir? Biz artıq cavabı bilməliyik, çünki açarın unikallığının metodda təyin olunma üsulu put()metodun tətbiq etdiyi eyni məntiqə malikdir get(). HashMapArqument kimi ötürülən obyektin açarını müəyyən etdikdən sonra , sadəcə olaraq müvafiq nin dəyərini qaytarır Entry. Heç bir uyğunluq tapılmazsa, metod get()geri qayıdacaq null. Koda nəzər salaq:

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()Yuxarıdakı kod bu nöqtəyə qədər olan metoda bənzəyir.Bundan if (e.hash == hash && ((k = e.key) == key || key.equals(k)))sonra sadəcə obyektin dəyərini qaytarır.

Qeydlər

• Obyektdə saxlanacaq məlumat strukturu adı və növü Entryolan massivdir .tableEntry
• Massivdəki hər bir fərdi mövqe vedrə adlanır, çünki o, LinkedListobyektlərin birinci elementini ehtiva edə bilər Entry.
• hashCode()Obyektin mövqeyini hesablamaq üçün açar tələb olunur Entry.
• equals()Açar xəritədəki açarın unikallığını yoxlamaq üçün istifadə olunur( map).
• hashCode()və equals()Dəyərlər metodlarda get()və .set()HashMap
• Dəyəri olan açarlar üçün hash kodu nullhəmişə 0-dır. Belə obyekt Entryhəmişə massivin sıfır mövqeyində saxlanılacaq.

Ümid edirəm ki, bu yazıda fikirlərimi düzgün çatdırmışam. Səhvlər tapsanız və ya suallarınız varsa, onları şərhlərdə buraxın. Xoşbəxt öyrənmə!