HashMap sinfinin ətraflı təhlili

Sinfin ətraflı müzakirəsinə keçməzdən əvvəl hash cədvəlləri ilə əlaqəli əsas anlayışlara diqqət yetirək. Bu məqalə hash xəritəsi ilə işləmək üsullarını müzakirə etməyəcək. Yalnız daxiletmə, axtarış və silmə əməliyyatları aydın və ətraflı müzakirə olunacaq. Düşünürəm ki , eyni Schildt-dən HashMap üçün mövcud olan metodların təsvirini oxumaq çətin olmayacaq. Yəqin ki, gələcəkdə bu cür üsullara həsr olunmuş başqa bir məqalə yazacağam, amma hələlik bu şübhə altındadır. Java 7 ilə müqayisədə Java 8-də HashMap sinfi əhəmiyyətli dəyişikliklərə məruz qalmışdır (+1000 kod sətirləri). Java 7-də tətbiqetmə haqqında burada oxuya bilərsiniz (lakin artıq aktual deyil): habr Hash cədvəli çox sürətli daxiletmə və axtarışı təmin edən assosiativ massiv interfeysini (mücərrəd açar-dəyər modeli və ya giriş) həyata keçirən məlumat strukturudur : asılı olmayaraq ədəd elementlərinin daxil edilməsi və axtarışı (bəzən silinməsi) sabitə yaxın vaxtda yerinə yetirilir - O(1). Əslində, bu, elementin yeri elementin özünün dəyərindən asılı olduğu müntəzəm massivdir. Elementin dəyəri ilə onun hash cədvəlindəki mövqeyi arasındakı əlaqə hash funksiyası ilə müəyyən edilir. Hash funksiyası açar adlandırdığımız məlumatın giriş hissəsini götürür və çıxış kimi hash dəyəri (yaxud hash kodu) kimi tanınan tam ədəd istehsal edir . Bundan sonra hash dəyəri açarımızı xüsusi hash cədvəli indeksinə bağlayır. Əsas əməliyyatlar üçün: daxil etmə, axtarış və silmə, biz eyni hash funksiyasından istifadə edirik, buna görə də bu əməliyyatlar kifayət qədər tez yerinə yetirilir. Bu səbəbdən, hash funksiyasının ardıcıl davranması və eyni giriş məlumatları üçün eyni indeksi çıxarması vacibdir. Nəzərə almaq lazımdır ki, nəticədə hash kodu böyük rəqəmsal dəyər ola bilər və orijinal massiv şərti olaraq yalnız 16 element üçün nəzərdə tutulub. Niyə cəmi on əlavə etmək üçün milyard elementdən ibarət massiv yaratmayaq? Buna görə də, biz bir şəkildə bu hash kodunu 0-dan 15-ə qədər olan dəyərlərə çevirməliyik (əgər massiv ölçüsü 16-dırsa). Və bunun üçün əlavə çevrilmələr istifadə olunur. Beləliklə, massivin ölçüsünü minimuma endirmək üçün bir indeks yaradırıq. Məsələn, Java 8-dən əvvəl HashMap-da istədiyiniz xananı tapmaq üçün bu əlavə üsuldan istifadə edilmişdir:

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

