HashMap классынын деталдуу анализи

Класстын деталдуу талкуусуна өтүүдөн мурун, хэш tableлары менен байланышкан негизги түшүнүктөргө токтололу. Бул макалада хэш карта менен иштөө ыкмалары талкууланbyte. Кыстаруу, издөө жана жок кылуу операциялары гана так жана кеңири талкууланат. Ошол эле Шилдттен HashMap үчүн жеткorктүү ыкмалардын сыпаттамасын окуу кыйын болбойт деп ойлойм. Балким, келечекте мен мындай ыкмаларга арналган дагы бир макала жазам, бирок азыр бул күмөн. Java 7ге салыштырмалуу Java 8деги HashMap классы олуттуу өзгөрүүлөргө дуушар болгон (+1000 code саптары). Java 7де ишке ашыруу жөнүндө бул жерден окуй аласыз (бирок мындан ары актуалдуу эмес): habr Хэш tableсы – бул ассоциативдик массив интерфейсин (абстракттуу ачкыч-маани модели же жазуу) ишке ашырган маалымат структурасы , ал абдан тез киргизүүнү жана издөөнү камсыз кылат: карабастан: сан элементтерин киргизүү жана издөө (кээде жок кылуу) туруктууга жакын убакытта аткарылат - O(1). Негизинен, бул элементтин жайгашкан жери элементтин өзүнүн маанисинен көз каранды болгон кадимки массив. Элементтин мааниси менен анын хэш tableсындагы позициясынын ортосундагы байланыш хэш функциясы менен аныкталат. Хеш-функция биз ачкыч деп атаган маалыматтардын кириш бөлүгүн алат жана чыгаруу катары ал хэш мааниси (же хэш codeу) деп аталган бүтүн санды чыгарат . Андан кийин хэш мааниси биздин ачкычыбызды белгилүү бир хэш tableнын индексине байланыштырат. Негизги операциялар үчүн: киргизүү, издөө жана жок кылуу, биз ошол эле хэш-функцияны колдонобуз, ошондуктан бул операциялар абдан тез аткарылат. Ушул себептен улам, хэш-функциянын ырааттуу иштеши жана бир эле киргизилген маалыматтар үчүн бир эле индексти чыгарышы маанилүү. Белгилей кетчү нерсе, натыйжада хэш-code чоң сандык мааниге ээ болушу мүмкүн жана баштапкы массив шарттуу түрдө 16 элемент үчүн гана иштелип чыккан. Эмне үчүн он гана кошуу үчүн миллиард элементтерден турган массив түзүүгө болбойт? Ошондуктан, биз кандайдыр бир жол менен бул хэш-codeду 0дөн 15ке чейинки маанилерге айлантышыбыз керек (эгерде массивдин өлчөмү 16 болсо). Жана бул үчүн, кошумча өзгөртүүлөр колдонулат. Ошентип, массивдин өлчөмүн кичирейтүү үчүн индексти түзөбүз. Мисалы, Java 8ге чейин HashMapда бул кошумча ыкма керектүү уячаны табуу үчүн колдонулган:

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

