Таҳлили муфассали синфи HashMap

Пеш аз гузаштан ба муҳокимаи муфассали синф, биёед ба мафҳумҳои асосии марбут ба ҷадвалҳои ҳаш тамаркуз кунем. Дар ин мақола усулҳои кор бо харитасозии hash баррасӣ намешавад. Танҳо амалиёти воридкунӣ, ҷустуҷӯ ва несткунӣ равшан ва муфассал баррасӣ карда мешавад. Ман фикр мекунам , ки хондани тавсифи усулҳои дастрас барои HashMap аз ҳамон Шилдт душвор нахоҳад буд. Шояд дар оянда ман мақолаи дигареро ба чунин усулҳо менависам, аммо ҳоло ин шубҳа аст. Дар муқоиса бо Java 7, синфи HashMap дар Java 8 тағироти назаррасро паси сар кардааст (+1000 сатри code). Шумо метавонед дар бораи татбиқи Java 7 дар ин ҷо бихонед (вале дигар аҳамият надорад): habr Ҷадвали ҳаш сохтори додаест, ки интерфейси массиви ассотсиативиро амалӣ мекунад (модели абстрактии калид ё вуруд), ки хеле зуд воридкунӣ ва ҷустуҷӯро таъмин мекунад: новобаста аз он аз элементҳои адад воридкунӣ ва ҷустуҷӯ (ва баъзан ҳазф кардан) дар вақти наздик ба як доимӣ - O(1) анҷом дода мешаванд. Аслан, ин массиви муқаррарӣ аст, ки дар он ҷойгиршавии элемент аз арзиши худи элемент вобаста аст. Муносибати байни арзиши элемент ва мавқеи он дар ҷадвали hash бо функсияи hash муайян карда мешавад. Функсияи хэш як пораи вуруди маълумотро мегирад, ки мо онро калид меномем ва ҳамчун баромади он адади бутунро ба вуҷуд меорад, ки ҳамчун арзиши hash (ё рамзи hash) маълум аст . Пас аз он арзиши hash калиди моро ба индекси мушаххаси ҷадвали hash мепайвандад. Барои амалҳои асосӣ: воридкунӣ, ҷустуҷӯ ва несткунӣ, мо ҳамон як функсияи hash-ро истифода мебарем, бинобар ин ин амалиётҳо хеле зуд иҷро мешаванд. Аз ин сабаб, муҳим аст, ки функсияи hash пайваста амал кунад ва як индексро барои ҳамон як маълумоти воридотӣ барорад. Қобor зикр аст, ки рамзи hash-и натиҷа метавонад арзиши бузурги ададӣ бошад ва массиви аслӣ шартан танҳо барои 16 элемент тарҳрезӣ шудааст. Чаро массиверо бо як миллиард элемент эҷод накунед, то танҳо даҳ адад илова кунед? Аз ин рӯ, мо бояд бо ягон роҳ ин рамзи хэшро ба арзишҳо аз 0 то 15 табдил диҳем (агар андозаи массив 16 бошад). Ва барои ин, тағироти иловагӣ истифода мешаванд. Ҳамин тавр, мо барои кам кардани андозаи массив индекс тавлид мекунем. Масалан, дар HashMap пеш аз Java 8, ин усули иловагӣ барои ёфтани чашмаки дилхоҳ истифода мешуд:

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

Ҳамчун вуруд, он рамзи хэшро гирифт, ки дар натиҷаи кор hashCode()ва дарозии массиви дохилӣ (шумораи ҳуҷайраҳо) гирифта шудааст. Ва он натиҷаро баргардонд "codeи hash" -> битвазни "AND" -> (дарозии массив - 1). Синф HashMapаз синф мерос мегирад AbstractMapва интерфейсҳои зеринро амалӣ мекунад: Map, Cloneable, Serializable. Усули .метод барои функсияи hash дар Java масъул аст hashCode(). Татбиқи пешфарз hashCode()арзишеро бармегардонад, ки codeи ҳеши идентификатсия номида мешавад . Ҳатто агар синф бекор карда шавад ҳам hashCode(), шумо ҳамеша метавонед бо занг задан хэши ID-и an objectро гиред System.identityHashCode(Object o). Татбиқи пешфарз hashCode()дар OpenJDK бо суроғаи хотира ҳеҷ иртиботе надорад, тавре ки баъзан боварӣ доранд. Тафсилоти бештар дар ин ҷо: habr Дар HashMap , ҷадвали ҳаш дар асоси массив (ё аниқтараш, динамикӣ, зеро ҷадвал метавонад васеъ шавад) рӯйхатҳои алоҳидаи алоқаманд амалӣ карда мешавад. Аслан, мо codeи хэш-и калидро дар натиҷаи усул ба даст меорем hashCode(), ки баъдан тағир дода мешавад (тавре ки баъдтар баррасӣ хоҳем кард) ва дар дохor он бо истифода аз усули иловагӣ, арзишҳои натиҷавӣ ба чашмакҳои зарурӣ тақсим карда мешаванд. Элементҳои массив (ячейкаҳо) инчунин сатил номида мешаванд , ки барои нигоҳ доштани гиреҳҳои алоҳида истифода мешаванд. Ҳар як сатил коллексия аст (рӯйхат ё дарахт). Гиреҳ an objectи синфи лонаро Node(ё TreeNodeдар сохтори дарахт) муаррифӣ мекунад. Дарвоқеъ, дар дохor ячейкаи массив LinkedListтанҳо рӯйхати ягонаи алоқаманд ё дарахти сурх-сиёҳ ҷойгир аст, ки асоси амалисозии синфи дигар - TreeMap.