Giriş kimi, iş nəticəsində əldə edilən hash kodunu hashCode()və daxili massivin uzunluğunu (xanaların sayı) götürdü. Və nəticəni qaytardı “hash code” -> bitwise “AND” -> (massiv uzunluğu – 1). Sinif HashMapsinifdən miras alır AbstractMapvə aşağıdakı interfeysləri həyata keçirir: Map, Cloneable, Serializable. .metod Java-da hash funksiyasından məsuldur hashCode(). Defolt tətbiq şəxsiyyət hash koduhashCode() adlı dəyəri qaytarır . Sinif ləğv etsə belə , siz həmişə zəng edərək obyektin ID hash-ini əldə edə bilərsiniz . OpenJDK-da defolt tətbiqetmənin bəzən hesab edildiyi kimi yaddaş ünvanı ilə heç bir əlaqəsi yoxdur. Daha ətraflı burada: habr HashMap-da hash cədvəli bir-biri ilə əlaqəli siyahıların massivinə (daha doğrusu, cədvəl genişlənə bildiyinə görə dinamik) əsasında həyata keçirilir. Əsasən, metodun nəticəsi olaraq açarın hash kodunu əldə edirik , sonra dəyişdirilir (daha sonra nəzərdən keçirəcəyik) və daxili olaraq, əlavə bir üsuldan istifadə edərək, nəticədə alınan dəyərlər tələb olunan hüceyrələrə paylanır. Massiv elementləri (hüceyrələr) ayrıca qovşaqları saxlamaq üçün istifadə olunan çömçələr adlanır . Kovaların hər biri bir kolleksiyadır (siyahı və ya ağac). Bir qovşaq yuvalanmış sinifin obyektini (və ya ağac strukturunda) təmsil edir. Əslində, massiv hüceyrəsinin içərisində yalnız bir-birinə bağlı siyahı və ya başqa bir sinfin həyata keçirilməsinin əsasını təşkil edən qırmızı-qara ağac var - . hashCode()System.identityHashCode(Object o)hashCode()hashCode()NodeTreeNodeLinkedListTreeMap

Qırmızı-qara ağacı olan seçim o qədər də tez-tez yaranmır (necə, nə və harada - aşağıda) və bu quruluşu başa düşmək olduqca çətindir, buna görə də vurğu Node tipli bir node olacaq. NodeHashMap , içərisində aşağıdakı sahələrə malik olan yuvalanmış sinifdir :

final int hash— açarın hashing nəticəsində əldə etdiyimiz cari elementin hashı;
final K key— cari elementin açarı. Metodda ilk obyekt olaraq təyin etdiyiniz şey bura yazılır put();
V value— cari elementin dəyəri. Metodda ikinci obyekt olaraq təyin etdiyiniz isə burada yazılır put();
Node < K, V> next— eyni səbətdəki növbəti node ilə əlaqə. Siyahı bağlıdır, ona görə də əgər varsa, növbəti qovşaqla deyil, keçid lazımdır.

İndi HashMap sinifinin sahələrinə baxaq:

transient Node < K, V> [] table– açar-dəyər cütlərini qovşaqlar şəklində saxlamaq üçün massiv əsasında həyata keçirilən hash cədvəlinin özü. Qovşaqlarımızın saxlandığı yer budur;
transient int size— açar-dəyər cütlərinin sayı;
int threshold— elementlərin maksimum sayı, çatdıqda hash cədvəlinin ölçüsü ikiqat artır. Düsturdan istifadə edərək hesablanır (tutum * loadFactor);
final float loadFactor— bu parametr cari hash cədvəlinin yeni hash cədvəli yaratmaq üçün hansı yük dərəcəsinə ehtiyac olduğunu müəyyən edir, yəni. hash cədvəli 75% dolu olan kimi yeni hash cədvəli yaradılacaq və cari elementlər ona köçürüləcək (baha başa gələn əməliyyat, çünki bütün elementlər yenidən dəyişdirilməlidir);
transient Set< Map.Entry< K,V>> entrySet- entrySet()təkrarlaya biləcəyimiz bir önbelleğe malikdir HashMap.

Və sabitlər:

static final int DEFAULT_INITIAL_CAPACITY= 1 << 4— standart hash cədvəlinin tutumu (16);
static final int MAXIMUM_CAPACITY = 1 << 30— hash cədvəlinin maksimum mümkün tutumu (təxminən 1 milyard);
static final float DEFAULT_LOAD_FACTOR = 0.75f— defolt yük faktoru;
static final int TREEIFY_THRESHOLD = 8bir vedrədəki elementlərin sayının "həddi" dir, ona çatdıqdan sonra daxili əlaqəli siyahı ağac quruluşuna (qırmızı-qara ağac) çevriləcəkdir.
static final int UNTREEIFY_THRESHOLD = 6— bir səbətdəki elementlərin sayı 6-ya qədər azalarsa, ağacdan əlaqəli siyahıya tərs keçid baş verəcək;
static final int MIN_TREEIFY_CAPACITY = 64— ağac strukturuna keçidin mümkün olduğu hash cədvəlinin minimum tutumu (kovaların sayı). Bunlar. Hash cədvəlində ən azı 64 vedrə varsa və bir vedrədə 8 və ya daha çox element varsa, o zaman ağac quruluşuna keçid baş verəcəkdir.