Киргизүү катары ал иштин натыйжасында алынган хэш-codeду hashCode()жана ички массивдин узундугун (уячалардын саны) алды. Ал "хэш code" -> биттик "ЖАНА" -> (массив узундугу – 1) натыйжасын кайтарды. Класс HashMapкласстан мурас алат AbstractMapжана төмөнкү интерфейстерди ишке ашырат: Map, Cloneable, Serializable. .метод Javaдагы хэш функциясы үчүн жооп берет hashCode(). Демейки ишке ашыруу иденттүүлүк хэш codeуhashCode() деп аталган маанини кайтарат . Класс жокко чыгарылса дагы , an objectтин ID хэшти ар дайым чалуу аркылуу ала аласыз . OpenJDKдеги демейки ишке ашыруунун эстутум дареги менен эч кандай байланышы жок, кээде ойлогондой. Көбүрөөк маалымат бул жерде: habr HashMapта хэш tableсы жалгыз байланышкан тизмелердин массивинин (же тагыраак айтканда динамикалык, анткени table кеңейиши мүмкүн) негизинде ишке ашырылат. Негизи, биз ыкманын натыйжасында ачкычтын хэш codeун алабыз , ал кийинчерээк өзгөртүлөт (кийин карап чыгабыз) жана ички кошумча ыкманы колдонуу менен, алынган маанилер керектүү уячаларга бөлүштүрүлөт. Массив элементтери (уячалар) жеке түйүндөрдү сактоо үчүн колдонулган чака деп да аталат . Чакалардын ар бири коллекция (тизме же дарак). Түйүн - уя салынган класстын an objectиси (же дарак структурасында). Чынында, массив уячасынын ичинде башка классты ишке ашыруунун негизин түзгөн жалгыз байланышкан тизме же кызыл-кара дарак жатат - . hashCode()System.identityHashCode(Object o)hashCode()hashCode()NodeTreeNodeLinkedListTreeMap

Кызыл-кара дарак менен опция көп пайда боло бербейт (кантип, эмне жана кайда - ылдыйда), жана бул түзүлүштү түшүнүү абдан кыйын, ошондуктан басым Түйүн тибиндеги түйүнгө бурулат. Түйүн бул уяланган класс, HashMapанын ичинде төмөнкү талаалар бар:

final int hash— ачкычты хэширлөөнүн натыйжасында биз алган учурдагы элементтин хэши;
final K key— учурдагы элементтин ачкычы. Бул жерде сиз методдо биринчи an object катары көрсөткөн нерсе жазылат put();
V value— учурдагы элементтин мааниси. Ал эми методдо экинчи an object катары көрсөткөн нерсе бул жерде жазылган put();
Node < K, V> next— ошол эле себеттин ичиндеги кийинки түйүнгө шилтеме. Тизме туташкан, андыктан ал бар болсо, кийинки түйүнгө эмес, шилтеме керек.

Эми HashMap классынын талааларын карап көрөлү:

transient Node < K, V> [] table– түйүндөр түрүндө ачкыч-маани түгөйлөрүн сактоо үчүн массивдин негизинде ишке ашырылган хэш tableнын өзү. Бул жерде биздин түйүндөр сакталат;
transient int size— ачкыч-маанorк жуптардын саны;
int threshold— элементтердин максималдуу саны, ага жеткенде хэш tableнын өлчөмү эки эсеге көбөйөт. Формула менен эсептелген (кубаттуулук * жүктөө фактору);
final float loadFactor— бул параметр жаңы хэш tableсын түзүү үчүн учурдагы хэш-tableга жүктөөнүн кандай даражасында керек экендигин аныктайт, б.а. хэш-table 75% толгондо, жаңы хэш-table түзүлөт жана ага учурдагы элементтер жылдырылат (кымбат операция, анткени бардык элементтерди кайра өзгөртүү керек);
transient Set< Map.Entry< K,V>> entrySetentrySet()- биз кайталай турган кэшти камтыйт HashMap.

Жана туруктуулар:

static final int DEFAULT_INITIAL_CAPACITY= 1 << 4— демейки хэш tableнын сыйымдуулугу (16);
static final int MAXIMUM_CAPACITY = 1 << 30— хэш tableнын максималдуу мүмкүн болгон сыйымдуулугу (болжол менен 1 млрд);
static final float DEFAULT_LOAD_FACTOR = 0.75f— демейки жүктөө коэффициенти;
static final int TREEIFY_THRESHOLD = 8бир чакадагы элементтердин санынын "босогосу" болуп саналат, ага жеткенде ички байланышкан тизме дарак структурасына (кызыл-кара дарак) айланат.
static final int UNTREEIFY_THRESHOLD = 6— эгерде бир себеттеги элементтердин саны 6га чейин азайса, анда дарактан байланышкан тизмеге тескери өтүү болот;
static final int MIN_TREEIFY_CAPACITY = 64— дарак структурасына өтүү мүмкүн болгон хэш tableнын минималдуу сыйымдуулугу (чакалардын саны). Ошол. Эгерде хэш tableсында жок дегенде 64 чака бар болсо жана бир чакада 8 же андан көп элемент болсо, анда дарак структурасына өтүү болот.