Варианти дарахти сурх-сиёҳ он қадар зуд-зуд ба вуҷуд намеояд (чӣ гуна, чӣ ва дар куҷо - дар зер) ва фаҳмидани ин сохтор хеле душвор аст, бинобар ин таваҷҷӯҳ ба гиреҳи навъи гиреҳ дода мешавад. Node синфи лонаест, ки дар дохor HashMapон майдонҳои зерин дорад:

final int hash— хэши элементи ҷорӣ, ки мо дар натиҷаи хэшкунии калид ба даст меорем;
final K key— калиди унсури ҷорӣ. Дар ин ҷо он чизе ки шумо ҳамчун an objectи аввал дар усул нишон медиҳед, ба он навишта мешавад put();
V value- арзиши элементи ҷорӣ. Ва он чизе, ки шумо ҳамчун an objectи дуюм дар метод муайян мекунед, дар ин ҷо навишта шудааст put();
Node < K, V> next— пайванд ба гиреҳи навбатӣ дар дохor як сабад. Рӯйхат пайваст аст, бинобар ин ба он пайванд лозим аст, на ба гиреҳи навбатӣ, агар мавҷуд бошад.

Акнун биёед ба майдонҳои худи синфи HashMap назар андозем:

transient Node < K, V> [] table– худи ҷадвали ҳаш, ки дар асоси массив амалӣ карда мешавад, барои нигоҳ доштани ҷуфтҳои калид-арзиш дар шакли гиреҳҳо. Дар ин ҷо гиреҳҳои мо нигоҳ дошта мешаванд;
transient int size— шумораи ҷуфтҳои калид-арзиш;
int threshold- шумораи максималии элементҳо, ки ҳангоми расидан ба онҳо андозаи ҷадвали хэш дучанд мешавад. Бо истифода аз формула ҳисоб карда мешавад (иқтидори * loadFactor);
final float loadFactor— ин параметр муайян мекунад, ки дар кадом дараҷаи сарборӣ ҷадвали ҳаши ҷорӣ барои сохтани ҷадвали нави ҳаш лозим аст, яъне. ҳамин ки ҷадвали хэш 75% пур мешавад, ҷадвали хэш-и нав сохта мешавад ва унсурҳои ҷорӣ ба он интиқол дода мешаванд (амали гаронарзиш, зеро ҳамаи элементҳо бояд дубора коркард карда шаванд);
transient Set< Map.Entry< K,V>> entrySet- дорои кэш шудааст entrySet(), ки бо он мо метавонем такрор кунем HashMap.

Ва доимӣ:

static final int DEFAULT_INITIAL_CAPACITY= 1 << 4— иқтидори пешфарз ҷадвали hash (16);
static final int MAXIMUM_CAPACITY = 1 << 30— ҳадди имкон иқтидори ҷадвали hash (тақрибан 1 миллиард);
static final float DEFAULT_LOAD_FACTOR = 0.75f— омor сарбории пешфарз;
static final int TREEIFY_THRESHOLD = 8"остона" -и шумораи элементҳо дар як сатил аст, ки пас аз расидан ба он рӯйхати дохorи алоқаманд ба сохтори дарахт (дарахти сурх-сиёҳ) табдил меёбад.
static final int UNTREEIFY_THRESHOLD = 6— агар шумораи элементҳо дар як сабад то 6 адад кам шавад, он гоҳ гузариши баръакс аз дарахт ба рӯйхати алоқаманд ба амал меояд;
static final int MIN_TREEIFY_CAPACITY = 64— ҳадди ақали иқтидори (шумораи сатилҳо) ҷадвали хэш, ки дар он гузариш ба сохтори дарахт имконпазир аст. Онхое. Агар дар ҷадвали ҳаш ҳадди аққал 64 сатил мавҷуд бошад ва дар як сатил 8 ё зиёда элемент мавҷуд бошад, пас гузариш ба сохтори дарахт ба амал меояд.