Sinif konstruktorları:

public HashMap()— defolt olaraq hash ekranı yaradır: həcm (capacity) = 16və yükləmə faktoru ilə (load factor) = 0.75;
public HashMap(Map< ? extends K, ? extends V> m)— başqa xəritələşdirmənin elementlərini yerləşdirmək üçün kifayət qədər ilkin tutuma malik olan başqa verilmiş xəritələşdirmənin elementləri tərəfindən inisiallaşdırılmış hash xəritəsi yaradır;
public HashMap(int initialCapacity)— verilmiş ilkin tutumla hash xəritəsi yaradır. HashMap-ın düzgün və düzgün işləməsi üçün daxili massivin ölçüsü ikinin gücü olmalıdır (yəni 16, 64, 128 və s.);
public HashMap(int initialCapacity, float loadFactor)— müəyyən edilmiş parametrlərlə hash xəritəsi yaradır: ilkin tutum və yük əmsalı.

Sinif interfeysi həyata keçirir və öz metodlarını əlavə etmədən Mapsinfi genişləndirir . Hash xəritəsi onun elementlərinin sırasına zəmanət vermir. Buna görə də, elementlərin hash xəritəsinə daxil edilmə ardıcıllığı onların iterator tərəfindən alınma ardıcıllığı deyil. Obyektlərin əlavə edilməsi Açar-dəyər cütünün əlavə edilməsi . Obyekt əlavə edərkən görülən addımlara nəzər salaq: AbstractMapput()

Daxil edilmiş obyektin açarının hash dəyəri hesablanır. Açar hash artıq bildiyimiz əsas metoda static final int hash(Object key)daxil olan bir üsulla hesablanır . hashCode()Bunun üçün ya ləğv edilmiş metod hashCode(), ya da onun standart tətbiqi istifadə olunur. Metodda əlavə dəyişikliklər 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.
Вычисляем индекс бакета (ячейки массива), в который будет добавлен наш элемент:
```
i = (n - 1) & hash
```
где n – длина массива.
Создается an object Node.
Теперь, зная индекс в массиве, мы получаем список (цепочку) элементов, привязанных к этой ячейке. Если в бакете пусто, тогда просто размещаем в нем элемент. Иначе хэш и ключ нового 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. Eyni zamanda, obyektimizin yerləşdiriləcəyi vedrənin indeksini hesablayırıq və orada artıq elementlərin olub olmadığını yoxlayırıq. Hesablayırıq:
```
i = (n - 1) & hash
i = (16 - 1) & 2306996
i = 4
```
  yoxlayın:
```
if ((p = tab[i = (n - 1) & hash]) == null)
```
6. Yoxlama nəticəsində həqiqəti əldə etdiyimiz üçün (kovada heç bir element yoxdur), aşağıdakı sahələri olan Node obyekti yaradılacaq:
```
{
int hash = 2306996 — сгенерированный хеш-code
String key = {"KING"} — ключ
Integer value = 100 — meaning
Node next = null — link на следующий узел
}
```
  Yaradılan Node obyektimiz [4] indeksinin altındakı kovaya əlavə olunacaq:
```
tab[i] = newNode(hash, key, value, null);
tab[4] = newNode(2306996, “KING”, 100, null);
```
  newNode()sadəcə Node sinfinin obyektini qaytaran bir üsuldur.
7. Əlavə etdikdən sonra elementlərin cari sayının parametrdən artıq olub olmadığını yoxlamaq üçün yoxlama aparılacaq threshold:
```
if (++size > threshold)
    resize();
```
  resize()Həddindən artıq olarsa, hash cədvəlinin ölçüsünü artırmaq üçün bir üsul çağırılacaq .
  
  Bu nöqtədə metod putVal()(və müvafiq olaraq put()) öz işini tamamlayacaq.
  
  Nəticə qrafik olaraq aşağıdakı kimi təqdim edilə bilər:
  
  Ümumiyyətlə, istənilən kova boş olarsa, hash cədvəlinə Node (açar-dəyər cütü) əlavə etmək belə görünür . İndi isə toqquşmaya səbəb olacaq elementi əlavə etməyə çalışaq (bir vedrədə birdən çox element olduqda).