Класстын конструкторлору:

public HashMap()— демейки боюнча хэш дисплейди түзөт: көлөмү боюнча (capacity) = 16жана жүктөө фактору менен (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классты кеңейтет . Хэш карта анын элементтеринин тартибине кепилдик бербейт. Демек, хэш картага элементтерди киргизүү тартиби сөзсүз түрдө алар итератор тарабынан алынган тартипте эмес. Объекттерди кошуу Ачкыч-маани жуптарын кошуу . Объектти кошуунун кадамдарын карап көрөлү: AbstractMapput()

Киргизилген 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. Текшерүүнүн натыйжасында биз чындыкка жеткендиктен (чакада эч кандай элементтер жок), төмөнкү талаалары бар Node an objectи түзүлөт:
```
{
int hash = 2306996 — сгенерированный хеш-code
String key = {"KING"} — ключ
Integer value = 100 — meaning
Node next = null — link на следующий узел
}
```
  Биздин түзүлгөн Node an objectиси [4] индексинин астындагы чакага кошулат:
```
tab[i] = newNode(hash, key, value, null);
tab[4] = newNode(2306996, “KING”, 100, null);
```
  newNode()жөн гана Node классынын an objectисин кайтарган ыкма.
7. Кошулгандан кийин, элементтердин учурдагы саны параметрден ашып кеткендигин текшерүү үчүн текшерүү жүргүзүлөт threshold:
```
if (++size > threshold)
    resize();
```
  resize()ашып кетсе, анда хэш tableнын өлчөмүн көбөйтүү үчүн ыкма чакырылат .
  
  Бул учурда, ыкма putVal()(жана, тиешелүүлүгүнө жараша put()) өз ишин аяктайт.
  
  Жыйынтыгын графикалык түрдө төмөнкүчө чагылдырууга болот:
  
  Жалпысынан алганда, хэш tableга Түйүндү (ачкыч-маани жуптарын) кошуу, эгер каалаган чака бош болсо, ушундай көрүнөт . Эми кагылышууга алып келе турган элементти кошууга аракет кылалы (бир чакада бирден ашык элемент болгондо).

Кагылышуулар жөнүндө бир аз Ар кандай ачкычтар бир чакага (ар кандай хэштер болсо да) түшкөн кырдаал кагылышуу же кагылышуу деп аталат. Хэш tableсы берorштер топтомунан чоңураак болсо жана жакшы хэш-функция тандалган болсо да, бул кагылышуулар болбойт деп кепилдик бербейт. Ал эми хэш мааниси int маанилеринин диапазону менен чектелген (болжол менен 4 миллиард). Пайда болгон жаңы маани да бир жерге жазылыш керек жана бул үчүн анын так кайда жазыларын аныктоо керек. Бул чыр-чатакты чечүү деп аталат. Эки ыкма бар:

тышкы чынжыр же чынжыр ыкмасы (HashMap ишке ашырылган) - б.а. клетка чындыгында тизмени (чынжыр) камтыйт. Ал эми тизме буга чейин бир нече маанилерди камтышы мүмкүн (сөзсүз эле хэш-code менен эмес).
сызыктуу текшерүү же ачык даректөө ыкмасы (IdentityHashMap программасында ишке ашырылган) - хэш-функция көрсөткөндөн кийин биринчи бош уячаны издөөдөн турат;

Кагылышуулар жөнүндө бул жерден окуй аласыз: чыкылдатыңыз

Методду колдонуп, put()хэш картасына дагы бир ачкыч-маани жуптарын кошобуз:
```
map.put("BLAKE", 10);
```
Биз "алдын ала хэшти" эсептейбиз - 63281361. Биз аны өзгөртүп, натыйжада акыркы хэш codeун алабыз - 63281940.
"Боштуктун" биринчи текшерүүсү эми жалганды кайтара тургандыктан (table түзүүнүн кереги жок), биз дароо биздин 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()Дарак структурасына баруунун ордуна, элементтерди кайра бөлүштүрүү, хэш tableнын өлчөмүн көбөйтүү ыкмасы чакырылат . өз кезегинде, кызыл-кара даракка айландырган treeify()шилтемеленген тизмеси . TreeNodeМетод resize()учурдагы сактагычтын бардык элементтери аркылуу кайталанат, алардын индекстерин кайра эсептейт (жаңы өлчөмдү эске алуу менен) жана элементтерди жаңы массивге бөлүштүрөт.

Кыскача айтканда, кызыл-кара дарактын түзүлүшү жөнүндө майда-чүйдөсүнө чейин барбастан, төмөнкүдөй болот:
1. Тизменин биринчи элементи бүт дарактын тамыры катары жазылат (кара):
```
if (root == null) {
    x.parent = null;
    x.red = false;
    root = x;
}
```
2. Башка элементтер үчүн:
  
  хэш маанисине жараша аларды солго же оңго бөлүштүрүңүз:
```
if ((ph = p.hash) > h)
    dir = -1;
else if (ph < h)
    dir = 1;
```
  Бардык сол балдар тамыр түйүнүнөн кичине (же барабар), ал эми бардык оң балдар чоңураак болушу керек.
3. Эгерде эки элементтин хэштери бирдей болсо жана аларды башка жол менен салыштырууга болбойт (алар интерфейсти ишке ашырбаса Comparable), биз дарактын курулушун үзгүлтүккө учуратабыз жана методду чакырабыз , ал өз кезегинде глобалдык уникалдуу хэш codeун эсептөө үчүн tieBreakOrder()жергorктүү ыкманы колдонот. System.identityHashCode().
  
  Көбүрөөк маалымат бул жерде: макалага шилтеме
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)
```
  Кызыл-кара дарактын кантип курулганын жана өзүн-өзү тең салмактуулугун бул жерден даана көрө аласыз: визуализация

Бул, принципиалдуу түрдө жана мисалды колдонуу менен, биз ачкыч катары төмөнкү ысымдарды кошкубуз келет деп ойлойлу: КИНГ, МЭРИ, ЖОЗЕ, АННА, ФРЕД, ТОНИ, АЛЕКС, ПЭПЕ. Жана бизде хэш tableсында жок дегенде 64 чака бар жана бул элементтердин баары бир чакага чогулду дейли. Структуралык жактан бул чака мындай болот (элементтер хэш-code боюнча сорттолот): CCHD түрү:

Чаканын ичинде көрүү:

Элементтерди алуу (ачкыч боюнча маанини алуу) Кошуу операциясына келсек, бул абдан жөнөкөй. Алгоритмди (чакада шилтемеленген тизме бар болгондо) төмөнкүдөй жазса болот:

Ачкычтын хэш codeун эсептеңиз.
Чака индексин эсептөө.
Индекс аркылуу өтүп, биринчи элементтин ачкычын учурдагы маани менен салыштырыңыз. Эгерде алар бирдей болсо, маанини кайтарыңыз, антпесе кийинки элементтин бар-жогун текшериңиз.
Эгерде кийинки Түйүн an objectиси нөл болсо, нөлдү кайтарыңыз.
Эгерде кийинки Түйүн an objectиси нөл эмес болсо, ага өтүп, элемент табылганга чейин же кийинки Түйүн an objectиси нөл болгонго чейин биринчи үч кадамды кайталаңыз.

Методду колдонуп, get()биз "KING" ачкычынын маанисин алабыз:

map.get("KING");

Ичинде, ыкма деп аталат getNode(int hash, Object key), ага ачкычтын өзү ("KING") жана анын хэштери (2306996) өткөрүлөт, ал операция учурундагыдай эле алдын ала эсептелген put().

Биз текшеребиз:
1. хэш tableсы да барбы:(tab = table) != null
  
  Эске сала кетейин, HashMap түзүүдө table үчүн массив конструктордо түзүлбөйт, бул resize()хэш tableга биринчи элементти кошкондо дайыма чакырылган методдо кийинчерээк болот. Демек, HashMapга эч кандай элементтер кошулбаган болсо, элементтерди сактоо үчүн жөн гана ички массив жок.
2. мурунку туюнтма чындыкты кайтарса, ички массивдин узундугу 0дөн чоң экенине ынанышыңыз керек:(n = tab.length) > 0;
3. эгерде мурунку туюнтма да чындыкты кайтарса, мурда эсептелген индекстеги чакага (биздин учурда 4) барып, элементтердин бар-жоктугун текшериңиз:
```
(first = tab[(n - 1) & hash]) != null)
```
4. Биз издеп жаткан ачкычты чаканын ичиндеги тизмедеги биринчи элементтин ачкычы менен салыштырабыз, анткени көпчүлүк чакаларда (баардык жерде кагылышуулар болбойт) бир эле элемент болот (биздин иш). Методдогудай эле put(), хэштер салыштырылат, эгерде алар дал келсе, ачкычтар шилтеме боюнча, андан кийин гана салыштырылат equals().
```
if (first.hash == hash && // always check first node
    ((k = first.key) == key || (key != null && key.equals(k))))