Созандагони синф:

public HashMap()— намоиши хэшро ба таври нобаёнӣ эҷод мекунад: аз рӯи ҳаҷм (capacity) = 16ва бо омor сарборӣ (load factor) = 0.75;
public HashMap(Map< ? extends K, ? extends V> m)— харитасозии хэшро эҷод мекунад, ки аз ҷониби унсурҳои харитасозии дигари додашуда бо иқтидори ибтидоӣ оғоз карда шудааст, ки барои ҷойгир кардани унсурҳои харитасозии дигар кифоя аст;
public HashMap(int initialCapacity)— харитаи хэшро бо иктидори ибтидоии додашуда месозад. Барои дуруст ва дуруст кор кардани HashMap, андозаи массиви дохилӣ бояд қудрати ду бошад (яъне 16, 64, 128 ва ғайра);
public HashMap(int initialCapacity, float loadFactor)— харитаи хэшро бо параметрхои му-айяншуда месозад: иктидори ибтидой ва фактори бор.

Синф интерфейсро амалӣ мекунад Mapва синфро AbstractMapбе илова кардани усулҳои худ васеъ мекунад. Харитаи хэш тартиби унсурҳои онро кафолат намедиҳад. Аз ин рӯ, тартиби ворид кардани элементҳо ба харитаи хэш ҳатман тартиби дарёфти онҳо аз ҷониби итератор нест. Илова кардани an objectҳо Илова кардани ҷуфти калидҳо бо истифода аз put(). Биёед қадамҳои ҳангоми илова кардани an objectро бубинем:

Қимати хэшии калиди an objectи воридшуда ҳисоб карда мешавад. Ҳеши калидӣ бо усуле ҳисоб карда мешавад static final int hash(Object key), ки аллакай ба hashCode()усули калидӣ, ки мо медонем, дастрас аст. Барои ин, ё усули бекоршуда hashCode()ё татбиқи пешфарзии он истифода мешавад. Тағйироти иловагӣ дар усул 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. Дар айни замон, мо индекси сатилро, ки an objectи мо ҷойгир карда мешавад, ҳисоб карда, тафтиш мекунем, ки дар он аллакай элементҳо мавҷуданд. Мо ҳисоб мекунем:
```
i = (n - 1) & hash
i = (16 - 1) & 2306996
i = 4
```
  тафтиш:
```
if ((p = tab[i = (n - 1) & hash]) == null)
```
6. Азбаски дар натиҷаи санҷиш мо ҳақиқӣ мегирем (дар сатил ягон элемент мавҷуд нест), an objectи Node бо майдонҳои зерин тавлид мешавад:
```
{
int hash = 2306996 — сгенерированный хеш-code
String key = {"KING"} — ключ
Integer value = 100 — meaning
Node next = null — link на следующий узел
}
```
  Объекти Node тавлидшудаи мо ба сатил зери индекс [4] илова карда мешавад:
```
tab[i] = newNode(hash, key, value, null);
tab[4] = newNode(2306996, “KING”, 100, null);
```
  newNode()усулест, ки танҳо an objectи синфи Node-ро бармегардонад.
7. Пас аз илова, тафтиш карда мешавад, ки оё шумораи ҷории элементҳо аз параметр зиёд аст threshold:
```
if (++size > threshold)
    resize();
```
  Агар аз ҳад зиёд бошад, пас усул resize()барои зиёд кардани андозаи ҷадвали ҳаш даъват карда мешавад.
  
  Дар ин лаҳза, усул putVal()(ва мутаносибан put()) кори худро анҷом медиҳад.
  
  Натиҷаро ба таври графикӣ ифода кардан мумкин аст:
  
  Умуман, ин аст он чизе ки илова кардани гиреҳ (ҷуфти калид-арзиш) ба ҷадвали хэш ба назар мерасад, агар сатor дилхоҳ холӣ бошад . Акнун биёед кӯшиш кунем, ки элементеро илова кунем, ки ба бархӯрд оварда мерасонад (вақте ки дар як сатил зиёда аз як элемент мавҷуд аст).