Toqquşmalar haqqında bir az Fərqli düymələrin eyni vedrədə (hətta müxtəlif hashlərlə) başa çatması vəziyyətinə toqquşma və ya toqquşma deyilir. Hash cədvəli verilənlər dəstindən böyük olsa və yaxşı hash funksiyası seçilsə belə, bu, toqquşmaların baş verməyəcəyinə zəmanət vermir. Və hash dəyəri int dəyərlərinin diapazonu ilə məhdudlaşır (təxminən 4 milyard). Yaranan yeni dəyərin də hardasa yazılması lazımdır və bunun üçün onun tam olaraq harada yazılacağını müəyyən etmək lazımdır. Buna münaqişənin həlli deyilir. İki yanaşma var:

xarici zəncirləmə və ya zəncirləmə üsulu (HashMap-də həyata keçirilir) - yəni. hüceyrə əslində bir siyahı (zəncir) ehtiva edir. Siyahıda artıq bir neçə dəyər ola bilər (eyni hash kodu ilə mütləq deyil).
xətti araşdırma və ya açıq ünvanlama metodu (IdentityHashMap-da həyata keçirilir) - hash funksiyası ilə işarə ediləndən sonra ilk boş xananın axtarışından ibarətdir;

Toqquşmalar haqqında burada oxuya bilərsiniz: klikləyin

Metoddan istifadə edərək, put()hash xəritələşdirilməsinə başqa bir açar-dəyər cütü əlavə edəcəyik:
```
map.put("BLAKE", 10);
```
“İlkin hash”ı hesablayırıq – 63281361. Biz onu dəyişdiririk və nəticədə son hash kodunu alırıq – 63281940.
İlk "boşluq" yoxlanışı indi yalanı qaytaracağından (cədvəl yaratmağa ehtiyac yoxdur), biz dərhal obyektimizin yerləşdiriləcəyi kovanın indeksini hesablayırıq:
```
i = (n - 1) & hash
i = (16 - 1) & 63281940
i = 4
```
Göstərilən indeksdəki çömçə içindəki elementlərin olması yoxlanılır və if ((p = tab[i = (n - 1) & hash]) == null)bu vəziyyətdə şərt yerinə yetirilmədiyi üçün (bacada artıq bir element var), onda biz bloka gedirik else.
Əvvəla, əlavə olunan elementi vedrə daxilində əlaqəli siyahının birinci elementi ilə müqayisə edirik:
```
(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 уже на первом этапе (разные хеши).
Игнорируем condition (p instanceof TreeNode), так How структура в бакете не является древовидной на данном этапе.
Далее переходим в цикл 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 в текущем и сохранить оба под нужным индексом; либо осуществить переход к древовидной структуре
После каждой итерации (добавления нового 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()Ağac strukturuna getmək əvəzinə, elementləri yenidən bölüşdürərək, hash cədvəlinin ölçüsünü artırmaq üçün bir üsul çağırılacaq . öz növbəsində qırmızı-qara ağaca çevrilənlərin treeify()əlaqəli siyahısı . TreeNodeMetod resize()cari yaddaşın bütün elementlərini təkrarlayır, onların indekslərini yenidən hesablayır (yeni ölçü nəzərə alınmaqla) və elementləri yeni massivdə yenidən bölüşdürür.

Qısaca, qırmızı-qara ağacın quruluşunun təfərrüatlarına girmədən aşağıdakılar baş verir:
1. Siyahının birinci elementi bütün ağacın kökü kimi yazılır (qara):
```
if (root == null) {
    x.parent = null;
    x.red = false;
    root = x;
}
```
2. Digər elementlər üçün:
  
  hash dəyərindən asılı olaraq onları sola və ya sağa paylayın:
```
if ((ph = p.hash) > h)
    dir = -1;