```
  Биздин учурда "KING" ачкычы "BLAKE" ачкычынын алдында тургандыктан (байланышкан тизмеде жаңы элементтер аягына кошулат, ал эми KING биринчи кошулду), биз ушул жерден токтоп, биринчи an objectти кайтарабыз. Get() ыкмасына Node териңиз, ал андан (100) мааниси бар талааны "жулуп" алат:
```
return (e = getNode(hash(key), key)) == null ? null : e.value;
```
Чаканын ичинде бирден ашык элемент болсо, анда:
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), антпесе дал келгенге чейин дарак (оң же сол суб дарак) аркылуу рекурсивдүү издөө жүргүзөбүз.

Объекттерди HashMapдан алып салуу Макаладагы бош орун түгөнүп калгандыктан, мен ачкыч аркылуу өчүрүү кандай болорун кыскача сүрөттөп берем. Алгоритм абдан окшош:

каалаган чака барып (кайра, ал алдын ала эсептелген);
чакада бир гана an object болсо (биз анын нөл көрсөткүчүн текшеребиз) хэштерди, шилтемелерди жана equals(эгерде күтүлбөгөн жерден хэштер бирдей болбосо) салыштырабыз. Дал келдиңизби? Жакшы, бул биздин ачкыч - аны жок кылуу (=нөл) жана бул ачкычтын маанисин кайтарыңыз.
эгерде чакада бирден ашык элемент болсо, биз элементти тапканга же тизменин аягына жеткенге чейин циклдин ар бир элементин текшеребиз.
эгерде элемент табылбаса, биз нөлдү кайтарабыз.

Дарак менен болгон кырдаалда, бир топ татаал ишке ашыруу бар, ал жөнүндө билбөө жана жакшы уктоо (ыкмасынын сүрөттөлүшү атүгүл ишке ашыруу кызыл-карада кадимки өчүрүү операциясына караганда татаалыраак деп айтылат. дарак). Мындан тышкары, жок кылынганда, бир чакадагы түйүндөрдүн саны 6га кайтып келиши мүмкүн, андан кийин дарак кайра байланышкан тизмеге кайра түзүлөт. Эгерде сиз көп жылдык тажрыйбасы бар иштеп чыгуучу болбосоңуз, анда муну билүү жана түшүнүү такыр зарыл эмес (жана жөн эле зарыл эмес).

Комментарийлер

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