Каме дар бораи бархӯрд Ҳолате, ки калидҳои гуногун дар як сатил (ҳатто бо hashes гуногун) хотима меёбанд, бархӯрд ё бархӯрд номида мешавад. Ҳатто агар ҷадвали ҳаш аз маҷмӯи додаҳо калонтар бошад ва функсияи хуби хэш интихоб шуда бошад ҳам, ин кафолат намедиҳад, ки бархӯрдҳо рух намедиҳанд. Ва арзиши hash бо доираи арзишҳои int маҳдуд аст (тақрибан 4 миллиард). Қимати нави ҳосилшуда низ бояд дар ҷое навишта шавад ва барои ин шумо бояд муайян кунед, ки он маҳз дар куҷо навишта мешавад. Ин ҳалли низоъ номида мешавад. Ду равиш вуҷуд дорад:

Усули занҷир ё занҷири беруна (дар HashMap амалӣ карда мешавад) - яъне. ячейка воқеан рӯйхат (занҷир) дорад. Ва рӯйхат метавонад аллакай якчанд арзишҳоро дар бар гирад (на ҳатман бо ҳамон codeи хэш).
Усули санҷиши хатӣ ё суроғаи кушод (дар IdentityHashMap амалӣ карда шудааст) - аз ҷустуҷӯи чашмаки холӣ пас аз он ки бо функсияи ҳаш нишон дода шудааст, иборат аст;

Шумо метавонед дар бораи бархӯрдҳо дар ин ҷо хонед: клик кунед

Бо истифода аз усул, put()мо ба харитасозии хэш як ҷуфти дигари калид-арзишро илова мекунем:
```
map.put("BLAKE", 10);
```
Мо "хэши пешакӣ" - 63281361 -ро ҳисоб мекунем. Мо онро тағир медиҳем ва дар натиҷа codeи охирини хэш - 63281940 мегирем.
Азбаски санҷиши аввалини "холӣ" акнун бардурӯғ бармегардад (ҳеҷати эҷоди ҷадвал нест), мо фавран индекси сатилро, ки an objectи мо ҷойгир карда мешавад, ҳисоб мекунем:
```
i = (n - 1) & hash
i = (16 - 1) & 63281940
i = 4
```
Сатил дар индекси нишондодашуда барои мавҷудияти элементҳо дар он тафтиш карда мешавад ва азбаски шарт if ((p = tab[i = (n - 1) & hash]) == null)дар ин ҳолат иҷро карда намешавад (дар сатил аллакай элемент мавҷуд аст), пас мо ба блок меравем else.
Пеш аз ҳама, мо унсури иловашударо бо унсури якуми рӯйхати алоқаманд дар сатил муқоиса мекунем:
```
(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(), ки андозаи ҷадвали ҳашро афзоиш диҳад, аз нав тақсим кардани элементҳо. treeify()дар навбати худ, рӯйхати пайванди TreeNodeтабдил ба дарахти сурх-сиёҳ. Ин усул resize()тавассути тамоми унсурҳои нигаҳдории ҷорӣ такрор мешавад, индексҳои онҳоро (бо назардошти андозаи нав) аз нав ҳисоб мекунад ва элементҳоро ба массиви нав тақсим мекунад.

Ба таври мухтасар, бидуни тафсилоти сохтори дарахти сурх-сиёҳ, инҳо рӯй медиҳанд:
1. Унсури якуми рӯйхат ҳамчун решаи тамоми дарахт навишта шудааст (сиёҳ):
```
if (root == null) {
    x.parent = null;
    x.red = false;
    root = x;
}
```
2. Барои унсурҳои дигар:
  
  вобаста ба арзиши hash онҳоро ба чап ё рост тақсим кунед:
```
if ((ph = p.hash) > h)
    dir = -1;
else if (ph < h)
    dir = 1;