else if (ph < h)
    dir = 1;
```
  Bütün sol uşaqlar kök düyünlərindən kiçik (və ya ona bərabər), bütün sağ uşaqlar isə daha böyük olmalıdır.
3. Əgər iki element eyni hashlərə malikdirsə və heç bir şəkildə müqayisə oluna bilmirsə (onlar interfeysi həyata keçirmirlər Comparable), biz ağacın tikintisini dayandırırıq və metodu çağırırıq , bu da öz növbəsində qlobal miqyasda unikal hash kodunu hesablamaq üçün tieBreakOrder()yerli metoddan istifadə edir. System.identityHashCode().
  
  Daha ətraflı burada: məqaləyə keçid
4. TreeNodeUşaq (sol və ya sağ) sıfır element tapılana qədər ağac elementlərini (obyektləri) yoxlayırıq .
```
if ((p = (dir <= 0) ? p.left : p.right) == null)
```
5. Uşaq node əlavə edin (dirəkdən asılı olaraq sola və ya sağa):
```
x.parent = xp;
if (dir <= 0)
    xp.left = x;
else
    xp.right = x;
```
6. Yeni elementin əlavə edilməsi ağacın tarazlığını poza biləcəyi üçün biz balanslaşdırma metodunu çağırırıq:
```
root = balanceInsertion(root, x);
```
  CCH-nin balanslaşdırılması haqqında burada oxuya bilərsiniz: habr
7. Balanslaşdırdıqdan sonra kök element dəyişə bilər. Biz ona ötürülən kökün ilk qovşaq olacağına zəmanət verən metodu çağırmaqla bunu düzəldirik:
```
moveRootToFront(tab, root)
```
  Qırmızı-qara ağacın necə qurulduğunu və özünü tarazlaşdırdığını burada aydın görə bilərsiniz: vizuallaşdırma

Prinsipcə, hamısı budur və bir nümunədən istifadə edərək, aşağıdakı adları açar kimi əlavə etmək istədiyimizi güman edək: KING, MARY, JOSE, ANNA, FRED, TONY, ALEX, PEPE. Və deyək ki, hash cədvəlində ən azı 64 vedrə var və bütün bu elementlər bir vedrədə toplanıb. Struktur olaraq bu vedrə belə görünəcək (elementlər hash koduna görə sıralanır): CCHD növü:

Kovanın içərisinə baxın:

Elementlərin axtarışı (açarla dəyərin alınması) Əlavə əməliyyatına gəldikdə, bu, olduqca sadədir. Alqoritm (çanaqda əlaqəli siyahı olduqda) belə yazıla bilər:

Açarın hash kodunu hesablayın.
Kova indeksini hesablayın.
İndeksdən keçin və ilk elementin açarını mövcud dəyərlə müqayisə edin. Əgər onlar bərabərdirsə, dəyəri qaytarın, əks halda, əgər varsa, növbəti elementi yoxlayın.
Növbəti Node obyekti null olarsa, null qaytarın.
Növbəti Node obyekti null deyilsə, ona gedin və element tapılana və ya növbəti Node obyekti null olana qədər ilk üç addımı təkrarlayın.

Metoddan istifadə edərək get()"KING" açarının dəyərini alırıq:

map.get("KING");

getNode(int hash, Object key)İçəridə, əməliyyat zamanı olduğu kimi əvvəlcədən hesablanmış açarın özü ("KING") və onun hash (2306996) ötürüldüyü üsul çağırılır put().

Yoxlayırıq:
1. hətta hash cədvəli mövcuddurmu:(tab = table) != null
  
  Nəzərinizə çatdırım ki, HashMap yaradarkən, konstruktorda cədvəl üçün massiv yaradılmır, bu, resize()heş cədvəlinə birinci element əlavə edilərkən həmişə çağırılan metodda daha sonra baş verir. Buna görə də, əgər HashMap-a heç bir element əlavə olunmayıbsa, sadəcə olaraq elementləri saxlamaq üçün daxili massiv yoxdur.
2. əvvəlki ifadə doğrudursa, daxili massivin uzunluğunun 0-dan böyük olduğuna əmin olmalısınız:(n = tab.length) > 0;
3. əvvəlki ifadə də doğrudursa, əvvəllər hesablanmış indeksdəki (bizim vəziyyətimizdə 4) kovaya keçin və elementlərin olub olmadığını yoxlayın:
```
(first = tab[(n - 1) & hash]) != null)
```
4. Axtardığımız açarı kovanın içərisindəki siyahıdakı birinci elementin açarı ilə müqayisə edirik, çünki əksər vedrələrdə (hər yerdə toqquşmamız olmur) yalnız bir element (bizim halda) olacaq. Metodda olduğu kimi put(), hashlar müqayisə edilir və əgər uyğun gəlirsə, açarlar istinadla və yalnız bundan sonra equals().
```
if (first.hash == hash && // always check first node
    ((k = first.key) == key || (key != null && key.equals(k))))