```
  Ҳама кӯдакони чап бояд аз гиреҳи решаи онҳо камтар (ё баробар) бошанд, дар ҳоле ки ҳамаи кӯдакони рост бояд калонтар бошанд.
3. Агар ду элемент хэшҳои якхела дошта бошанд ва онҳоро бо ягон роҳи дигар муқоиса кардан мумкин набошад (онҳо интерфейсро амалӣ накунанд Comparable), мо сохтмони дарахтро қатъ мекунем ва методро даъват мекунем tieBreakOrder(), ки дар навбати худ усули аслии худро System.identityHashCode()барои ҳисоб кардани codeи hash дар саросари ҷаҳон истифода мебарад .
  
  Тафсилоти бештар дар ин ҷо: истинод ба мақола
4. Мо унсурҳои дарахтро (an objectҳо TreeNode) тафтиш мекунем, то он даме, ки элементи сифр (чап ё рост) пайдо шавад.
```
if ((p = (dir <= 0) ? p.left : p.right) == null)
```
5. Гиреҳи кӯдакро илова кунед (вобаста ба директор ба чап ё рост):
```
x.parent = xp;
if (dir <= 0)
    xp.left = x;
else
    xp.right = x;
```
6. Азбаски илова кардани як унсури нав метавонад мувозинати дарахтро вайрон кунад, мо усули мувозинатро меномем:
```
root = balanceInsertion(root, x);
```
  Шумо метавонед дар бораи мувозинати CCH дар ин ҷо хонед: habr
7. Пас аз мувозинат, унсури реша метавонад тағир ёбад. Мо инро тавассути даъват кардани усуле ислоҳ мекунем, ки кафолат медиҳад, ки решаи ба он интиқолшуда гиреҳи аввал хоҳад буд:
```
moveRootToFront(tab, root)
```
  Дар ин ҷо шумо метавонед равшан бубинед, ки дарахти сурх-сиёҳ чӣ гуна сохта шудааст ва худмувозинат мекунад: визуализатсия

Ин ҳама аст, дар асл, ва бо истифода аз як мисол, биёед фарз кунем, ки мо мехоҳем номҳои зеринро ҳамчун калид илова кунем: КИНГ, МАРИ, ХОЗЕ, АННА, ФРЕД, ТОНИ, АЛЕКС, ПЕПЕ. Ва биёед бигӯем, ки мо дар ҷадвали ҳаш ҳадди аққал 64 сатил дорем ва ҳамаи ин элементҳо дар як сатил ҷамъ шудаанд. Сохтор, ин сатил чунин хоҳад буд (унсурҳо аз рӯи codeи хэш мураттаб карда мешаванд): Навъи CCHD:

Намоиш дар дохor сатил:

Ҷустуҷӯи элементҳо (ҷустуҷӯи арзиш тавассути калид) Дар бораи амалиёти иловакунӣ, ин хеле содда аст. Алгоритмро (вақте ки дар сатил рӯйхати алоқаманд мавҷуд аст) метавон чунин навишт:

Рамзи хэш-и калидро ҳисоб кунед.
Индекси сатилро ҳисоб кунед.
Индексро гузаред ва калиди унсури аввалро бо арзиши мавҷуда муқоиса кунед. Агар онҳо баробар бошанд, арзишро баргардонед, вагарна унсури ояндаро тафтиш кунед, агар он мавҷуд бошад.
Агар an objectи навбатии гиреҳ нул бошад, нулро баргардонед.
Агар an objectи навбатии Node сифр набошад, ба он равед ва се қадами аввалро то пайдо шудани элемент ё an objectи навбатии Node сифр такрор кунед.

Бо истифода аз усул, get()мо арзиши калиди "KING" -ро мегирем:

map.get("KING");

Дар дохor он усул номида мешавад getNode(int hash, Object key), ки ба он худи калид ("КИНГ") ва хэши он (2306996) интиқол дода мешавад, ки ҳамон тавре ки ҳангоми амалиёт пешакӣ ҳисоб карда мешавад put().

Мо тафтиш мекунем:
1. Оё ҷадвали ҳаш ҳатто вуҷуд дорад:(tab = table) != null
  
  Ёдовар мешавам, ки ҳангоми сохтани HashMap дар конструктор массив барои ҷадвал сохта намешавад; ин баъдтар дар усули resize(), ки ҳамеша ҳангоми илова кардани элементи аввал ба ҷадвали hash даъват мешавад, рӯй медиҳад. Аз ин рӯ, агар ба HashMap ягон элемент илова карда нашуда бошад, танҳо массиви дохилӣ барои нигоҳ доштани элементҳо вуҷуд надорад.
2. агар ифодаи қаблӣ ҳақиқӣ баргардад, шумо бояд боварӣ ҳосил кунед, ки дарозии массиви дохилӣ аз 0 зиёд аст:(n = tab.length) > 0;
3. агар ифодаи қаблӣ низ ҳақиқӣ баргардад, ба сатил дар индекс (дар ҳолати мо 4), ки қаблан ҳисоб карда шуда буд, гузаред ва онро барои мавҷудияти элементҳо тафтиш кунед:
```
(first = tab[(n - 1) & hash]) != null)
```
4. Мо калидеро, ки мо меҷӯем, бо калиди элементи якуми рӯйхат дар дохor сатил муқоиса мекунем, зеро дар аксари сатилҳо (на дар ҳама ҷо мо бархӯрд дорем) танҳо як элемент (парвандаи мо) мавҷуд хоҳад буд. Мисли усули усули put(), хэшҳо муқоиса карда мешаванд ва агар мувофиқат кунанд, калидҳо аз рӯи истинод муқоиса карда мешаванд ва танҳо пас аз он equals().
```
if (first.hash == hash && // always check first node
    ((k = first.key) == key || (key != null && key.equals(k))))
```
  Азбаски дар ҳолати мо, калиди "КING" пеш аз калиди "BLAKE" хоҳад буд (дар дохor рӯйхати алоқаманд, унсурҳои нав ба охир илова карда мешаванд ва KING аввал илова карда шудааст), мо дар ин лаҳза таваққуф мекунем ва an objectи якуми Node-ро ба усули get() ворид кунед, ки аз ӯ майдонеро бо арзиши (100) "рабояд":
```
return (e = getNode(hash(key), key)) == null ? null : e.value;
```
Агар дар дохor сатил зиёда аз як элемент мавҷуд бошад, пас:
1. агар сатил рӯйхати алоқаманд бошад, мо рӯйхатро тавассути ҳар як элементи давр мегузарем, do – whileто пайдо шудани мувофиқат:
```
do {
    if (e.hash == hash &&
        ((k = e.key) == key || (key != null && key.equals(k))))
        return e;
} while ((e = e.next) != null);
```
2. агар сатил як сохтори дарахт бошад, он гоҳ усул ба таври иловагӣ номида мешавад getTreeNode(), ки дар навбати худ методро барои ёфтани калиди зарурӣ истифода мебарад find(). Мо ҷустуҷӯи дарахтро анҷом медиҳем - хэшҳо муқоиса карда мешаванд ва гиреҳи решаи чап ё рост барои ҷустуҷӯ муайян карда мешавад. Агар калидҳо баробар бошанд (бо истинод ё аз ҷониби equals), ин гиреҳро баргардонед. Агар гиреҳҳои кӯдаки чап ё рост нул бошанд, мо ба таври иловагӣ калидҳоро бо истифода аз compareTo муқоиса мекунем (агар калидҳо интерфейсро иҷро кунанд Comparable), вагарна мо ҷустуҷӯи рекурсивиро тавассути дарахт (зердарахти рост ё чап) анҷом медиҳем, то пайдо шудани мувофиқат.

Хориҷ кардани an objectҳо аз HashMap Азбаски ҷой дар мақола тамом мешавад, ман ба таври мухтасар шарҳ медиҳам, ки чӣ гуна несткунӣ тавассути калид сурат мегирад. Алгоритм хеле монанд аст:

ба сатor дилхоҳ равед (боз пешакӣ ҳисоб карда мешавад);
агар дар сатил танҳо як an object мавҷуд бошад (мо нишоннамои нули онро тафтиш мекунем) мо hashes, пайвандҳо ва equals(агар ногаҳон hashes баробар нашаванд) муқоиса мекунем. Бозефтед? Аҷаб, ин калиди мост - онро нест кунед (=null) ва арзиши ин калидро баргардонед.
агар дар сатил зиёда аз як элемент мавҷуд бошад, мо ҳар як элементро дар давра тафтиш мекунем, то он даме ки элементро пайдо кунем ё ба охири рӯйхат расем.
агар элемент ёфт нашуда бошад, мо нулро бармегардонем.

Дар ҳолати дарахт, як амали хеле душворе вуҷуд дорад, ки беҳтар аст, ки дар бораи он надонед ва оромона хоб равед (тавсифи усул ҳатто мегӯяд, ки татбиқ нисбат ба амалиёти тозакунии муқаррарӣ дар сурх-сиёҳ мураккабтар аст. дарахт). Ғайр аз он, вақте ки нест карда мешавад, шумораи гиреҳҳо дар як сатил метавонад ба 6 баргардад ва он гоҳ дарахт ба рӯйхати пайвастшуда дубора барқарор карда мешавад. Агар шумо як таҳиягар набошед, ки таҷрибаи чандинсола дошта бошед, донистан ва фаҳмидани инро тамоман лозим нест (ва танҳо лозим нест).

Шарҳҳо

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