```
  Bizim vəziyyətimizdə "KING" açarı "BLAKE" açarından əvvəl olacağından (əlaqəli siyahıda sonuna yeni elementlər əlavə olunur və əvvəlcə KING əlavə olunur), biz bu nöqtədə dayanacağıq və ilk obyekti qaytaracağıq. Get() metoduna Node yazın, ondan (100) dəyəri olan bir sahəni "qoparır":
```
return (e = getNode(hash(key), key)) == null ? null : e.value;
```
Kovanda birdən çox element varsa, onda:
1. do – whileƏgər vedrə əlaqəli siyahıdırsa, uyğunluq tapılana qədər siyahıdan dövrədə elementlərin hər birini keçirik :
```
do {
    if (e.hash == hash &&
        ((k = e.key) == key || (key != null && key.equals(k))))
        return e;
} while ((e = e.next) != null);
```
2. vedrə ağac quruluşudursa, metod əlavə olaraq çağırılır getTreeNode()və bu da öz növbəsində tələb olunan açarı tapmaq üçün metoddan istifadə edir find(). Biz ağac axtarışını həyata keçiririk - hashlər müqayisə edilir və axtarış üçün sol və ya sağ kök node müəyyən edilir. Düymələr bərabərdirsə (istinad və ya ilə equals), bu nodu qaytarın. Sol və ya sağ alt qovşaqlar null olarsa, biz əlavə olaraq compareTo istifadə edərək düymələri müqayisə edirik (əgər düymələr interfeysi həyata keçirirsə Comparable), əks halda uyğunluq tapılana qədər ağac (sağ və ya sol alt ağac) vasitəsilə rekursiv axtarış aparırıq.

HashMap-dan obyektlərin silinməsi Məqalədə yer tükəndiyi üçün açarla silinmənin necə baş verdiyini qısaca təsvir edəcəyəm. Alqoritm çox oxşardır:

istədiyiniz çömçəyə gedin (yenə də əvvəlcədən hesablanır);
vedrədə yalnız bir obyekt varsa (biz onun null göstəricisini yoxlayırıq) hashları, bağlantıları müqayisə edirik və equals(birdən heşlər bərabər deyilsə). Eşitmə tapdınız? Əla, bu bizim açarımızdır - onu silin (=null) və bu açarın dəyərini qaytarın.
vedrədə birdən çox element varsa, elementi tapana və ya siyahının sonuna çatana qədər hər bir elementi dövrədə yoxlayırıq.
element tapılmadıqda, biz null qaytarırıq.

Bir ağac vəziyyətində, bilməmək və sağlam yatmaq daha yaxşı olan olduqca çətin bir tətbiq var (metodun təsviri hətta həyata keçirilməsinin qırmızı-qara rəngdə adi silmə əməliyyatından daha mürəkkəb olduğunu söyləyir. ağac). Üstəlik, silindikdə, bir vedrədəki qovşaqların sayı 6-ya qayıda bilər və sonra ağac yenidən əlaqəli siyahıda yenidən qurulacaq. Əgər siz uzun illər təcrübəsi olan bir tərtibatçı deyilsinizsə, bunu bilmək və anlamaq heç də lazım deyil (və sadəcə lazım deyil).

Şərhlər

TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION